staging.inyokaproject.org

@Stefan Schmitz: Alles in Funktionen zu verpacken ist sauberer. Dann kommt man gar nicht erst in Versuchung bei mehreren Funktionen auf "globale" Variablen zugreifen zu wollen.

C

#include <stdio.h>
#include <stdlib.h>
long fibo(long n) {
   if(n)
      return (n <= 2) ? n : fibo(n-2) + fibo(n-1);
}
int main(void) {
   long f;
   long i=0;
   printf("Wie viele Fibonacci-Zahlen wollen Sie ausgeben:");
   scanf("%ld",&f);
   while(i++ < f)
      printf("F(%ld) = %ld\n", i, fibo(i));
   return EXIT_SUCCESS;
}

C (gekürzt)

#include <stdio.h>
#include <stdlib.h>
long fibo(long n){if(n)return(n<=2)?n:fibo(n-2)+fibo(n-1);}int main(void){long f;long i=0;scanf("%ld",&f);while(i++<f)printf("F(%ld)=%ld\n",i,fibo(i));return EXIT_SUCCESS;}

Die Näherung zum goldenen Schnitt fehlt. Ansonsten ein stinknormaler Rekursiver Ansatz, für große Fibonaccizahlen kaum zu gebrauchen. Konsequenterweise könntest du die Zählervariable i dann auch in nen Integer stecken, bis das Ding den Integerbereich verlässt habe ich bestimmt nen Bart. Was an der gekürzten Fassung gekürzt sein soll außer sämtlichen das Lesen erleichternden Whitespaces weiss ich auch nicht.

EDIT: Zusätzlich stimmt dein Code nicht Fibo(2) ergibt bei dir 2 sollte aber 1 ergeben, damit stimmen dann natürlich auch alle Folgewerte nicht... EDITEDIT: Was soll die if(n) Abfrage, nach meinen (wenigen) Kenntnissen von C führt die nur zu Nonsens.

Scheme ☺

(define iter-fib
  (lambda (a b n)
    (if (< b n)
      (begin
        (write b)
        (newline)
        (iter-fib b (+ a b) n))
      0)))

(define fib
  (lambda (n)
    (iter-fib 0 1 n)))

Das stimmt doch oder? Ich weiß nicht was ich falsch gemacht habe...

# gcc -o fibo fibo.c
# ./fibo
Wie viele Fibonacci-Zahlen wollen Sie ausgeben:100 
F(1)=1                                             
F(2)=2                                             
F(3)=3                                             
F(4)=5                                             
F(5)=8                                             
F(6)=13                                            
F(7)=21
F(8)=34
F(9)=55
F(10)=89
F(11)=144
F(12)=233
F(13)=377
F(14)=610
F(15)=987
F(16)=1597
F(17)=2584
F(18)=4181
F(19)=6765
F(20)=10946
F(21)=17711
F(22)=28657
F(23)=46368
F(24)=75025
F(25)=121393
F(26)=196418
F(27)=317811
F(28)=514229
F(29)=832040
F(30)=1346269
F(31)=2178309
F(32)=3524578
F(33)=5702887
F(34)=9227465
F(35)=14930352
F(36)=24157817
F(37)=39088169
F(38)=63245986
F(39)=102334155
F(40)=165580141

Stimmt, wenn man bei 1 statt 0 anfängt.

peter02 schrieb:

Das stimmt doch oder? Ich weiß nicht was ich falsch gemacht habe...

Wie gesagt die Aufgabenstellung ist noch etwas mehr (nicht viel mehr aber + goldener Schnitt, siehe das Ursprungsposting

# gcc -o fibo fibo.c
# ./fibo
Wie viele Fibonacci-Zahlen wollen Sie ausgeben:100 
F(1)=1                                             
F(2)=2                                             
[...]

Und das ist so nicht richtig, die (rekursive) Definition der Fibonacci-Folge ist

f(0) = 0, f(1) = 1, ..., f(n) = f(n-1)+ f(n-2), also f(2) = f(1) + f(0) = 1.

Und damit sind dann auch alle weiteren Berechnungen verschoben, und das sehr gewaltig, denn (wenn die if Anfrage nicht irgendeine regulierende Funktion hat, denn die Blicke ich noch immer nicht), dann rechnet er zB. für f(4) schon

f(4) = f(3) + f(2) = f(2)+f(1) + f(2) = 2 + 1 + 2 = 5,

richtig wäre 3 (f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 2, f(4) = 3 usw. und mit jeder Zahl kommen Rekursionszweige die in f(2) enden dazu, der Fehler explodiert also ein wenig 😉.

@DasIch, leider stimmt es auch dann nicht, die Folge fängt ja mit 0,1,1,2 an, damit die 1,2 als Vorgänger stimmen müsste man schon die ersten 2 Fibonaccis verwerfen, ist eben ein vollkommen anderes Zahlentriplet, und eine Lösung die mehr oder minder zufällig die Fibonaccizahlen falsch Nummeriert und ohne Folgenstart ausgibt, würde ich so oder so nicht als Lösung werten 😉.

EDIT: Hab mir mal die Mühe gemacht die enumeration der Wahrheitswerte unter c nochmal kurz rauszusuchen, alle Zahlen ungleich 0 sind true?. Dann erstaunt mich das Verhalten deines Programms ungemein, Meiner Schätzung nach müsste deine Funktion bei 0 irgendwas völlig zufälliges ausgeben, oder eventuell sogar void, insofern würde ich sowas erwarten wie F(0) = 4235232 oder F(0) = , aber keine komplette Tilgung des ersten Eintrags. Auf jeden Fall ist es stilistisch höchst bedenklich und so wie schon geschrieben auch auf garkeinen Fall korrekt. Kennt gcc den -Wall Flag? Würde mich wundern, wenn er dann das Kompilat noch erstellt.

EDITEDIT: Und nicht böse sein wegen der Klugscheisserei 😉, denke nur du kannst das auch richtig.

@Greebo: Mit dem if hast Du recht – da kann sonst etwas passieren. Mit den nötigen, und IMHO empfehlenswerten Flags spuckt der gcc auch eine entsprechende Warnung für die Funktion aus:

bj@s8n:~$ gcc -Wall -ansi -pedantic test.c
test.c: In function ‘fibo’:
test.c:7: warning: control reaches end of non-void function 

Der Code fängt aber bei i=1 an, denn zu dem Zeitpunkt, wo fibo() aufgerufen wird, ist i++ in der while-Bedingung schon ausgeführt worden. Das "Post" in dem Postinkrement-Operator bezieht sich auf die Auswertung der Bedingung – nicht auf den Schleifenkörper.

Ob die Fibonacci-Folge mit 0 1, 1 1, oder 1 2 beginnt ist übrigens Definitionssache und für die Aufgabenstellung auch nicht ganz so wichtig. Dem goldenen Schnitt nähert man sich so oder so.

Ich glaube eine Lösung in Factor gab's bisher noch nicht. ☺

#! /usr/bin/env factor
USING: io kernel locals math math.parser sequences ;
IN: golden-ratio

: (fib-start) ( -- n1 n2 )  0 1 ;
: (fib-next) ( n1 n2 -- n2 n1+n2 )  swap over + ;  inline
: (fib-end) ( n1 n2 -- )  2drop ;

:: fib-each-index ( n body: ( n1 n2 i -- ) -- )
    (fib-start)
    n [ [ (fib-next) ] dip 2over rot  body call ] each
    (fib-end) ;

: ask-upper-limit ( -- n )
    "How many iterations? " write flush  readln string>number ;

: print-fib-and-ratio ( n1 n2 i -- )
    "fib(" write  number>string write  ") = " write
    dup number>string write
    swap /f  "  " write number>string print ;

ask-upper-limit [ print-fib-and-ratio ] fib-each-index

Natürlich ist es Definitionssache, sie ist ja so definiert 😀. Nein ehrlich, mir wäre noch keine Publikation begegnet, die die Folge anders nummeriert, und das wäre auch relativ schlecht, denn dadurch würden Sachen wie die explizite Berechnung von Folgengliedern nicht mehr funktionieren (Bzw. die Formel sähe dann deutlich anders aus). Das es für die Aufgabenstellung nicht sonderlich relevant ist, stimmt schon. Aber wozu falsch machen, wenn man es auch korrekt lösen kann. Das hat dann noch den kleinen Nebeneffekt, dass man anhand von Kontrollwerten aus anderen Lösungen die eigene Korrektheit etwas absichern kann.

@Greebo: Dann ist Dir wohl noch nicht der Mathematikduden begegnet, der mit F_0=F_1=1 beginnt und dazu die entsprechende Aufgabe von Leonardo von Pisa a.k.a. Fibonacci aus dem Jahr 1202 zitiert.

Tja, da muss ich dann mal uns beide enttäuschen. Eventuell sind wir sogar alle falsch und peter02 richtig. Jedenfalls habe ich mir mal ne Primärquelle hier angesehen, und dort fängt die Folge eindeutlich mit F(1) = 1, F(2) = 2, F(3) = 3 an, F(0) bleibt undefiniert, was ich mal der Nullophobie im frühen Mittelalter zurechne ^^. Nichts desto trotz ist in allen mir zur Verfügung stehenden Quellen F(0) = 0 Standard, und ich meine mich auch zu erinnern, dass in einer Mathevorlesung mal eine Korrektur des Kanickelproblems durch Pisa selbst vorgenommen wurde, den entsprechenden Verweis muss ich aber wirklich suchen.

Ich spiele derzeit etwas mit Perl 6 herum. Habe derzeit mal zwei Lösungen in Perl 6 geschrieben. Für die Ausführung habe ich den aktuellen Rakudo Developer Compiler genommen, müsste allerdiengs auch mit dem letzten Release "Oslo" Funktionieren. Hier einmal eine Rekursive Lösung und einmal eine Itterative Lösung. beide nutzen einen Cache so das die Werte nicht mehrmals berechnet werden. Die Performance ist allerdiengs unter aller sau, aber um Performance geht es mir derzeit eh noch nicht.

Die erste Zeile "#!perl6" ist die Binarie die Rakudo beim Compilieren erzeugt.

Habe das ganze ausführlich Kommentiert, sollte eigentlich selbsterklärend sein.

Und hier die Rekursive Lösung:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

#!perl6

# Erstellt einen neuen Typ Int::Pos der von Int abgeleitet
# ist und nur Positive Ganzzahlen erlaubt
subset Int::Pos of Int where { $_ > 0 };

# sub für fibonnaci zahlen mit cache. Benötigt einen
# Parameter vom Typ Int::Pos
sub fib ( Int::Pos $n ) {
    # State Variable die als cache dient, ein hash
    state %cache;
    # bei 1 oder 2 wissen wir bereits das ergebnis
    return 1 if $n == 1|2;
    # zuerst cache abfragen und wenn zahl existiert dann diese
    # zurück geben
    return %cache{$n} if %cache.exists($n);
    # ansonsten wird die fibonacci zahl aus beiden vorgängern berechnet
    return %cache{$n} = fib($n-2) + fib($n-1);
}

# die ersten 50 fibonacci zahlen berechnen. 1..50 erzeugt die liste und mit
# jedem durchlauf wird ein wert aus der liste genommen und $num zugeteilt
for 1 .. 50 -> $num {
    printf "%4d: %.0lf\n", $num, fib($num);
}

Und hier einmal die Itterative Lösung:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#!perl6

# Neuen Typ der nur Positive Integer erlaubt
subset Int::Pos of Int where { $_ > 0 };

# itterative lösung für fibonnaci zahlen mit cache
sub fib ( Int::Pos $n ) {
    # Array das bisherige ergebnise cached
    state @array = ( 1, 1 );
    # Cache abfragen ob die angeforderte fib zahl schonmal berechnet wurde
    # und wenn ja dies zurück geben. 
    return @array[$n-1] if @array.exists($n-1); 
    # ansonsten von der letzten fib bis zur aktuellen anfrage hochrechnen
    for @array.elems .. $n-1 -> $idx {
        @array[$idx] = @array[$idx-2] + @array[$idx-1];
    }
    return @array[$n-1];
}

# Die ersten 50 Fibonacci Zahlen berechnen
for 1 .. 50 -> $num {
    printf "%4d: %.0lf\n", $num, fib($num);
}

Irgendwie finde ich das bisher niemand diese Aufgabe gelöst hat. Auf diese steile These komme ich, weil die Näherungen an den Goldenen Schnitt sich auch wenn man entsprechend grosse und präzise Ganzzahlen für die Fibonacci-Zahlen verwendet, sich der Goldene Schnitt bei Verwendung von double aber ab Schritt 40 gar nicht mehr ändert. Und die 40. oder 41. Fibonacci-Zahl kann man noch in 28 Bits unterbringen, also in einem 32 Bit-Ganzzahltypen.

Drauf gekommen bin ich, weil ich mal testen wollte wie weit man bei einem PET, VIC-20, oder C64 ohne ”Tricks” bei dieser Aufgabe kommt. Da ist bei der Präzision für den Schnitt schon beim 25. Schritt Schluss. Folgendes BASIC-Programm berechnet die Fibonacci-Zahlen und die Näherung des Goldenen Schnitts bis entweder die Fibonacci-Zahlen zu gross werden oder der Schnitt-Wert sich nicht mehr ändert:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

10 N=0:A=1:B=1:G0=-1
20 N=N+1:G1=B/A
30 PRINTN;A;G1
40 IFN=100THENEND
50 IFG0=G1THEN100
60 G0=G1
70 C=A+B:A=B:B=C
80 IFMID$(STR$(B),3,1)="."THEN110
90 GOTO20
100 PRINT"RATIO STABLE":END
110 PRINT"FIB TOO LARGE":END

N zählt die Schritte. A und B sind die zwei aktuellen Fibonacci-Zahlen, C wird temporär zum Berechnen der nächsten Zahl verwendet. G0 und G1 sind der vorherige und aktuelle Näherungswert für den Goldenen Schnitt. Wenn die sich nicht mehr unterscheiden, bricht das Programm ab mit RATIO STABLE als Ausgabe. Das passiert nach Schritt 25.

Ob die Fibonacci-Zahlen zu gross werden, wird überprüft in dem nach einem Dezimalpunkt in der Zeichenkettendarstellung geschaut wird. Zahlen die nicht mehr präzise repräsentiert werden können, werden als Kommazahl mit 10er-Exponent dargestellt. Die grösste Fibonacci-Zahl die das BASIC exakt kann ist 701408733. Danach kommt 1.13490317E+09.

Man braucht also nicht nur ”grosse” Ganzzahlen, sondern auch ”grosse” Dezimalbrüche. In Python gibt es dafür das decimal-Modul. Eine Präzision von 42 Dezimalstellen braucht man mindestens:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#!/usr/bin/env python3
from decimal import Decimal, getcontext
from itertools import islice, pairwise


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


def main():
    getcontext().prec = 42
    for n, (a, b) in enumerate(
        islice(pairwise(iter_fibonacci_numbers()), 100), 1
    ):
        print(f"{n:3}  {a:21} ", Decimal(b) / a)


if __name__ == "__main__":
    main()

Ausgabe:

  1                      1  1
  2                      1  2
  3                      2  1.5
  4                      3  1.66666666666666666666666666666666666666667
  5                      5  1.6
  6                      8  1.625
  7                     13  1.61538461538461538461538461538461538461538
  8                     21  1.61904761904761904761904761904761904761905
  9                     34  1.61764705882352941176470588235294117647059
 10                     55  1.61818181818181818181818181818181818181818
 11                     89  1.61797752808988764044943820224719101123596
 12                    144  1.61805555555555555555555555555555555555556
 13                    233  1.61802575107296137339055793991416309012876
 14                    377  1.61803713527851458885941644562334217506631
 15                    610  1.61803278688524590163934426229508196721311
 16                    987  1.61803444782168186423505572441742654508612
 17                   1597  1.61803381340012523481527864746399499060739
 18                   2584  1.61803405572755417956656346749226006191950
 19                   4181  1.61803396316670652953838794546759148529060
 20                   6765  1.61803399852180339985218033998521803399852
 21                  10946  1.61803398501735793897314087337840306961447
 22                  17711  1.61803399017559708655637739258088193777878
 23                  28657  1.61803398820532505147084481976480441078968
 24                  46368  1.61803398895790200138026224982746721877157
 25                  75025  1.61803398867044318560479840053315561479507
 26                 121393  1.61803398878024268285650737686687041262676
 27                 196418  1.61803398873830300685273243796393405899663
 28                 317811  1.61803398875432253760883040549257262964466
 29                 514229  1.61803398874820362134379819107829391185639
 30                 832040  1.61803398875054083938272198451997500120187
 31                1346269  1.61803398874964810153097189343288748385352
 32                2178309  1.61803398874998909704729677929072505324084
 33                3524578  1.61803398874985884835007198024841555499694
 34                5702887  1.61803398874990859892542145758806022283100
 35                9227465  1.61803398874988959589659781966119622236443
 36               14930352  1.61803398874989685440771925537991334698606
 37               24157817  1.61803398874989408190317858604525400618773
 38               39088169  1.61803398874989514090567915831514134110503
 39               63245986  1.61803398874989473640271811083789570455902
 40              102334155  1.61803398874989489090910068099941803398875
 41              165580141  1.61803398874989483189291401799204893780106
 42              267914296  1.61803398874989485443509143685262693111382
 43              433494437  1.61803398874989484582474584327826103106370
 44              701408733  1.61803398874989484911360520514078058962519
 45             1134903170  1.61803398874989484785737271312758779235765
 46             1836311903  1.61803398874989484833721082730464662244255
 47             2971215073  1.61803398874989484815392897678666292899491
 48             4807526976  1.61803398874989484822393641416355517918575
 49             7778742049  1.61803398874989484819719595255086212205107
 50            12586269025  1.61803398874989484820740990001204904326284
 51            20365011074  1.61803398874989484820350851924118133676199
 52            32951280099  1.61803398874989484820499871409259753505275
 53            53316291173  1.61803398874989484820442951030921664668132
 54            86267571272  1.61803398874989484820464692680794311350484
 55           139583862445  1.61803398874989484820456388109514460140572
 56           225851433717  1.61803398874989484820459560173481367087956
 57           365435296162  1.61803398874989484820458348552860497455715
 58           591286729879  1.61803398874989484820458811350756199405053
 59           956722026041  1.61803398874989484820458634577689963189281
 60          1548008755920  1.61803398874989484820458702098992969887258
 61          2504730781961  1.61803398874989484820458676308150186009100
 62          4052739537881  1.61803398874989484820458686159375530945598
 63          6557470319842  1.61803398874989484820458682396542280014262
 64         10610209857723  1.61803398874989484820458683833816687871770
 65         17167680177565  1.61803398874989484820458683284826715230581
 66         27777890035288  1.61803398874989484820458683494522225296641
 67         44945570212853  1.61803398874989484820458683414425667739652
 68         72723460248141  1.61803398874989484820458683445019830344559
 69        117669030460994  1.61803398874989484820458683433333900086825
 70        190392490709135  1.61803398874989484820458683437797528255119
 71        308061521170129  1.61803398874989484820458683436092574007972
 72        498454011879264  1.61803398874989484820458683436743808581119
 73        806515533049393  1.61803398874989484820458683436495059108826
 74       1304969544928657  1.61803398874989484820458683436590072952558
 75       2111485077978050  1.61803398874989484820458683436553780893654
 76       3416454622906707  1.61803398874989484820458683436567643226634
 77       5527939700884757  1.61803398874989484820458683436562348286599
 78       8944394323791464  1.61803398874989484820458683436564370773724
 79      14472334024676221  1.61803398874989484820458683436563598252384
 80      23416728348467685  1.61803398874989484820458683436563893329279
 81      37889062373143906  1.61803398874989484820458683436563780619934
 82      61305790721611591  1.61803398874989484820458683436563823671073
 83      99194853094755497  1.61803398874989484820458683436563807227001
 84     160500643816367088  1.61803398874989484820458683436563813508078
 85     259695496911122585  1.61803398874989484820458683436563811108920
 86     420196140727489673  1.61803398874989484820458683436563812025317
 87     679891637638612258  1.61803398874989484820458683436563811675284
 88    1100087778366101931  1.61803398874989484820458683436563811808985
 89    1779979416004714189  1.61803398874989484820458683436563811757916
 90    2880067194370816120  1.61803398874989484820458683436563811777422
 91    4660046610375530309  1.61803398874989484820458683436563811769972
 92    7540113804746346429  1.61803398874989484820458683436563811772818
 93   12200160415121876738  1.61803398874989484820458683436563811771730
 94   19740274219868223167  1.61803398874989484820458683436563811772146
 95   31940434634990099905  1.61803398874989484820458683436563811771987
 96   51680708854858323072  1.61803398874989484820458683436563811772048
 97   83621143489848422977  1.61803398874989484820458683436563811772025
 98  135301852344706746049  1.61803398874989484820458683436563811772033
 99  218922995834555169026  1.61803398874989484820458683436563811772030
100  354224848179261915075  1.61803398874989484820458683436563811772031

Adna_rim schrieb:

[…] Aufgabenstellung: Die Fibonacci-Folge mit f1=1 und f2=1 für die ersten 100 Fibonacci-Zahlen zu bestimmen und daraus für alle Fibonacci-Zahlen den Näherungswert an den Goldener Schnitt bestimmen.

Für solche Aufgabenstellungen sind natürlich alle Programmiersprachen schlecht geeignet, welche mit einem endlichen Zahlenraum arbeiten, egal wie groß dieser sein mag. Vielmehr sollte man es mit einem Programm versuchen, welches Zahlen beliebiger Länge verarbeiten kann.

Und nur die ersten 100 Zahlen einer Folge berechnen zu sollen, ist auch nur etwas für Anfänger.

Eine anspruchsvollere Aufgabenstellung wäre:

• Berechne einen Näherungswert für den Goldenen Schnitt als Dezimalzahl mit 500 Nachkommastellen! Verwende die Fibonacci-Folge.

Meine Lösung:

#! /usr/bin/bc
/*	Berechnet iterativ die ersten N Fibionacci Zahlen und daraus einen
	Näherungswert für den Goldenen Schnitt mit vorgebbarer Genauigkeit.
*/
scale = 500		/* Rechnet mit dieser Anzahl Nachkommastellen	*/
n = 1000		/* Anzahl der Iterationen			*/
f = 1 ; f_ = 0		/* eine Fibionacci-Zahl und deren Vorgänger	*/
while ( n -- > 0 )
	{ "n: "; n ; "f: " ; f + f_ ; f_ = f ; f = last ; "g: " ; f / f_ }
quit

1000 Iterationen reichen noch nicht ganz für 500 konstante Nachkommastellen, etwas mehr aber schon.

Wobei es für einige dieser beschränkten Programmiersprachen Bibliotheken gibt, die diese Wertbeschränkungen umgehen (Stichwort: Big Integer). Und Sprachen, die von Haus aus "beliebig" große Werte erlauben, benutzen unter der Haube auch eine Art Big Integer.