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.