Kā uzrakstīt Fibonači secību?

Sākotnēji es biju nepareizi kodējis programmu. Tā vietā, lai atgrieztu Fibonači skaitļus starp diapazonu (t. i., startNumber 1, endNumber 20 = tikai skaitļi starp 1 & amp; 20), es uzrakstīju, lai programma parādītu visus Fibonači skaitļus starp diapazonu (t. i., startNumber 1, endNumber 20 parāda = pirmos 20 Fibonači skaitļus). Es domāju, ka man ir drošs kods. Es arī nesaprotu, kāpēc tas notiek.

startNumber = int(raw_input("Enter the start number here "))
endNumber = int(raw_input("Enter the end number here "))

def fib(n):
    if n < 2:
        return n
    return fib(n-2) + fib(n-1)

print map(fib, range(startNumber, endNumber))

Kāds norādīja manā II daļā (kas tika slēgta, jo dublējās - https://stackoverflow.com/questions/504193/how-to-write-the-fibonacci-sequence-in-python-part-ii), ka man ir nepieciešams nodot startNumber un endNumber caur ģeneratoru, izmantojot while cilpu. Vai kāds var man norādīt, kā to izdarīt? Jebkura palīdzība ir apsveicama.

Es esmu programmētājs, kas mācās programmēt, un es esmu nonācis nelielā apjukumā. Man lūdza uzrakstīt programmu, kas aprēķinātu un parādītu Fibonači secību pēc lietotāja ievadīta sākuma skaitļa un beigu skaitļa (t.i., startNumber = 20 endNumber = 100, un tā parādītu tikai skaitļus starp šiem diapazoniem). Viltība ir izmantot to iekļaujoši (ko es nezinu, kā to izdarīt Python? - Es pieņemu, ka tas nozīmē izmantot iekļaujošu diapazonu?).

Līdz šim man nav nekādas faktiskas kodēšanas, bet gan:

  • Uzrakstīt Fib secības formulu bezgalīgajam
  • Rādīt no sākumcipara līdz galīgajam ciparam tikai no Fib secības.

Man nav ne jausmas, ar ko sākt, un es lūdzu idejas vai ieskatu, kā to uzrakstīt. Esmu arī mēģinājis uzrakstīt Fib secības forumla, bet arī tajā es apmaldos.

martineau
Rediģēts jautājums 20priekšpusdienari5t janvārī 2018 в 1:42
Programmēšana
python sequences fibonacci
30priekšpusdienari4t janvārī 2009 в 5:49
1 skats
Risinājums

Daudz informācijas par Fibonači secību ir atrodams [wikipedia][1] un [wolfram][2]. Daudz vairāk, nekā jums varētu būt nepieciešams. Jebkurā gadījumā ir labi iemācīties izmantot šos resursus, lai atrastu (ja iespējams, ātri) to, kas jums nepieciešams.

Uzrakstiet Fib secības formulu uz bezgalīgo

Matemātikā tā tiek dota rekursīvā formā:

![fibonacci no wikipedia][3]

Programmēšanā bezgalīgs nepastāv. Jūs varat izmantot rekursīvo formu, tulkojot matemātisko formu tieši savā valodā, piemēram, Python valodā tā kļūst:

def F(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return F(n-1)+F(n-2)

Izmēģiniet to savā iecienītākajā valodā un pārliecinieties, ka, pieaugot n, šī forma prasa daudz laika. Patiesībā tas ir O(2n) laiks.

Ieskatieties manis norādītajās vietnēs, un jūs to redzēsiet (vietnē wolfram):

[![Fibonači vienādojums][4]][4]][4]

Šo formulu ir diezgan viegli īstenot un ļoti, ļoti ātri aprēķināt Python:

from math import sqrt
def F(n):
    return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

Cits veids, kā to izdarīt, ir pēc definīcijas (no wikipedia):

Pirmais kārtas skaitlis ir 0, otrais skaitlis ir 1, un katrs nākamais skaitlis ir vienāds ar summu iepriekšējo divu skaitļu skaitļu skaitlis ir vienāds ar secības skaitļiem, tādējādi iegūstot secību 0, 1, 1, 1, 2, 3, 5, 8 utt.

Ja jūsu valoda atbalsta iteratorus, jūs varat darīt kaut ko līdzīgu:

def F():
    a,b = 0,1
    while True:
        yield a
        a, b = b, a + b

Rādīt sākumciparu līdz galīgajam ciparam tikai no Fib sekvences.

Kad zināt, kā ģenerēt Fibonači skaitļus, jums vienkārši ir jāapgriež skaitļi un jāpārbauda, vai tie atbilst dotajiem nosacījumiem.

Pieņemsim, ka tagad esat uzrakstījis f(n), kas atgriež Fibonači secības n-to locekli (piemēram, ar sqrt(5) ).

Lielākajā daļā valodu var izdarīt kaut ko līdzīgu:


def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur
Tony Edgecombe
Rediģēta atbilde 8pēcpusdienari4t septembrī 2017 в 12:47
Komentāri (14)

Fibonači secības ideja ir parādīta nākamajā Python kodā:

def fib(n):
   if n == 1:
      return 1
   elif n == 0:   
      return 0            
   else:                      
      return fib(n-1) + fib(n-2)

Tas nozīmē, ka fib ir funkcija, kas var veikt vienu no trim darbībām. Tā definē, ka fib(1) == 1, fib(0) == 0 un fib(n) ir:

fib(n-1) + fib(n-2)

kur n ir patvaļīgs vesels skaitlis. Tas nozīmē, ka, piemēram, fib(2) izvēršas līdz šādai aritmētikai:

fib(2) = fib(1) + fib(0)
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(2) = 1 + 0
fib(2) = 1

Mēs varam aprēķināt fib(3) tādā pašā veidā, izmantojot turpmāk parādīto aritmētisko formulu:

fib(3) = fib(2) + fib(1)
fib(2) = fib(1) + fib(0)
fib(2) = 1
fib(1) = 1
fib(0) = 0
# Therefore by substitution:
fib(3) = 1 + 1 + 0

Svarīgi ir saprast, ka fib(3) nevar aprēķināt, neaprēķinot fib(2), ko aprēķina, zinot fib(1) un fib(0) definīcijas. Tas, ka funkcija izsauc pati sevi, kā to dara fibonacci funkcija, tiek saukts par rekursiju, un tas ir svarīgs temats programmēšanā.

Tas izklausās pēc mājasdarba uzdevuma, tāpēc es nedarīšu sākuma un beigu daļu. Tomēr Python ir brīnišķīgi izteiksmīga valoda, tāpēc tam vajadzētu būt jēgai, ja jūs saprotat matemātiku, un, cerams, tas jums iemācīs par rekursiju. Veiksmi!

Rediģēšana: Viena no iespējamām kritiskām piezīmēm manam kodam ir tā, ka tajā nav izmantota ļoti parocīgā Python funkcija yield, kas padara fib(n) funkciju daudz īsāku. Tomēr mans piemērs ir mazliet vispārīgāks, jo ne daudzās valodās, izņemot Python, ir yield.

Komentāri (5)
 
def fib():
    a,b = 1,1
    num=eval(input("Please input what Fib number you want to be calculated: "))
    num_int=int(num-2)
    for i in range (num_int):
        a,b=b,a+b
    print(b)
sloth
Rediģēta atbilde 6pēcpusdienari0t augustā 2012 в 2:19
Komentāri (1)