[Recursivite] function/procedure d'une suite logique

Version imprimable

01/03/2005, 13h43
Tata

[Recursivite] function/procedure d'une suite logique

Bonjour,
Je ne suis pas encore familier de ces boards, et j espere que je post au bon endroit (si c'est pas le cas je suis desole).

ma suite est:
1
11
21
1211
111221
312211
etc

ex de construction de ligne: ligne 4 -> 1211. elle est constituee de un 1, un 2 et deux 1. donc la ligne 5 -> 111221.

Je dois construire une function/procedure recursive qui renvoit les 10 1eres lignes.

Si vous pouviez me donner une piste (faute de constuire tout le programme, car je concois tres bien que vous n'etes pas la pour faire mon boulot ). ca fait 1 semaine que je lutte sur cet exo, et la j'ai épuisé tout ce que je savais.

Merci d'avance.

ps: c'est un copie/colle de la section DELPHI, à priori c'est plus appropié ici.
01/03/2005, 14h16
lalystar
Je ne vois pas du tout comment le faire de manière récursive ? Peut-être en commencant par la fin ? C'est un peu forcé...

Sinon pour moi, on part de "1".
On parcourt la chaine en comptant le nb de caractères consécutifs identiques : ca nous donne 11.
On recommence avec 11 comme tu l'as décrit. On dispose d'une fonction G qui effectue ce traitement.

Si tu le veux de manière récursive : si on a une fonction F qui prend en entrée un indice n, rang de la chaine qu'on souhaite calculer.
Code:

1 2 3 4 5 6 7 8 9 function F(n) { if n = 1 then return 1; else tmp := F(n-1) return G(tmp); end if; end;
Ca te convient ?

Laly.
01/03/2005, 14h28
Tata

G(tmp) renvoie quoi pour n = 5 par exemple? je suis pas sur d'avoir tout saisi.

c'est simple si tous les nombres de la chaine sont identiques, mais comme on peut avoir un '11121' je peux pas juste utiliser un F := F(n-1) meme avec du code derriere. parceke ca me sortirait un F (n) du type := '3121111211' et pas juste '311211'. j ai egalement tente d'utiliser du copy parcek on peut remarquer ke chaque fin du string fini par les 2 derniers caracteres du F(n-2). mais la encore j'arrive pas a grand chose pour le centre de la chaine.

en bref comme ca doit se voir, je suis perdu :?

Ce qu'il faut savoir, c'est quel est le mécanisne pour obtenir la ligne n à partir de la ligne n-1, après ça, c'est tout simple à coder.

Donc généraliser le mécanisne ci-dessous pour une ligne quelconque, il faut parcourir la chaine pour compter les nombre identiques et générer la ligne suivante.

Citation:

ex de construction de ligne: ligne 4 -> 1211. elle est constituee de un 1, un 2 et deux 1. donc la ligne 5 -> 111221.

Il faut une routine de conversion ligne n-1 vers ligne n, et que tu passe aussi un parametre pour savoir si il faut encore transformer la chaine.

En gros
Code:

1 2 3 4 5 6 7 8 9 funtion F(n: Cardinal; ligne: string):string; begin if n = 1 then // ou 0 à verifier (condition d'arrêt) result := ligne else // Mettre dans ligne la transformatation en ligne + 1. //... result := F(n - 1, ligne); end;

Il te faut une fonction de transformation,

qui a une chaine d'entiers "111221" représentant ta ligne associe la ligne suivante.

Disons que ta chaine est dans c[0...n] ou n+1 est la longeur. Je te donne le code dans le cas ou tu n'as pas de chaine d'identiques de plus de 9 (pour plus, il suffit d'éclater ton nombre en chaine de chiffre grace à la partie entière du log base 10)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 int val=c[0] int compteur=1 int long=0 int position=0 while(long<n){ long=long+1 if(c[long]<>val){ newc[position]=compteur newc[position+1]=val position=position+2 val=c[long] compteur=1 } else{ compteur=compteur+1 } } newc[position]=compteur newc[position+1]=val

salut,
ton problème me fait triper donc je m'y met voilà une solution je te le met en algo français puis en java.

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
36
37
38
39
40
41
42
43
44
45
 
 
procedure recursive( ligne_restante : entier,//nombre de ligne qu'il reste à faire
	ligne_precedente : chaine de caratère, //la ligne précédente
	resultat_suivant : tableau de chaine de caratère)//le tableau à remplir pour
							//l'affichage,si on affiche directement 	
 
						       //dans la procedure on peut enlever ce 		
 
						      //paramètre
debut
	nombre_de_fois : entier;//nombre de fois que le chifre est à la suite
	le_caractete_tester : caractere//le caractère que l'on test
	compteur : entier//pour savoir ou est la fin de la cahine
	resultat : chaine de caractete
 
	//initialisation
	nombre_de_fois = 0
	compteur = 0 
	resultat  = null
	le_caractete_tester = ligne_precedente[0]//on prend le premier cara
 
	//on remplis le tableau avec la ligne précédente ou on peut afficher directement(dans
	// ce cas on a pas besoin de resultat_suivant comme paramètre
	resultat_suivant[ligne_restante-1] = ligne_precedente 
 
 
	//on parcours toute la chaine
	tant que compteur < ligne_precedente.longueur alors
		si le_caractere_tester <> ligne_precedente[compteur] alors
			resultat = resultat + nombre_de_fois + 						
 
		le_caractere_a_tester
			nombre_de_fois = 0
		fin si
		le_caractere_a_tester = ligne_precedente[compteur]
		compteur = compteur+1
		nombre_de_fois = 0
 
	fin tant que
	resultat = resultat + nombre_de_fois + le_caractere_a_tester
	si ligne_restante <> 0 alors
		recherche( ligne_restante-1,resultat,resultat_suivant)
	finsi
fin procedure

utilisation de la procédure
si on affiche directement dans la procedure on doit juste faire

Code:

1
2
3
4
 
debut
recursive(10,'1')
fin

sinon il faut faire l'affichage
afficher() représente une fonction pour afficher des chaine de cara

Code:

1
2
3
4
5
6
7
8
 
debut
affiche : tableau de chaine de caratère
recursive(10,'1',affiche)
pour i de 0 à 9 faire
afficher(affiche[i])
fin pour
fin

voila le code java

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
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
 
 
import java.util.*;
public class Aide {
 
	//on affiche diretement dans la procedure
	public static void recur_affiche(
		int ligne_restante,
		String ligne_precedente) {
		int nombre_de_fois;
		String le_caractete_tester;
		int compteur;
		String resultat;
 
		resultat = "";
		nombre_de_fois = 0;
		compteur = 0;
 
		System.out.println(ligne_precedente);
		le_caractete_tester = ligne_precedente.charAt(0) + "";
		while (compteur < ligne_precedente.length()) {
			if (le_caractete_tester
				.compareTo(ligne_precedente.charAt(compteur) + "")
				!= 0) {
				resultat = resultat + nombre_de_fois + le_caractete_tester;
				nombre_de_fois = 0;
			}
			nombre_de_fois = nombre_de_fois + 1;
			le_caractete_tester = ligne_precedente.charAt(compteur) + "";
			compteur = compteur + 1;
		}
		resultat = resultat + nombre_de_fois + le_caractete_tester;
 
		if (ligne_restante > 1) {
			recur_affiche(ligne_restante - 1, resultat);
		}
	}
 
	//on met les resultats dans un tableau qui sera afficher plus tard
	public static void recur(
		int ligne_restante,
		String ligne_precedente,
		Vector resultat_suivant) {
		int nombre_de_fois;
		String le_caractete_tester;
		int compteur;
		String resultat;
 
		resultat = "";
		nombre_de_fois = 0;
		compteur = 0;
 
		resultat_suivant.add(ligne_precedente);
		le_caractete_tester = ligne_precedente.charAt(0) + "";
		//on prend le premier cara
		while (compteur < ligne_precedente.length()) {
			if (le_caractete_tester
				.compareTo(ligne_precedente.charAt(compteur) + "")
				!= 0) {
				resultat = resultat + nombre_de_fois + le_caractete_tester;
				nombre_de_fois = 0;
			}
			nombre_de_fois = nombre_de_fois + 1;
			le_caractete_tester = ligne_precedente.charAt(compteur) + "";
			compteur = compteur + 1;
		}
		resultat = resultat + nombre_de_fois + le_caractete_tester;
 
		if (ligne_restante > 1) {
			recur(ligne_restante - 1, resultat, resultat_suivant);
		}
	}
 
	public static void main(String[] args) {
 
		//utilisation de la procedure qui met le résultat dans un tableau
		Vector affiche = new Vector();
		Aide.recur(10, "1", affiche);
		for (int i = 0; i <= 9; i++) {
			System.out.println((String) affiche.elementAt(i));
		}
 
		//utilisation de la procédure qui affiche les résultats
		recur_affiche(10, "1");
 
	}
}

jespère que ça va te servir, dis moi si j'ai pas été clair
@++

02/03/2005, 15h00
Tata

tu m autorises a te mailer? ;)
02/03/2005, 16h13
le--handballeur

no pb,mon adresse est dispo sur mon profil si t'as besoin
mais mes compétences se limitent à java et C(et C++ éventuellement).
Je crois que toi c'est plutot delphi mais si je peu t'aider se serra avec plaisir.