IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

 
 Ответить  Открыть новую тему 
> Сложная задача на комбинаторику, никак не могу решить((
сообщение
Сообщение #1


Новичок
*

Группа: Пользователи
Сообщений: 38
Пол: Мужской

Репутация: -  0  +


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

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

P.S в этой теме я постарался учесть все замечания сделанные мне ранее) просто очень нужна помощь..
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гость






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


Новичок
*

Группа: Пользователи
Сообщений: 38
Пол: Мужской

Репутация: -  0  +


Цитата(volvo @ 16.12.2007 11:45) *

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

ЛЮБОЕ решение мне ПОДОЙДЕТ!!! Напиши плиииз.....
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






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

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 -
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Новичок
*

Группа: Пользователи
Сообщений: 38
Пол: Мужской

Репутация: -  0  +


Цитата(volvo @ 16.12.2007 12:01) *

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

Ой а если не трудно пропиши плииз всю програмку а то я нуб чет сам не могу доделать)) а я разберусь.. Я буду очень благодарен!!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 38
Пол: Мужской

Репутация: -  0  +


Ну вот опять мучаюсь ниче не полючается(((( может все таки напишешь прогу полностью? плиииз)
Заранее благодарен...)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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

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).
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Новичок
*

Группа: Пользователи
Сообщений: 38
Пол: Мужской

Репутация: -  0  +


А можешь написать это в паскале? Если не трудно напиши программой плиииз! мне завтра уже сдавать... заранее спасибо)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Новичок
*

Группа: Пользователи
Сообщений: 38
Пол: Мужской

Репутация: -  0  +


Люди пишите лучше программой сразу .. я нуб))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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


... и собираюсь им оставаться...
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Новичок
*

Группа: Пользователи
Сообщений: 38
Пол: Мужской

Репутация: -  0  +


Цитата(Michael_Rybak @ 16.12.2007 17:04) *

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

нет конечно но просто времени мало... я лучше потом разберусь)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


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


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

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

 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 4.12.2021 21:16
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name