Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Интересные и занимательные задачи по программированию > Сколькими способами можно пройтись по лестнице.

Автор: neutrino 4.1.2005, 16:30

Привет!

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

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

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

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

Автор: Fedor 4.1.2005, 17:13

Элементарно, 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.

Автор: neutrino 4.1.2005, 17:56

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

Автор: Fedor 4.1.2005, 18:03

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

Автор: neutrino 4.1.2005, 19:49

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

Автор: neutrino 4.1.2005, 20:13

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

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

Автор: Fedor 4.1.2005, 22:39

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

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

ой

Автор: Fedor 4.1.2005, 22:51

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

Автор: neutrino 4.1.2005, 22:53

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

Автор: Fedor 4.1.2005, 22:59

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

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

закона не знаю smile

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

Автор: neutrino 7.1.2005, 13:36

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

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

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

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