Aufgaben aus dem Schulbuch I.

Teil I.
Teil II
Teil III

Betrachten 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 infty

Der 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  frac2n14n+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 Überschrift
Aus 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+1

und da für Fibonacci-Zahlen r=un
dann
 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 yn

2, 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+1an

Teilen 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

Zum Vergleich




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:

12
P.13
Q.12


so dass  alpha= frac3 alpha+12 alpha+1,2 alpha22 alpha1=0

und 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+...+ sqrtc
Verlauf 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+a
bei 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(2cyn)


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<10
y0=0,01 bei 10<c<100
y0=0,001 bei 100<c<1000
usw.
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)(xx0)+f(x0) Graph zu funktionieren y= frac1x werden durch die Formel ausgedrückt y= frac2x0 fracxx20

Zahlen ersetzen 1,2,3,4,... statt x0 Wir erhalten die Gleichungen der Tangenten

y=2x


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 alpha
Ferner Gleichsetzen der Tangentengleichung mit Null und Ausdrücken x Wir bekommen die Gleichung x=x0 fracf(x0)f(x0)

Stattdessen f(x0) Ersatz  frac1x0 alpha
Stattdessen f(x0) Ersatz  frac1x20

Wir bekommen den Ausdruck x=x0+( frac1x0 alpha)x20
Wenn wir die Klammern erweitern, bekommen wir x=x0+x0 alphax20

Ersatz 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,5

Einsetzen dieser Werte in die Gleichung y= frac2x0 fracxx202 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): # a -  , n -   x0=1 #    1 arr=[] for i in range(n): arr.append(x0) #      x0=0.5*(x0+a/x0) #      return arr print square_root(2,10) 

codepad.org

Berechnung 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|na2|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): # n- , a -    x0=a #    a arr=[] for i in range(n_count): #       a arr.append(x0-a) #  a x0=2*a+(na*a)/x0 return arr print square_root(2.0,1.0,10) 

codepad.org

Im 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"

 sqrt52= frac( sqrt52)( 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+24= sqrt52 deshalb  sqrt5+2=4+ sqrt5+2 . Wieder zerstören wir die Irrationalität im Zähler des zweiten Terms:

 sqrt52= 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  sqrt52 . 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 WolframAlpfa
WolframAlpfa berechnet fortgesetzte Fraktionen unter Verwendung der fortgesetzten Fraktionsoperation
Berechnen Sie den Wert  sqrt3
der Link
Berechnen Sie den Wert  sqrt3+1
der 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 |na2| 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.org
Im 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 2p1 ungerade Primzahl
p ist gleich 1
(Beispiele: 22=3a+1,24=5b+1,26=7c+1,2101=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.

Source: https://habr.com/ru/post/de419237/


All Articles