Задача

Ещё задолго до того, как Шарик нашёл умную книжку, утерянную Печкиным, когда он только начинал свои эксперименты по распиливанию шахматных досок, когда ещё на шахматной доске белые поля были белыми, а чёрные – чёрными, он задал одну из своих первых задачек Матроскину.

«Сколько разных последовательностей длины $n$ можно составить из клеток распиленных шахматных досок, если ни в одной из последовательностей никакие три белых поля не должны идти подряд«?

Матроскин так и не решил ещё эту задачку, так что ваша задача помочь ему.

Входные данные

Длина последовательности $n (n ≤ 64)$.

Выходные данные

Вывести количество указанных последовательностей.

Тесты

Входные данные	Выходные данные
1	2
2	4
3	7
4	13

Код задачи

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        long x1, x2, x3, 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);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

long x1, x2, x3, 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);

}

Решение задачи

Для решения задачи воспользуемся рекуррентным соотношением $f(n)=f(n−1)+f(n−2)+f(n−3)$ $f (n) = f (n - 1) + f (n - 2) + f (n - 3)$ , где $f$ — функция, возвращающая ответ на поставленную задачу. Из условия следует, что для любой последовательности рассматривать следует только три варианта её последних элементов: …Ч, …ЧБ, …ЧББ (где Ч — чёрная клетка, Б — белая), так как в случае, если конец последовательности квадратов содержит только чёрный квадрат, чёрный и белый или чёрный и два белых, то нарушить последовательность могли только предшествующие этим окончаниям, которые имеют длины $1, 2,$ и $3$ соответственно, последовательности. Именно это и влечёт справедливость указанного выше рекуррентного соотношения. Значения $f(n)$ при $n≤3$ можно вычислить вручную и сохранить, а остальные вычислять в цикле с использованием предыдущих, вплоть до получения требуемого.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com

Facebook
X
Shares

java@Cat

Учебные материалы по изучению основ языка програvмирования Java

e-olymp 1281. Простая задачка Шарика