Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
MrFoxyGmFr
0 / 0 / 0
Регистрация: 15.12.2017
Сообщений: 2
1

Задача на последовательности

15.12.2017, 18:42. Просмотров 196. Ответов 3
Метки нет (Все метки)

Миша доволен своими успехами. В прошлом году он не получил ни одной "двойки"! Он выписал все свои оценки в строку, одну за другой, и обнаружил, что среди них нет двух подряд идущих "троек". А всё потому, что каждый раз, получив "тройку", Миша спешил её исправить и обещал никогда больше троек не получать.

Требуется выяснить, сколько существует различных последовательностей из n оценок("троек", "четвёрок" и "пятёрок"), в которой нет двух рядом стоящих "троек".


Формат файла входных данных:

В единственной строке записано натуральное число n <= 105.


Формат файла выходных данных:

В единственной строке выходного файла должно быть записано количество различных последовательностей из n чисел "3", "4", "5", в которых нет двух рядом стоящих "3" по модулю 1018 + 9.

Пример:
in - out
1 - 3
2 - 8
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.12.2017, 18:42
Ответы с готовыми решениями:

Задача с использованием последовательности
Дана строка s. Если последовательность {s}_{1},...,{s}_{n} является палиндромом, тоесть ...

задача на последовательности никак не получается
Вводится последовательность вещественных чисел, оканчивающаяся нулём, и состоящая более чем из...

и еще одна задача на последовательности
Вводится последовательность вещественных чисел, оканчивающаяся нулём, и состоящая более чем из...

задача на обработку последовательности символов
Даны натуральное число n , символы S1, .... Sn. Заменить в последовательности S1, .... Sn, каждую...

Сумма последовательности чисел. Задача
Доброго времени суток помогите решить очень простенькую задачу. В стандартном потоке ввода...

3
Байт
Эксперт C
18959 / 12170 / 2543
Регистрация: 24.12.2010
Сообщений: 24,828
15.12.2017, 19:17 2
Близкая тема
Вычислить количество слов длины n для алфавита
0
MrFoxyGmFr
0 / 0 / 0
Регистрация: 15.12.2017
Сообщений: 2
15.12.2017, 19:24  [ТС] 3
Немного не помогло :-(
Как и в том примере знаю, что максимальное кол-во последовательностей = 3^n, необходимо найти - сколько вычесть.Пока сам прорешал и нашел, сколько нужно убрать для первой пятерки:
1 - убираем 0; 2 - убираем 1; 3 - убираем 5; 4 - убираем 21;. 5 - убираем 81
0
Байт
Эксперт C
18959 / 12170 / 2543
Регистрация: 24.12.2010
Сообщений: 24,828
15.12.2017, 20:59 4
Цитата Сообщение от MrFoxyGmFr Посмотреть сообщение
Немного не помогло
Так там же есть рекуррентная формула! И ее можно даже в конечном виде раскрыть. А уж запрограммировать, что в цикле, что рекурсивно - сущие пустяки!
Смотрите. Есть 2 выражения, зависящие от k.
A(k) - количество последовательностей, оканчивающихся на тройку
B(k) - количество последовательностей, не оканчивающихся на тройку
Обе эти последовательности не содержат подряд идущих троек (то есть - допустимы)
A(k+1) = B(k)
B(k+1) = 2*A(k) + 2*B(k)
Эти формулу понятны?
Начальные значения очевидны: A(1) = 1, B(1) = 2
Ну и крутим цикл до n...

Добавлено через 5 минут
C++
1
2
3
4
5
6
7
8
int A = 1, B =2;
for(i=2; i<=n; i++) {
  int tA = B;
  int tB = 2*A + 2*B;
  A = tA;
  B = tB;
}
cout << A+B;
Усе!
ЗЫ. Я тут не рассматриваю дополнительные условия типа "дать ответ по модулю" - это все вещи в общем-то стандартные.

Добавлено через 10 минут

Не по теме:

Почему я не очень люблю задачи про этих бедолаг, Петю и Васю, потому что решение тут короче условия. Толи дело - Великая Теорема Ферма!:D

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.12.2017, 20:59

Задача с циклом For. Выбрать из последовательности числа не меньше заданного
Составить программу с циклом for. (Заранее спасибо!)

Задача на нахождение среди символов последовательности требуемых букв
Даны символы s1, s2, … Известно, что символ s1 отличен от восклицательного знака и что среди s2,...

Преобразование последовательности - 2 (задача с acmp). Найти ошибку в коде
Здравствуйте. #include &lt;stdio.h&gt; #include &lt;stdio.h&gt; #include &lt;math.h&gt; #include &lt;cstdio&gt;...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru