Сложная задача на комбинаторику, никак не могу решить(( Опции

[Lodar']

Люди помогите плииз! я никак не могу решить эту задачу...вот третий день мучаюсь,все никак((
Кто чем может помогите...ну мне очень надо...вот условие задачки:

Подсчитать число двоичных N-значных натуральных чисел (N<36), в каждом из которых нет трех единиц идущих подряд, а незначащие нули в записи чисел отсутствуют.
Ваша программа должна запросить значение N; найти и сообщить число n- значных двоичных чисел без трех единиц подряд.
Пример: Исходные данные: 4 Ответ: 6 (Имеются ввиду числа 1000, 1001, 1010, 1011, 1100, 1101)

P.S в этой теме я постарался учесть все замечания сделанные мне ранее) просто очень нужна помощь..

[volvo]

Решение обязательно комбинаторное? Перебор с небольшой оптимизацией (чтоб не делать ЯВНО рутинную работу) не подойдет тебе?

[Lodar']

Решение обязательно комбинаторное? Перебор с небольшой оптимизацией (чтоб не делать ЯВНО рутинную работу) не подойдет тебе?

ЛЮБОЕ решение мне ПОДОЙДЕТ!!! Напиши плиииз.....

[volvo]

Ну, полностью писать не буду, а вот рекурсивную функцию, делающую основной подсчет - покажу, разберись с ней, и попробуй дописать все остальное - правильный вызов и описания переменных (там не так много). Если сможешь - значит, действительно разобрался...

procedure count_all(const s: string; const len: integer);
begin
  if len = n then inc(count)
  else begin
    count_all(s + '0', len + 1);

    if s[len - 1] + s[len] <> '11'
    then count_all(s + '1', len + 1);
  end;
end;

Если тебя интересует вопрос времени - то за 1.5 секунды находится ответ для n = 25, то есть, процедура работает достаточно быстро...

Сообщение отредактировано: volvo - 16.12.2007 12:03

[Lodar']

Ну, полностью писать не буду, а вот рекурсивную функцию, делающую основной подсчет - покажу, разберись с ней, и попробуй дописать все остальное - правильный вызов и описания переменных (там не так много). Если сможешь - значит, действительно разобрался...

Ой а если не трудно пропиши плииз всю програмку а то я нуб чет сам не могу доделать)) а я разберусь.. Я буду очень благодарен!!

[Lodar']

Ну вот опять мучаюсь ниче не полючается(((( может все таки напишешь прогу полностью? плиииз)
Заранее благодарен...)

[Michael_Rybak]

Можно использовать рекуррентное соотношение:

f(0) = 1
f(1) = 2
f(2) = 4
f(n) = f(n - 1) + f(n - 2) + f(n - 3)

Формула получается следующим образом:

Если в n-значном числе первая цифра - 0, то дальше может идти что угодно, т.е. вариантов будет f(n-1).

Если в n-значном числе первая цифра - 1, а за ней идет 0, то дальше тоже может идти что угодно, и таких вариантов будет f(n-2), т.к. после "10" остается n-2 неопределенные цифры.

Если в n-значном числе первая цифра - 1, и за ней идет 1, то третьей цифрой может быть только 0 (иначе нарушится правило), а за ним может идти что угодно, и таких вариантов будет f(n-3).

Таким образом, f(n) = f(n - 1) + f(n - 2) + f(n - 3).

Ответом к задаче будет f(N) - f(N - 1), потому что от нас требуют числа без незначащих нулей, поэтому мы из общего числа устраивающих нас чисел - f(N) - вычитаем количество чисел, начинающихся с нуля - f(N - 1).

[Lodar']

А можешь написать это в паскале? Если не трудно напиши программой плиииз! мне завтра уже сдавать... заранее спасибо)

[Lodar']

Люди пишите лучше программой сразу .. я нуб))

[Michael_Rybak]

пишите лучше программой сразу .. я нуб))

... и собираюсь им оставаться...

[Lodar']

... и собираюсь им оставаться...

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

[Michael_Rybak]

я лучше потом разберусь)

Да нет. Ты лучше сейчас разберись ;)

volvo тебе даже написал код, который осталось только вызвать, и будет работающая программа. С нулевым знанием паскаля это делается за час максимум (включая знакомство с понятием переменной, процедуры и т. д). Ищешь любой пример использование процедур, и разбираешься.