Числа фиббоначчи – фиббоначчи саннары

Задано следующее рекурентное соотношение:

F₀=1, F₁=1, F_i= F_i-1+F_i-2, т.е. 1, 1, 2, 3, 5, 8, 13, 21, 34…

Для решения этой задачи можно использовать рекурсивную функцию:

Function fibbonachi(n:integer):integer;

Begin

If n=0 then fibbonachi:=1

Else

If n=1 then fibbonachi:=1

Else

fibbonachi:=fibbonachi(n-1)+ fibbonachi(n-2)

End;

Либо итеративную функцию:

Function fibbonachi(n:integer):integer;

Var f,f1,f2,I:integer;

Begin

If n=0 then fibbonachi:=1

Else

If n=1 then fibbonachi:=1

Else

begin

f1:=1;

f2:=1;

for I:=2 to n do

begin

f:=f1+f2;

f2:=f1;

f1:=f

end;

fibbonachi:=f

end

End;

Рассмотрим еще две задачи на рекурсию.

1) Задана лестница с n ступенями. При подъеме по лестнице можно шагать либо на следующую ступень, либо через одну ступень, либо через две. Нужно определить сколькими различными способами можно подняться по данной лестнице.

Решение – чишү.

При n=1 – 1.

При n=2 – 2 (1+1, 2).

При n=3 – 4 (1+1+1, 1+2, 2+1, 3).

Далее число вариантов зависит от предыдуших супеней, т.е. F(n)= F(n-1) + F(n-2) + F(n-3).

Для решения этой задачи можно использовать рекурсивную функцию:

Function baskch(n:integer):integer;

Begin

If n=1 then baskch:=1

Else

If n=2 then baskch:=2

Else

If n=3 then baskch:=4

Else

baskch:= baskch(n-1)+ baskch(n-2) + baskch(n-3)

End;

Либо итерративную функцию:

Function baskch(n:integer):integer;

Var f,f1,f2,f3,I:integer;

Begin

case n of

1: baskch:=1;

2: baskch:=2;

3: baskch:=4

else begin

f1:=1; f2:=2; f3:=4;

for I:=3 to n do

begin

f:=f1+f2+f3;

f3:=f2;

f2:=f1;

f1:=f

end;

baskch:=f

end

end

End;

 

2) Задан круг с 2k вершинами на ней. Пары вершин соединяются хордами, не имеющими общих концов. Определить число различных вариантов соединений вершин хордами, дающих минимальное разбиение круга своими сечениями.

Решение – чишү.

Если задана какая-то разбивка круга хордами и очередная хорда не пересекает остальные хорды, то число областей увеличится на 1. Если же данная хорда будет пересекать при соединении вершин другие хорды, то число областей увеличится больше чем на 1. Отсюда следует, что в минимальном разбиении хорды не должны пересекаться и число областей образованных хордами будет равняться k+1.

При k=0 число вариантов F(0)=1.

При k=1 число вариантов F(1)=1.

При k=2 число вариантов F(2)=2.

    2          2

1          3

              1          3

    4            4

Для решения задачи перенумируем вершины по часовой стрелке.

В этом случае число вариантов определяется разбиением всех хорд круга, первой исходящей хордой из вершины 1. Она может присоединятся только к вершинам с четными номерами, иначе будут пересечения хорд и число областей не будет минимальной. Тогда число вариантов разбиения F(2)=F’(2-число вершин между 1 и 4 по часовой стрелке по кругу, 0 - число вершин между 4 и 1 по часовой стрелке по кругу)+F’(0,2)=F(1)*F(0)+ F(0)*F(1)=1*1+1*1=2.

Для произвольного k при переборе вариантов проведения хорд из вершины 1 будет следующая формула:

F(k)= F(0)*F(k-1)+F(1)*F(k-2)+F(2)*F(k-3)+…+F(k-2)*F(1)+ F(k-1)*F(0)

В зависимости от значения k для вектора F нужно подобрать соответствующий тип. В случае необходимости при больших значениях k необходимо будет представить их в виде векторов разряда числа и соответственно написать процедуры вычисления арифметических операций над ними.

Для ускорения вычисления чисел Фибоначчи можно обратиться к использованию матриц следующего вида

А	1	1
	1	0

Если мы рассмотрим степени этой матрицы

А1=	1	1	А2=	2	1	А3=	3	2	…Аi=	Fi+1	Fi
	1	0		1	1		2	1		Fi	Fi-1

То обнаружим, что значения элементов степеней этой матрицы совпадают с числами Фибоначчи данного порядка.

Обнаружив это свойство матрицы, можно использовать математический аппарат матриц. Используя свойства матриц можно ускорить вычисления чисел фиббоначчи. Для этого рассмотрим умножение матриц

А*В =	A11	A12	*	B11	B12	=	A11B11+A12 B21	A11B12+A12 B22
	A21	A22		B21	B22		A21B11+A22 B21	A21B12+A22 B22

Процесс вычисления произведения таких матриц требует выполнения 12 арифметических операций. Если процесс вычисления матрицы будет производится в соответствии с определением Аⁿ=АAA…A, то арифметических операций потребуется 12(n-1). И для вычисления чисел Фибоначчи при малых n с использованием матриц требует большего времени.

Для решения этой задачи при больших n далее рассмотрим степени матрицы А.

А¹, А²(12), А³=AAA=А²А(24), А⁴=АAAA(36)=А³A(36)=(А²)²(24)…
А⁸=АAAAАAAA(86)=…= (((А²)²) ²(36)…

Т.е. степени матрицы могут быть получены разными способами: либо через произведение всех матриц, определяющих ее степень, либо с использованием промежуточных вычислений можно сократить процесс вычисления степени матрицы.

Например при

n=2^k=32, Аⁿ=((((A²)²)²)²)²  - требуется 60 арифметических операций;

n=73=64+8+1=1*2⁰+0*2¹+0*2²+1*2³+0*2⁴+0*2⁵+1*2²

A A² A⁴ A⁸ A¹⁶ A³² A⁶⁴

Аⁿ= А⁷³= A *   A⁸  * A⁶⁴

Таким образом, видно, что для данного случая вычислений с помощью матриц требуется 8*12=96 арифметических операций вместо 73*12=876;

3. n=2^k=256, Аⁿ=(((((((A²)²)²)²)²)²)²)²  — требуется 8*12=96 арифметических операций с помощью матрицы вместо 255 операций при обычным способе.

Число арифметических операций для вычисления чисел Фибоначчи при быстром умножении матриц равно сумме числа единиц в двоичном разложении n и числу значащих разрядов n, умноженной на 12. Это число колеблется от 12 ∟log₂ n до 24 ∟log₂ n [7]. Программа имеет следующий вид:

Program Fibbonachi;

Type tabn=array[1..2,1..2] of long int

Var A,B:tabn;

I,j,k,n:integer;

Procedure tapkrlau(a,b: tabn; var c: tabn);

Begin

C[1,1]:=B[1,1]*A[1,1]+ B[1,2]*A[2,1];

C[1,2]:=B[1,1]*A[1,2]+ B[1,2]*A[2,2];

C[2,1]:=B[2,1]*A[1,1]+ B[2,2]*A[2,1];

C[2,2]:=B[2,1]*A[1,2]+ B[2,2]*A[2,2];

End;

Begin

Read(n);

A[1,1]:=1; A[1,2]:=1; A[2,1]:=1; A[2,2]:=0;

B[1,1]:=1; B[1,2]:=0; Bb[2,1]:=0; B[2,2]:=1; {A⁰}

While n<>0 do

1

3

4

5

6

2

Begin

If n mod 2=1 then

Tapkrlau(B,A,B);

Tapkrlau(A,A,A);

n:=n div 2

End;

Write(B[1,2])

End.

Теория графов

Граф G(X,A) – это совокупность элементов X={x₁, x₂, x₃, … x_n,} с его множеством связей A={<x_i1, x_j1>, <x_i2, x_j2>,<x_i3, x_j3>, … <x_ik, x_jk>} где n – число вершин, k – число связей.

X={1,2,3,4,5,6}

A={<1,2>,<1,3>,<1,4>,<5,4>,<2,5>,<6,2>,<5,6>,<6,5>,<6,3>}

Граф G(X,A) – называется неориентированным графом, если в А для любой связи <x_i,x_j> существует связь <x_j, x_i>.

 

Графы могут иметь различное представление:

графическое                   6   3   7 4

Например: 1         2

                1 2 3      4   5

 

              5 8 6 9 7

список элементов связи

A={<1,5>,<1,6>,<1,7>,<2,7>,<3,7>,<2,3>,<3,4>,<5,6>,<6,7>}

матрица смежности

	0	0	0	0	1	1	1	, где Ai,j принимает значение 1 при наличии связи из i в j, иначе 0.
	0	0	1	0	0	0	1
	0	1	0	1	0	0	0
A=	0	0	1	0	0	0	0
	1	0	0	0	0	1	0
	1	0	0	0	1	0	1
	1	1	0	0	0	1	0

Неориентированные графы имеют симметричную матрицу смежности и его связи называются ребрами, а для ориентированных графов связи называются дугами.

Матрица инцеденций

	1	0	0	0	1	0	0	, где строки соответствуют ребрам, а столбцы вершинам. Для i –го ребра <j,k> в строке i Ai,j=1 Ai,k=1
	1	0	0	0	0	1	0
	1	0	0	0	0	0	1
	0	1	0	0	0	0	1
A=	0	0	1	0	0	0	1
	0	1	1	0	0	0	0
	0	0	1	1	0	0	0
	0	0	0	0	1	1	0
	0	0	0	0	0	1	1

имеющий размер m x n.

Рассмотрим программу преобразования графа из формы списка элементов связи в остальные формы и проверкуналичия эйлерова цикла в графе с помощью матрицы смежности.

Program convert;

Const n=7;

Var a_insedent:array[1..m,1..n] of integer;{ матрица инциденций }

A_smegn:array[1..n,1..n]of integer;{матрица смежности }

A_spisok:array[1..2,n*(n-1)] of integer;{ список элементов связей-ребер}

I,j,m,chэslo_reber:integer;

Svazanoe_mnogestvo:set of 1..n;{связаное множество для решения задачи об эйлеровом цикле }

Proverochnij_vector:array[1..n] of integer;

Ejler:Boolean;

Begin

{инициализация массивов}

For i:=1 to n do

Begin

For j:=1 to n do A_smegn[i,j]:=0;

For j:=1 to m do A_insedent[j,i]:=0

End;

For i:=1 to n*(n-1) do begin A_spisok[1,i]:=0; A_spisok[2,i]:=0 end;

{Ввод списка связей }

m:=0;

while not eof do

begin

m:=m+1;

readln(A_spisok[1,m],A_spisok[2,m]);

{формирование матрицы смежности}

A_smegn[A_spisok[1,m],A_spisok[2,m]]:=1;

A_smegn[A_spisok[2,m],A_spisok[1,m]]:=1;

{формирование матрицы инцеденций}

A_insedent[m,A_spisok[1,m]]:=1;

A_insedent[m,A_spisok[2,m]]:=1;

end;

{Проверка наличия эйлерова цикла в графе разлагается на две задачи:

— проверка связанности графа, т.е. наличия соединяющих путей (последовательности ребер с общими концами) для любой пары вершин;

— наличия замкнутого пути, проходящего по всем ребрам, который определяется четносьтю степеней всех вершин в графе}

ejler:=true;{проверяется нарушение свойства эйлерова цикла}

Svazanoe_mnogestvo:=[1];

Proverochnij_vector[1]:=1;

i:=1;{номер проверяемой вершины в Proverochnij_vector }

J:=2;{ свободное место в Proverochnij_vector }

Whэle i<>j do {пока компанента связанности не проверена выполнить}

Begin

Chэslo_reber:=0;

For m:=1 to n do

If A_smegn[m,Proverochnij_vector[I]=1 then

Begin

Chэslo_reber:=Chэslo_reber+1;

If not(m in Svazanoe_mnogestvo) then

begэn

Proverochnij_vector[j]:=m;

Svazanoe_mnogestvo:= Svazanoe_mnogestvo+[m]

end

End;

If odd Chэslo_reber then ejler:=false

i:=i+1;

End;

If Svazanoe_mnogestvo<>[1..n] then ejler:=false;

Эf ejler then write(‘эйлеров цикл есть’)

Else write(‘эйлерова цикл нет’)

End.

Перебор подмножест

Пусть задано множество X={x₁, x₂, x₃}. Переберем все подмножества – Бирелгән төркемне аралап чыгыйк

x₁, x₂, x₃

0 0 0     - > { }

0 0 1     - > {x₁ }

0 1 0     - > { x₂ }

0 1 1     - > {x₁, x₂ }

1 0 0     - > { x₃}

1 0 1     - > {x₁, x₃}

1 1 0     - > { x₂, x₃}

1 1 1     - > {x₁, x₂, x₃}

Следующая программа проводит этот перебор как перебор двоичного кода в векторе с n разрядами

uses crt;

const

n=4;

k=12;

var

mn,p:array[1..n] of integer;

i,y:integer;

bette:boolean;

begin

clrscr;

write('(');

for i:=1 to n do

begin

mn[i]:=0;

write(' 0');

p[i]:=random(9)+1;

end;

writeln(') -> {} = 0');

repeat

{добавить 1 }

y:=0;

i:=n;

while mn[i]=1 do

begin

   mn[i]:=0;

   i:=i-1

end;

mn[i]:=1;

for i:=1 to n do

if mn[i]=1 then y:=y+p[i];

{печать множества }

write('(');

for i:=1 to n do

write(mn[i]:2);

write(') -> {');

for i:=n downto 1 do

if mn[n-i+1]=1 then

    write(' X',i);

writeln('} =',y);

{проверка конца }

bette:=true;

for i:=1 to n do

if mn[i]=0 then

   bette:=false

until bette

end.

Перебор перестановок

Пусть задано множество X={1, 2, 3}. Переберем все перестановки этих чисел

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

Const n=10;

Var x:array[1..n] of integer;

i,j,r:integer;

Begin

For i:=1 to n do

Begin

x[i]:=I;

write(x[i],’ ‘)

end;

writeln;{первая перестановка }

Repeat

{Переход к следующей перестановке }

J:=n;

While (x[j]<x[j-1]) and (j>0) do j:=j-1;

i:=n;

While x[i]<x[j] do i:=i-1;

{Xi<->Xj – меняяем местами }

R:=x[i];

X[i]:=x[j];

X[j]:=r;

{печать – бастырып чыгару}

For i:=1 to n do

write(x[i],’ ‘)

writeln;{первая перестановка }

{проверка условия завершения

Bette:=true;

For i:=1 to n-1 do

If x[i]<x[i-1] thrn

Bette:=false

Until bette;

End.

Тестирование программ

Рассмотрим следующую задачу, сформулированную для олимпиады.

Задана квадратная матрица А размерности n x n из натуральных чисел до 100, где n<1000. Составить программу построения вектора В и вычисления суммы его элементов, где B_i= min A_lk для 1 < l < i и i < k < n.

Входной файл: input.txt, в первой строке которой задается размерность матрицы N, затем построчно задаются элементы матрицы, в N строках по N символов.

Выходной файл: в выходной файл Output.txt выдается сумма элементов вектора В.

Ограничения по времени: 1 секунд

Ограничения по памяти: 256Kb

Пример:

INPUT.TXT

4

1  12 4  2

12 34 11 7

4  1  2  12

1  1  1  1

OUTPUT.TXT

6

Для оценки работ этой программы жюри нужно определить следующие аспекты:

метод решения задачи, удовлетворяющий данным ограничениям;

создания системы тестов, учитывающих все типы особых случаев и их оценки;

создание автоматизированной системы проверки правильности решенной программы с использованием данной системы тестов, которая на каждом тесте, определяя правильность программы, оценивала бы работу участника олимпиады.

На данном примере все аспекты мы рассмотрим.

1. Если воспользоваться рассмотренными методами решения данной задачи, то потребуется 1 Мгб памяти для массива, что невозможно в Турбо Паскале. Также, если определять для каждого B_i= min A_lk (1 < l < i, i < k < n), требуется около 10⁹ операций сравнения, что тоже недопустимо ограничениями времени.

Поэтому рассмотрим для ускорения процесса задачи следующую задачу построения вектора D=(d₁,d₂,d₃,…,d_n) по заданному вектору C=(c₁,c₂,c₃,…,c_n), где d_i=min c_j для i < j < n

For i:=1 to n-1 do

Begin

d[i]:=c[i];

for j:=i+1 to n do

if c[i]>d[j] then c[i]:=d[j]

End

Данный метод определения вектора D требует n(n-1)/2 операций сравнения. Но если сменить порядок определения элементов вектора D, то число сравнений будет n.

d[n]:=c[n];

For i:=n-1 downto 1 do

if c[i]>d[i+1] then d[i]:=d[i+1]

else d[i]:=c[i]

Этот подход сокращает вычисления время вычисления данного вектора в n раз.

При решении нашей задачи можно произвести преобразования заданной матрицы по каждой строке к данному виду

A₁₁ A₁₂ A₁₃ … A_1n       A’₁₁ A’₁₂ A’₁₃   … A’_1n

A₂₁ A₂₂ A₂₃ … A_2n             A’₂₁ A’₂₂   A’₂₃ … A’_2n

A= A₃₁ A₃₂ A₃₃ … A_3n => A’= A’₃₁ A’₃₂   A’₃₃ … A’_3n

               ...

A_n1 A_n2 A_3n … A_nn       A_n1 A_n2   A_3n … A’_nn

где A’_ij = min A’_il для i < l < n. Это преобразование сохраненяет результат решения и B_i= min A_lk (1 < l < i, i < k < n) = min A’_lk (1 < l < i, i < k < n) = min (min A’_{i i+1},A’_{j i}) для 1 < j < i-1, соответственно появляется возможность сокращения времени решения данной задачи в n раз. Данный подход позволяет уложится в ограничения по времени.

Для решения проблемы нехватки памяти также можно решить, используя данную преоброзованию матрицу следующим образом. Поскольку при вычислении B_i требуется только два элемента или два вектора – текущий преобразованный и интегрированный A’’, где элементы содержат A’’_k=min A_lj для 1 < l < k, k < j < n. При смене i на i+1 новая интегрирующая строка A’’ i+1 строки получается из A’’ i строки и текущей строки матрицы А.

If A1[n]<A[n] {A1 – A’’}

then A1[n]:=A[n];

For j:=n downto i+1 do

Begin

If A[j]>A[j+1] then A[j]:=A[j+1];

If A[j]<A1[j] then A1[j]:=A[j];

End;

Таким образом, задача решается двуми векторами. Вектор В будет вычисляться по мере обработки вектора A’’, где при заданном i в A1 элементы A1_i для элементов от 1 до i будут соответствовать вектору В, а для элементов от i+1 до n будут соответствовать вектору A’’. Общий вид программы будет следующим.

{$ A +, B -, D +, E +, F -, G -, I +, L +, N -, O -, P -, Q +, R -, S +, T -, V +, X +, Y +}

{$M 16384,0,655360}

const maxn=1000;

var a:array[1..2,1..maxn]of integer;

n,i,j:integer;

q:longint;

begin

reset(input,'input.txt');

rewrite(output,'output.txt');

readln (n);

{Ввод строки для формирования интегрированной строким}

for i:=1 to n do {ввод первой строки }

read (a [1, i ]);

readln;

{установка минимумов по первой строке }

for i:=n-1 downto 1 do

if a[1,i]>a[1,i+1] then a[1,i]:=a[1,i+1];

{работа с остальными строками }

for i:=2 to n do

begin

{ чтение }

for j:=1 to n do

   read(a[2,j]);

readln;

{ поиск минимумов }

for j:=n downto i do

   begin

     if a[2,j]<a[1,j] then a[1,j]:=a[2,j];

     if a[2,j]<a[2,j-1] then a[2,j-1]:=a[2,j];

   end

end;

{суммирование}

q:=0;

for i:=1 to n do

q:=q+a[1,i];

write(q); { результат – нәтиҗә }

close(input);

close (output);

end.

2. Далее рассмотрим следующую систему тестов для проверки правильности программы участников олимпиады.

1-ый тест берется из примера, приведенного в условии задачи;

далее тесты генерируются следующей программой

program gen _ test _1;

var

i,j,n,n_test,n_task,

max_zn,min_zn:integer;

f_out:text;

name,zn:string;

begin

write (‘ n =’); readln (n); {определение размера массива}

write(‘ Номер задачи =’);readln(n_task);

write(‘ Номер теста =’);readln(n_test);

write (‘ самое малое значение =’); readln (min _ zn);

write (‘ самое болшое значение =’); readln (max _ zn);

str(name, n_task,I);

str(zn, n_test,I);

name:=name+’_’+zn;

rewrite (f_out,name);

for i:=1 to n do

begin

for j:=1 to n do

write(‘ ‘,random(max_zn - min_zn)+min_zn);

writeln(f_out)

end;

close(f_out)

end.

2-ой тест – матрица размерности 10х10 из элементов равных 1;

3-ий тест – матрица размерности 10х10 из элементов равных 2 кроме A_1n = 1;

4-ый тест – матрица размерности 10х10 из 99;

5-ый тест – матрица размерности 10х10 из случайных значений от 1 до 99;

6-ой тест – матрица размерности 1000х1000 из элементов равных 1;

7-ой тест – матрица размерности 1000х1000 из элементов равных 2 кроме A_1n = 1;

8-ой тест – матрица размерности 1000х1000 из 99;

9-ый тест – матрица размерности 1000х1000 из случайных значений от 1 до 99.

Оценка тестов можно сделать по 10 5 10 5 10 5 10 5 10 балов. В данном случае ценность отдельного случая опредеяется сложностью реализации. Для отдельной оценки полностью завершенной задачи можно внести баллы бонусы – 10 баллов. Таким образом, ценность данной работы 70 баллов.

3. Инструкция по использованию тестирующей системы

Подготовка системы к работе

· завести каталог TEST, где будет производится тестирование;

· завести каталог TESTS, где будут храниться файлы с тестами, ответами, оценки и проверочные программы;

· каждую предложенную на олимпиаду работу членам жюри надо решить и приготовить следующие файлы:

· 1_<номер задачи>.pas – исходный текст программы участника олимпиады странслировать и получить файл 1_<номер задачи>.exe. Затем разместить в каталоге TEST;

· приготовить тесты и занести их в файлы <номер задачи>_<номер теста>.tst. Затем разместить в каталоге TESTS;

· Каждый приготовленный тест использовать для получения ответа программой, приготовленной членами жюри. Эти ответы занести в соответствующий файл <номер задачи>_<номер теста>.ans. Эти файлы с правильными ответами также разместить в каталоге TESTS;

· Приготовить программу сравнения ответа участника олимпиады с ответом приготовленным членами жюри в файле <номер задачи>.exe и разместить в разместить в каталоге TESTS;

· Затем приготовить для каждой задачи файл оценки <номер задачи>.inf, где записывается следующая информация

.Название = C.

.Количество тестов = 9

.Входной файл = input.txt

.Выходной файл = output.txt

.Ограничение времени = 3

.Баллы за тесты = 10 5 10 5 10 5 10 5 10

.Bonus за все тесты = 10

Этот файл разместить в каталоге TESTS;

Приготовить программу проверки правильности ответа в файле <номер задачи>.exe. Затем разместить в каталоге TESTS.

При подготовке проверки ответа можно использовать следующие фрагменты программы:

uses testlib;

var i,x,y,n:integer;

t:boolean;

begin

n:=inf.readinteger;

t:=false;

for i:=1 to n do

begin

x:=ans.readinteger;

y:=ouf.readinteger;

if x<>y then

    begin

       quit (_ wa,' '); { неправильный ответ }

       t:=true;

       break;

    end;

end;

if not t then quit(_Ok,' ') { правильный ответ }

end.

Пояснения по расширению testlib, который используется при проверке тестируемых данных.

uses testlib;

var x,y:integer;

begin

x:=ans.readinteger; {longint real string char}{ ввод правильного ответа }

y:=ouf.readinteger;                      {ввод ответа участника олимпиады}

 z:=inf.readinteger;                      {ввод информации и }

end;