Задача
Ещё задолго до того, как Шарик нашёл умную книжку, утерянную Печкиным, когда он только начинал свои эксперименты по распиливанию шахматных досок, когда ещё на шахматной доске белые поля были белыми, а чёрные – чёрными, он задал одну из своих первых задачек Матроскину.
«Сколько разных последовательностей длины [latex]n[/latex] можно составить из клеток распиленных шахматных досок, если ни в одной из последовательностей никакие три белых поля не должны идти подряд»?
Матроскин так и не решил ещё эту задачку, так что ваша задача помочь ему.
Входные данные
Длина последовательности [latex]n[/latex] ([latex]n ≤ 64[/latex]).
Выходные данные
Вывести количество указанных последовательностей.
Тесты
| Входные данные | Выходные данные |
| 1 | 2 |
| 2 | 4 |
| 3 | 7 |
Код программы на С++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
#include<iostream> using namespace std; int main() { long n,x1,x2,x3,x4; cin >> n; x1=2; x2=4; x3=7; for (int i=3; i<n; i++) { x4=x1+x2+x3; x1=x2; x2=x3; x3=x4; } if (n==1) cout << 2 << endl; else if (n==2) cout << 4 << endl; else if (n==3) cout << 7 << endl; else cout << x4 << endl; return 0; } |
Код программы на Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
import java.util.*; import java.lang.*; import java.io.*; class Ideone { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); long x1,x2,x3; long x4=0; long n=in.nextLong(); x1=2; x2=4; x3=7; for (int i=3; i<n; i++) { x4=x1+x2+x3; x1=x2; x2=x3; x3=x4; } if (n==1) System.out.println(2); else if (n==2) System.out.println(4); else if (n==3) System.out.println(7); else System.out.println(x4); } } |
Решение
Для решения задачи воспользуемся рекуррентным соотношением [latex]f \left( n \right) = f \left( n-1 \right)+f \left( n-2 \right)+f \left( n-3 \right)[/latex], где [latex]f[/latex] — функция, возвращающая ответ на поставленную задачу. Из условия следует, что для любой последовательности рассматривать следует только три варианта её последних элементов: …Ч, …ЧБ, …ЧББ (где Ч — чёрная клетка, Б — белая), так как в случае, если конец последовательности квадратов содержит только чёрный квадрат, чёрный и белый или чёрный и два белых, то нарушить последовательность могли только предшествующие этим окончаниям, которые имеют длины 1, 2, и 3 соответственно, последовательности. Именно это и влечёт справедливость указанного выше рекуррентного соотношения. Значения [latex]f \left( n \right)[/latex] при [latex]n \le 3[/latex] можно вычислить вручную и сохранить, а остальные вычислять в цикле с использованием предыдущих, вплоть до получения требуемого.
Ссылки
Код на ideone.com (C++)
Код на ideone.com (Java)
Задача с сайта e-olymp.com.
Засчитанное решение.
Зачтено. Правда мы рассматривали в классе задачу с битовыми последовательностями без трех единиц подряд. по сути это та же задача на вариант последовательности трибоначчи, только с забавной легендой.
Предлагаю рассмотреть такую модификацию задачи. Шарик распилил только одну шахматную доску. Т.е. можно использовать не более чем 32 белые и 32 черные клетки. Как решить такую задачу на динамику?