Рекурентні послідовності
Перегляньте навчальну презентацію, зверніть особливу увагу на властивості чисел Фібоначчі:
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();