Числа Фибоначчи

18/09/2016 by Мазурок Игорь Евгеньевич

Рассмотрим общеизвестный ряд чисел A000045:
[latex]0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, \ldots[/latex] Этот ряд представляет собой неотрицательную ветвь последовательности Фибоначчи. Будем считать, что последовательность задаётся следующим рекуррентным соотношением
[latex]f_n=\left\{\begin{matrix}
0, & n=0\\
1, & n=1\\
f_{n-1}+f_{n-2}, & n>1
\end{matrix}\right.[/latex]

Давайте напишем функцию, которая вычисляет [latex]n[/latex]-е по порядку число Фибоначчи, используя приведенное соотношение:

#include <cmath>
#include <iostream>
using namespace std;

unsigned long long f (unsigned short n) {
    return n < 2? n : f(n-1) + f(n-2);
}

int main() {
    cout << f(6);
    return 0;
}

#include <cmath>

#include <iostream>

using namespace std;

unsigned long long f (unsigned short n) {

return n < 2? n : f(n-1) + f(n-2);

}

int main() {

cout << f(6);

return 0;

}

Для теста мы вывели на печать вычисленное этим способом 6-е по порядку число Фибоначчи. Программа напечатала 8. И не ошиблась. Давайте посмотрим как происходили вызовы функций:

Порядок вызовов при вычислении шестого по счёту числа Фибоначчи по прямому рекурсивному алгоритму

Легко видеть, что для вычисления каждого числа Фибоначчи (кроме двух первых) выполняется строго два вызова функции. Т.е. если нам понадобится вычислить, следующее (седьмое) число Фибоначчи, то количество вызовов практически удвоится. И действительно, каждое следующее число вычисляется вдвое дольше, чем предыдущее. При наличии терпения ещё можно как-то дождаться конца вычисления 50-го числа, но дальше вычисляется уж очень долго.
В чём причина? Почему человек, вычисляя на листе бумаги, легко обгоняет компьютер?
Конечно, неэффективный алгоритм.
На рисунке цветом выделены те блоки, вычисление которых действительно необходимо. Число таких блоков растёт с увеличением номера числа линейно, говорят [latex]O\left( n\right)[/latex]. А вот остальные блоки — сплошные повторы и их число растёт как [latex]O\left( 2^n\right)[/latex].
Попробуйте изменить программу так, чтобы она работала быстро (без повторных вычислений.
В качестве упражнения, я попрошу не использовать циклов.
После того, как у Вас всё получится (или окончательно опустятся руки), загляните под спойлер и постарайтесь разобраться с моим вариантом решения задачи.

Рекурсивное решение без повторов

#include <iostream>
using namespace std;

unsigned long long tomorrow (
		unsigned short n, 
		unsigned long long yesterday, 
		unsigned long long today) 
{
	return n == 0? today : tomorrow(n - 1, today, yesterday + today);
}

unsigned long long h (unsigned short n) {
	return tomorrow (n, 0, 1);
}

int main() {
	cout<< f(93) << endl;
	return 0;
}

#include <iostream>

using namespace std;

unsigned long long tomorrow (

unsigned short n,

unsigned long long yesterday,

unsigned long long today)

{

return n == 0? today : tomorrow(n - 1, today, yesterday + today);

}

unsigned long long h (unsigned short n) {

return tomorrow (n, 0, 1);

}

int main() {

cout<< f(93) << endl;

return 0;

}

Related Images:

MLoops 18

27/12/2015 by Александр Димитриев

Условие

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n > 0[/latex] (количество столбцов) и [latex]m > 0[/latex] (количество строк).

1123581321345589144233377
1235813213455891442333776
2358132134558914423337761
3581321345589144233377610
5813213455891442333776109

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

В одной строке задано два числа [latex]n[/latex] и [latex]m[/latex].

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

Вывести таблицу размерностью [latex]n\times m[/latex].

Тесты

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

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

1 1

2 2

11
12

5 5

11235

12358

23581

35813

58132

9 18

112358132

123581321

235813213

358132134

581321345

813213455

132134558

213455891

345589144

558914423

891442333

144233377

233377610

377610987

610987159

987159725

159725844

258441816

418167651

25 5

1123581321345589144233377
1235813213455891442333776
2358132134558914423337761
3581321345589144233377610
5813213455891442333776109

1123581321345589144233377

1235813213455891442333776

2358132134558914423337761

3581321345589144233377610

5813213455891442333776109

Код

#include <iostream>
#include <cmath>
using namespace std;
 

int f(int a) {
	int b=1;
	for (int i=0; i<a; i++) {
		 b*=10;
	}
	return b;
}
 
int g(int a) {
	return (a==0 ? 1 : floor(log10(a))+1);
}
 
void h(int &i, int &j, int &a, int &b, int &a1, int &b1) {
	cout << endl; 
	a=a1;
	b=b1;
	i++;
	j=0; 
}
 
int main() {
	int n, m, a=1, b=0, c, a1=0, b1=1;
	cin >> n >> m;
	int i=1, j=0;
	while (i<=m) {
		if (j==n) {
		   	h(i, j, a, b, a1, b1);
		}
		c=a+b;
		a=b;
		b=c;
		if (j==0) {
		    a1=a;
		   	b1=b;
		}
		if (j+g(c)>n) { // если текущее число Фибоначчи выходит за предел строки
		    cout << c/f(g(c)-n+j); // печатаем ту часть что не выходит за ее предел
		 	h(i, j, a, b, a1, b1);
		} 
		else if (i<=m) {
		 	cout << c;
		 	j+=g(c); 
		} 
	}
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int f(int a) {

int b=1;

for (int i=0; i<a; i++) {

b*=10;

}

return b;

}

int g(int a) {

return (a==0 ? 1 : floor(log10(a))+1);

}

void h(int &i, int &j, int &a, int &b, int &a1, int &b1) {

cout << endl;

a=a1;

b=b1;

i++;

j=0;

}

int main() {

int n, m, a=1, b=0, c, a1=0, b1=1;

cin >> n >> m;

int i=1, j=0;

while (i<=m) {

if (j==n) {

h(i, j, a, b, a1, b1);

}

c=a+b;

a=b;

b=c;

if (j==0) {

a1=a;

b1=b;

}

if (j+g(c)>n) { // если текущее число Фибоначчи выходит за предел строки

cout << c/f(g(c)-n+j); // печатаем ту часть что не выходит за ее предел

h(i, j, a, b, a1, b1);

}

else if (i<=m) {

cout << c;

j+=g(c);

}

return 0;

}

Решение

Несложно догадаться что данная последовательность чисел это числа Фибоначчи. Для того чтобы построить таблицу надо сначала найти числа Фибоначчи (у меня это — [latex]a,b,c[/latex]), после печатаем их в строку далее переходим на новую строку и начинаем со 2 элемента относительно предыдущей строки это выполняет функция [latex]h[/latex], и так пока [latex]i \le m[/latex]. Но может возникнуть проблема с выходом за предел строки и для того чтобы этого не произошло нам нужны функции [latex]f[/latex], которая возводит 10 в заданную степень, это нам надо чтобы отрезать то что выходит за предел строки, для этого используем целочисленное деление на 10 в нужной степени, и [latex]g[/latex], которая считает количество цифр в данном числе Фибоначчи, для того чтобы определить в какую степень нам надо возвести 10, чтобы оставить только ту часть что не выходит за предел строки.
Код программы

Related Images:

Mloop 21

21/12/2015 by Максим Носов

Задача

Вычислить с точностью [latex]\varepsilon [/latex] сумму ряда [latex]\sum _{i=1}^{\infty }{\frac{i}{fib(i)}}[/latex]

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

Точность [latex]\varepsilon [/latex].

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

Сумма ряда.

Тесты

№	Точность [latex]\varepsilon [/latex]	Сумма ряда	Количество членов
1	1	3	2
2	0.5	8.502	8
3	0.1	9.156	12
4	0.01	9.307	18

Код

#include <iostream>
using namespace std;

int main() {
	double fib1=1,fib2=1,fib3,sum=3,E,a=1; //задаем переменные
	int k=2;
	cin>>E; //вводим точность, с которой будут происходить вычисления //если точность равна 1 то сумма последовательности 
	if(E==2 || E==1)cout<<2<<endl<<3; //если точность равна 1 или 2 по сумма будет равнна сумме двух первых членов последовательности
	else if(E<1){
		for(int i=3;a>=E;i++){ //задаем цикл:пока следующее слагаемое больше точности
			fib3=fib1+fib2;
			a=i/fib3; //слагаемое
			sum+=a;
			fib1=fib2;
			fib2=fib3;
			//k++;  //считаем количество слагаемых, для того чтобы потом проверить результат
		}
	//cout<<k<<endl;
        cout<<sum;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double fib1=1,fib2=1,fib3,sum=3,E,a=1; //задаем переменные

int k=2;

cin>>E; //вводим точность, с которой будут происходить вычисления //если точность равна 1 то сумма последовательности

if(E==2 || E==1)cout<<2<<endl<<3; //если точность равна 1 или 2 по сумма будет равнна сумме двух первых членов последовательности

else if(E<1){

for(int i=3;a>=E;i++){ //задаем цикл:пока следующее слагаемое больше точности

fib3=fib1+fib2;

a=i/fib3; //слагаемое

sum+=a;

fib1=fib2;

fib2=fib3;

//k++; //считаем количество слагаемых, для того чтобы потом проверить результат

}

//cout<<k<<endl;

cout<<sum;

}

return 0;

}

Решение

Предлагаю следующее решение. Вычисляем первые два члена суммы:[latex]\sum _{i=1}^{2}{\frac{i}{fib(i)}}=1+\frac{1}{2}[/latex]. Каждое следующее слагаемое находим по формуле [latex]\frac{i}{fib(i)}[/latex] и записываем в переменную [latex]a[/latex], которую прибавляем к переменной [latex]sum[/latex], где хранится сумма, известная нам на данный момент (изначально это сумма первых двух членов) . [latex]fib_1[/latex] и [latex]fib_2[/latex] это два последних числа Фибоначчи, которые нам нужны для вычисления следующего [latex]fib_3[/latex]. Продолжаем искать слагаемые пока следующее слагаемое больше точности [latex]\varepsilon [/latex]. Вводим дополнительную переменную [latex]k[/latex] для того чтоб сосчитать количество слагаемых. Затем можно проверить правильность вычислений тут, подставляя [latex]k[/latex] как количество слагаемых.

Ссылка на код.