Ֆիբոնաչիի թվերը, հավանաբար, ամենապարզ հաջորդականությունն են, և մեզանից գրեթե յուրաքանչյուրը գիտի դա.
F0=0, F1=1, Fn=Fn-2+ Fn-1, n >=2
Fibonacci n-րդ թիվը գտնելը բավականին պարզ է.
function fibonacchi(n){ if ( n == 0 ) return 0; if (n == 1) return 1; return fibonacchi(n-2) + fibonacchi(n-1); } console.log(fibonacchi(10));
Պարզ ռեկուրսիվ ֆունկցիա, որն իրեն կանչում է այնքան ժամանակ, մինչև հասնի այն պահին, երբ n = 0 կամ n = 1: Թվում է, թե ոչ մի բարդ բան չկա:
Ֆիբոնաչիի թվերը շատ հաճախ օգտագործվում են որպես բացատրություն այնպիսի մոտեցման համար, ինչպիսին է հիշողությունը: Memoization-ը մոտեցում է, որը թույլ է տալիս պահպանել միջանկյալ լուծումների արդյունքները, որպեսզի հաջորդ հաշվարկներում նույնը չկրկնենք։
Սկզբունքը աներևակայելի պարզ է, այս դեպքում մենք հատկացնում ենք զանգված՝ բոլոր արժեքները, որոնցից == 0, և գրի ենք առնում ստացված բոլոր հաշվարկները, հետևաբար ունենք հետևյալ կոդը.
var results = [0,1]; function fibonacchi(n){ if ( n == 0 ) return results[0]; if (n == 1) return results[1]; if (!results[n]){ results[n] = fibonacchi(n-2) + fibonacchi(n-1); } return results[n]; }
Իրականում, ինչպես տեսնում ենք այս լուծման մեջ, մենք հատկացնում ենք զանգված, որն իր մեջ պահում է բոլոր միջանկյալ արդյունքները և չի փորձում նորից գտնել բոլոր թվերը։ Այսպիսով, առաջին գործարկումը կաշխատի ճիշտ այնպես, ինչպես ալգորիթմի նախորդ տարբերակը, ԲԱՅՑ երկրորդ գործարկումը չի փնտրի արդեն գտնված արժեքները:
Եթե մեզ անհրաժեշտ է արժեքը գտնել միայն մեկ անգամ, և մենք սահմանափակված ենք հիշողությամբ, ապա խորհուրդ եմ տալիս օգտագործել ոչ ռեկուրսիվ ֆունկցիա, քանի որ այս դեպքում այն աշխատում է O (n) ժամանակում և միևնույն ժամանակ օգտագործելով O ( 1) հիշողություն. Ռեկուրսիվ ալգորիթմներն իրենց պահում են էքսպոնենցիալ ժամանակում:
Գծային լուծումը հանգում է նրան, որ մեզ անհրաժեշտ են միայն Ֆիբոնաչիի թվերի վերջին երկու արժեքները.
function fib_n(n) { if (n <= 2) return 1; var x = 1; var y = 1; var ans = 0; for (var i = 2; i < n; i++) { ans = x + y; x = y; y = ans; } return ans; }
Ինչպես տեսնում եք, նման ալգորիթմն աշխատում է O(n) ժամանակով և օգտագործում է միայն O(1) հիշողություն:
Բայց, ինչպես պարզվեց, Ֆիբոնաչիի թվերը կարելի է գտնել O (logn) ժամանակում՝ մատրիցները հասցնելով հզորության:
Ինքնություն կա.
Փաստորեն, դուք կարող եք շատ ավելին իմանալ Ֆիբոնաչիի թվերի մասին պարզապես Վիքիում :
Նշելով P թվի մատրիցը՝ ստանում ենք.
Հետևաբար, եզրակացությունն այն է, որ n-րդ Ֆիբոնաչիի թվի արժեքը պարզելու համար անհրաժեշտ է P մատրիցը հասցնել հզորության.
function fib_matrix(n) { var a = 1, ta, b = 1, tb, c = 1, rc = 0, tc, d = 0, rd = 1; while (n) { //power is odd if (n & 1) { tc = rc; rc = rc*a + rd*c; rd = tc*b + rd*d; } ta = a; tb = b; tc = c; a = a*a + b*c; b = ta*b + b*d; c = c*ta + d*c; d = tc*tb+ d*d; n >>= 1; } //return vector value return rc; }
Այսպիսով, բազմապատկելով մատրիցն ինքն իրենով կամ արդյունքների վեկտորով, կարող եք գտնել նաև Ֆիբոնաչիի համարի պահանջվող արժեքը։
Գոյություն ունի նաև Բինեի բանաձևով թվի որոշման մեթոդ, սակայն դրա օգտագործումը մեծ խնամք է պահանջում կոտորակների հետ աշխատելիս։
function bine(n){ var index = Math.pow(5, 0.5); var left = (1 + index) / 2; var right = (1 — index) / 2; return Math.round((Math.pow(left, n) — Math.pow(right, n)) / index); }
Փոքր թեստի արդյունքներ.
Սկզբունքորեն, այս թեստը մեզ ոչ մի նոր բան ցույց չի տալիս, բացի այն, որ երկրաչափական աճող ալգորիթմները լավագույնը չեն 🙂
Ինչպես միշտ. օրինակների սկզբնական կոդը կարող եք գտնել այստեղ :
Օրինակ 4.4. Ֆիբոնաչիի թվերը ( F i ) որոշվում են F 0 = F 1 = 1 բանաձեւերով; F i \u003d F i -1 + F i -2 i \u003d 2, 3, … համար (յուրաքանչյուր հաջորդ թիվը հավասար է երկու նախորդների գումարին): Հաշվե՛ք բոլոր Ֆիբոնաչիի թվերի գումարը, որոնք չեն գերազանցում տրված M բնական թիվը։Փորձարկում
Թեստի համարը | Տվյալներ | Արդյունք |
1 | M=10 | S=1+1+2+3+5+8=20 |
2 | M=1 | S=1+1=2 |
ՑույցԴպրոց AY
Fibonacci alg ( arg ամբողջ թիվ M, res ամբողջ թիվ S) տրված | M>0
սկսել ամբողջ F0, F1, F2 F0:=1; F1:=1; F2:=2 S:=4 | 4 – Ֆիբոնաչիի առաջին երեք թվերի գումարը nc, մինչդեռ F2<=M F0:=F1; F1:=F2; F2:=F0+F1 | վերանշանակումների շարք S:=S+F2; kts S:=S–F2 | S-ից հանվում է F2-ի վերջին արժեքը, որը գերազանցում է M con
Ալգորիթմի կատարում F0F1F2ՍF2<M112351235823581344+3=77+5=1212+8=2020+13=33++++— (cc)33-13=20 | բլոկ սխեմա |
TurboPascal
SummaFib ծրագիր; Օգտագործում է crt; Var M, {տրված թիվ} F0, F1, F2, {երեք անընդմեջ Ֆիբոնաչիի թվեր} S. Ամբողջ թիվ; {Ֆիբոնաչիի թվերի գումարը}
ՍԿՍԵԼ ClrScr ; Write(' Մուտքագրեք բնական M: '); ReadLn(M);
F0:=1; F1:=1; F2:=2; S:=4; {4-ը Ֆիբոնաչիի առաջին երեք թվերի գումարն է} Write(' Fibonacci թվեր, որոնք չեն գերազանցում ', M, ' :', F0:4, F1:4); Մինչդեռ F2<=M անել սկսել F0:=F1; F1:=F2; Գրել (F1 : 4); F2:=F0+F1; S:=S+F2; վերջ; S:=S-F2; {վերջին թվի գումարից հանում, որը գերազանցում է M}
WriteLn; WriteLn; WriteLn(' Պատասխան . Այս թվերի գումարը ', S է); Կարդացեք ՎԵՐՋ.
Pascal ծրագրի արդյունքները
Մուտքագրեք բնական M> 0:10 <Մուտքագրեք> Ֆիբոնաչիի թվերը, որոնք չեն գերազանցում 10-ը: 1 1 2 3 5 8 Պատասխան. Այս թվերի գումարը 20 է: |
QBasic
CLS INPUT « Մուտքագրեք բնական M: », M
F0 = 1 : F1 = 1 : F2 = 2 S = 4 '4 Ֆիբոնաչիի առաջին երեք թվերի գումարն է ՏՊԱԳՐԵԼ « Ֆիբոնաչիի թվերը չգերազանցող »; Մ; ":"; F0; F1 ; Մինչդեռ F2 <= Մ F0=F1 : F1=F2 : PRINT F1; F2=F0+F1՝ S=S+F2 WEND S=S–F2 'հանում վերջին թվի գումարից, որը մեծ է M-ից
PRINT : PRINT : PRINT "Պատասխան . Այս թվերի գումարը "; S& END
167
Ավելին Դիմկա Մալեևից
Ծրագրային ինժեներ @ Denizen14 հունիսի, 2015թԱլգորիթմներ. Ծառի անցումՎաղուց չէի գրում, քանի որ անընդհատ չէր։ Խոսեցինք ծառերի մասին, հիմա անդրադառնանք ծառերի անցմանը: Ծառերի անցումները անհրաժեշտ են ծառի մեջ անհրաժեշտ տարրը օպտիմալ կերպով
1. Ցուցադրել Ֆիբոնաչիի շարքի առաջին n թվերը: Անցումային աղյուսակ 2. Ցուցադրել Ֆիբոնաչիի շարքի n-րդ տարրը: Անցումային աղյուսակ 3. Ցուցադրել Ֆիբոնաչիի շարքի n1-րդ և n2-րդ տարրերը և դրանց գումարը: Անցումային աղյուսակ 4. Գտի՛ր Ֆիբոնաչիի քսաներորդ թիվը: Անցումային աղյուսակ 5. Գտե՛ք երկու անգամ Ֆիբոնաչիի քսաներորդ թիվը: Անցումային աղյուսակ 6. [5,10] միջակայքում համակարգիչը գեներացնում է 10 պատահական թվեր։ Ցուցադրել Ֆիբոնաչիի թվերը էկրանին: Գտե՛ք նրանց միջին թվաբանականը: Անցումային աղյուսակ 7. x թիվը մուտքագրվում է ստեղնաշարից: Ստուգեք՝ արդյոք դա Ֆիբոնաչիի թիվ է։ Թեստավորման ծրագիր. Անցումային աղյուսակ 8. Գտե՛ք Ֆիբոնաչիի թվերի թիվը [2, 6] միջակայքում: Անցումային աղյուսակ 9. Գտե՛ք Ֆիբոնաչիի թվերի թիվը [a, b] միջակայքում: Անցումային աղյուսակ |
1. Ցուցադրել Ֆիբոնաչիի շարքի առաջին n թվերը: Լուծում. Ֆիբոնաչիի թվերը գտնելու առաջին ալգորիթմը: Պատասխան՝ n=6 1 1 2 3 5 8 ծրագիր fib_01; օգտագործում է crt; var i, ch, ch1, ch2, n :integer;{i — Ֆիբոնաչիի թվերի հաշվիչ; n-ը Ֆիբոնաչիի թվերի թիվն է. ch — Ֆիբոնաչիի համարը; ch1, ch2 — Ֆիբոնաչի թվերի որոնման ալգորիթմի օժանդակ փոփոխականներ}սկսել clrscr; գրել (‘n=’); readln(n); ch:=0; {Ֆիբոնաչիի թվերը գտնելու ալգորիթմ} ch1:=1; համար i:=1-ից n անել վերջ.Լավագույն հոսքային աղյուսակ |
2. Ցուցադրել Ֆիբոնաչիի շարքի n-րդ տարրը: Լուծում. Ֆիբոնաչիի թվերը գտնելու առաջին ալգորիթմը: Պատասխան՝ n=10 ch=55ծրագիր fib_02; օգտագործում է crt; var ch, ch1, n, i, ch2՝ ամբողջ թիվ;{i — Ֆիբոնաչիի թվերի հաշվիչ; n-ը Ֆիբոնաչիի թվերի թիվն է. ch — Ֆիբոնաչիի համարը; ch1, ch2 — Ֆիբոնաչի թվերի որոնման ալգորիթմի օժանդակ փոփոխականներ}սկսել clrscr; գրել (‘n=’); readln(n);ch:=0; ch1:=1; i:=1-ից մինչև n անել գրել (‘ch=’:5,ch) {միայն վերջին հայտնաբերված Ֆիբոնաչի թիվը պետք է ցուցադրվի, ուստի ելքային հայտարարությունը գտնվում է օղակից դուրս} վերջում:Լավագույն հոսքային աղյուսակ |
3. Ցուցադրել Ֆիբոնաչիի շարքի n1-րդ և n2-րդ տարրերը և դրանց գումարը Լուծում. Ֆիբոնաչիի թվերը գտնելու առաջին ալգորիթմը:Պատասխան՝ n1=5 n2=10 5 55 S=60կամՊատասխան՝ n1=10 n2=5 5 55 S=60 Ծրագիր fib_03; Օգտագործում է CRT; var n1, n2, ch, ch1,ch2, i, max, s:integer;{i — Ֆիբոնաչիի թվերի հաշվիչ; n1, n2 — Ֆիբոնաչիի թվեր; ch — Ֆիբոնաչիի համարը; ch1, ch2 — Ֆիբոնաչի թվերի որոնման ալգորիթմի օժանդակ փոփոխականներ; max — Ֆիբոնաչիի թվի ամենամեծ թիվը; S — թվերի գումարը}սկսել clrscr; s:=0; գրել (‘n1 =’); readln(n1); գրել (‘n2 =’); readln(n2); ch:=0; ch1:=1; եթե n2 > n1 ապա max :=n2 else max :=n1; {այս ստուգումը կատարվում է այն դեպքում, երբ սկզբում մուտքագրվում է ավելի մեծ թիվ, ապա ավելի ցածր} i:=1-ից մինչև max do գրել; գրել(‘S=’:5,s); վերջ.Լավագույն հոսքային աղյուսակ |
4. Գտի՛ր Ֆիբոնաչիի քսաներորդ թիվը: Լուծում. Ֆիբոնաչիի թվերը գտնելու առաջին ալգորիթմը: Պատասխան՝ ch=6765 ծրագիր fib_04; օգտագործում է crt; var ch, ch1, n, i, ch2՝ ամբողջ թիվ;{i — Ֆիբոնաչիի թվերի հաշվիչ; ch — Ֆիբոնաչիի համարը; ch1, ch2 — Ֆիբոնաչի թվերի որոնման ալգորիթմի օժանդակ փոփոխականներ}սկսել clrscr;ch:=0; ch1:=1; i:=1-ից 20 անել գրել (‘ch=’:5,ch) {միայն վերջին հայտնաբերված Ֆիբոնաչի թիվը պետք է ցուցադրվի, ուստի ելքային հայտարարությունը գտնվում է օղակից դուրս} վերջում: Լավագույն հոսքային աղյուսակ |
5. Գտե՛ք երկու անգամ Ֆիբոնաչիի քսաներորդ թիվը: Լուծում. Ֆիբոնաչիի թվերը գտնելու առաջին ալգորիթմը: Պատասխան՝ ch*2=13530 ծրագիր fib_05; օգտագործում է crt; var ch, ch1, n, i, ch2՝ ամբողջ թիվ;{i — Ֆիբոնաչիի թվերի հաշվիչ; ch — Ֆիբոնաչիի համարը; ch1, ch2 — Ֆիբոնաչի թվերի որոնման ալգորիթմի օժանդակ փոփոխականներ}սկսել clrscr;ch:=0; ch1:=1; i:=1-ից 20 անել գրել (‘ch*2=’:5, ch*2) {միայն վերջին հայտնաբերված Ֆիբոնաչիի թիվը պետք է ցուցադրվի, ուստի ելքային հայտարարությունը գտնվում է օղակից դուրս} վերջում:Լավագույն հոսքային աղյուսակ |
6. [5,10] միջակայքում համակարգիչը գեներացնում է 10 պատահական թվեր։ Ցուցադրել Ֆիբոնաչիի թվերը էկրանին: Գտե՛ք նրանց միջին թվաբանականը:Լուծում. Ֆիբոնաչիի թվերը գտնելու առաջին ալգորիթմը (ավելի ռացիոնալ կլինի օգտագործել Ֆիբոնաչիի թվերը գտնելու երկրորդ ալգորիթմը) : Պատասխանը կարող է լինել. Ֆիբոնաչիի թվերի թիվը 0 է կամ ch=8 ch=8 ch=8 Sred =8…ծրագիր fib_06; usecrt; varx: բայթ; {պատահական համար} ch, ch1, ch2: բայթ; {Ստուգելով Ֆիբոնաչիի շարքը} S, kch՝ ամբողջ թիվ; {Ֆիբոնաչիի թվերի գումարը և թիվը} Sred՝ իրական; {միջին թվաբանական} ii, i: բայթ; {ii — հաշվիչը պատահական թվերի համար, i — հաշվիչը Ֆիբոնաչիի շարքի համար} սկսվում է clrscr; պատահականացնել; կճ :=0; ii-ի համար :=1-ից 10 do {ընդհանուր 10 համարները կստուգվեն}սկիզբ x := պատահական (10-5+1)+5; {պատահական թիվ} ch :=0; {Ֆիբոնաչիի թվերի ստուգման ալգորիթմի սկիզբ} ch1 :=1; համար i :=1-ից 6 անել {որովհետև [5, 10] միջակայքում կա ընդամենը 6 Ֆիբոնաչիի թիվ՝ 1 1 2 3 5 8} վերջ;գրել; {ստուգեք բաժանումը 0:}- ով, եթե kch< >0, ապա սկսեք Sred:=s/kch ; write (‘Sred=’:5, sred) end else writeln(‘Ֆիբոնաչիի թվերի թիվը 0 է։’); վերջ.Լավագույն հոսքային աղյուսակ |
7. x թիվը մուտքագրվում է ստեղնաշարից: Ստուգեք՝ արդյոք դա Ֆիբոնաչիի թիվ է։ Թեստավորման ծրագիր.Լուծում. Ֆիբոնաչիի թվերը գտնելու երկրորդ ալգորիթմը: Պատասխան՝ x=5 1. ch1=1 ch2=0 ch=1 2. ch1=0 ch2=1 ch=1 3. ch1=1 ch2=1 ch=2 4. ch1=1 ch2=2 ch=3 5. ch1=2 ch2=3 ch=5 Ցիկլը ավարտված է x — Ֆիբոնաչիի թիվx=6 1. ch1=1 ch2=0 ch=1 2. ch1=0 ch2=1 ch=1 3. ch1=1 ch2=1 ch=2 4. ch1=1 ch2=2 ch=3 5. ch1. =2 ch2=3 ch=5 6. ch1=3 ch2=5 ch=8 Ավարտված ցիկլը x Ֆիբոնաչիի թիվ չէ ծրագիր fib_07; օգտագործում է crt; var i, ch, ch1, ch2, x, n: integer;{x — տրված համարը; i — ցիկլի սերիական համարը; ch — Ֆիբոնաչիի համարը; ch1, ch2 — Ֆիբոնաչի թվերի որոնման ալգորիթմի օժանդակ փոփոխականներ} սկսել clrscr; գրել (‘x=’); readln (x); ch1:=0; ch2:=1; ch:=1; i:=1; կրկնել գրել(i:5,’. ‘); մինչև (x<չ) ; writeln(‘Օղակը ավարտվեց’); եթե x = ch -1, ապա writeln( ‘x-ը Ֆիբոնաչիի թիվ է’) else writeln( ‘x-ը Ֆիբոնաչիի թիվ չէ’) {այստեղ x=ch-1 քանի որ հանգույցի վերջին գործողությունը թիվը 1} վերջով ավելացնելն է:Լավագույն հոսքային աղյուսակ |
8. Գտե՛ք Ֆիբոնաչիի թվերի թիվը [2, 6] միջակայքում: Թեստավորման ծրագիր.Լուծում. Ֆիբոնաչիի թվերը գտնելու երկրորդ ալգորիթմը: Պատասխան՝ x=2 Ֆիբոնաչիի թիվ= 2 k=1x=3 Ֆիբոնաչիի թիվ= 3 k=2x=4 x-ը Ֆիբոնաչիի թիվ չէx=5 Ֆիբոնաչիի թիվ= 5 k=3x=6 x-ը Ֆիբոնաչիի թիվ չէk=3 ծրագիր fib_08; օգտագործում է crt; var ch, ch1, ch2, x, n, k՝ ամբողջ թիվ;{x — թվեր տրված միջակայքից; k — Ֆիբոնաչիի թվերի թիվը; ch — Ֆիբոնաչիի համարը; ch1, ch2 — Ֆիբոնաչի թվերի որոնման ալգորիթմի օժանդակ փոփոխականներ} սկսել clrscr; x:=2; {առաջին թիվը տրված միջակայքում} k:=0; {նախ թվերի թիվը 0} է , մինչդեռ x<=6 do {6-ը վերջին թիվն է տվյալ միջակայքում}սկսել գրելն(‘x=’,x); ch1:=0; ch2:=1; ch:=1; {ալգորիթմ ստուգելու համար, արդյոք X-ը Ֆիբոնաչիի թիվ է} կրկնել մինչև (x<չ) ; {մինչև X-ը մեծ լինի հաջորդ Ֆիբոնաչիի թվից} , եթե x=ch-1, ապա {եթե X-ը հավասար է հաջորդ Ֆիբոնաչիի թվին, ապա թիվը ավելանում է 1-ով: inc(x) {պատրաստել հաջորդ X-ը փորձարկման համար} վերջ ; writeln(‘k=’,k) վերջ:Լավագույն հոսքային աղյուսակ |
9. Գտե՛ք Ֆիբոնաչիի թվերի թիվը [a, b] միջակայքում: Լուծում. Ֆիբոնաչիի թվերը գտնելու երկրորդ ալգորիթմը: Պատասխան ՝ տրված միջակայքում առաջին թիվը=10 վերջին թիվը տրված միջակայքում=1000 Ֆիբոնաչիի թիվ= 13 Ֆիբոնաչիի թիվ= 21 Ֆիբոնաչիի թիվ= 34 Ֆիբոնաչիի թիվ= 55 Ֆիբոնաչիի թիվ= 89 Ֆիբոնաչիի համար= 144 Ֆիբոնաչիի թիվ= 233 Ֆիբոնաչիի թիվ= 377 Ֆիբոնաչիի թիվը = 610 Ֆիբոնաչիի թիվ= 987 k=10 ծրագիր fib_09; օգտագործում է crt; var ch, ch1, ch2, a, b, x, k :integer;{x — թվեր տրված միջակայքից; a, b — միջակայքի սահմանները; k — Ֆիբոնաչիի թվերի թիվը; ch — Ֆիբոնաչիի համարը; ch1, ch2 — Ֆիբոնաչի թվերի որոնման ալգորիթմի օժանդակ փոփոխականներ}սկսել clrscr; write(‘ first number in the range =’ ); readln(a); write(‘վերջին թիվը տրված միջակայքում=’ ); readln(b) ; x:=a; {ստուգվող առաջին թիվը հավասար է տրված միջակայքի առաջին թվին} k:=0; իսկ x<=b do {մինչ X-ը տիրույթից դուրս է} սկսվում էch1:=0; ch2:=1; ch:=1; {ալգորիթմ ստուգելու համար, արդյոք X-ը Ֆիբոնաչիի թիվ է} կրկնել inc (ch); մինչև (x<չ) ; {մինչև X-ը մեծ լինի հաջորդ Ֆիբոնաչիի համարից}եթե x=ch-1 ապասկսել գրել (‘Fibonacci number= ‘,ch-1); inc(k) end;inc(x) {ստուգեք հաջորդ X} վերջը; writeln(‘k=’,k) վերջ: |