Permutations, maximum et minimum des chiffres d'un entier

Version imprimable

20/01/2008, 08h38
JetliMohamed

Permutations, maximum et minimum des chiffres d'un entier

On se propose de saisir un entier N de trois chiffres, de déterminer et d'afficher tous ses nombres qui peuvent etre formés par les chiffres de N, ainsi que le plus petit et le plus grand de ces nombres.
Exemples :
Pour N = 427
* Les nombres formées par les chiffres de N sont : 427, 472, 724, 742, 247, 274
*Le plus petit nombres est 274 et le plus grand nombre 742.

Mon idée est la suivante :

On lit un entier (N) entre [100..999] puis on le convertit en chaîne de caractères puis on applique un algo de tri pour trouver le maximum de ses chiffres.
Deuxièmement on affiche la chaîne inversément pour obtenir le minimum de ces chiffres. Enfin on fait des permutations. Et voilà, mon problème est dans cette procédure.

Que pensez-vous de mon idée et SVP aidez-moi à résoudre ce problème et corriger mes fautes car mon idée n'est pas optimale pour le moment.

Merci pour tous j'attends vos discussions.
20/01/2008, 09h23
WhiteTigerZ

Holla !! :D
Je connais la solution pour avoir le nombre des cas possibles
la solution se trouve dans une formule mathématique :
Il s'agit d'un arrangement de n objet parmi n telque n est la longueur du chiffre choisi

Citation:

A=n!/(n-p)!

il faut tout simplement créer une fonction factorielle et puis tu l'appelles...
Pour l'affichage des nombres je crois qu'il faut convertir en chaine ainsi tu la coupes et tu déplaces ch[1] dans la position (2,3,...,n) ensuite ch[2] dans [1,3,...,n] de même jusqu'à arriver a ch[n] essaye d'utiliser la procédure copy ou insert !! un tableau peut être pour sauvegarder les valeurs...
Pour le plus petit et le plus grand un tri est indispensable tout en utilisant un tableau et n'oublie pas d'utiliser les procédures VAL (conversion en valeur) et STR (conversion en chaine)
bonne chance ;)
20/01/2008, 12h59
krachik

Bonjour

Citation:

Envoyé par WhiteTigerZ

Je connais la solution pour avoir le nombre des cas possibles
la solution se trouve dans une formule mathématique :
Il s'agit d'un arrangement de n objet parmi n telque n est la longueur du chiffre choisi

Citation:

A=n!/(n-p)!

Alors Faux sur toute la ligne,un chiffre ne peut avoir une longueur de plus de 1(sauf un nombre),Pourquoi parler d'un arrangement alors qu'on parle d'une simple permutation ?:? un petit rappel sur les "arrangements" et "permutations" devraitent t'eclairer.
N etant le nombre et L etant sa longueur (converti en chaine pour connaitre sa longueur) le nombre de cas possible sera n!

Citation:

Envoyé par JetliMohamed

On lit un entier (N) entre [100..999] puis on le convertit en chaîne de caractères puis on applique un algo de tri pour trouver le maximum de ses chiffres.

Oui c'est une possibilité et pour trouver le minimum il faudra faire un autre tri :P (trop de travail) ,Et si tu faisais d'abord les permutations et que tu plaçais dans un tableau ,apres appliquer algo de tri pour avoir le min et le max(comme ça tu ne tri qu'uen seule fois)

Citation:

Enfin on fait des permutations. Et voilà, mon problème est dans cette procédure.

Mais tu n'as rien proposé concernant ça alors je te laisse y reflechir et apres on vera ou tu en es.
Bon courage
@+
20/01/2008, 14h33
darrylsite

Citation:

Envoyé par krachik

Bonjour

Alors Faux sur toute la ligne,un chiffre ne peut avoir une longueur de plus de 1(sauf un nombre),Pourquoi parler d'un arrangement alors qu'on parle d'une simple permutation ?:? un petit rappel sur les "arrangements" et "permutations" devraitent t'eclairer.
N etant le nombre et L etant sa longueur (converti en chaine pour connaitre sa longueur) le nombre de cas possible sera n!

Oui c'est une possibilité et pour trouver le minimum il faudra faire un autre tri :P (trop de travail) ,Et si tu faisais d'abord les permutations et que tu plaçais dans un tableau ,apres appliquer algo de tri pour avoir le min et le max(comme ça tu ne tri qu'uen seule fois)

Mais tu n'as rien proposé concernant ça alors je te laisse y reflechir et apres on vera ou tu en es.
Bon courage
@+

Il n' a pas du tout tort en parlant d' arrangement.A=n!/(n-p)! si n=p alors (n-p)!=1. Donc A=n!. Vous avez donc tous raison.

Citation:

Envoyé par JetliMohamed;

Que pensez-vous de mon idée et SVP aidez-moi à résoudre ce problème et corriger mes fautes car mon idée n'est pas optimale pour le moment.

Il recherche donc une idée optimale et vous lui parlez des chaines de caracteres, str,val ... Savez vous le coup du calcul ? (=log...lol).
Moi, je suis toujours amoureux de ce petit operateur : mod (et aussi div).
Ex: 312 mod 10 est 2; 31 mod 10 est 1; 3 mod 10 est 3
pour trouver les chiffres, il suffit de savoir jouer. chiffre[i]= n mod 10 et n=n div 10. Jusqu' à avoir n egal à 0.
Et c ' est plus intuitif comme ça (j' aime la facilité).

Pour avoir les permutation, c' est simple. Tu peux garder les chiffres dans un tableau de 3 elements. Ensuite faire 3 boubles sur les indices du tableau et eviter que les indice se repetent (pour respecter la permutation : un element doit apparaitre une et une seule fois)
Ex: Si t=(1,4,9), tu peux avoir nombre[1]=1+4*10+9*100

Aussi, je ne vois pas pourquoi vous voulez faire un tri. Et sur quel tableau ?
Moi, j' aime la facilité (encore une fois). Vu qu' on a aucun interet à garder les nombres en memoire, il suffit d' avoir 2 variables par exemple mini et max (initialiser avec mini=1000 et max=0 par exemple) et de les comparer avec les nombres generés par la permutation. On obtient ainsi le minimum et le maximum.
20/01/2008, 15h06
droggo

Fio,

Citation:

Envoyé par darrylsite

...
Il recherche donc une idée optimale et vous lui parlez des chaines de caracteres, str,val ... Savez vous le coup du calcul ? (=log...lol).
Moi, je suis toujours amoureux de ce petit operateur : mod (et aussi div).
Ex: 312 mod 10 est 2; 31 mod 10 est 1; 3 mod 10 est 3
pour trouver les chiffres, il suffit de savoir jouer. chiffre[i]= n mod 10 et n=n div 10. Jusqu' à avoir n egal à 0.
Et c ' est plus intuitif comme ça (j' aime la facilité).

Et à ton avis, comment est faite la conversion ?

Ici, on a un outil simple pour obtenir le résultat (conversion en chaine), pourquoi chercher à faire autrement ?

Pour le temps de calcul, tu obtiendras au mieux ce que fait la conversion, probablement même moins bien, car il est fort possible que les calculs soient optimisés au niveau de la conversion (mais ce serait à vérifier, pour chaque version de chaque compilateur :)).
20/01/2008, 17h40
darrylsite
Citation:

Envoyé par droggo

Fio,

Et à ton avis, comment est faite la conversion ?

Ici, on a un outil simple pour obtenir le résultat (conversion en chaine), pourquoi chercher à faire autrement ?

Pour le temps de calcul, tu obtiendras au mieux ce que fait la conversion, probablement même moins bien, car il est fort possible que les calculs soient optimisés au niveau de la conversion (mais ce serait à vérifier, pour chaque version de chaque compilateur :)).

Je suis ne suis pas d' accord avec toi. Pour trouver le dernier chiffre, on fait : 122 mod 10. Or si on doit passer par les chaines :
Code:

1 2 3 str(122,ch); chiffre:=str[3]
En plus, c' est un exercice d' ecole donc il doit montrer qu' il maitrise vraiment le probleme en utilisant des astuces mathematiques.
Une fois qu' on est rodé, on peut faire ce qu' on veut parce qu' on sait combien ça nous coute.
Il faut toujours commencer sur de bonnes bases. Tu le repetes à chaque fois.
20/01/2008, 18h36
WhiteTigerZ

Salut les gars :)
en jetant un coup d'oeil a ce sujet j'ai du me poser une question !!
comment savoir le nombre d'anagrammes commençant par une voyelle ,d'un mot donné composé uniquement de lettres...
est ce que il s'agit d'un arrangement sachant qu'on connait le nombre de voyelle ??
Merci d'avance pour votre réponse ;)

Citation:

PS :
Salut drogg ça fait longtemps...ah :aie:

bon je viens de trouver la solution à mon problème : (prenant le mot : "abc" comme exemple )
on sait que le nombre de voyelle est de 6
et dans mon problème je veux savoir le nombres des mots possibles commençant par une seule voyelle donc il s'agit d'un arrangement de 1 objet parmi 6(=6 choix).Une fois ce choix effectué il faut ensuite calculer le nombre de permutation qui est égale à (3-1)!= 2! (tout en tentant compte que je travaille avec le mot "abc" ) Ainsi il aura 2!*6 anagrammes du mot "abc"

A propos j'ai un petit problème en faisant l'exercice sur pascal :( , je veux créer une condition de saisie (le mot saisi doit être former par des lettres)
or j'arrive par a faire cette condition :bug:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 procedure saisie ( var ch : string; var l : integer ); var verif : boolean ; i : integer ; begin repeat verif:=true ; writeln('saisir une chaine :'); {la saisie de la chaine } readln(ch); l:=length(ch); {partie de verification } for i:=1 to l do begin if (upcase(ch[i]) <> ['A'..'Z'] ); then verif:=false ; end; until verif:= true ; end;
De l'aide sera la bienvenue :yaisse2:

21/01/2008, 03h20
krachik

Citation:

Envoyé par darrylsite

Il n' a pas du tout tort en parlant d' arrangement.A=n!/(n-p)! si n=p alors (n-p)!=1. Donc A=n!. Vous avez donc tous raison.

La question n'est pas de dire 1+1=2 ou 1*2=2 ou 8/4=2 etc pour dire que chacun à raison mais de comprendre le principe de ce que l'on veut faire

Citation:

de déterminer et d'afficher tous ses nombres qui peuvent etre formés par les chiffres de N

Desolé d'insister mais je ne vois pas de notion d'arrangement dans ça:l'idée de choisir 3 chiffres dans une serie de 3 chiffres ne concorde pas trop puisse qu'on sait deja qu'on choisira toujours 3 chiffresà chaque fois (je parle de son exemple N=427).Dans notre cas il s'agit simplement de changer l'ordre de succession des chiffres contenus dans le nombre d'où permutation :P
@+

Feo,
Citation:
Envoyé par WhiteTigerZ
bon je viens de trouver la solution à mon problème : (prenant le mot : "abc" comme exemple )
on sait que le nombre de voyelle est de 6
et dans mon problème je veux savoir le nombres des mots possibles commençant par une seule voyelle donc il s'agit d'un arrangement de 1 objet parmi 6(=6 choix).Une fois ce choix effectué il faut ensuite calculer le nombre de permutation qui est égale à (3-1)!= 2! (tout en tentant compte que je travaille avec le mot "abc" ) Ainsi il aura 2!*6 anagrammes du mot "abc"

A propos j'ai un petit problème en faisant l'exercice sur pascal :( , je veux créer une condition de saisie (le mot saisi doit être former par des lettres)
or j'arrive par a faire cette condition :bug:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 procedure saisie ( var ch : string; var l : integer ); var verif : boolean ; i : integer ; begin repeat verif:=true ; writeln('saisir une chaine :'); {la saisie de la chaine } readln(ch); l:=length(ch); {partie de verification } for i:=1 to l do begin if (upcase(ch[i]) <> ['A'..'Z'] ); then verif:=false ; end; until verif:= true ; end;
De l'aide sera la bienvenue :yaisse2:
Ton code compile ?

Cette ligne

Code:

if (upcase(ch[i]) <> ['A'..'Z'] ); then

devrait être refusée :
<> ne peut pas s'appliquer dans ce cas
et un ; entre la condition et le then)

Il faut écrire

Code:

if not( upcase(ch[i]) in ['A'..'Z'] ) then

:)

21/01/2008, 07h26
WhiteTigerZ

Citation:

Envoyé par droggo

Feo,

Ton code compile ?

Cette ligne

Code:

if (upcase(ch[i]) <> ['A'..'Z'] ); then

devrait être refusée :
<> ne peut pas s'appliquer dans ce cas
et un ; entre la condition et le then)

Il faut écrire

Code:

if not( upcase(ch[i]) in ['A'..'Z'] ) then

:)

la négation !! oui c'est ça le problème
Merci Drogg

A propos il s'agit d'un arrangement de n objet parmi n ainsi A de n objet parmis n sera n! (qui égal de même au nombre de permutation)
24/01/2008, 22h27
katrena99

Citation:

Envoyé par krachik

La question n'est pas de dire 1+1=2 ou 1*2=2 ou 8/4=2 etc pour dire que chacun à raison mais de comprendre le principe de ce que l'on veut faire

Desolé d'insister mais je ne vois pas de notion d'arrangement dans ça:l'idée de choisir 3 chiffres dans une serie de 3 chiffres ne concorde pas trop puisse qu'on sait deja qu'on choisira toujours 3 chiffresà chaque fois (je parle de son exemple N=427).Dans notre cas il s'agit simplement de changer l'ordre de succession des chiffres contenus dans le nombre d'où permutation :P
@+

Arrangement (Fr) = Permutation (En)
Un élément ne peut être choisi qu'une seule fois et l'ordre est important : arrangement.
On le note xPy (xAy notation française ou francophone), où x est la liste des éléments parmi lesquels on va choisir, et y le nombre d'éléments qu'on va choisir.
Cas particulier : xPy avec x=y alors xPy=xPx; xPx=x!
Le cas proposé par JetliMohamed est ce genre de cas, 3 éléments distincts parmi lesquels on va choisir 3 sachant que l'ordre compte. Donc 3P3=3!=6 dans le cas où les chiffres sont distincts. Dans le cas où un élément se répète, on fait xPy/r! où r est la somme des nombres d'apparitions d'un ou de plusieurs éléments qui se repètent. Exemple : prenons encore le problème proposé par JetliMohamed ; si l'utlisateur rentre 922, on a un arrangement de "3 dans 3" avec un élément qui existe deux fois. Alors le nombre de "permutations" est trouvé par : 3P3/2! qui est égal à 3, vérifie au crayon si tu veux. La formule de xPy est donnée par WhiteTigerZ et confirmée par darrylsite.
Convaincu ?

Veuillez revenir au problème de JetliMohamed. Merci.
29/01/2008, 13h19
katrena99

Citation:

Envoyé par JetliMohamed

On se propose de saisir un entier N de trois chiffres, de déterminer et d'afficher tous ses nombres qui peuvent etre formés par les chiffres de N, ainsi que le plus petit et le plus grand de ces nombres.
Exemples :
Pour N = 427
* Les nombres formées par les chiffres de N sont : 427, 472, 724, 742, 247, 274
*Le plus petit nombres est 274 et le plus grand nombre 742.

Mon idée est la suivante :

On lit un entier (N) entre [100..999] puis on le convertit en chaîne de caractères puis on applique un algo de tri pour trouver le maximum de ses chiffres.
Deuxièmement on affiche la chaîne inversément pour obtenir le minimum de ces chiffres. Enfin on fait des permutations. Et voilà, mon problème est dans cette procédure.

Que pensez-vous de mon idée et SVP aidez-moi à résoudre ce problème et corriger mes fautes car mon idée n'est pas optimale pour le moment.

Merci pour tous j'attends vos discussions.

J'ai eu le même sujet exactement dans un test, la semaine dernière. J'ai ouvert un autre sujet : . J'aurais peut-être dû continuer dans celui-là. Tu trouveras une solution au problème. Elle n'est peut-être pas optimale comme tu dis mais, c'est au moins une solution. En plus, ça marche avec plus de 3 chiffres (ou 3 caractères). Lis attentivement le code dans le message de Droggo parce qu'il est mieux indenté que le miens, il sera plus facile à comprendre.

Donc toi tu dis que, pour trouver les permutations, d'abord tu tries les caractères de la chaîne par ordre croissant, puis décroissant afin de connaître la permutation qui donne le maximum et celle qui donne le minimum. Ainsi, tu obtiens deux permutations parmi 6 (ou plus si le nombre N contient plus de 3 chiffres). Il t'en reste 4 alors. As-tu déjà pensé à comment les retrouver ?

Ciao!

Citation:

Envoyé par katrena99

J'ai eu le même sujet exactement dans un test, la semaine dernière. J'ai ouvert un autre sujet : . J'aurais peut-être dû continuer dans celui-là. Tu trouveras une solution au problème. Elle n'est peut-être pas optimale comme tu dis mais, c'est au moins une solution. En plus, ça marche avec plus de 3 chiffres (ou 3 caractères). Lis attentivement le code dans le message de Droggo parce qu'il est mieux indenté que le miens, il sera plus facile à comprendre.

Donc toi tu dis que, pour trouver les permutations, d'abord tu tries les caractères de la chaîne par ordre croissant, puis décroissant afin de connaître la permutation qui donne le maximum et celle qui donne le minimum. Ainsi, tu obtiens deux permutations parmi 6 (ou plus si le nombre N contient plus de 3 chiffres). Il t'en reste 4 alors. As-tu déjà pensé à comment les retrouver ?

Ciao!

Enfin, j' ai pensé à une solution beaucoup plus simple et optimale pour trouver les permutations des nombres à trois chiffres:

On convertit le nombre en chaine soit nombre. Pour faire simple, tu peux utiliser str.

Tu fais trois boucles for imbriquées avec les indices i,j,k par exemple.
Tu auras toutes les permutations avec "nombre[i]+nombre[j]+nombre[k]" pour
i<>j et i<>k et j<>k

Pour resumer :
Code:

1 2 3 4 5 6 7 8 9 10 11 pour i de 1 à 3 pour j de 1 à 3 pour k de 1 à 3 si i<>j et i<>k et j<>k alors "c' est une concatenation" ecrire(nombre[i]+nombre[j]+nombre[k]) finsi finpour finpour finpour

Citation:
Envoyé par darrylsite
Enfin, j' ai pensé à une solution beaucoup plus simple et optimale pour trouver les permutations des nombres à trois chiffres:

On convertit le nombre en chaine soit nombre. Pour faire simple, tu peux utiliser str.

Tu fais trois boucles for imbriquées avec les indices i,j,k par exemple.
Tu auras toutes les permutations avec "nombre[i]+nombre[j]+nombre[k]" pour
i<>j et i<>k et j<>k

Pour resumer :
Code:

1 2 3 4 5 6 7 8 9 10 11 pour i de 1 à 3 pour j de 1 à 3 pour k de 1 à 3 si i<>j et i<>k et j<>k alors "c' est une concatenation" ecrire(nombre[i]+nombre[j]+nombre[k]) finsi finpour finpour finpour
Bravo! Je n'y ai pas pensé une seule seconde. Seulement, ça ne marche que pour des entiers de 3 chiffres. Avec 3 chiffres uniquement, je préfère remplir le tableau ou afficher moi-même : t[1]:=ch, t[2]:=ch[1]+ch[3]+ch[2] et ainsi de suite...
Mais c'est vraiment une très bonne idée darrylsite!!

Ciao!