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

[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վ-ու :

[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;}

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