6-Laboratoriya ishi Mavzu: Dinamik programmalash

Dinamika va o’tish matritsasi.

Masalan Fibonatchi ketma-ketligini dinamik programmalash metodi bilan yechishga urinib ko’raylik. F[i]=F[i-2]+F[i-1] formula bizga ma’lum.

Endi (F[i], F[i-1]) ikkita sondan iborat vektorni va (F[i-1], F[i-2]) vektorni olaylik. (F[i], F[i-1]) ni (F[i-1]+F[i-2], F[i-1]) bilan almashtirishimiz mumkin. Uni esa (F[i-1], F[i-2]) vektorga quyidagicha bog’lash mumkin:

(F[i-1]+F[i-2], F[i-1]) = (F[i-1], F[i-2]) x

Bu asosiy formula hisoblanadi. Bizda esa F[1]=F[2]=1 ekanligi ma’lum. U holda quyidagilarni yozishimiz mumkin:

(F[3], F[2]) = (F[2], F[1]) x ;

(F[4], F[3]) = (F[3], F[2]) x = (F[2], F[1]) x x = (F[2], F[1]) x ;
(F[5], F[4]) = (F[4], F[3]) x = (F[2], F[1]) x x = (F[2], F[1]) x ;
Umumiy holda:

(F[n], F[n-1]) = (F[2], F[1]) x ;

Asosiy hisoblanishi kerak bo’lgan qiymat bu matritsaning (n-3) darajasini hisoblash. Buni esa binar darajaga ko’tarish algoritmi bo’yicha hisoblash mumkin.

Javob esa darajaga ko’tarilgan matritsaning (1, 1) va (2, 1) kataklarda turgan elementlarining yig’indisi.

8-topshiriq

You are given a natural number N. Let’s consider sequences with N digits and containing only 0 and 1. It is well known that the number of such sequences equals to 2^N. For example for N=3 such sequences: 000, 001, 010, 011, 100, 101, 110, 111.

Your task is to calculate then number of sequences not containing three ones successively. Among given sequences 111 don’t satisfy to such requirement.

Input__The_input_contains_single_integer_number_N_(1_≤_N_≤_70).__Output'>Input

The input contains single integer number N (1 ≤ N ≤ 70).

Output

Output one number – the answer to the problem.

Samples

№	Input	Output
1	1	2
2	3	7

#include

using namespace std;

bool check(string& s)

{

int n = s.length();

for (int i = 2; i < n; i++) {

if (s[i] == '1' && s[i - 1] == '1' && s[i - 2] == '1')

return 1;

}

return 0;

}

int countStr(int i, string& s)

{

if (i < 0) {

if (check(s))

return 1;

return 0;

}

s[i] = '0';

int ans = countStr(i - 1, s);

s[i] = '1';

ans += countStr(i - 1, s);

s[i] = '0';

return ans;

}

int main()

{

int N;

cin>>N;

string s(N, '0');

cout << pow(2,N) - countStr(N - 1, s);
return 0;

}