Версия для печати темы

Автор: Lodar' 16.12.2007 15:29

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

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

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

Автор: volvo 16.12.2007 15:45

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

Автор: Lodar' 16.12.2007 15:50

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

Автор: volvo 16.12.2007 16:01

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

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, то есть, процедура работает достаточно быстро...

Автор: Lodar' 16.12.2007 16:18

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

Автор: Lodar' 16.12.2007 18:33

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

Автор: Michael_Rybak 16.12.2007 18:47

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

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' 16.12.2007 19:49

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

Автор: Lodar' 16.12.2007 20:20

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

Автор: Michael_Rybak 16.12.2007 21:04

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

Автор: Lodar' 16.12.2007 21:34

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

Автор: Michael_Rybak 16.12.2007 21:46

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

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