Aide en algo

Version imprimable

12/08/2009, 13h18
haribooo

Aide en algo

Bonjour tout le monde, tout d'abord je me présente puisque c'est mon tout premier post. Je m'appelle Calude,j'ai 26ans et j'habite en France, plus précisément à Bordeaux :)

Je dois effectuer des exercices d'algo ... et j'ai un peu de peine ...

Je viens donc solliciter l'aide de quelqu'un qui pourrait m'éclairer dans mes petits soucis ...

Il s'agit donc des sujets suivants :

- Quicksort
- Récursivité terminale
- Charge du stack

C'est environ 10 petits exercices ...

Merci beaucoup à ceux qui prendront un peu le temps de me répondre ...
12/08/2009, 15h23
pseudocode

Nous avons pour politique de ne pas faire les exercices à la place des gens.

Cependant nous répondrons à toute question précise que tu formuleras (dans la limite de nos connaissances :P).

Pour commencer, je dois transformer une procédure identique à celle ci-postée, sans utiliser de formant de boucle. Je ne dois également pas, emploier aucune entité globale du module qui la contient.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
	PROCEDURE Iteration (n : INTEGER) : INTEGER;
	VAR
		k, s: INTEGER;
	BEGIN (*Iter*)
		k:= n; s:=0;
		WHILE k > 0 DO
			REPEAT s:=s+k UNTIL s > n;
			k:=k-2
		END;
		RETURN s
	END Iter;
 
....

Voici ce que j'ai fais .... mais j'obtiens pas le bon résultat :

Code:

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
 
	PROCEDURE Iteration2 (n : INTEGER) : INTEGER;
	VAR
		k, s: INTEGER;
 
		PROCEDURE Rep (n : INTEGER) : INTEGER;
		BEGIN (*Rep*)
			s := s+k;			
			IF ~(s > n) THEN 	
				s := Rep(n);
			END;
			k := k -2;
			RETURN s
		END Rep;
 
		PROCEDURE Whi (n : INTEGER) : INTEGER;
		BEGIN (*Whi*)
			IF k > 0 THEN n := Rep(n); n := Whi(n) END;
			RETURN n
		END Whi;
 
	BEGIN (*Iter2*)		
		k:= n; s:=0;
		s := Whi(k);
		RETURN s;
	END Iter2;
 
	PROCEDURE Do*;
	BEGIN (*Do*)
		Out.Int(Iteration(3), 5); 
		Out.Ln; 
		Out.Int(Iteration2(3), 5); 
	END Do;
 
....

Ce n'est pas la mort .... mais je suis coincé ... si quelqu'un pouvait m'éclairer sur ca, ce serais super ...

merci

13/08/2009, 12h10
pseudocode

Citation:

Envoyé par haribooo

Pour commencer, je dois transformer une procédure identique à celle ci-postée, sans utiliser de formant de boucle.

Sans utiliser aucune boucle ? 8O.

Ton idée c'est visiblement de remplacer la boucle "while" par un appel récursif. Est-ce vraiment le but de l'exercice ? Le code final sera plus complexe que l'énoncé. :aie:

L'alternative c'est de décortiquer l'algo pour comprendre ce qu'il calcule (mathématiquement). C'est plus compliqué a faire, mais le code final sera simple.

Bref, est-ce que le but de l'exercice c'est de faire du triturage de "code" ou du triturage de "math" ?
13/08/2009, 13h35
haribooo

Tu as tout compris .... c'est bien dans la transformer en récursif ... donc, triturage de code ...
(Ce que j'ai essayé de faire dans la code que j'ai donné en 2e) ...

Mais celui-ci ne fonctionne pas .... Je ne trouve pas mon erreur ...
13/08/2009, 13h53
pseudocode

Citation:

Envoyé par haribooo

Tu as tout compris .... c'est bien dans la transformer en récursif ... donc, triturage de code ...
(Ce que j'ai essayé de faire dans la code que j'ai donné en 2e) ...

Mais celui-ci ne fonctionne pas .... Je ne trouve pas mon erreur ...

Ton instruction "k := k - 2;" devrait être dans la boucle WHILE, donc dans la procedure "Whi()".

Tel que tu l'as codé, tu vas exécuter cette instruction autant de fois que tu fais des boucles REPEAT.
13/08/2009, 13h57
haribooo

Citation:

Envoyé par pseudocode

Ton instruction "k := k - 2;" devrait être dans la boucle WHILE, donc dans la procedure "Whi()".

Je viens de le tester .... mais ça ne fonctionne pas. Le résultat obtenu ne correspond toujours pas au résultat obtenu avec la procédure de l'énoncé.

Citation:

Envoyé par haribooo

Je viens de le tester .... mais ça ne fonctionne pas. Le résultat obtenu ne correspond toujours pas au résultat obtenu avec la procédure de l'énoncé.

Il y aussi des écrasements curieux de la variable "n" dans ton code, genre "n := Rep(n);". Normalement "n" est une constante dans l'énoncé, donc tu n'as pas de raison de la modifier.

En java, j'obtiens ceci:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 int k,s; int iter(int n) { k=n; s=0; whileloop(n); return s; } void whileloop(int n) { if (k>0) { repeatloop(n); k=k-2; whileloop(n); } } void repeatloop(int n) { s=s+k; if (!(s>n)) repeatloop(n); }
ce qui me donne bien les mêmes resultats que:
Code:

1 2 3 4 5 6 7 8 9 int iter(int n) { int k,s; k=n;s=0; while (k>0) { do {s=s+k;} while(!(s>n)); k=k-2; } return s; }

13/08/2009, 14h27
haribooo

Merci ...

Je vais jeter un coup d'oeil à ton code ... et voir si j'arrive à le refaire en pascal ...

je te tiens au courant dans les minutes qui suivent ...
13/08/2009, 14h34
haribooo

AIE AIE AIE .... merci :ccool:... tu avais raison dès le début .... je devais bouger le k := k -2; dans la procédure whi() .....

mais il fallait que le le place entre l'appel des 2 procédures comme tu l'as fais dans ton code ...

Moi je l'ai mise après, pensant que c'était égal ....

Bref .... merci .... c'était vraiment une erreur toute :aie::aie: ........
13/08/2009, 15h24
pseudocode

Citation:

Envoyé par haribooo

AIE AIE AIE .... merci :ccool:... tu avais raison dès le début .... je devais bouger le k := k -2; dans la procédure whi() .....

mais il fallait que le le place entre l'appel des 2 procédures comme tu l'as fais dans ton code ...

Moi je l'ai mise après, pensant que c'était égal ....

Bref .... merci .... c'était vraiment une erreur toute :aie::aie: ........

Sinon, pour le fun, l'algo se résume a une formule de math : s = 2*n + Somme jusqu'a n-2 des nombre pairs ou impairs (suivant la parité de n)
13/08/2009, 15h34
haribooo

excellent .... (j'ai quand même du tester ca sur une feuille avec mon stylo ... :roll: )

tu vas me dire que t'as vu ca comme ca ? :ccool:

joli joli ....
13/08/2009, 15h43
pseudocode
Citation:

Envoyé par haribooo

tu vas me dire que t'as vu ca comme ca ? :ccool:

J'ai surtout remarqué que la boucle "REPEAT/UNTIL" n'est pas franchement utile.
- La première fois (quand k=n), on va passer 2 fois dedans => s=2*n
- Les fois suivantes, on passe une fois et on sort (car s restera toujours plus grand que n)

Ce qu'on peut doncc réécrire comme cela:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 BEGIN (*Iter*) k:= n; s:=0; s:=s+k s:=s+k k:=k-2 WHILE k > 0 DO s:=s+k; k:=k-2 END; RETURN s END Iter;