Рекурентні послідовності

Перегляньте навчальну презентацію, зверніть особливу увагу на властивості чисел Фібоначчі:

1) Найбільший спільний дільник двох чисел Фібоначчі дорівнює числу Фібоначчі з індексом рівним найбільшому спільному дільнику індексів, тобто: .
В наслідок цього:
1)Fm ділиться Fn тоді й тільки тоді, коли m ділиться на n (за виключенням n = 2);
2)кожне третє число Фібоначчі парне (F3 = 2, F6 = 8, F9 = 34);
3)кожне четверте ділиться на три (F4 = 3, F8 = 21, F12 = 144);
4)кожне п'ятнадцяте закінчується нулем (F15 = 610);
5)два сусідніх числа Фібоначчі взаємно прості;
6)Fm може бути простим тільки для простих m (за єдиним виключенням m = 4, що пов'язано з F2 = 1). Зворотнє твердження невірно. На даний момент невідомо, чи існує нескінченно багато простих чисел Фібоначчі.

 

Тренувальні вправи

1. В режимі кослоль "Вивести на екран N перших чисел Фібоначчі"

int n, f1, f2, fi;
f1 = 1;
f2 = 1;
n =Convert.ToInt32(Console.ReadLine());
if (n > 0) Console.WriteLine(f1);
if (n > 1) Console.WriteLine(f2);
for (int i = 3; i <= n; i++)
{
fi = f1 + f2;
Console.WriteLine(fi + " ");
f1 = f2;
f2 = fi;
}

2.  Серед чисел Фібоначчі знайти та вивести на екран тільки  парні,  або тільки кратні 3,  скориставшись  властивостями чисел Фібоначчі

 а) int n, f1, f2, fi;
f1 = 1;
f2 = 1;
 Console.Write("Введіть n, що більше 20");
n =Convert.ToInt32(Console.ReadLine());
Console.WriteLine("Кожне третє число Фібоначчі - парне );
  for (int i = 3; i <= n; i++)
{
fi = f1 + f2;
 if (i%3= =0) Console.WriteLine(fi + " ");
f1 = f2;
f2 = fi;
}

 б) int n, f1, f2, fi;
f1 = 1;
f2 = 1;
 Console.Write("Введіть n , що більше 20");
n =Convert.ToInt32(Console.ReadLine());
 Console.WriteLine("Кожне четверте число Фібоначчі - кратне 3);
  for (int i = 3; i <= n; i++)
{
fi = f1 + f2;
 if (i%4= =0) Console.WriteLine(fi + " ");
f1 = f2;
f2 = fi;
}

Обчислення ланцюгових дробів

Вираз    називається ланцюговим дробом.

Нескінченний ланцюговий дріб позначається так: 

а скінченний ланцюговий дріб із останнім знаменником bn – так 

Скорочений запис цих позначень є таким:   

Ланцюгові дроби обчислюються з кінця.

Розглянемо послідовність {zi} знаменників ланцюгового дробу

zn = bn , zn-1 = bn-1 + an/zn, zn-2 = bn-2 + an-1 /zn-1, ..., z1 = b1 + a2 /z2, z0 = b0 + a1/z1.

Послідовність визначається рекурентним співвідношенням zi = bi + ai+1/zi+1 для всіх і = n-1, n-2,..., 0 і першим членом zn = bn, а значення z0 дорівнює значенню дробу.

Тому значення скінченного ланцюгового дробу можна обчислити за тим самим алгоритмом, що і значення членів рекурентної послідовності.

Обчислити ланцюговий дріб:   

Для цього дробу ai = 1, bi = 2n + 1, і = 1,..., n, b0 =1.

Змінну b використаємо для зберігання значень 2і + 1, а змінну z — для зберігання значень знаменників. Значення змінної b має зменшуватися на 2 кожної ітерації циклу. Крім модифікації значення b, в тілі циклу треба обчислити чергове значення z за формулою рекурентного співвідношення: zi =b + 1/zi-1.

int n;

Console.WriteLine("Введи значення n");

n = Convert.ToInt32(Console.ReadLine());

int b=2*n+1;

double z=b;

while (b>1)

{

b=b-2;

z=b+1/z;

}  

Console.WriteLine("Значення даного ланцюгового дробу: {0:f4}",z);

Console.ReadLine();