Pascal Zahl

Kirby.exe

Top Contributor
Also ich mache gerade als Übung in Assembler die Aufgabe die Pascal Zahlen zu implementieren. Soweit ich habe ich das ungefähre Gerüst fertig sowie die ersten beiden if's(was jetzt nicht besonders kompliziert war) jedoch bin ich verwirrt wie ich die Rekursion schachteln sollte :(

Die Rekursion bei den Pascal Zahlen ist ja: pas(n-1,k)+pas(n-1,k-1).
Was ich mich dabei Frage ist, soll ich erst beide Rekursiven Aufrufe tätigen und Anschließend addieren?

Also irgendwie so?:
Java:
public void pas(int n, int k){
    if(n == 0 || n == 1){
        return 1;
    }else if(k == 0 || k == n){
        return 1;
    }else{
        int a = pas(n-1,k);
        int b = pas(n-1,k-1);
        return (a+b);
    }
}
 
Zuletzt bearbeitet:
K

kneitzel

Gast
Die Rekursion bei den Pascal Zahlen ist ja: pas(n-1,k)+pas(n-1,k-1).
Was ich mich dabei Frage ist, soll ich erst beide Rekursiven Aufrufe tätigen und Anschließend addieren?

Wie soll es denn auch anders gehen? Wie willst Du etwas addieren, was Du nicht hast?

Aber es ist egal, wie Du es schreibst. Du kannst es also so schreiben:
Java:
        int a = pas(n-1,k);
        int b = pas(n-1,k-1);
        return (a+b);

oder so:
Java:
        return pas(n-1,k) + pas(n-1,k-1);

Um das letztere auszuführen müssen die Teilausdrücke von links nach rechts evaluiert werden um dann anschließend die Operation auszuführen. (JLS 15.7 Evaluation Order: https://docs.oracle.com/javase/specs/jls/se13/html/jls-15.html#jls-15.7)
Und in 15.7.2 wird auch klar gesagt, dass die Operanden erst ermittelt werden, ehe die Operation ausgeführt wird (Evaluate Operands before Operation: https://docs.oracle.com/javase/specs/jls/se13/html/jls-15.html#jls-15.7.2).

Oder habe ich Dich missverstanden und Deine Frage dreht sich um etwas anderes?
 

Kirby.exe

Top Contributor
Wie soll es denn auch anders gehen? Wie willst Du etwas addieren, was Du nicht hast?

Aber es ist egal, wie Du es schreibst. Du kannst es also so schreiben:
Java:
        int a = pas(n-1,k);
        int b = pas(n-1,k-1);
        return (a+b);

oder so:
Java:
        return pas(n-1,k) + pas(n-1,k-1);

Um das letztere auszuführen müssen die Teilausdrücke von links nach rechts evaluiert werden um dann anschließend die Operation auszuführen. (JLS 15.7 Evaluation Order: https://docs.oracle.com/javase/specs/jls/se13/html/jls-15.html#jls-15.7)
Und in 15.7.2 wird auch klar gesagt, dass die Operanden erst ermittelt werden, ehe die Operation ausgeführt wird (Evaluate Operands before Operation: https://docs.oracle.com/javase/specs/jls/se13/html/jls-15.html#jls-15.7.2).

Oder habe ich Dich missverstanden und Deine Frage dreht sich um etwas anderes?
Naja also ich muss den Kram ja in Assembler machen xD Deswegen war ich mir nicht ganz sicher ob meine Idee ganz richtig war :)
 

Kirby.exe

Top Contributor
Also ich schicke einfach meinen bisherigen Assembler Code:

Code:
#Einlesen von n
addi zero t0 1
sysmove exc t0
syscall

#Einlesen von k
addi zero t1 2
sysmove exc t0
syscall

#Zahlen in Arbeitsregister verschieben
sysmove a0 exc
sysmove a1 exc

#Unterprogrammaufruf
ldpc ra
addi ra ra 3
jmp pascal


#Ausgabe des Ergebnis
sysmove O[0] v1
addi zero t6 6
sysmove exc t6
syscall

#Reguläre Beenden des Programms
ende:
sysmove exc zero
syscall







############################################

pascal:

#Retten der register auf den Stack
addi SP SP -12
sto SP ra 12
sto SP a0 8
sto SP a1 4


#Falls n = 0 oder n = 1
beq zero a0 first
beq t0 a0 first  

#Falls k = 0 oder k = n
beq zero a1 second
beq a0 a1 second

#Else
jmp third


#Cases

first:
addi zero v0 1
ldd SP a1 4 # a1 vom Stack holen
ldd SP a0 8 # a0 vom Stack holen
ldd SP ra 12 # ra vom Stack holen
addi SP SP 12
stpc ra


second:
addi zero v1 1
ldd SP a1 4 # a1 vom Stack holen
ldd SP a0 8 # a0 vom Stack holen
ldd SP ra 12 # ra vom Stack holen
addi SP SP 12
stpc ra


third:      # <------ Hier ist der Else-Zweig mit dem rekursiven aufruf
ldpc ra
addi ra ra 3
jmp pascal

ldpc ra
addi ra ra 3
jmp pascal

add v0 v1 v1
ldd SP a1 4 # a1 vom Stack holen
ldd SP a0 8 # a0 vom Stack holen
ldd SP ra 12 # ra vom Stack holen
addi SP SP 12
stpc ra
 

mihe7

Top Contributor
Erstmal aufdröseln:
Java:
public int pas(int n, int k){
    int a = 1;
    int b;
    if (n == 0 || n == 1 || k == 0 || k == n) { 
        return a;
    }
    n--;
    a = pas(n, k);
    b = a;
    k--;
    a = pas(n, k);
    a+=b;
    return a;
}

Dann ist a das Ausgaberegister. Die Register n, k und b müssen dagegen gesichert werden.

Im Spoiler der Assemblercode (ich hoffe mal, dass mit der Kopiererei jetzt nix durcheinander gekommen ist...)
Code:
addi zero t0 1
sysmove exc t0
syscall


addi zero t1 2
sysmove exc t1
syscall


sysmove a0 I[0]
sysmove a1 I[1]


ldpc ra
addi ra ra 3
jmp pascal

sysmove O[0] v0
addi zero t6 6
sysmove exc t6
syscall


ende:
sysmove exc zero
syscall



pascal:

# Register retten
addi SP SP -16
sto SP ra 16
sto SP a0 12
sto SP a1 8
sto SP v1 4

# a = 1
addi zero v0 1

# if (n == 0 || n == 1 || k == 0 || k == n)
beq zero a0 rtn
beq t0 a0 rtn
beq zero a1 rtn
beq a0 a1 rtn

# else-Zweig

# n--; a = pas(n,k);
subi a0 a0 1
ldpc ra
addi ra ra 3
jmp pascal

# b = a
addi zero v1 0
addi v0 v1 0

# k--; a = pas(n,k);
subi a1 a1 1
ldpc ra
addi ra ra 3
jmp pascal

# a += b
add v0 v1 v0

# return a
rtn:
ldd SP v1 4 
ldd SP a1 8
ldd SP a0 12 
ldd SP ra 16 
addi SP SP 16
stpc ra
 

Kirby.exe

Top Contributor
Erstmal aufdröseln:
Java:
public int pas(int n, int k){
    int a = 1;
    int b;
    if (n == 0 || n == 1 || k == 0 || k == n) {
        return a;
    }
    n--;
    a = pas(n, k);
    b = a;
    k--;
    a = pas(n, k);
    a+=b;
    return a;
}

Dann ist a das Ausgaberegister. Die Register n, k und b müssen dagegen gesichert werden.

Im Spoiler der Assemblercode (ich hoffe mal, dass mit der Kopiererei jetzt nix durcheinander gekommen ist...)
Code:
addi zero t0 1
sysmove exc t0
syscall


addi zero t1 2
sysmove exc t1
syscall


sysmove a0 I[0]
sysmove a1 I[1]


ldpc ra
addi ra ra 3
jmp pascal

sysmove O[0] v0
addi zero t6 6
sysmove exc t6
syscall


ende:
sysmove exc zero
syscall



pascal:

# Register retten
addi SP SP -16
sto SP ra 16
sto SP a0 12
sto SP a1 8
sto SP v1 4

# a = 1
addi zero v0 1

# if (n == 0 || n == 1 || k == 0 || k == n)
beq zero a0 rtn
beq t0 a0 rtn
beq zero a1 rtn
beq a0 a1 rtn

# else-Zweig

# n--; a = pas(n,k);
subi a0 a0 1
ldpc ra
addi ra ra 3
jmp pascal

# b = a
addi zero v1 0
addi v0 v1 0

# k--; a = pas(n,k);
subi a1 a1 1
ldpc ra
addi ra ra 3
jmp pascal

# a += b
add v0 v1 v0

# return a
rtn:
ldd SP v1 4
ldd SP a1 8
ldd SP a0 12
ldd SP ra 16
addi SP SP 16
stpc ra
Dankeee :)
 

Neue Themen


Oben