Discussion :

[vmolines]

Bonjour,

je souhaitais faire une fonction qui retourne la chaine suivant celle passée en paramètre. Exemple :

A > B
Z > BA
AAZ > ABA
...

Je me suis dit facile ,c'est juste un changement de base alors j'ai décomposé :

. Transformation de la chaine en entier base 10
. Ajout de l'incrément (1 par défaut mais on peut le passer en paramètre)
. Transorfmation de l'entier en chaine

Mais je me bute à un problème et m'embrouille dans la compréhension. Voici l'algo que j'ai fait :

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
FONCTION sIncrementeChaine(psChaine est une chaîne, psAlphabet est une chaîne = "ABCDEFGHIJKLMNOPQRSTUVWXYZ", pnStep = 1)
 
nChaineDansBase est un entier sans signe sur 8 octets = 0
nIndice est un entier
nPuissance est un entier = 0
nBase est un entier = Taille(psAlphabet)
sChaineResultat est une chaîne = ""
 
//Conversion de la chaine en entier
POUR nIndice = Taille(psChaine) A 1 PAS -1
	nChaineDansBase += Position(psAlphabet,psChaine[[nIndice]]) * Puissance(nBase,nPuissance)
	nPuissance++
FIN
 
//Ajout de l'incrément
nChaineDansBase += pnStep
 
//Conversion de l'entier dans la base
TANTQUE nChaineDansBase <> 0 
	//Recherche de la puissance max
	nPuissance = 0
	TANTQUE PartieEntière(nChaineDansBase/Puissance(nBase,nPuissance + 1)) <> 0
		nPuissance++
	FIN
	sChaineResultat = sChaineResultat + psAlphabet[[PartieEntière(nChaineDansBase/Puissance(nBase,nPuissance))]]
	//On retranche la partie convertie
	nChaineDansBase = nChaineDansBase - (PartieEntière(nChaineDansBase/Puissance(nBase,nPuissance)) * Puissance(nBase,nPuissance))
FIN
 
RENVOYER sChaineResultat

Comme vous pouvez le voir, j'ai aussi l'alphabet en paramètre qui me permettra de le changer au besoin. Ainsi je définit la base comme la taille de l'alphabet.

L'opération de conversion de la chaine en entier fonctionne car j'ai bien :

Z = 26
A = 1 (c'est là ou je sens l'embrouille...)
BA = 27

Le problème est qu'avec mon algo, quand j'incrémente :

- Y je tombe sur A : Y = 25 et on l'incrémente à 26. La conversion donne bien une puissance de 1 avec un reste de 0 et on tombe sur A...

Est ce que vous voyez où je me perd ?

[Médiat]

Avec A = 0 cela devrait aller mieux (bonne intuition)

[vmolines]

Mais j'ai quand même un problème car ma boucle se ait tant que le reste <> 0. Or si je dis dis que A = 0, j'aurais une infinité de 0.

Comme en base 10 où 0 = 0000000000000.

Le problème ici, c'est que j'ai l'impression que c'est pas une vraie base car A <> AA.

Tu me suis ?

J'arrive pas à échaffauder un algo qui réponde à la problématique d'incrémenter une chaîne comme je le décris.

[Médiat]

Rajoute un caractère espace ' ' qui vaut 0 dans ton alphabet et puis A = 1 --> Z = 26 et tu comptes en base 27.
Après, tu supprimes toutes les chaines qui contiennent au moins un espace (ou tu testes au fur et à mesure).

Sinon, il y a d'autres algorithmes...

[vmolines]

J'ai fait ça mais y'a toujours un problème. Enfin c'est plutôt que je n'ai pas compris comment utiliser ce nouveau caractère dans mon alphabet...

[Médiat]

Tu veux les chaines avec 2 caractères A et B et de longueur 2

Code :

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

1
2
3
4
5
6
A
B
AA
AB
BA
BB

Si tu compte en base 3 :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
_ = 0
A = 1
B = 2
 
1   --> A
2   --> B
10  --> A_ à supprimer
11  --> AA
12  --> AB
20  --> B_ à supprimer
21  --> BA
22  --> BB

Si tu sais manipuler les tableaux, il y a plus direct...

[vmolines]

Ah ok je vois mieux maintenant merci. J'avais pas intégré le fait qu'on doive effacer le caractère nul.

Sinon par les tableaux ça marche comment globalement ?

On décompose le nombre dans les puissances décroissantes et on affecte à chaque indice du tableau ?

[Médiat]

Pour les tableaux, oublie les problèmes de numération :
1) tu crées un tableau avec toutes les lettres de ton alphabet (disons _T)
2) Tu initialises un tableu vide (disons _X)

3) Pour toute la "nouvelle" partie du tableau _X tu concatènes successivement chacun des éléments de _T (c'est donc un boucle sur une partie de _X et tout _T)
4) Si tu n'as pas fini (boucle sur la longueur maxi) goto 3)

[FrancisSourd]

On peut faire l'addition à la main directement dans la base 26.
S[i] représente le ième caractère de la chaîne

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
 
entrée: chaîne S
soit i la longueur de la chaîne
début_boucle
Si i = 0 alors
  ajoute A devant S
  sort de la boucle
Sinon
  Si S[i] = 'Z' alors  { retenue! }
    S[i] := 'A'
    i = i - 1
  Sinon
    S[i] := le caractère qui suit S[i]
    Sort de la boucle
  Fin_Si
Fin_Si
fin_boucle

NB: le successeur de Z est AA, celui de AZ est BA (comme dans les plaques minéralogiques).

[random]

ton problème revient à trouver le suivant d'un nombre en base 26
tu trouveras partout des routines de changement de base