ֆիբոնաչիի թվեր

[linus]

ֆիբոնաչիի ֆունկցիան սահմանվում է հետևյալ կերպ


f(n) = 1 if n = 0;
f(n) = 1 if n = 1;
f(n) = f(n-1) + f(n-2);

հեշտ խնդիր

տալ անրադարձ(ռեկուրսիվ) առնչություն, որով կհաշվվի ֆիբ. թվերը բոլոր n - երի համար, ընդ որում ալգորիթմի բարդությունը լինի O(n) (ո կարգի)

[Սամվել]

Ուզում էի գրեի էն էլ հավեսս փախավ թող մնա վաղը

[teleport]

ֆիբոնաչիի ֆունկցիան սահմանվում է հետևյալ կերպ


f(n) = 1 if n = 0;
f(n) = 1 if n = 1;
f(n) = f(n-1) + f(n-2);

հեշտ խնդիր

տալ անրադարձ(ռեկուրսիվ) առնչություն, որով կհաշվվի ֆիբ. թվերը բոլոր n - երի համար, ընդ որում ալգորիթմի բարդությունը լինի O(n) (ո կարգի)

Բոլոր n - երի համար: Ասենք 1000000000000000000000000000003 :

Չեմ կարծում , որ վերևինս կկարողանա:

[Սամվել]

Բոլոր n - երի համար: Ասենք 1000000000000000000000000000003 :

Չեմ կարծում , որ վերևինս կկարողանա:

Բավականին հեշտ ալգորիթմ է ուղակի ժամանակ չունեմ գրեմ ...ստուգեմ... տեղադրեմ...

Այլ հարց է որ այդ թիվը համակարգչին հաշվելու համար շատ երկար ժամանակ կպահանջվի բայց դե ալգորիթմը միևնույնն է բոլոր թվերի համար

եթե մինչև կիրակի իրիկունը անող չլինի ես կտեղադրեմ

[teleport]

Բավականին հեշտ ալգորիթմ է ուղակի ժամանակ չունեմ գրեմ ...ստուգեմ... տեղադրեմ...

Այլ հարց է որ այդ թիվը համակարգչին հաշվելու համար շատ երկար ժամանակ կպահանջվի բայց դե ալգորիթմը միևնույնն է բոլոր թվերի համար

եթե մինչև կիրակի իրիկունը անող չլինի ես կտեղադրեմ

Բարեկամս , կտեղադրես կտեսնենք:
Ասեմ միանգամից , որ ես պահանջելում եմ գուգլերորդ ֆիբոնաչիի թիվը:
Ժամանակակից համակարգիչները բավականին արագագործ են , հաստատ կարողանում են հաշվել նշված թիվը:

[linus]

Բարեկամս , կտեղադրես կտեսնենք:
Ասեմ միանգամից , որ ես պահանջելում եմ գուգլերորդ ֆիբոնաչիի թիվը:
Ժամանակակից համակարգիչները բավականին արագագործ են , հաստատ կարողանում են հաշվել նշված թիվը:

այ եթե լավ ալգորիթմ լինի ապա գուգլերորդը կհաշվի

[Cesare]

այ եթե լավ ալգորիթմ լինի ապա գուգլերորդը կհաշվի

Եթե գրում եք C++-ով C#_ով Paskal–ով, Basik–ով կամ Java–ով, ապա երբ n_ը բավականին մեծացնենք, ապա F(n)-ը կդառնա բավականին մեծ և հնարավորություն չի լինի պահել int, long, կամ նույնիսկ __int64 տիպում :

Մնացած դեպքերում ալգորիթմը պարզա : Այսիննքն ըտե ալգորիթմ չկա մի հատ for ես գրում պրխնում :

Իսկ առաջին դեպքում պետք ա օգտագործել երկար մաթեմատիկա , որը Օ(n) կախվածությամբ խի արդեն :

Ու մի բան, եթե ալգորիթմը Օ(n) ա, ապա 1000000000000-ից մեծ n-երի համար կոմպը ի աշխատի կոռեկտ ժամանակում :

Փորձից ելնելով գիտեմ /կարելի ա հաշվել/, որ 10000000 գործողությունը կատարում ա 1վ-ու :

[jorazak]

Ահա պատրաստի սուրսը C++ լեզվով: Եթե որևէ անհասկանալի պահ կա, ասեք, կբացատրեմ:

#include <iostream>
using std::cout;
using std::cin;
using std::endl;
unsigned long fibonacci( unsigned long )

int main()
{
unsigned long result, number;
cout << "Mutkagrek drakan amboxj tiv: ";
cin >> number;
result = fibonacci( number );
cout << "Fibonachii hajordakanutyan (" << number << ") andamy havasar e " << result << endl;
}
//Ստորև նկարագրված է Ֆիբոնաչիի ռեկուրսիվ ֆունկցիան
{
if ( n == 0 )
return n;
else if( n == 1)
return n;
else
return fibonacci (n-1) + fibonacci (n-2);
}

Ռեկուրսիվ ֆունկցիաների մանրամասն նկարագրությունը կարդացեք Հ. Մ. Դեյտել, Պ. Ջ. Դեյտելի C++ ի գրքում:

[*e}|{uka*]

Ռեկուրսիվ ֆունկցիաների մանրամասն նկարագրությունը կարդացեք Հ. Մ. Դեյտել, Պ. Ջ. Դեյտելի C++ ի գրքում:

աաաա~~~

[linus]

Ահա պատրաստի սուրսը C++ լեզվով: Եթե որևէ անհասկանալի պահ կա, ասեք, կբացատրեմ:

#include <iostream>
using std::cout;
using std::cin;
using std::endl;
unsigned long fibonacci( unsigned long )

int main()
{
unsigned long result, number;
cout << "Mutkagrek drakan amboxj tiv: ";
cin >> number;
result = fibonacci( number );
cout << "Fibonachii hajordakanutyan (" << number << ") andamy havasar e " << result << endl;
}
//Ստորև նկարագրված է Ֆիբոնաչիի ռեկուրսիվ ֆունկցիան
{
if ( n == 0 )
return n;
else if( n == 1)
return n;
else
return fibonacci (n-1) + fibonacci (n-2);
}

Ռեկուրսիվ ֆունկցիաների մանրամասն նկարագրությունը կարդացեք Հ. Մ. Դեյտել, Պ. Ջ. Դեյտելի C++ ի գրքում:

ընդ որում ալգորիթմի բարդությունը լինի O(n) (ո կարգի)
եթե մի քիչ ուշադիր նայես ապա քո ալգորիթմի բարդություը n^2 կարգի է:

[shgalex]

ֆիբոնաչիի ֆունկցիան սահմանվում է հետևյալ կերպ


f(n) = 1 if n = 0;
f(n) = 1 if n = 1;
f(n) = f(n-1) + f(n-2);

հեշտ խնդիր

տալ անրադարձ(ռեկուրսիվ) առնչություն, որով կհաշվվի ֆիբ. թվերը բոլոր n - երի համար, ընդ որում ալգորիթմի բարդությունը լինի O(n) (ո կարգի)

Իսկ՞ այսպես կստացվի:

size_t  fibonacci(size_t n){
   size_t  fibi, fib1 = 1, fib2 = 1; int j = 2;
      if(n > 2){
               for(int i = 2; i < n; i++){
                       fibi = fib1 + fib2;
	  fib2 = fib1; fib1 = fibi;}
                         }
	else if(n == 1) return fib1;
	else if(n == 2) return fib2;
return fibi;}

Ներեղություն , ես անրադարձ բարը չեի նկատել:

[Cesare]

ընդ որում ալգորիթմի բարդությունը լինի O(n) (ո կարգի)
եթե մի քիչ ուշադիր նայես ապա քո ալգորիթմի բարդություը n^2 կարգի է:

Եթե լավ նայենք n^2 ել չի :
p(n)-ի կարգի ա, որտեղ p(0) = p(1) = 1 ;
p(n) = p(n-2) + p(n-1) + 1;

Ես կնախընտրեի սենց

#include <cstdio>

int fibonacci(int x)
{
int next = 1, curr = 1, prev = 1, i;
for(i = 1; i < x; i++)
{
next = curr + prev ;
prev = curr;
curr = next;
}
return next;
}

int main()
{
int n;
scanf("%d", &n);
printf("%d\n", fibonacci(n));
}

Ավելացվել է 6 րոպե անց
Մի հետաքրքիռ բան ել :
f(n) = (1/sqrt(5)) * (pow((1+sqrt(5))/2, n)-pow((1+sqrt(5))/2), n))

ներեղություն տպագրական սխալների համար: