Привет!

Есть лестница, ступеньки которой пронумерованы от 1. Есть правило как по такой лестнице подниматься: если стоишь на ступеньке с номером не являющимся простым числом - можешь подняться на следующую ступеньку или перепрыгнуть на ступеньку за ней, если номер ступеньки является простым числом, можно подняться только на одну - следующую за ней ступеньку. Надо пройти с первой ступеньки до k-той. Сколькими способами можно до k-той ступеньки подняться?

А теперь, внимание, задача: написать нерекурсивную (!!!) функцию для подсчета количества способов забраться на k-тую ступеньку.

Напомню, что простое число - это такое число, которое делится только на себя и на 1 (исключение: единица не является простым числом). Например: 2, 3, 5, 7, 11 ...

П.С. Эту задачку задали моей жене (она учится на упрвлении пр-вом).

Элементарно, neutrino

Используем метод динамического программирования - зная, сколько способов для i-той ступеньки, находим количество способов для i+1-ой и (если не простое) для i+2-ой

Написал на паскале. Если что-то непонятно, объясню

Код

const maxsteps = 100;  {максимальное количество ступенек в лечтнице} function ifprime(a:integer):boolean; {выясняет, простое ли число} var i:word; begin for i:=2 to trunc(sqrt(a)) do  if a mod i = 0 then begin ifprime:=false; exit; end; ifprime:=true; end; var a:array[1..MaxSteps+2] of longint;   {массив, содержащий количество способов для каждой из ступенек} i:word; k:integer; begin readln(k); a[1]:=1;          {на первую одним способом} a[2]:=1;          {на вторую одним способом} for i:=2 to k do  begin    if ifprime(i) then       a[i+1]:=a[i+1]+a[i]    else     begin       a[i+1]:=a[i+1]+a[i];       a[i+2]:=a[i+2]+a[i];     end;  end; writeln(a[k]); end.

Это сообщение отредактировал(а) Fedor - 4.1.2005, 17:14

Я сам решил эту задачу. Какова сложность твоего алгоритма?

K*(время определения простоты числа)

Программа работает неправильно. До 4-й ступеньки можно добраться 2-мя способами, а она пишет 1.

Видимо ошибка в том, что ты не проверяешь что единица не простое число.

Все равно есть более оптимальное решение.

Цитата(neutrino @ 4.1.2005, 19:13)

Видимо ошибка в том, что ты не проверяешь что единица не простое число.

ой

какая сложность получилась у тебя?
И покажи решение плиз если можно...

Неа. Не покажу. Пусть загрузят комбинаторную библиотеку и сами решат.
Добавлено @ 22:55
Сложность, кстати, посчитать у меня трудно за незнанием закона распределения простых чисел ...

Цитата(neutrino @ 4.1.2005, 21:53)

Сложность, кстати, посчитать у меня трудно за незнанием закона распределения простых чисел

закона не знаю
ну я ведь тоже не идеально посчитал... а так... округлил навскидку...

Ну? Еще версии...

Цитата(Fedor @ 4.1.2005, 21:59)

Внимание! Fedor==Morpheus

Кхмм... А я думаю кто это этот Дядь Федр ...