Nachricht für neue Nutzer.
Nachricht für engagierte Nutzer.

Lernpfad Know-How-Computer/KHC Programmieraufgaben Teil 2: Unterschied zwischen den Versionen

Aus ZUM-Unterrichten
KKeine Bearbeitungszusammenfassung
Markierung: Quelltext-Bearbeitung 2017
KKeine Bearbeitungszusammenfassung
Markierung: Quelltext-Bearbeitung 2017
 
(22 dazwischenliegende Versionen desselben Benutzers werden nicht angezeigt)
Zeile 2: Zeile 2:
{{Fortsetzung|
{{Fortsetzung|
vorher=zurück|
vorher=zurück|
vorherlink=Benutzer:Ukalina/Lernpfad_Know-How-Computer/Know-How-Assembler|
vorherlink=Lernpfad_Know-How-Computer/Know-How-Assembler|
weiter=weiter|
weiter=weiter|
weiterlink=Benutzer:Ukalina/Lernpfad_Know-How-Computer/KHC_als_Von-Neumann-Rechner|
weiterlink=Lernpfad_Know-How-Computer/KHC_als_Von-Neumann-Rechner|
übersicht=Startseite|
übersicht=Startseite|
übersichtlink=Benutzer:Ukalina/Lernpfad_Know-How-Computer}}
übersichtlink=Lernpfad_Know-How-Computer}}


{{Box|Programmieraufgaben Teil 2|Hier kommen ein paar weitere Programmieraufgaben, die schon etwas anspruchsvoller sind. Entsprechend länger und unübersichtlicher sind die Maschinenprogramme. Daher macht es Sinn, erst ein Assemblerprogramm zu schreiben. Auch dieses kann man mit Stift und Streichhölzern erst mal „von Hand” auf dem Papier testen. Anschließend kann man es in die KHC-Maschinensprache übersetzen, um es z.B. im KHC-Emulator laufen zu lassen.|Lernpfad}}  
{{Box|Anspruchsvollere Programmieraufgaben für Könner|Hier kommen ein paar weitere Programmieraufgaben, die schon etwas anspruchsvoller sind. Entsprechend länger und unübersichtlicher sind die Maschinenprogramme. Daher macht es Sinn, erst ein Assemblerprogramm zu schreiben. Auch dieses kann man mit Stift und Streichhölzern erst mal von Hand auf dem Papier testen. Anschließend kann man es in die KHC-Maschinensprache übersetzen, um es z.B. im KHC-Emulator laufen zu lassen.|Lernpfad}}  


<div style="width: 100%; overflow: hidden;">
<div style="width: 100%; overflow: hidden;">
   <div style="width: 40%; float: left;">  
{{Box
  {{Box|1=Programm testen im KHC-Emulator
|1=Auch hier gilt wieder für alle Übungsaufgaben:
|2=* Alle Zellen des Hauptspeichers enthalten solange standardmäßig den Wert 0, bis etwas anderes per Tastatureingabe oder durch das Laden einer Speicherkonfiguration hineingeschrieben wird.
* Nach dem Programmende darf der Datenwert, der dann in einer Speicherzelle steht, von dem ursprünglichen Wert abweichen, der vor der Programmausführung in der Zelle stand.
|3=Kurzinfo}}
   <div style="width: 60%; float: left;">  
   
{{Box
|1=5. Aufgabe "Ist x < y ?"
|2=Entscheide, ob der Wert der Variablen x kleiner ist als der Wert der Variablen y.
; Vor dem Programmstart steht
: in Speicherzelle 21 ein beliebiger Wert x, z.B. der Wert 5, und <br>in Speicherzelle 22 ein beliebiger Wert y, z.B. der Wert 7.
; Nach dem Programmende steht
: in Speicherzelle 23 der Wert 1, wenn der ursprüngliche Wert von x kleiner als der ursprüngliche Wert von y war, <br>andernfalls steht in Speicherzelle 23 weiterhin der Initialisierungswert 0.
|3=Üben}}
 
{{Lösung versteckt
|1= Hier kann man sich am Grundaufbau des Programms aus der 4. Aufgabe "Ist x = y ?" und an den entsprechenden Tipps orientieren.
|2=Tipp anzeigen|3=Tipp  verstecken}}
 
 
{{Box
|1=6. Aufgabe "x - y = ? , wobei das Ergebnis jetzt auch negativ sein darf"
|2=Berechne die Differenz zweier beliebiger natürlicher Zahlen x und y. Im Gegensatz zu Aufgabe 2 wird jetzt nicht mehr zwingend vorausgesetzt, dass y kleiner oder gleich x sein muss. Das bedeutet, dass das Ergebnis nun auch negativ werden kann. Da im KHC negative Zahlen als Grunddatentypen nicht zugelassen sind, wird das Ergebnis in zwei Speicherzellen ausgegeben: die eine enthält den Betrag der Differenz und die andere das Vorzeichen des Ergebnisses, wobei der Wert 1 für ein negatives Ergebnis steht, der Wert 0 für ein nicht-negatives Ergebnis.
; Vor dem Programmstart steht
: in Speicherzelle 23 ein beliebiger Wert x, z.B. der Wert 3, und <br> in Speicherzelle 24 ein beliebiger Wert y, z.B. der Wert 5.
; Nach dem Programmende steht
: in Speicherzelle 23 der Betrag der Differenz x - y, im Beispiel also der Wert 2, <br>in Speicherzelle 24 der Wert 1, wenn das Ergebnis negativ ist und der Wert 0, wenn dies nicht der Fall ist. <br>Da im vorliegenden Beispiel das Ergebnis 3 - 5 = -2, also negativ ist, steht in diesem Fall <br>in Speicherzelle 23 der Betrag 2 und <br>in Speicherzelle 23 der Wert 1 für das negative Vorzeichen
|3=Üben}}
 
{{Lösung versteckt
|1= Auch hier ist es sinnvoll, wie in den Programmen "Ist x = y ?" und "Ist x < y ?" eine entsprechende Fallunterscheidung durchzuführen.
|2=Tipp anzeigen|3=Tipp  verstecken}}
 
{{Lösung versteckt
|1="x - y = ? (Betrag und Vorzeichen der Differenz für beliebige x und y)" in Assembler
<pre>
start:          isz x
                jmp xistungleich0
                jmp xistgleich0
xistungleich0:  isz y
                jmp xundyungleich0
                jmp fertig
xistgleich0: isz y
                jmp ynachx
                jmp fertig
xundyungleich0: dec x
                dec y 
                jmp start
ynachx:        isz y
                jmp yrunterxrauf
                jmp yauf1
yrunterxrauf:  inc x
                dec y
                jmp ynachx
yauf1:          inc y
fertig:        stp
x:              5
y:              3
</pre>
|2=Lösung in Assembler anzeigen
|3=Lösung in Assembler verstecken}}
 
 
{{Box
|1=7. Aufgabe "Kleiner Gauß 1 + 2 + 3 + ... + n = ?"
|2=Berechne die Summe der natürlichen Zahlen von 1 bis n, also 1+2+3+...+n.
; Vor dem Programmstart steht
: in Speicherzelle 23 ein beliebiger Wert n, z.B. der Wert 4.
; Nach dem Programmende steht
: in Speicherzelle 24 die Summe der natürlichen Zahlen von 1 bis 4, im Beispiel also der Wert 1+2+3+4 = 10.
Das Programm heißt "Kleiner Gauß", weil der berühmte Mathematiker Carl Friedrich Gauß einer Anekdote nach in der Schule schon als kleiner Junge die Summe der natürlichen Zahlen von 1 bis 100 sehr schnell mithilfe einer Formel berechnete, die er selbst entdeckt hatte und die heute als Gaußsche Summenformel bekannt ist.
|3=Üben}}
 
{{Lösung versteckt
|1= {{Box
  |1=Lösungsidee
  |2=Die Zahl n wird in einer Schleife mehrfach zum Summenwert s addiert, dabei aber bei jedem Schleifendurchgang um 1 verringert. Da bei jedem Additionsdurchgang der Wert in n auf 0 heruntergezählt wird, wird n jedesmal zusätzlich in der Hilfsspeicherstelle h gerettet. Vor dem Zurückspielen dieses geretteten Wertes von h nach n wird er um 1 verringert. So wird also schrittweise erst n nach s geschoben, dann n-1, dann n-2 usw. bis 1.
  |3=Unterrichtsidee}}
|2=Tipp anzeigen
|3=Tipp verstecken}}
 
{{Lösung versteckt
|1="Kleiner Gauß 1 + 2 + 3 + ... + n = ?" Lösung in Assembler
<pre>
start1:  isz n
        jmp nnachsundh
        jmp htest
nnachsundh: dec n
        inc s
        inc h
        jmp start1
htest:  isz h
        jmp hminus1
        stp
hminus1: dec h
start2:  isz h
        jmp hnachn
        jmp start1
hnachn:  inc n
        dec h
        jmp start2
n: 4
s: 0
h: 0
</pre>
|2=Lösung in Assembler anzeigen
|3=Lösung in Assembler verstecken}}
 
 
{{Box
|1=8. Aufgabe "Produkt x * y = ?"
|2=Berechne das Produkt zweier Zahlen x und y.
; Vor dem Programmstart steht
: in Speicherzelle 23 ein beliebiger Wert x, z.B. der Wert 2, und <br>in Speicherzelle 24 ein beliebiger Wert y, z.B. der Wert 3.
; Nach dem Programmende steht
: in Speicherzelle 25 das Produkt x * y, im Beispiel also der Wert 2*3 = 6.
|3=Üben}}
 
{{Lösung versteckt
|1={{Box
  |1=Lösungsidee
  |2=Der Wert y in M(24) wird so oft zu p in M(25) hinzuaddiert wie es der Wert x in M(23) angibt. Da nach dem einmaligen Hinzuaddieren von M(24) zu M(25) der Wert in M(24) gleich 0 ist, wird der Wert von M(24) bei diesem Hinzuaddieren zu M(25) gleichzeitig auch noch in die Hilfsspeicherzelle h mit M(22) "gerettet" und von dort aus anschließend wieder nach M(24) zurück kopiert. Nach jeder Erhöhung von M(25) um M(24) wird M(23) um 1 verringert. Dies wird solange wiederholt, bis M(23) gleich 0 ist.
  |3=Unterrichtsidee}}
|2=Tipp anzeigen
|3=Tipp verstecken}}
 
 
{{Box
|1=9. Aufgabe "Größter gemeinsamer Teiler ggT von x und y = ?"
|2=Berechne den größten gemeinsamen Teiler zweier natürlicher Zahlen x und y, also den ggT von x und y.
; Vor dem Programmstart steht
: in Speicherzelle 27 eine beliebige natürliche Zahl x, z.B. der Wert 9 und <br>in Speicherzelle 28 eine beliebige natürliche Zahl y, z.B. der Wert 6.
; Nach dem Programmende steht
: Speicherzelle 29 der ggT von x und y, im Beispiel also der Wert 3.
; Hinweis
: Für dieses Maschinenprogramm sollte der KHC mindestens 30 Speicherzellen besitzen.
|3=Üben}}
 
{{Lösung versteckt
|1={{Box
  |1=Lösungsidee
  |2=Der ggT zweier natürlicher Zahlen x und y kann mit dem so genannten "Euklidischen Algorithmus" berechnet werden:<br>
"Euklid berechnete den größten gemeinsamen Teiler, indem er nach einem gemeinsamen 'Maß' für die Längen zweier Linien suchte. Dazu zog er wiederholt die kleinere der beiden Längen von der größeren ab. Dabei nutzt er aus, dass sich der größte gemeinsame Teiler zweier Zahlen (oder Längen) nicht ändert, wenn man die kleinere von der größeren abzieht." (siehe Wikipedia: https://de.wikipedia.org/wiki/Euklidischer_Algorithmus)
  |3=Unterrichtsidee}}
|2=Tipp anzeigen
|3=Tipp verstecken}}
 
{{Lösung versteckt
|1="ggT von x und y = ?" Lösung in Assembler 
<pre>
start:          isz x             
                jmp xistungleich0
                jmp xistgleich0
xistungleich0:  isz y
                jmp xundyungleich0
                jmp xgroesser y
xistgleich0:    isz y
                jmp ygroesserx
                jmp xundygleich0
xundyungleich0: dec x
                dec y
                inc z
                jmp start
xundygleich0:  stp
xgroessery:    isz z
                jmp znachy
                jmp start
znachy:        inc y
                dec z
                jmp xgroessery
ygroesserx:    isz z
                jmp znachx
                jmp start
znachx:        inc x
                dec z
                jmp ygroesserx
x: 9
y: 6
z: 0
</pre>
|2=Lösung in Assembler anzeigen
|3=Lösunge in Assembler verstecken}}
 
 
====Schaffst du das auch ohne Hilfe?====
Hier kommen Aufgaben, zu denen es in diesem Lernpfad ganz bewusst keine Tipps und keine Lösungen gibt. Bist du so fit und schaffst es auch ohne Hilfe, diese KHC-Maschinenprogramme zu schreiben? Um dein Programm zu testen, verwende am besten den KHC-Emulator mit den 40 Speicherzellen in diesem Kapitel.
 
 
{{Box
|1=10. Aufgabe "x nach y kopieren"
|2=Kopiere den Inhalt von Zelle x so nach Zelle y, dass nach dem Programmende sowohl in x als auch in y der ursprüngliche Wert von x steht.
; Vor dem Programmstart steht
: in Speicherzelle x ein beliebiger Wert, z.B. der Wert 4, und <br />in den Speicherzellen y der Wert 0.
; Nach dem Programmende steht
: in den Speicherzellen x und y der ursprüngliche Wert von x, also im Beispiel der Wert 4.
|3=Üben}}
 
{{Box
|1=11. Aufgabe "x verdoppeln"
|2=Verdopple den Wert in Zelle x.
; Vor dem Programmstart steht
: in Speicherzelle x ein beliebiger Wert, z.B. der Wert 5.
; Nach dem Programmende steht
: in Speicherzellen x das Doppelte seines ursprünglichen Wertes, im Beispiel also der Wert 10.
|3=Üben}}
 
{{Box
|1=12. Aufgabe "x halbieren mit Rest"
|2=Berechne die Hälfte von x als ganze Zahl mit Rest. Beispiel: 7 / 2 = 3 Rest 1
; Vor dem Programmstart steht
: in Speicherzelle x ein beliebiger Wert, z.B. der Wert 7, und <br />in den Speicherzellen y und z der Wert 0.
; Nach dem Programmende steht
: in Speicherzelle y die Hälfte des ursprünglichen x-Wertes, abgerundet auf eine ganze Zahl, im Beispiel also der Wert 3 und<br /> in Speicherzelle z der Divisionsrest, im Beispiel also der Wert 1, denn 7 / 2 = 3 Rest 1.
|3=Üben}}
 
{{Box
|1=13. Aufgabe "x geteilt durch y mit Rest"
|2=Berechne den ganzzahligen Quotient von x geteilt durch y mit Rest, wobei der Versuch einer Division durch 0 abgefangen wird. Beispiel: 14 / 4 = 3 Rest 2
; Vor dem Programmstart steht
: in Speicherzelle x ein beliebiger Wert, z.B. der Wert 14, <br /> in Speicherzelle y ein weiterer beliebiger Wert, z.B. der Wert 4 und <br /> in den Speicherzellen q, r und f der Wert 0.
; Nach dem Programmende steht
: in Speicherzelle q der ganzzahlige Quotient von x geteilt durch y, im Beispiel also der Wert 3, da die Zahl 4 dreimal vollständig in die 14 passt, und <br /> in Speicherzelle r der Divisionsrest, im Beispiel also der Wert 2. <br /> In Speicherzelle f steht normalerweise der Wert 0 außer in dem Fall, dass in y der Wert 0 stand, denn durch 0 darf bekanntlich nicht dividiert werden. In diesem Fehlerfall steht in f der Wert 1.
|3=Üben}}
</div>
 
<div style="margin-left: 62%;">
{{Box|1=Programm testen im KHC-Emulator
         |2={{KnowHowComputer
         |2={{KnowHowComputer
           |Speicherkonfiguration1=# Alles auf 0
           |Speicherkonfiguration1=# Alles auf 0
           |Speicherkonfiguration2=# x - y = ? Version 2
           |Speicherkonfiguration2=# Ist x < y ?
1: isz 21
2: jmp 4 
3: jmp 7
4: isz 22
5: jmp 10
6: jmp 14
7: isz 22
8: jmp 13
9: jmp 14
10: dec 21
11: dec 22
12: jmp 1 
13: inc 23
14: stp   
21: 5     
22: 7     
23: 0     
          |Speicherkonfiguration3=# x - y = ? erweitert
1: isz 23
1: isz 23
2: jmp 4
2: jmp 4
Zeile 38: Zeile 282:
23: 3
23: 3
24: 5
24: 5
           |Speicherkonfiguration3=# Kleiner Gauß
           |Speicherkonfiguration4=# Kleiner Gauß
1: isz 23  
1: isz 23  
2: jmp 4
2: jmp 4
Zeile 64: Zeile 308:
24: 0
24: 0
25: 0
25: 0
           |Speicherkonfiguration4=# x * y = ?
           |Speicherkonfiguration5=# x * y = ?
  1: isz 23
  1: isz 23
  2: jmp 4
  2: jmp 4
Zeile 90: Zeile 334:
24: 3
24: 3
25: 0
25: 0
          |Speicherkonfiguration5=#
           |nohelp=true
           |nohelp=true
          |Speichergroesse=25
         }}
         }}
       |3=Experimentieren
       |3=Experimentieren
     }}
     }}
</div>


<div style="margin-left: 42%;">
{{Box
|1=Auch hier gilt wieder für alle Übungsaufgaben:
|2=* Alle Zellen des Hauptspeichers enthalten solange standardmäßig den Wert 0, bis etwas anderes per Tastatureingabe oder durch das Laden einer Speicherkonfiguration hineingeschrieben wird.
* Nach dem Programmende darf der Datenwert, der dann in einer Speicherzelle steht, von dem ursprünglichen Wert abweichen, der vor der Programmausführung in der Zelle stand.
|3=Kurzinfo}}
{{Box
|1=5. Aufgabe „Ist x < y ?”
|2=Entscheide, ob der Wert der Variablen x kleiner ist als der Wert der Variablen y.
; Vor dem Programmstart steht
: in Speicherzelle 21 ein beliebiger Wert x, z.B. der Wert 5, und <br>in Speicherzelle 22 ein beliebiger Wert y, z.B. der Wert 7.
; Nach dem Programmende steht
: in Speicherzelle 23 der Wert 1, wenn der ursprüngliche Wert von x kleiner als der ursprüngliche Wert von y war, <br>andernfalls steht in Speicherzelle 23 weiterhin der Initialisierungswert 0.
|3=Üben}}
{{Lösung versteckt
|1= Hier kann man sich am Grundaufbau des Programms aus der 4. Aufgabe „Ist x = y ?” und an den entsprechenden Tipps orientieren.
|2=Tipp anzeigen|3=Tipp  verstecken}}
{{Box
|1=6. Aufgabe „x - y = ? (Betrag und Vorzeichen der Differenz für beliebige x und y)”
|2=Berechne die Differenz zweier beliebiger natürlicher Zahlen x und y. Im Gegensatz zu Aufgabe 2 wird jetzt nicht mehr zwingend vorausgesetzt, dass y kleiner oder gleich x sein muss. Das bedeutet, dass das Ergebnis nun auch negativ werden kann. Da im KHC negative Zahlen als Grunddatentypen nicht zugelassen sind, wird das Ergebnis in zwei Speicherzellen ausgegeben: die eine enthält den Betrag der Differenz und die andere das Vorzeichen des Ergebnisses, wobei der Wert 1 für ein negatives Ergebnis steht, der Wert 0 für ein nicht-negatives Ergebnis.
; Vor dem Programmstart steht
: in Speicherzelle 23 ein beliebiger Wert x, z.B. der Wert 3, und <br> in Speicherzelle 24 ein beliebiger Wert y, z.B. der Wert 5.
; Nach dem Programmende steht
: in Speicherzelle 23 der Betrag der Differenz x - y, im Beispiel also der Wert 2, <br>in Speicherzelle 24 der Wert 1, wenn das Ergebnis negativ ist und der Wert 0, wenn dies nicht der Fall ist. <br>Da im vorliegenden Beispiel das Ergebnis 3 - 5 = -2, also negativ ist, steht in diesem Fall <br>in Speicherzelle 23 der Betrag 2 und <br>in Speicherzelle 23 der Wert 1 für das negative Vorzeichen
|3=Üben}}
{{Lösung versteckt
|1= Auch hier ist es sinnvoll, wie in den Programmen „Ist x = y ?” und „Ist x < y ?” eine entsprechende Fallunterscheidung durchzuführen.
|2=Tipp anzeigen|3=Tipp  verstecken}}
<!--
{{Lösung versteckt
|1=„x - y = ? (Betrag und Vorzeichen der Differenz für beliebige x und y)” in Assembler
<pre>
start:          isz x              ; Ist x=0 ?
                jmp xistungleich0  ; nein: dann y überprüfen ab Marke xistungleich0
                jmp xistgleich0    ; ja:  dann y überprüfen ab Marke xistgleich0
xistungleich0:  isz y              ; Hier ist x!=0. Ist zusätzlich y=0?
                jmp xundyungleich0 ; nein, dann ist x!=0 und y!=0, also ab Marke xundyungleich0
                                  ; beide verringern und dann Schleife wiederholen
                jmp fertig        ; ja:  dann ist x!=0 und y=0, also fertig
xistgleich0: isz y              ; Hier ist x=0. Ist zusätzlich y=0?
                jmp ynachx        ; nein: dann ist x=0 und y!=0, also y nach x kopieren und dann y=1 setzen
                jmp fertig        ; ja:  dann ist x=0 und y=0, also fertig
xundyungleich0: dec x              ; Hier ist x!=0 und y!=0. Daher werden x und y verringert
                                  ; und dann die Schleife wiederholt
                dec y 
                jmp start          ; zurück zum Start ganz nach oben
ynachx:        isz y              ; Ist y=0 ? Schleifenanfang des Kopiervorgangs y nach x
                jmp yrunterxrauf  ; nein: dann nächster Schritt, um y nach x kopieren 
                jmp yauf1          ; ja:  Hier muss noch das negative Vorzeichen in y angezeigt werden
yrunterxrauf:  inc x
                dec y
                jmp ynachx        ; Schleifenende des Kopiervorgangs y nach x
yauf1:          inc y              ; y um 1 erhöhen (negatives Vorzeichen)
fertig:        stp                ; fertig
x:              5
y:              3
</pre>
|2=Lösung in Assembler anzeigen
|3=Lösung in Assembler verstecken}}
{{Lösung versteckt
|1=„x - y = ? (Betrag und Vorzeichen der Differenz für beliebige x und y)” in Maschinensprache
<pre>
</pre>
|2=Lösung in Maschinensprache anzeigen
|3=Lösung in Maschinensprache verstecken}}
-->
{{Box
|1=7. Aufgabe „Kleiner Gauß 1 + 2 + 3 + ... + n = ?”
|2=Berechne die Summe der natürlichen Zahlen von 1 bis n, also 1+2+3+...+n.
; Vor dem Programmstart steht
: in Speicherzelle 23 ein beliebiger Wert n, z.B. der Wert 4.
; Nach dem Programmende steht
: in Speicherzelle 24 die Summe der natürlichen Zahlen von 1 bis 4, im Beispiel also der Wert 1+2+3+4 = 10.
Das Programm heißt „Kleiner Gauß”, weil der berühmte Mathematiker Carl Friedrich Gauß einer Anekdote nach in der Schule schon als kleiner Junge die Summe der natürlichen Zahlen von 1 bis 100 sehr schnell mithilfe einer Formel berechnete, die er selbst entdeckt hatte und die heute als „Gaußsche Summenformel” bekannt ist.
|3=Üben}}
{{Box
|1=8. Aufgabe „Produkt x * y = ?”
|2=Berechne das Produkt zweier Zahlen x und y.
; Vor dem Programmstart steht
: in Speicherzelle 23 ein beliebiger Wert x, z.B. der Wert 2, und <br>in Speicherzelle 24 ein beliebiger Wert y, z.B. der Wert 3.
; Nach dem Programmende steht
: in Speicherzelle 25 das Produkt x * y, im Beispiel also der Wert 2*3 = 6.
|3=Üben}}
{{Box
|1=9. Aufgabe „Größter gemeinsamer Teiler ggT von x und y = ?”
|2=Berechne den größten gemeinsamen Teiler zweier natürlicher Zahlen x und y, also den ggT von x und y.
; Vor dem Programmstart steht
: in Speicherzelle 27 eine beliebige natürliche Zahl x, z.B. der Wert 9 und <br>in Speicherzelle 28 eine beliebige natürliche Zahl y, z.B. der Wert 6.
; Nach dem Programmende steht
: Speicherzelle 29 der ggT von x und y, im Beispiel also der Wert 3.
|3=Üben}}
{{Lösung versteckt
|1= Der ggT zweier natürlicher Zahlen x und y kann mit dem so genannten „Euklidischen Algorithmus“ berechnet werden:<br>
„Euklid berechnete den größten gemeinsamen Teiler, indem er nach einem gemeinsamen „Maß“ für die Längen zweier Linien suchte. Dazu zog er wiederholt die kleinere der beiden Längen von der größeren ab. Dabei nutzt er aus, dass sich der größte gemeinsame Teiler zweier Zahlen (oder Längen) nicht ändert, wenn man die kleinere von der größeren abzieht.“ (siehe Wikipedia: https://de.wikipedia.org/wiki/Euklidischer_Algorithmus)
|2=Tipp 1 anzeigen
|3=Tipp 1verstecken}}
{{Lösung versteckt
|1= start:  isz x              ; Ist x=0 ?
jmp xistungleich0  ; nein, dann y überprüfen ab Marke xistungleich0
jmp xistgleich0    ; ja,  dann y überprüfen ab Marke xistgleich0
xistungleich0:  isz y      ; Hier ist x!=0. Ist zusätzlich y=0?
jmp xundyungleich0 ; nein, dann ist x!=0 und y!=0, also ab Marke xundyungleich0
                    ; beide verringern und dann Schleife wiederholen
jmp xgroesser y    ; ja,  dann ist x!=0 und y=0, also weiter bei Marke xgroessery
xistgleich0: isz y      ; Hier ist x=0. Ist zusätzlich y=0?
jmp ygroesserx    ; nein, dann ist x=0 und y!=0, also weiter bei Marke ygroesserx
jmp xundygleich0  ; ja, dann ist x=0 und y=0, also weiter bei Marke xundygleich0 und fertig
xundyungleich0:  dec x ; Hier ist x!=0 und y!=0. Daher werden x und y verringert und dann
                            ; die Schleife wiederholt
dec y
        inc z
jmp start          ; Schleifenende: Zurück zum Anfang in Marke start
xundygleich0: stp        ; fertig
xgroessery: isz z          ; Schleife, um z nach y zu verschieben
        jmp znachy
jmp start          ; wenn z ganz nach y verschoben, dann das Ganze von vorn
znachy:  inc y
        dec z
        jmp xgroessery
ygroesserx: isz z          ; Schleife, um z nach x zu verschieben
        jmp znachx
jmp start          ; wenn z ganz nach x verschoben, dann das Ganze von vorn
znachx:  inc x
        dec z
        jmp ygroesserx
x: 9                        ; Beispielwert für x
y: 6                        ; Beispielwert für y
z: 0                        ; Vorgabewert für z
|2=Lösung in Assembler anzeigen
|3=Lösunge in Assembler verstecken}}


{{Box|1=Programm Testen im KHC-Emulator
        |2={{KnowHowComputer
          |Speicherkonfiguration1=# Alles auf 0
          |Speicherkonfiguration2=# ggT von x und y
1:  isz 27
2: jmp 4 
3: jmp 7 
4:  isz 28
5: jmp 10
6: jmp 14
7: isz 28
8: jmp 20
9: stp
10:  dec 27
11: dec 28
12:  inc 29
13: jmp 1 
14:  isz 29
15:  jmp 17
16: jmp 1 
17:  inc 28
18:  dec 29
19:  jmp 14
20:  isz 29
21:  jmp 23
22: jmp 1 
23:  inc 27
24:  dec 29
25:  jmp 20
26:  0
27:  9   
28:  6   
29:  0   
30:  0
          |nohelp=true
          |Speichergroesse=40
        }}
      |3=Experimentieren
    }}


   </div>
   </div>
</div>
</div>
   
   
<!--
Hinweis: Im Javascript-Code khc-emulator.html kann die Anzahl der verfügbaren Hauptspeicherzellen ganz oben in der Variablen speicheranzahl verändert werden. Der Standardwert ist speicheranzahl = 25; kann aber bei umfangreicheren Programmen beliebig erhöht werden. Bei diesem ggT-Programm bietet sich z.B. der Wert speicheranzahl = 30 an.
-->
{{Fortsetzung|
{{Fortsetzung|
vorher=zurück|
vorher=zurück|
vorherlink=Benutzer:Ukalina/Lernpfad_Know-How-Computer/Know-How-Assembler|
vorherlink=Lernpfad_Know-How-Computer/Know-How-Assembler|
weiter=weiter|
weiter=weiter|
weiterlink=Benutzer:Ukalina/Lernpfad_Know-How-Computer/KHC_als_Von-Neumann-Rechner|
weiterlink=Lernpfad_Know-How-Computer/KHC_als_Von-Neumann-Rechner|
übersicht=Startseite|
übersicht=Startseite|
übersichtlink=Benutzer:Ukalina/Lernpfad_Know-How-Computer}}
übersichtlink=Lernpfad_Know-How-Computer}}
 
 
[[Kategorie:Know-How-Computer]]

Aktuelle Version vom 8. August 2025, 20:05 Uhr

zurück
Startseite
weiter

Anspruchsvollere Programmieraufgaben für Könner
Hier kommen ein paar weitere Programmieraufgaben, die schon etwas anspruchsvoller sind. Entsprechend länger und unübersichtlicher sind die Maschinenprogramme. Daher macht es Sinn, erst ein Assemblerprogramm zu schreiben. Auch dieses kann man mit Stift und Streichhölzern erst mal von Hand auf dem Papier testen. Anschließend kann man es in die KHC-Maschinensprache übersetzen, um es z.B. im KHC-Emulator laufen zu lassen.
Auch hier gilt wieder für alle Übungsaufgaben:
  • Alle Zellen des Hauptspeichers enthalten solange standardmäßig den Wert 0, bis etwas anderes per Tastatureingabe oder durch das Laden einer Speicherkonfiguration hineingeschrieben wird.
  • Nach dem Programmende darf der Datenwert, der dann in einer Speicherzelle steht, von dem ursprünglichen Wert abweichen, der vor der Programmausführung in der Zelle stand.
5. Aufgabe "Ist x < y ?"

Entscheide, ob der Wert der Variablen x kleiner ist als der Wert der Variablen y.

Vor dem Programmstart steht
in Speicherzelle 21 ein beliebiger Wert x, z.B. der Wert 5, und
in Speicherzelle 22 ein beliebiger Wert y, z.B. der Wert 7.
Nach dem Programmende steht
in Speicherzelle 23 der Wert 1, wenn der ursprüngliche Wert von x kleiner als der ursprüngliche Wert von y war,
andernfalls steht in Speicherzelle 23 weiterhin der Initialisierungswert 0.
Hier kann man sich am Grundaufbau des Programms aus der 4. Aufgabe "Ist x = y ?" und an den entsprechenden Tipps orientieren.


6. Aufgabe "x - y = ? , wobei das Ergebnis jetzt auch negativ sein darf"

Berechne die Differenz zweier beliebiger natürlicher Zahlen x und y. Im Gegensatz zu Aufgabe 2 wird jetzt nicht mehr zwingend vorausgesetzt, dass y kleiner oder gleich x sein muss. Das bedeutet, dass das Ergebnis nun auch negativ werden kann. Da im KHC negative Zahlen als Grunddatentypen nicht zugelassen sind, wird das Ergebnis in zwei Speicherzellen ausgegeben: die eine enthält den Betrag der Differenz und die andere das Vorzeichen des Ergebnisses, wobei der Wert 1 für ein negatives Ergebnis steht, der Wert 0 für ein nicht-negatives Ergebnis.

Vor dem Programmstart steht
in Speicherzelle 23 ein beliebiger Wert x, z.B. der Wert 3, und
in Speicherzelle 24 ein beliebiger Wert y, z.B. der Wert 5.
Nach dem Programmende steht
in Speicherzelle 23 der Betrag der Differenz x - y, im Beispiel also der Wert 2,
in Speicherzelle 24 der Wert 1, wenn das Ergebnis negativ ist und der Wert 0, wenn dies nicht der Fall ist.
Da im vorliegenden Beispiel das Ergebnis 3 - 5 = -2, also negativ ist, steht in diesem Fall
in Speicherzelle 23 der Betrag 2 und
in Speicherzelle 23 der Wert 1 für das negative Vorzeichen
Auch hier ist es sinnvoll, wie in den Programmen "Ist x = y ?" und "Ist x < y ?" eine entsprechende Fallunterscheidung durchzuführen.

"x - y = ? (Betrag und Vorzeichen der Differenz für beliebige x und y)" in Assembler 

start:          isz x
                jmp xistungleich0
                jmp xistgleich0
xistungleich0:  isz y
                jmp xundyungleich0
                jmp fertig
xistgleich0: 	isz y
                jmp ynachx
                jmp fertig
xundyungleich0: dec x
                dec y  
                jmp start
ynachx:         isz y
                jmp yrunterxrauf
                jmp yauf1
yrunterxrauf:   inc x
                dec y
                jmp ynachx
yauf1:          inc y
fertig:         stp
x:              5
y:              3


7. Aufgabe "Kleiner Gauß 1 + 2 + 3 + ... + n = ?"

Berechne die Summe der natürlichen Zahlen von 1 bis n, also 1+2+3+...+n.

Vor dem Programmstart steht
in Speicherzelle 23 ein beliebiger Wert n, z.B. der Wert 4.
Nach dem Programmende steht
in Speicherzelle 24 die Summe der natürlichen Zahlen von 1 bis 4, im Beispiel also der Wert 1+2+3+4 = 10.
Das Programm heißt "Kleiner Gauß", weil der berühmte Mathematiker Carl Friedrich Gauß einer Anekdote nach in der Schule schon als kleiner Junge die Summe der natürlichen Zahlen von 1 bis 100 sehr schnell mithilfe einer Formel berechnete, die er selbst entdeckt hatte und die heute als Gaußsche Summenformel bekannt ist.
Lösungsidee
Die Zahl n wird in einer Schleife mehrfach zum Summenwert s addiert, dabei aber bei jedem Schleifendurchgang um 1 verringert. Da bei jedem Additionsdurchgang der Wert in n auf 0 heruntergezählt wird, wird n jedesmal zusätzlich in der Hilfsspeicherstelle h gerettet. Vor dem Zurückspielen dieses geretteten Wertes von h nach n wird er um 1 verringert. So wird also schrittweise erst n nach s geschoben, dann n-1, dann n-2 usw. bis 1.

"Kleiner Gauß 1 + 2 + 3 + ... + n = ?" Lösung in Assembler 

start1:  isz n
         jmp nnachsundh
         jmp htest
nnachsundh: dec n
         inc s
         inc h
         jmp start1
htest:   isz h
         jmp hminus1
         stp
hminus1: dec h
start2:  isz h
         jmp hnachn
         jmp start1
hnachn:  inc n 
         dec h
         jmp start2
n: 4
s: 0
h: 0


8. Aufgabe "Produkt x * y = ?"

Berechne das Produkt zweier Zahlen x und y.

Vor dem Programmstart steht
in Speicherzelle 23 ein beliebiger Wert x, z.B. der Wert 2, und
in Speicherzelle 24 ein beliebiger Wert y, z.B. der Wert 3.
Nach dem Programmende steht
in Speicherzelle 25 das Produkt x * y, im Beispiel also der Wert 2*3 = 6.
Lösungsidee
Der Wert y in M(24) wird so oft zu p in M(25) hinzuaddiert wie es der Wert x in M(23) angibt. Da nach dem einmaligen Hinzuaddieren von M(24) zu M(25) der Wert in M(24) gleich 0 ist, wird der Wert von M(24) bei diesem Hinzuaddieren zu M(25) gleichzeitig auch noch in die Hilfsspeicherzelle h mit M(22) "gerettet" und von dort aus anschließend wieder nach M(24) zurück kopiert. Nach jeder Erhöhung von M(25) um M(24) wird M(23) um 1 verringert. Dies wird solange wiederholt, bis M(23) gleich 0 ist.


9. Aufgabe "Größter gemeinsamer Teiler ggT von x und y = ?"

Berechne den größten gemeinsamen Teiler zweier natürlicher Zahlen x und y, also den ggT von x und y.

Vor dem Programmstart steht
in Speicherzelle 27 eine beliebige natürliche Zahl x, z.B. der Wert 9 und
in Speicherzelle 28 eine beliebige natürliche Zahl y, z.B. der Wert 6.
Nach dem Programmende steht
Speicherzelle 29 der ggT von x und y, im Beispiel also der Wert 3.
Hinweis
Für dieses Maschinenprogramm sollte der KHC mindestens 30 Speicherzellen besitzen.
Lösungsidee

Der ggT zweier natürlicher Zahlen x und y kann mit dem so genannten "Euklidischen Algorithmus" berechnet werden:

"Euklid berechnete den größten gemeinsamen Teiler, indem er nach einem gemeinsamen 'Maß' für die Längen zweier Linien suchte. Dazu zog er wiederholt die kleinere der beiden Längen von der größeren ab. Dabei nutzt er aus, dass sich der größte gemeinsame Teiler zweier Zahlen (oder Längen) nicht ändert, wenn man die kleinere von der größeren abzieht." (siehe Wikipedia: https://de.wikipedia.org/wiki/Euklidischer_Algorithmus)

"ggT von x und y = ?" Lösung in Assembler 

start:          isz x              
                jmp xistungleich0 
                jmp xistgleich0 
xistungleich0:  isz y
                jmp xundyungleich0
                jmp xgroesser y
xistgleich0:    isz y
                jmp ygroesserx
                jmp xundygleich0
xundyungleich0: dec x
                dec y
                inc z		 
                jmp start
xundygleich0:   stp
xgroessery:     isz z
                jmp znachy
                jmp start
znachy:         inc y
                dec z
                jmp xgroessery		 
ygroesserx:     isz z
                jmp znachx
                jmp start
znachx:         inc x
                dec z
                jmp ygroesserx
x: 9 
y: 6
z: 0


Schaffst du das auch ohne Hilfe?

Hier kommen Aufgaben, zu denen es in diesem Lernpfad ganz bewusst keine Tipps und keine Lösungen gibt. Bist du so fit und schaffst es auch ohne Hilfe, diese KHC-Maschinenprogramme zu schreiben? Um dein Programm zu testen, verwende am besten den KHC-Emulator mit den 40 Speicherzellen in diesem Kapitel.


10. Aufgabe "x nach y kopieren"

Kopiere den Inhalt von Zelle x so nach Zelle y, dass nach dem Programmende sowohl in x als auch in y der ursprüngliche Wert von x steht.

Vor dem Programmstart steht
in Speicherzelle x ein beliebiger Wert, z.B. der Wert 4, und
in den Speicherzellen y der Wert 0.
Nach dem Programmende steht
in den Speicherzellen x und y der ursprüngliche Wert von x, also im Beispiel der Wert 4.
11. Aufgabe "x verdoppeln"

Verdopple den Wert in Zelle x.

Vor dem Programmstart steht
in Speicherzelle x ein beliebiger Wert, z.B. der Wert 5.
Nach dem Programmende steht
in Speicherzellen x das Doppelte seines ursprünglichen Wertes, im Beispiel also der Wert 10.
12. Aufgabe "x halbieren mit Rest"

Berechne die Hälfte von x als ganze Zahl mit Rest. Beispiel: 7 / 2 = 3 Rest 1

Vor dem Programmstart steht
in Speicherzelle x ein beliebiger Wert, z.B. der Wert 7, und
in den Speicherzellen y und z der Wert 0.
Nach dem Programmende steht
in Speicherzelle y die Hälfte des ursprünglichen x-Wertes, abgerundet auf eine ganze Zahl, im Beispiel also der Wert 3 und
in Speicherzelle z der Divisionsrest, im Beispiel also der Wert 1, denn 7 / 2 = 3 Rest 1.
13. Aufgabe "x geteilt durch y mit Rest"

Berechne den ganzzahligen Quotient von x geteilt durch y mit Rest, wobei der Versuch einer Division durch 0 abgefangen wird. Beispiel: 14 / 4 = 3 Rest 2

Vor dem Programmstart steht
in Speicherzelle x ein beliebiger Wert, z.B. der Wert 14,
in Speicherzelle y ein weiterer beliebiger Wert, z.B. der Wert 4 und
in den Speicherzellen q, r und f der Wert 0.
Nach dem Programmende steht
in Speicherzelle q der ganzzahlige Quotient von x geteilt durch y, im Beispiel also der Wert 3, da die Zahl 4 dreimal vollständig in die 14 passt, und
in Speicherzelle r der Divisionsrest, im Beispiel also der Wert 2.
In Speicherzelle f steht normalerweise der Wert 0 außer in dem Fall, dass in y der Wert 0 stand, denn durch 0 darf bekanntlich nicht dividiert werden. In diesem Fehlerfall steht in f der Wert 1.
Programm testen im KHC-Emulator
# Alles auf 0 # Ist x < y ? 1: isz 21 2: jmp 4 3: jmp 7 4: isz 22 5: jmp 10 6: jmp 14 7: isz 22 8: jmp 13 9: jmp 14 10: dec 21 11: dec 22 12: jmp 1 13: inc 23 14: stp 21: 5 22: 7 23: 0 # x - y = ? erweitert 1: isz 23 2: jmp 4 3: jmp 7 4: isz 24 5: jmp 10 6: jmp 20 7: isz 24 8: jmp 13 9: jmp 20 10: dec 23 11: dec 24 12: jmp 1 13: isz 24 14: jmp 16 15: jmp 19 16: inc 23 17: dec 24 18: jmp 13 19: inc 24 20: stp 23: 3 24: 5 # Kleiner Gauß 1: isz 23 2: jmp 4 3: jmp 8 4: dec 23 5: inc 24 6: inc 25 7: jmp 1 8: isz 25 9: jmp 11 10: stp 11: dec 25 12: isz 25 13: jmp 15 14: jmp 1 15: inc 23 16: dec 25 17: jmp 12 18: 0 19: 0 20: 0 21: 0 22: 0 23: 4 24: 0 25: 0 # x * y = ? 1: isz 23 2: jmp 4 3: stp 4: isz 24 5: jmp 7 6: jmp 11 7: dec 24 8: inc 25 9: inc 22 10: jmp 4 11: isz 22 12: jmp 14 13: jmp 17 14: dec 22 15: inc 24 16: jmp 11 17: dec 23 18: jmp 1 19: 0 20: 0 21: 0 22: 0 23: 2 24: 3 25: 0


Programm Testen im KHC-Emulator
# Alles auf 0 # ggT von x und y 1: isz 27 2: jmp 4 3: jmp 7 4: isz 28 5: jmp 10 6: jmp 14 7: isz 28 8: jmp 20 9: stp 10: dec 27 11: dec 28 12: inc 29 13: jmp 1 14: isz 29 15: jmp 17 16: jmp 1 17: inc 28 18: dec 29 19: jmp 14 20: isz 29 21: jmp 23 22: jmp 1 23: inc 27 24: dec 29 25: jmp 20 26: 0 27: 9 28: 6 29: 0 30: 0


zurück
Startseite
weiter
Abgerufen von „https://unterrichten.zum.de/index.php?title=Lernpfad_Know-How-Computer/KHC_Programmieraufgaben_Teil_2&oldid=143557“