Сложная задача на комбинаторику, никак не могу решить(( |
1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!
Сложная задача на комбинаторику, никак не могу решить(( |
Lodar' |
Сообщение
#1
|
Новичок Группа: Пользователи Сообщений: 38 Пол: Мужской Репутация: 0 |
Люди помогите плииз! я никак не могу решить эту задачу...вот третий день мучаюсь,все никак((
Кто чем может помогите...ну мне очень надо...вот условие задачки: Подсчитать число двоичных N-значных натуральных чисел (N<36), в каждом из которых нет трех единиц идущих подряд, а незначащие нули в записи чисел отсутствуют. Ваша программа должна запросить значение N; найти и сообщить число n- значных двоичных чисел без трех единиц подряд. Пример: Исходные данные: 4 Ответ: 6 (Имеются ввиду числа 1000, 1001, 1010, 1011, 1100, 1101) P.S в этой теме я постарался учесть все замечания сделанные мне ранее) просто очень нужна помощь.. |
volvo |
Сообщение
#2
|
Гость |
Решение обязательно комбинаторное? Перебор с небольшой оптимизацией (чтоб не делать ЯВНО рутинную работу) не подойдет тебе?
|
Lodar' |
Сообщение
#3
|
Новичок Группа: Пользователи Сообщений: 38 Пол: Мужской Репутация: 0 |
|
volvo |
Сообщение
#4
|
Гость |
Ну, полностью писать не буду, а вот рекурсивную функцию, делающую основной подсчет - покажу, разберись с ней, и попробуй дописать все остальное - правильный вызов и описания переменных (там не так много). Если сможешь - значит, действительно разобрался...
procedure count_all(const s: string; const len: integer); Если тебя интересует вопрос времени - то за 1.5 секунды находится ответ для n = 25, то есть, процедура работает достаточно быстро... Сообщение отредактировано: volvo - |
Lodar' |
Сообщение
#5
|
Новичок Группа: Пользователи Сообщений: 38 Пол: Мужской Репутация: 0 |
Ну, полностью писать не буду, а вот рекурсивную функцию, делающую основной подсчет - покажу, разберись с ней, и попробуй дописать все остальное - правильный вызов и описания переменных (там не так много). Если сможешь - значит, действительно разобрался... Ой а если не трудно пропиши плииз всю програмку а то я нуб чет сам не могу доделать)) а я разберусь.. Я буду очень благодарен!! |
Lodar' |
Сообщение
#6
|
Новичок Группа: Пользователи Сообщений: 38 Пол: Мужской Репутация: 0 |
Ну вот опять мучаюсь ниче не полючается(((( может все таки напишешь прогу полностью? плиииз)
Заранее благодарен...) |
Michael_Rybak |
Сообщение
#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). |
Lodar' |
Сообщение
#8
|
Новичок Группа: Пользователи Сообщений: 38 Пол: Мужской Репутация: 0 |
А можешь написать это в паскале? Если не трудно напиши программой плиииз! мне завтра уже сдавать... заранее спасибо)
|
Lodar' |
Сообщение
#9
|
Новичок Группа: Пользователи Сообщений: 38 Пол: Мужской Репутация: 0 |
Люди пишите лучше программой сразу .. я нуб))
|
Michael_Rybak |
Сообщение
#10
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата пишите лучше программой сразу .. я нуб)) ... и собираюсь им оставаться... |
Lodar' |
Сообщение
#11
|
Новичок Группа: Пользователи Сообщений: 38 Пол: Мужской Репутация: 0 |
|
Michael_Rybak |
Сообщение
#12
|
Michael_Rybak Группа: Пользователи Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата я лучше потом разберусь) Да нет. Ты лучше сейчас разберись ;) volvo тебе даже написал код, который осталось только вызвать, и будет работающая программа. С нулевым знанием паскаля это делается за час максимум (включая знакомство с понятием переменной, процедуры и т. д). Ищешь любой пример использование процедур, и разбираешься. |
Текстовая версия | 25.04.2024 19:06 |