Teil I.Teil IITeil IIIBetrachten Sie die algorithmische Lösung für Problem Nummer 
38 aus dem Buch "Aufgaben für Kinder von 5 bis 15 Jahren".
Berechnen Sie den Betrag:
 f r a c 1 1 c d o t 2  + f r a c 1 2 c d o t 3 + f r a c 1 3 c d o t 4 + . . . + f r a c 1 99 c d o t 100      
(mit einem Fehler von nicht mehr als 1% der Antwort)
Im Folgenden finden Sie einen Algorithmus zum Berechnen von Teilsummen dieser Reihe in 
Schema (Lisp) in 
drRacket (mit drRacket können Sie Berechnungen in gewöhnlichen Brüchen durchführen):
#lang racket (define series_sum ( lambda (n) (if (= n 0) 0 (+ (/ 1 (* n (+ n 1))) (series_sum(- n 1))) ) ) ) (series_sum 10) (series_sum 100) (series_sum 1000) (series_sum 10000) (series_sum 100000) (series_sum 1000000) (define series_sum_1 ( lambda (n) (if (= n 0) 0 (+ (/ 1.0 (* n (+ n 1.0))) (series_sum_1(- n 1.0))) ) ) ) (series_sum_1 10) (series_sum_1 100) (series_sum_1 1000) (series_sum_1 10000) (series_sum_1 100000) (series_sum_1 1000000) 
Die letzten beiden Beispiele drRacket wurden mit einem Fehler berechnet

Dieses Programm kann auf online ide 
ideone.com und 
codepad.org ausgeführt werden .
Der gleiche Algorithmus in Python def series_sum(n): if n==0: return 0 else: return 1.0/(n*(n+1.0))+series_sum(n-1.0) print(series_sum(10)) print(series_sum(100)) 
Link zu ideone.com
 Wenn wir Teilsummen in gewöhnlichen Brüchen betrachten, können wir sehen, dass die Summe der Reihen ist
 f r a c n n + 1
Ich möchte Sie daran erinnern 
 lim fracnn+1= frac11+ frac1n= frac11=1 bei 
n to inftyDer zweite Band des Kurses der Differential- und Integralrechnung 363 (4) befasst sich mit dem allgemeinen Fall
 sum frac1( alpha+n)( alpha+n+1)= frac1 alpha+1
Die Aufgabe aus dem 
Kurs "Mathematik für Entwickler":
Finden Sie die Anzahl der Mitglieder in einer Sequenz 
 frac2n−14n+5 außerhalb des Intervalls liegen 
(1− frac11000;1+ frac11000)Kommen wir zum Hauptthema des Artikels.
Betrachten wir noch ein Beispiel aus einem Problembuch.
43 . Die Anzahl der Kaninchen (Fibonacci) bildet eine Sequenz 
(a1=1),1,3,5,8,13,21,34,..., in dem 
an+2=an+1+an für alle 
n=1,2,... . Finden Sie den größten gemeinsamen Teiler von Zahlen 
a100 und 
a99 .
Antwort: Zwei benachbarte Fibonacci-Zahlen sind Koprime, d. H. 
 gcd(un+1,un)=1(gcd ist der größte gemeinsame Teiler, d. h. GCD).
“Beweis aus dem Buch“ Jenseits der Seiten eines Mathematiklehrbuchs ”[10-11]
Spoiler ÜberschriftAus Gleichheit u n + 2 = u n + 1 + u n Daraus folgt  g c d ( u n + 2 , u n + 1 ) = g c d ( u n + 1 , u n )  . Auf diese Weise sichern, kommen wir zu  gcd(u2,u1)= gcd(1,1)=1 und daher sind zwei benachbarte Fibonacci-Zahlen Koprime.
Beweisen Sie das 
 gcd(un+2,un+1)= gcd(un+1,un) Das Buch wird nicht gegeben, sondern nach dem euklidischen Algorithmus
 gcd(un+2,un+1)= gcd(un+1,r)wo 
r - Rest der Teilung 
un+2 auf 
un+1und da für Fibonacci-Zahlen 
r=undann
 gcd(un+2,un+1)= gcd(un+1,un) In der nächsten Aufgabe müssen Sie den 
Goldenen Schnitt berechnen. 
 frac sqrt5+12 ca.1.618 . [Dies ist das Seitenverhältnis einer Postkarte, das beim Schneiden eines Quadrats, dessen Seite die kleinere Seite der Postkarte ist, ähnlich bleibt.]
53 . Für eine Folge von Fibonacci-Zahlen 
an Aufgaben 43 finden die Grenze der Beziehung 
 fracan+1an während des Strebens 
n bis unendlich:
 fracan+1an=2, frac32, frac53, frac85, frac138, frac2113, frac3421.
Betrachten Sie die Segmente, die die Unterschiede zweier benachbarter Mitglieder der Serie darstellen 
 fracan+1an .

Sogar Mitglieder der Serie 
 fracan+1an eine wachsende Sequenz darstellen 
xn frac32, frac85, frac2113,...,
Seltsame Zeilenmitglieder 
 fracan+1an eine abnehmende Sequenz darstellen 
yn2, frac53, frac138,...,
Durch das eingebettete Intervall-Lemma (Verlauf der Differential- und Integralrechnung, 38)
c= limxn= limyn
Für unsere Reihe an einem Punkt 
c faire Gleichheit 
 fracan+2an+1= fracan+1anTeilen 
an+2=an+1+an auf 
an+1 Wir bekommen die Gleichung 
 fracan+2an+1=1+ fracanan+1 .
Durch Ersetzen 
 fracan+2an+1=x, fracanan+1= frac1x Wir erhalten die 
quadratische Gleichung x=1+ frac1x .
Wenn 
wir im 
Geogebra- Programm die Punkte 2 und 2 verbinden 
 frac32 , 
 frac32 und 
 frac53 , 
 frac53 und 
 frac85 usw. - eine 
selbstähnliche Figur bekommen

Im Allgemeinen gibt es in Python einen Standardalgorithmus zur Berechnung von Fibonacci-Zahlen.
Dieser Algorithmus ist auf 
Python.org verfügbar
 def fib(n): a, b = 0, 1 while a < n: print(a) a, b = b, a+b fib(100) 
Sie können den 
Link überprüfen
Ändern Sie diesen Algorithmus so, dass eine Annäherung an den Goldenen Schnitt ausgegeben wird. Für zwei benachbarte Zahlen a und b teilen wir die Summe a + b durch b
 def fib(n): a, b = 0.0 , 1.0 while a < n: print((a+b)/b) a, b = b, a+b fib(100) 
Sie können den 
Link überprüfen
Hier sind einige Aufgaben aus dem 
SICP- Tutorial zum Goldenen 
Schnitt .
Die AufgabenÜbung 1.13.Beweisen Sie, dass 
Fib (n) die Ganzzahl ist, die am nächsten liegt 
 varphin/ sqrt5 wo 
 varphi=(1+ sqrt5)/2 .
Übung 1.35.Zeigen Sie, dass der goldene Schnitt 
 varphi (Abschnitt 1.2.2) ist ein fester Transformationspunkt 
x bis1+1/x und verwenden Sie diese Tatsache, um zu berechnen 
 varphi mit dem Festkomma-Verfahren.
Übung 1.37.... Definieren Sie die cont-frac-Prozedur so, dass die Berechnung (cont-frac ndk) den Wert ergibt 
k -elementare endliche fortgesetzte Fraktion. Testen Sie Ihr Verfahren, indem Sie Annäherungen an 1 / φ mit berechnen
 (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) k) 
für sequentielle Werte 
k .
  Das folgende Beispiel aus dem Aufgabenbuch "Aufgaben für Kinder von 5 bis 15 Jahren"
54 . Berechnen Sie die unendliche fortgesetzte Fraktion
1 + \ frac {1} {2 + \ frac {1} {1+ \ frac {1} {2+ \ frac {1} {1+ \ frac {1} {2 + ...}}}}
UPD Betrachten Sie die Gleichung
 alpha=1+ frac12+ frac1 alpha
Nach den Sätzen 236 und 235 aus dem Buch „Zahlentheorie“:
 alpha= fracP1 alpha+P0Q1 alpha+Q0
Wir erstellen eine Wertetabelle 
Pn und 
Qn bei 
n=0,1:so dass 
 alpha= frac3 alpha+12 alpha+1,2 alpha2−2 alpha−1=0und seitdem 
 alpha>0, dann
 alpha= frac1+ sqrt32
Betrachten Sie das Problem aus dem Buch „Hinter den Seiten eines Mathematiklehrbuchs“ [10-11].
4 . Zeigen Sie diese Nummer 
 sqrt1+ sqrt1+ sqrt1+... gleich der Zahl 
 varphi Definieren des Goldenen Schnitts.
Betrachten Sie die 
Option xn= sqrtc+ sqrtc+...+ sqrtcVerlauf der Differential- und Integralrechnung, 35 (2)
Auf diese Weise xn+1 erhalten von xn nach der Formel
xn+1= sqrtc+xn
... Nach dem Hauptsatz Optionen xn hat eine endliche Grenze a . Um dies festzustellen, gehen wir in der Gleichheit an die Grenze
x2n+1=c+xn;
Wir kommen so a erfüllt die quadratische Gleichung
a2=c+a
Diese Gleichung hat die Wurzeln verschiedener Vorzeichen; aber die Grenze, die uns interessiert a kann nicht negativ sein, daher ist es genau gleich der positiven Wurzel:
a= frac sqrt4c+1+12
Daraus können wir schließen, dass der "goldene Schnitt" eine Lösung für die Gleichung ist 
a2=c+abei 
c=1 .
Ferner wird im Verlauf der Differential- und Integralrechnung 35 (3) ein Algorithmus zur Berechnung der inversen Zahl verwendet
Lass c Ist eine positive Zahl und setzen xn=cyn . Die oben beschriebene Rekursionsrelation wird ersetzt durch:
yn+1=yn(2−cyn)
Den Anfangswert nehmen y0 unter der Bedingung: 0<y0< frac1c wir verstehen das yn monoton ansteigend, wird dazu neigen  frac1c . Nach diesem Schema wird bei Zählmaschinen die inverse Zahl berechnet c .
Algorithmus zur Berechnung der inversen Zahl 
c in Python:
( 
Ideone.com und 
codepad.org )
 def reciprocal(c,y0,n): arr=[] for i in range(n): arr.append(y0) y0=y0*(2-c*y0) return arr 
Die wechselseitige Funktion nimmt eine Zahl als Eingabe 
c Anfangswert 
y0 Anzahl der Iterationen 
n und gibt ein Array von "Annäherungen" an die Zahl zurück 
 frac1c .
y0=0,1 bei 
c<10y0=0,01 bei 
10<c<100y0=0,001 bei 
100<c<1000usw.
Beispiele, wie die reziproke Funktion mit verschiedenen funktioniert 
c >>> reciprocal(3,0.1,10) 
[0,1, 0,17, 0,2533, 0,31411733000000003, 0,3322255689810133, 0,3333296519077525,
0,3333333332926746, 0,333333333333333333, 0,333333333333333333, 0,3333333333333333]
 >>> reciprocal(8,0.1,10) 
[0,1, 0,12, 0,1248, 0,12499968, 0,1249999999991808, 0,125, 0,125, 0,125, 0,125, 0,125]
 >>> reciprocal(5,0.1,10) 
[0.1, 0.15000000000000002, 0.18750000000000003, 0.19921875000000003, 0.19999694824218753, 0.1999999999534339, 0.20000000000000004, 0.1999999999999999998,
0,19999999999999998, 0,19999999999999998]
Geometrische Interpretation
Versuchen wir, die Tangentenmethode zu verwenden, um die inverse Zahl zu approximieren.
Tangenten 
y=f′(x0)(x−x0)+f(x0) Graph zu funktionieren 
y= frac1x werden durch die Formel ausgedrückt 
y= frac2x0− fracxx20Zahlen ersetzen 
1,2,3,4,... statt 
x0 Wir erhalten die Gleichungen der Tangenten
y=2−x
y=1− fracx4
y= frac23− fracx9
y= frac12− fracx16
Erstellen Sie diese Diagramme

Wenn Sie die Hyperbel nach unten bewegen 
 alpha dann kreuzt es die Abszissenachse am Punkt 
 frac1 alpha .
Die Tangentengleichung wird in konvertiert 
y= frac2x0− fracxx20− alphaFerner Gleichsetzen der Tangentengleichung mit Null und Ausdrücken 
x Wir bekommen die Gleichung 
x=x0− fracf(x0)f′(x0)Stattdessen 
f(x0) Ersatz 
 frac1x0− alphaStattdessen 
f′(x0) Ersatz 
− frac1x20Wir bekommen den Ausdruck 
x=x0+( frac1x0− alpha)x20Wenn wir die Klammern erweitern, bekommen wir 
x=x0+x0− alphax20Ersatz 
0.1 in die Gleichung 
x=x0(2− alphax0) und sehen, welche Werte "durchlaufen" werden 
x bei 
 alpha=2 wir bekommen 
0,1,0,18,0,29,0,42,0,49,0,5Einsetzen dieser Werte in die Gleichung 
y= frac2x0− fracxx20−2 wir werden direkt
y=0,111− fracx0,897
y=0,222− fracx0,81
y=0,816− fracx0,504
y=0,857− fracx0,49
y=1,5− fracx0,326
y=2− fracx0,25

Quadratwurzelextraktion
Zurück zu irrationalen Ausdrücken betrachten wir eine iterative Methode zum Extrahieren der Quadratwurzel.
Wir werden einen Algorithmus mit 
der iterativen Heron-Methode schreiben
xn+1= frac12(xn+ fracaxn)
 def square_root(a,n):  
codepad.orgBerechnung der Quadratwurzel unter Verwendung der von 
Rafael Bombelli verwendeten fortgesetzten Fraktionen
Um den Wert zu finden  sqrtn Zunächst definieren wir die gesamte Annäherung:  sqrtn=a pmr wo 0<r<1 . Dann n=(a pmr)2=a2 pm2ar+r2 . Daraus lässt sich das leicht ableiten r= frac|n−a2|2a pmr . Ersetzen des resultierenden Ausdrucks in der Formel  sqrtn=a pmr erhalten wir eine fortgesetzte Fraktionserweiterung:
a \ pm {\ frac {| na ^ {2} |} {2a \ pm {\ frac {| na ^ {2} |} {2a \ pm {\ frac {| na ^ {2} |} {2a \ pm \ cdots}}}}}
Wir können also den Quadratwurzel-Extraktionsalgorithmus unter Verwendung der Zerlegung in einen fortgesetzten Bruch schreiben
 def square_root(n,a,n_count):  
codepad.orgIm Allgemeinen können reelle und komplexe Zahlen sowie Funktionen einer oder mehrerer Variablen private Zähler und Nenner sein.
Die Methode zum Extrahieren des ganzzahligen Teils ermöglicht es, eine irrationale Zahl in Form eines unendlichen fortgesetzten Bruchs mit Einheiten in den Zählern darzustellen (häufige Zähler gleich Eins).
Hier ist ein Beispiel für eine fortgesetzte fraktionierte Erweiterung einer Zahl 
 sqrt5 aus dem Buch "Algebra"
 sqrt5−2= frac( sqrt5−2)( sqrt5+2) sqrt5+2= frac1 sqrt5+2
Auf diese Weise,  sqrt5=2+ frac1 sqrt5+2
Wählen Sie den ganzzahligen Teil der Zahl aus  sqrt5+2:E( sqrt5+2)=4 . Mittel  sqrt5+2 kann dargestellt werden als 4+ alpha . Es ist klar, dass  alpha= sqrt5+2−4= sqrt5−2 deshalb  sqrt5+2=4+ sqrt5+2 . Wieder zerstören wir die Irrationalität im Zähler des zweiten Terms:
 sqrt5−2= frac1 sqrt5+2
Das Ergebnis ist:
 sqrt5=2+ frac14+ frac1 sqrt5+2
Machen wir noch einen ähnlichen Schritt:
\ sqrt {5} = 2 + \ frac {1} {4+ \ frac {1} {4+ \ frac {1} {\ sqrt {5} +2}}
Es ist leicht zu erkennen, dass der Prozess der Isolierung des gesamten Teils und der Bildung einer fortgesetzten Fraktion in diesem Beispiel kein Ende hat. In jedem neuen Nenner erscheint 4 und Begriff  sqrt5−2 . Daher ist es klar, dass  sqrt5 wird als unendlicher fortgesetzter Bruch dargestellt:
 sqrt5=[2,4,4,4,...]
Hypothese
Wenn 
d in mathbbN, sqrtd notin mathbbN dann der fortgesetzte Bruchteil der Zahl 
 sqrtd+[ sqrtd] rein periodisch.
Evarist Galois hat diese Hypothese bewiesen.
Das heißt, wenn auf den nicht periodischen Teil der Fraktion 
[1;2,2,2,...]= sqrt2 füge den ganzen Teil hinzu 
[ sqrt2]=1 dann erhalten wir einen rein periodischen Bruchteil 
[2,2,2,...] .
 sqrt3=[1;1,2,...]; sqrt3+1=[2,1,...] sqrt5=[2;4,4,4,...]; sqrt5+2=[4,4,4,...] sqrt6=[2;2,4,...]; sqrt6+2=[4,2,...] sqrt13=[3;1,1,1,1,6,...]; sqrt13+3=[6,1,1,1,1,1,...]Cloud Computing WolframAlpfaWolframAlpfa berechnet fortgesetzte Fraktionen unter Verwendung der fortgesetzten Fraktionsoperation
Berechnen Sie den Wert 
 sqrt3der LinkBerechnen Sie den Wert 
 sqrt3+1der Link Wenn in der Wurzel Zersetzung nach der Bombelli-Methode
 sqrtn=a pm frac|na2|2a pm frac|na2|2a pm frac|na2|2a pm cdots
zum ersten Term hinzufügen 
a erhalten wir einen rein periodischen Anteil
 sqrtn+a=2a pm frac|na2|2a pm frac|na2|2a pm frac|na2|2a pm cdots
Es bleibt, den Bruch in eine bekanntere Form zu bringen (mit Einheiten im Zähler).
Teilen Sie den Zähler und den Nenner des Bruchs durch 
|n−a2| wir bekommen den Ausdruck
 sqrtn+a=2a pm frac1 frac2a|na2| pm frac12a pm frac1 frac2a|na2| pm cdots
Auf diese Weise
 sqrt2+1=2+ frac1 frac21+ frac12+ frac1 frac21+...=[2,2,2,...]
 sqrt3+1=2+ frac1 frac22+ frac12+ frac1 frac22+...=[2,1,...]
 sqrt5+2=4+ frac1 frac41+ frac14+ frac1 frac41+...=[4,4,4,...]
 sqrt6+2=4+ frac1 frac42+ frac14+ frac1 frac42+...=[4,2,...]
 sqrt13+3=6+ frac1 frac64+ frac16+ frac1 frac64+...=[6, frac32,...]
Wir werden ein Programm schreiben, das die fortgesetzte Bruchnäherung berechnet 
[6, frac32,...] #lang racket (define continued_fraction ( lambda (n) (if (= n 0) 1 (+ 6 (/ 1 (+ 3/2 (/ 1 (continued_fraction(- n 1)))))) ))) (continued_fraction 4) 
codepad.orgIm vierten Schritt bekommen wir 
6 frac38186305 das ist gleich 
6.60555114... , während 
 sqrt13+3 ca.6.60555127 .
PS Lösen Sie das Problem („Probleme für Kinder von 5 bis 15 Jahren“)
27 . Beweisen Sie, dass der Rest der Division einer Zahl 
2p−1 ungerade Primzahl
p ist gleich 
1(Beispiele: 
22=3a+1,24=5b+1,26=7c+1,210−1=1023=10 cdot93) .
Dieses Problem wird in dem Artikel 
Amazing Adventures of Continued Fractions des Quantum-Magazins behandelt.
Bücher:
"Aufgaben für Kinder von 5 bis 15 Jahren" V. I. Arnold.
"Der Verlauf der Differential- und Integralrechnung" G. M. Fichtenholtz
"Zahlentheorie" A. A. Buchstab
"Hinter den Seiten eines Mathematiklehrbuchs" N. Ya. Vilenkin, L.P. Shibasov, Z.F. Shibasova
"Algebra" N. Ya. Vilenkin, R. S. Guter, S. I. Schwarzburd
Digitale Arithmetik Ercegovac Milos D., Lang Tomas
"Die Struktur und Interpretation von Computerprogrammen" Harold Abelson, Gerald Sassman
Siehe auch
Der Artikel "Zu einer Aufgabe, die im Interview nicht mehr angeboten wird."
Der 
Blog von Spice IT Recruitment veröffentlicht Interviewaufgaben für verschiedene Unternehmen.
Aufgaben für Interviews in Yandex.
In 
diesem Video löst A. Savvateev Probleme mit Interviews bei Tesla.