1296 / 469 / 151
Регистрация: 24.08.2011
Сообщений: 2,249
|
||||||
1 | ||||||
Количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом19.12.2014, 12:46. Показов 43274. Ответов 17
Метки нет (Все метки)
http://informatics.mccme.ru/mo... p?id=654#1
Логика решения: изначально есть 2 последовательности - 0 и 1. После нуля может быть и 0 и 1, после 1 только 0. Соответственно, количество новых последовательностей, которые заканчиваются на 0 - это количество старых с 0 в конце + количество старых с 1 в конце. А количество новых с 1 в конце - это количество старых с 0 в конце. Динамическое программирование начинаю осваивать
0
|
19.12.2014, 12:46 | |
Ответы с готовыми решениями:
17
Поиск числа последовательностей, в которых никакие 2 единицы не стоят рядом Подсчитать количество последовательностей длины N , состоящих из 0 и 1, в которых никакие две единицы не стоят рядом Подсчитать количество последовательностей длины N, состоящих из 0 и 1, в которых никакие две единицы не стоят рядом Рекурсия для начинающих. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом |
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
19.12.2014, 12:56 | 2 |
Логически, как будто, все правильно. А на каких n не проходит? Может быть происходит переполнение разрядной сетки? long long не такое уж большое число, когда речь идет об экспотенциальном росте.
Кстати, проверить переполнение после строки 12 можно по условию tmp < a[0]
0
|
19.12.2014, 13:03 | 3 | |||||
Керра,
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
19.12.2014, 13:29 | 4 |
Ilot, А в чем разница? В использовании рекурсии вместо итерации? Но это и по эффективности много хуже, и по поиску проблемных мест. Плюс к тому в игру включается еще одна сущность - стек, и надо еще специальным образом следить за его поведением...
0
|
19.12.2014, 13:47 | 5 | |||||
Байт, ну раз заговорили о эффективности то:
1
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
19.12.2014, 22:21 | 7 |
Не могу не согласиться Где тут смайл, разводящий руками? И правда. Хорошая рекурентная последовательность Фибоначчиево типа (а может, и сам Фибоначчи, детали не смотрел), легко найти аналитическое выражение, да и переполнение легче отслеживается, ибо как ни крути, double посильнее чем даже long long long
0
|
1296 / 469 / 151
Регистрация: 24.08.2011
Сообщений: 2,249
|
||||||
20.12.2014, 00:29 [ТС] | 8 | |||||
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
20.12.2014, 00:48 | 9 |
Ну что ж ты, как девочка, прямо? Покажь, на каких не проходит. Поймай переполнение (уже было сказано как). А если хочешь реальной точности, то
Но и тут не забывай, что твой компутер - всего лишь конечный автомат (хотя и очень большой)
Да по большому счету всем плевать. на какую это тему. И что такое "динамическое программирование" - тоже не в курсах. Есть твоя несложная задачка. Логически решенная - безукоризненно (хотя есть и другие столь же безукоризненные варианты) Значит - дело в железе. И задача любого уважающего себя программиста - это железо надуть.
0
|
1296 / 469 / 151
Регистрация: 24.08.2011
Сообщений: 2,249
|
|
20.12.2014, 00:51 [ТС] | 10 |
Байт, вот чтоб я знала на каких не проходит. В первом посте ссылка на сайт с тестовой системой. И система, как обычно, свои тесты не выдает.
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
20.12.2014, 01:05 | 11 |
Простите. Не врубился, что это борьба с роботом. И Y <= 100. Что при Y=100 навярняка вызывает переполнение как уже заметил уважаемый zer0mail
Ответ, видимо, нужен точный, так что фокусыIlot из поста 5 могут и не помочь. (хотя по времени - это самый эффективный вариант). Единственное, что остается - длинная арифметика. Но тут "задачник" можно хорошо обмануть, зная максимальное Y. А можно и не обманывать. В программировании есть 3 числа 0, 1 и бесконечность!
0
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
20.12.2014, 01:05 | 12 |
0
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
20.12.2014, 01:12 | 14 |
Байт, ну я в лонг даблах считал, и у меня последние 8 или 9 неправильно считает, отсальное правильно.
0
|
Диссидент
27706 / 17322 / 3812
Регистрация: 24.12.2010
Сообщений: 38,979
|
|
20.12.2014, 01:23 | 15 |
Ну, и чего ты хотел? Именно в последних и фишка. Робот, он ведь тоже хитер. Сказал бы 200 - все ясно, включай длиннючку. А тут - на грани. Хочется выскользнуть, покрутиться...
Добавлено через 4 минуты Если программа дает хоть один неправильный результат, это неправильная программа. Я думаю, что Винни-Пух со мной бы согласился.
0
|
221 / 166 / 47
Регистрация: 17.07.2012
Сообщений: 587
|
|
20.12.2014, 01:25 | 16 |
Байт, я уже сдал эту задачу.
0
|
3224 / 1751 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
||||||
20.12.2014, 03:46 | 17 | |||||
0
|
0 / 0 / 0
Регистрация: 13.12.2021
Сообщений: 1
|
|
13.12.2021, 23:32 | 18 |
Бедные пекусы, ловите ДП решение..
#include <iostream> using namespace std; const int Sizei = 100, Sizej = 2; int main() { int n; long long Summ = 0; cin >> n; long long Array[Sizei][Sizej]; Array[0][0] = Array[0][1] = 1; for (int i = 1; i < n; i++) { Array[i][0] = Array[i - 1][1]; Array[i][1] = Array[i - 1][0] + Array[i - 1][1]; } for (int i = 0; i < Sizej; i++) { Summ += Array[n - 1][i]; } cout << Summ << endl; return 0; }
0
|
13.12.2021, 23:32 | |
13.12.2021, 23:32 | |
Помогаю со студенческими работами здесь
18
Сколькими способами можно выбрать из них пять книг, никакие две из которых не стоят рядом Определить количество перестановок, в которых никакие три одинаковые цифры не стоят рядом Подсчитать количество последовательностей длины N, состоящих из 0 и 1 Подсчитать количество последовательностей длины N, состоящих из 0 и 1 Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |