[MIPS] Tours de Hanoi

**mimosa803** · 15/01/2009, 13h26

Bonjour,

J'ai un devoir à faire et je ne sais pas comment commcer. Je dois réaliser un programme en assembleur (MIPS) qui traite les tours de Hanoi.
Je souhaite que vous m'aidez en me donnant vos idées.

Merci

**Obsidian** · 16/01/2009, 02h06

Envoyé par mimosa803

Bonjour,

J'ai un devoir à faire et je ne sais pas comment commcer. Je dois réaliser un programme en assembleur (MIPS) qui traite les tours de Hanoi.
Je souhaite que vous m'aidez en me donnant vos idées.

Merci

Qu'est-ce qui te pose problème ? Le MIPS ou les tours de Hanoï ?

**mimosa803** · 16/01/2009, 12h29

Bonjour,

Le problème c'est au niveau MIPS, j'ai du mal à comprendre comment je gère les appels récursifs.

**Obsidian** · 16/01/2009, 17h10

Je connais pas beaucoup le MIPS mais apparemment, l'appel de fonction/procédure/sous-programme se fait par l'instruction JAL qui stocke l'adresse de retour dans $31/$ra. Donc un seul niveau de retour. Il faudrait que cette adresse soit en fait empilée, comme le font les autres microprocesseurs.

Si ton CPU ne fait pas ce travail de lui-même, il faut gérer la pile manuellement à l'entrée dans ta fonction. Donc :

au début de ton programme, tu initialises $sp à l'adresse de fin d'un segment de mémoire que tu vas consacrer à ta pile (qui devrait en principe être fonction du nombre de disques en jeu dans ta tour de Hanoï) ;
à l'entrée dans ta fonction « Hanoï », tu empiles l'adresse de retour stockée dans $ra, en décrémentant le pointeur de pile $sp de 4 octets (taille d'une adresse) et en stockant le contenu de $ra à l'adresse nouvellement pointée par $sp ;
à la fin de ta fonction, tu recharges dans $ra l'adresse pointée par $sp, tu fais remonter le pointeur de pile $sp de 4 octets, et tu sors avec JR $ra.

**mimosa803** · 16/01/2009, 22h52

merci pour votre réponse, j'ai essayé de réaliser le programme et j'espère que vous m'aidez à trouver l'erreur :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
.data
 
chaine:  		.asciiz "Donner un nombre de disques < 5  : "
deplacerdisque: .asciiz "Deplacer le disque de "
vers: 			.asciiz " vers "
nln: 			.asciiz "\n"
piquet1: 		.asciiz "Piquet-A"
piquet2: 		.asciiz "Piquet-B"
piquet3: 		.asciiz "Piquet-C"
 
.text
.globl main
 
main: 
 
addi $v0,$zero,4
la $a0,chaine
syscall
 
addi $v0,$zero,5
syscall
 
move $a0,$v0  	#je sauvegarde dans a0 (argument de hanoi) le nombre de disques
 
subu $sp,$sp,28 # réserver 7 mots dans la pile
 
sw $ra,24($sp) 	# sauver l'adresse de retour
 
la $a1,piquet1 	# passer à hanoi 4 variables y compris le a0
la $a2,piquet2 
la $a3,piquet3 	# le noms des piquets est dans $a1-$a3
 
jal hanoi 		# appeler la fonction hanoi
 
lw $ra,24($sp) 	# récupérer l'addresse de retour
addi $sp,$sp,28 # restaurer la pile
jr $ra 			# retour à l'appelant (exit)
 
hanoi:
addi $sp,$sp,-20 # 
sw $ra,0($sp) 	# sauver l'adresse de retour
sw $a0,4($sp) 	# sauver n
sw $a1,8($sp) 	# sauver piquet A
sw $a2,12($sp) 	# sauver piquet B
sw $a3,16($sp) 	# sauver piquet C
 
li $t0,1 		# mettre $t0 = 1 pour le comparer à n (nombre de disques)
bne $t0,$a0,recursion # if (n =/= 1) recursion
 
li $v0,4 # print
la $a0,deplacerdisque
syscall 
 
move $a0,$a1 # copier piquet A dans a0
syscall
 
la $a0,vers
syscall
 
move $a0,$a3 # copy piquet C dans a0
syscall
 
la $a0,nln # faire un retour à la ligne
syscall
 
fincas: # sortir du code
 
lw $ra,0($sp) # récupérer les variables
lw $a0,4($sp) # récupérer n
lw $a1,8($sp) # récupérer piquet A
lw $a2,12($sp) # récupérer piquet B
lw $a3,16($sp) # récupérer piquet C
addi $sp,$sp,20 # restaurer la pile
jr $ra # retourner
 
recursion:
lw $a0,4($sp) # récupérer n 
addi $a0,$a0,-1 # n=(n-1)
lw $a1,8($sp) # récupérer piquet A
lw $a2,16($sp) # récupérer piquet C
lw $a3,12($sp) # récupérer piquet B
jal hanoi # appeler la fonction hanoi
 
li $v0,4 # print
la $a0,deplacerdisque
syscall
 
move $a0,$a1 # copier piquet A dans a0
syscall
la $a0,vers
syscall
 
move $a0,$a3 # copier piquet C dans a0
syscall
la $a0,nln 
syscall
 
lw $a0,4($sp) # récupérer n
addi $a0,$a0,-1 # n=(n-1)
lw $a1,12($sp) # récupérer piquet B
lw $a2,8($sp) # récupérer piquet A
lw $a3,16($sp) # récupérer piquet C
jal hanoi # call hanoi
j fincas # goto exit code (return)

**Obsidian** · 18/01/2009, 01h04

J'ai jeté un oeil, mais pas encore analysé ton programme en détail. Cependant, pourquoi utilises-tu deux blocs différents « hanoi » et « recursion » ? La nature même d'une fonction récursive est de s'appeler elle-même.

En principe, tu ne dois avoir qu'un seul bloc d'affichage « Piquet X vers piquet Y ».

**mimosa803** · 18/01/2009, 01h32

Bonjour,

merci pour votre aide mais est ce que vous avez une proposition ?

**Obsidian** · 18/01/2009, 15h35

Ce qu'il y a dans « recursion » devrait suffire à résoudre le problème, et devrait s'appeler « hanoi ». En gros :

1) Enregistrement des paramètres dans le cadre de pile local.

2) Bouger n-1 disques du poteau de départ au poteau intermédiaire. Pour ce faire, se rappeler soi-même avec n=n-1 et inverser poteau d'arrivée et poteau intermédiaire.

3) Bouger le dernier le disque du poteau de départ au poteau d'arrivée et provoquer l'affichage.

4) Bouger les n-1 disques du poteau intermédiaire au poteau d'arrivée. Même chose qu'en 1) : a1, a2, a3 valent respectivement Intermédiaire, Départ et Arrivée.

5) Récupération des paramètres dans le cadre de pile, vidage de la pile, et sortie.

Au niveau implémentation, 2) et 4) ne doivent avoir lieu que si n>1. Place alors le test que utilises pour sauter vers « récursion » en tête de ces étapes et sers-t'en pour passer directement aux suivantes si n<=1.

Pour ne pas te tromper dans les piquets, souviens-toi qu'à l'étape 1), tu as sauvegardé Départ, Intermédiaire et Arrivée dans 8($sp), 12($sp) et 16($sp). Tu peux les y relire directement pour définir l'ordre des piquets à chaque étape ( 2), 3) et 4) ).

PS: « li », je ne connais pas.

**mimosa803** · 19/01/2009, 13h29

Bonjour,

li sert charger un registre par une valeur immédiate.

Bon, j'ai exécuté mon code mais il ne donne pas le bon résultat.

Voilà l'affichage que j'ai obtenu :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Donner un nombre de disques < 5  : 2
Deplacer le disque de Piquet-A vers Piquet-B
Deplacer le disque de Piquet-A vers Piquet-B
Deplacer le disque de Piquet-B vers Piquet-C

Alors que normalement, je dois avoir :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Donner un nombre de disques < 5  : 2
Deplacer le disque de Piquet-A vers Piquet-B
Deplacer le disque de Piquet-A vers Piquet-C
Deplacer le disque de Piquet-B vers Piquet-C

**Obsidian** · 19/01/2009, 14h05

Envoyé par mimosa803

Bon, j'ai exécuté mon code mais il ne donne pas le bon résultat.

As-tu modifié ton code pour prendre en compte les remarques que j'ai postées ? Si oui, montre-nous tes modifs.

Tout ce qu'il te faut, c'est une seule fonction de Hanoï recevant le nombre de disques à gérer, le piquet de départ dans $a0, le piquet intermédiaire dans $a1 et le piquet d'arrivée dans $a2.

Au premier appel, depuis ta fonction principale, tu les initialises respectivement à A, B et C. C'est la fonction elle-même qui se rappelera elle-même en permutant les piquets qu'il faut, mais sans savoir qu'il s'agit de A, B ou C. À l'étape 2), $a0 reste $a0, $a1 doit devenir $a2 et $a2 doit devenir $a1. À l'étape 4) $a0 doit correspondre au $a1 initial, $a1 au $a0 initial et $a2 au $a2 inital aussi (d'où nécessité de recharger).

À l'entrée dans ta fonction, tu sauvegardes tous ces registres à des places fixes dans ta pile. Tu n'as qu'à les recharger depuis cette place, quand c'est nécessaire, à l'entrée des phases 2), 3) et 4).

**mimosa803** · 19/01/2009, 19h14

Bonsoir,

En fait, j'ai utilisé deux fonctions hanoi et récursion parce que j'en ai besoin : je teste sur la valeur de n (nombre de disques), si il est égale à 1 j continue sinon je saute vers récursion. Est ce que vous pouvez m'aidez en écrivant votre idée en MIPS, c'est pas très clair pour moi.

Merci

**droggo** · 19/01/2009, 20h08

Heo,

Envoyé par mimosa803

Bonsoir,

En fait, j'ai utilisé deux fonctions hanoi et récursion parce que j'en ai besoin : je teste sur la valeur de n (nombre de disques), si il est égale à 1 j continue sinon je saute vers récursion.

Non, tu n'en as pas besoin, comme te l'a déjà dit Obsidian.
Ce test est tout simplement la condition d'arrêt de la récursion, et en fait donc partie.

**Obsidian** · 21/01/2009, 13h46

Envoyé par mimosa803

sinon je saute vers récursion.

Est ce que vous pouvez m'aidez en écrivant votre idée en MIPS, c'est pas très clair pour moi.

Pour compléter ce que dit Droggo, si tu te trouves dans une fonction et qu'en cas de n>1, tu sautes vers une autre fonction, alors, par définition, ta fonction n'est pas récursive.

C'est vers toi-même qu'il faut sauter. Il faut donc ré-entrer dans « hanoi » après avoir adapté les paramètres.

[MIPS] Tours de Hanoi

Autres architectures Assembleur

Discussions similaires

Partager

Partager