CHALLENGE #2 : Recherche de nombres spéciaux
Page 1 sur 1
25022009
CHALLENGE #2 : Recherche de nombres spéciaux
CHALLENGE #2
__________________________________________
On cherche la liste de tous les nombres N inférieurs à N_MAX qui vérifient cette relation :
Il existe au moins un ensemble de nombres N(i) différents de {N}, résultant d'une combinaison quelconque des chiffres de N et dont la somme est égale à N.
Exemple
Si N=125, alors les nombres N(i) sont
1
2
5
12
15
21
25
51
52
152
215
251
512
521
125 = 51 + 52 + 21 + 1
+++++++++++++++++++++++++++++++++++++++++++++
EXCLUSIF au FORUM INFOMATH
Production Personnelle 2009
_______________________________
EXCLUSIF au FORUM INFOMATH
Production Personnelle 2009
_______________________________
Dernière édition par methodiX le Jeu 26 Fév - 18:33, édité 1 fois
methodiX- Admin
-
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7014
Date d'inscription : 22/03/2007
Feuille de personnage
Capacité linguistique:
(1000/1000)
CHALLENGE #2 : Recherche de nombres spéciaux :: Commentaires
On n'a pas encore des membres ACCRO ... malheureusement
Tout le monde poste la même chose :
"Je veux des exercices corrigés..."
Tout le monde poste la même chose :
"Je veux des exercices corrigés..."
Non j'aime bien cette zone les défis c'est une choses originale
alors je vais réfléchir un peut avec ce challenge ^^
alors je vais réfléchir un peut avec ce challenge ^^
Alors s'il vous plaît vérifiez avec moi cette méthode :
Aprés docomposer le nombre (N) dans un tableau tels que chaque case contient une combinaison du nombre (N) et je vais vous montrer mon algorithme aprés
Mais pour le moment j'ai penser sur le calcul dans le tableau à fin de vérifier si le nombre contient une série qui le compose ou non
alors
Considérons que l'indice du tableau commence par zéro
J'ai pas exécuter cet algorithme sur machine en attendant vos remarque
Je vais essayé maintenant avec la composition du N dans un tableau.
merci
Aprés docomposer le nombre (N) dans un tableau tels que chaque case contient une combinaison du nombre (N) et je vais vous montrer mon algorithme aprés
Mais pour le moment j'ai penser sur le calcul dans le tableau à fin de vérifier si le nombre contient une série qui le compose ou non
alors
Considérons que l'indice du tableau commence par zéro
- Code:
i = taille - 1;
somme = 0;
difference = T[taille];
while (somme < n && i > taille)
{
if (difference >= T[i])
{
somme += T[i];
Save (T[i], V); // On stocke cet valeur dans un tableau (V)
difference =N - somme ;
}
i--;
}
if (somme == N)
{printf("La série qui compose %d sont : ",N);affiche(V,tailleV);}
else
printf("%d n'a pas une combinaison avec ses propres nombre ! ");
J'ai pas exécuter cet algorithme sur machine en attendant vos remarque
Je vais essayé maintenant avec la composition du N dans un tableau.
merci
@direct: est-ce que tu peux expliquer clairement que fait le code que tu as proposé. Il faut toujours bien introduire les solutions qu'on donne, surtout lorsqu'il s'agit d'une solution partielle. ça ne fait augmenter le nombre de lecteurs et les encourage à en comprendre le principe.
Amicalement.
Amicalement.
Je suis désolé si mon code n'est pas claire
aprés une décomposition du nombre (N) dans un tableau :
Pour N = 125
Le tableau T contient : 1: 2: 5 : 12 : 15 : 21 : 25 : 51 : 52
Les éléments sont trié dans l'ordre croissant.
Alors on suppose qu'on a les variable : Somme, Différence, i, taille, V
tels que
- i : compteur entier
- Somme, Différence : variables auxilières
- taille : la taille du tableau (T)
- V : tableau vide pour sauvegarder les élément quand on les additionne nous donne (N)
i = taille
T[i] = 52
Différence = 52
Si 52 >= 52 on fait
Somme = Somme + 52 //52+0 = 52
et puis on sauvegarde ce nombre dans (V)
Différence = N - Somme // 125 - 52 = 73
décrémentation du (i)
On entre dans la boucle une autre fois ; 73 est elle >= 51 ==> oui
même opérations...
Jusqu'à ce que la condition d'arêt du boucle est vrai
Mais si on trouve Différence < T[i] le programme va sauter cette case
L'avantage de comparer avec la différence ici c'est de savoir chaque fois de quoi l'opération est elle besoin comme opérande si elle n'est pas satisfaite alors le nombre ne vérifie pas la théorie
aprés une décomposition du nombre (N) dans un tableau :
Pour N = 125
Le tableau T contient : 1: 2: 5 : 12 : 15 : 21 : 25 : 51 : 52
Les éléments sont trié dans l'ordre croissant.
Alors on suppose qu'on a les variable : Somme, Différence, i, taille, V
tels que
- i : compteur entier
- Somme, Différence : variables auxilières
- taille : la taille du tableau (T)
- V : tableau vide pour sauvegarder les élément quand on les additionne nous donne (N)
i = taille
T[i] = 52
Différence = 52
Si 52 >= 52 on fait
Somme = Somme + 52 //52+0 = 52
et puis on sauvegarde ce nombre dans (V)
Différence = N - Somme // 125 - 52 = 73
décrémentation du (i)
On entre dans la boucle une autre fois ; 73 est elle >= 51 ==> oui
même opérations...
Jusqu'à ce que la condition d'arêt du boucle est vrai
Mais si on trouve Différence < T[i] le programme va sauter cette case
L'avantage de comparer avec la différence ici c'est de savoir chaque fois de quoi l'opération est elle besoin comme opérande si elle n'est pas satisfaite alors le nombre ne vérifie pas la théorie
Tu as attaqué la partie la plus difficile du problème !!!
mmm, je ne crois pas que l'algorithme que tu as proposé fait correctement ce qu'il doit faire !
En fait, le problème est un peu plus compliqué :
Autrement dit, soit E = {1, 2, 3, 4, 5, 6} : chercher tous les sous-ensembles de E dont la somme est N=6.
Manuellement, "je crois" que c'est :
ça se complique plus si E = {1, 2, 2, 3, 3, 6}...
il faut penser à un algorithme qui traite tous ces cas !!!
mmm, je ne crois pas que l'algorithme que tu as proposé fait correctement ce qu'il doit faire !
En fait, le problème est un peu plus compliqué :
- Code:
étant donné un ensemble non vide d'entiers noté E, il s'agit de trouver tous les sous-ensembles de E dont la somme des éléments est égale à un nombre prédéfini N.
Autrement dit, soit E = {1, 2, 3, 4, 5, 6} : chercher tous les sous-ensembles de E dont la somme est N=6.
Manuellement, "je crois" que c'est :
- Code:
E_1 = {6}
E_2 = {1,5}
E_3 = {2,4}
E_4 = {1,2,3}
ça se complique plus si E = {1, 2, 2, 3, 3, 6}...
il faut penser à un algorithme qui traite tous ces cas !!!
Oh oui haha c'est compliqué un peux je vais le réfléchir un peut avec ce problème
J'ai essayé de décomposer ce problème en des modules, et voila ce que je vais faire:
1-Ecrire une fonction "Saisie" qui permet de saisir l'entier positif N_MAX
2-Ecrire une procédure "Chiffres" qui permet de mettre les chiffres d'un entier N dans un tableau T et de taille t_T
3-Ecrire une procédure "Arrangement" qui prend pour entrées un tableau T de taille t_T et un entier l et qui retourne un tableau C de taille t_C contenant tous les arrangements possibles de l éléments du tableau T parmi t_T
4. Ecrire une procédure "Combinaison" qui prend pour entrées un tableau T et sa taille t_T et qui retourne toutes les combinaisons possibles des éléments de T dans un tableau tC de taille t_tC
5.Ecrire une procédure "Inférieur" qui prend pour entrées un entier N, un tableau tC et sa taille t_tC et retourne un tableau C et sa taille t_C ne contenant que les entiers strictement inférieurs à N.
6. Ecrire une procédure "Ensemble" qui prend pour entrées N, un tableau C et sa taille tC et qui retourne une variable booléenne exist qui indique s'il existe un ensemble non vide de C dont la somme de ses éléments est égale à N.
7-Ecrire une procédure "Liste qui prend pour entrée un entier N_MAX et qui retourne un tableau contenant tous les entiers N vérifiants les hypothèses de l'énoncé.
8-Ecrire l'algorithme principal qui résoud le problème
9-Traduire en un language de programmation exécutable
1-Ecrire une fonction "Saisie" qui permet de saisir l'entier positif N_MAX
2-Ecrire une procédure "Chiffres" qui permet de mettre les chiffres d'un entier N dans un tableau T et de taille t_T
3-Ecrire une procédure "Arrangement" qui prend pour entrées un tableau T de taille t_T et un entier l et qui retourne un tableau C de taille t_C contenant tous les arrangements possibles de l éléments du tableau T parmi t_T
4. Ecrire une procédure "Combinaison" qui prend pour entrées un tableau T et sa taille t_T et qui retourne toutes les combinaisons possibles des éléments de T dans un tableau tC de taille t_tC
5.Ecrire une procédure "Inférieur" qui prend pour entrées un entier N, un tableau tC et sa taille t_tC et retourne un tableau C et sa taille t_C ne contenant que les entiers strictement inférieurs à N.
6. Ecrire une procédure "Ensemble" qui prend pour entrées N, un tableau C et sa taille tC et qui retourne une variable booléenne exist qui indique s'il existe un ensemble non vide de C dont la somme de ses éléments est égale à N.
7-Ecrire une procédure "Liste qui prend pour entrée un entier N_MAX et qui retourne un tableau contenant tous les entiers N vérifiants les hypothèses de l'énoncé.
8-Ecrire l'algorithme principal qui résoud le problème
9-Traduire en un language de programmation exécutable
Réponses:
1-Fonction Saisie(): entier
2. Procédure Chiffres (N:entier, var T:TAB, var t_T:entier)
3. Procédure Arrangement (l, t_T :entier, T: TAB, var C: TAB, var t_C: entier)
(à suivre...)
4. Procédure Combinaison (t_T :entier, T :TAB, var tC :TAB, var t_tC :entier)
5. Procédure Inférieure (N, t_tC: entier, tC: TAB, var C:TAB, var t_C: entier)
8-Algorithme principal
1-Fonction Saisie(): entier
- Code:
VAR N_MAX: entier
Début
répéter
écrire("Saisir N_MAX")
lire(N_MAX)
jusqu'a N_MAX>0
Saisie<- N_MAX
fin
2. Procédure Chiffres (N:entier, var T:TAB, var t_T:entier)
- Code:
VAR i :entier
début
i<-0
répéter
i<- i+1
T[i] <- N mod 10
N <- (N-T[i])/10
jusqu'à N=0
fin
3. Procédure Arrangement (l, t_T :entier, T: TAB, var C: TAB, var t_C: entier)
(à suivre...)
4. Procédure Combinaison (t_T :entier, T :TAB, var tC :TAB, var t_tC :entier)
- Code:
VAR i, j, l, t_C :entier
C: TAB
début
i <- 1
pour l de 1 à t_T faire
Arrangement(l, t_T, T, C, t_C)
pour j de 1 à t_C faire
tC[i] <- C[j]
i <- i+1
fin pour
fin pour
fin
5. Procédure Inférieure (N, t_tC: entier, tC: TAB, var C:TAB, var t_C: entier)
- Code:
VAR k, i: entier
début
k <- 0
pour i de 1 à t_tC faire
si tC[i]
k <- k + 1
C[k] <- tC[i]
fin si
fin pour
t_C <- k
fin
- Code:
VAR i, j, x: entier
début
pour j de 1 à t_C faire
pour i de 2 à t_C faire
Si C[i]
x <- C[i]
C[i] <- C[j]
C[j] <- x
fin pour
fin pour
i <- 0
répéter
x <- N - C[t_C - i]
j <-0
répéter
j <- j+1
y<- x - C[j]
si y<>0 alors
x <- y
fin si
jusqu'à y=<0 ou j=t_C
i <- i+1
jusqu'à (y = 0) ou (i = t_C)
si y = 0 alors exist <- vrai
sinon exist <- faux
fin si
fin
- Code:
VAR N, t_T, t_tC, t_C: entier
T, C, tC: TAB
exist: booléen
début
j <- 0
pour N de 1 à N_MAX faire
Chiffres(N, T, t_T)
Combinaison(t_T, T, tC, t_tC)
Inférieur( N, t_tC, tC, C, t_C)
Ensemble(N, t_C, C, exist)
Si exist alors
j <- j + 1
I[j] <- N
fin si
fin pour
Si j=0 alors e <- "vide"
sinon e <- ""
fin si
fin
8-Algorithme principal
- Code:
TYPE TAB: tableau de 1000 entiers
VAR i, j, N_MAX: entier
I: TAB
e: chaine
début
N_MAX <- Saisie()
Liste( N_MAX, j, I, e)
Ecrire ("La liste est:",e)
Si e<>"" alors
pour i de 1 à j faire
Ecrire(I[i])
fin pour
fin si
fin
ça mérite d'être étudié minitieusement. Je le ferai le plus tôt possible. Merci pour la participation.
moi je veux bien y devenir accro ! j'apprécie vos initiatives !methodiX a écrit:On n'a pas encore des membres ACCRO ... malheureusement
en ce qui concerne ce challenge vous pensez qu'il est à la portée d'une bachelière ex - section maths pour voir si devrais me mettre à y réfléchir
sinon ....
cordialement vôtre ....
Oui - c'est à la portée d'un ex-bachelier de la section maths... il suffit d'un bon raisonnement pour déterminer les étapes de résolution. Que le bon sens et très peu de théorie sont exigés !!!
On attend ta participation.
On attend ta participation.
Pas forcément section math, moi j'ai eu bac technique.
Voici la suite de la solution que j'ai proposé:
3-Procédure Arrangement (l, t_T :entier, T: TAB, var C: TAB, var t_C: entier)
Voici la suite de la solution que j'ai proposé:
3-Procédure Arrangement (l, t_T :entier, T: TAB, var C: TAB, var t_C: entier)
- Code:
VAR i, j, x, max, t_D, m, case, k: entier
existe: booléen
D: TAB
début
pour i de 1 à t_T faire
pour j de 1 à t_T faire
si T[i]>T[j] alors
x<-T[i]
T[i]<-T[j]
T[j]<-x
fin si
fin pour
fin pour
x<-0
pour i de 1 à t_T faire
x<- x+T[i]*10^(t_T-l)
fin pour
max<-x div 10^(t_T-l)
k<-0
pour i de 1 à max faire
Chiffres(i, D, t_D)
j<-0
répéter
j<-j+1
si j=1 ou D[j]<>D[j-1] alors
existe<-faux
m<-0
répéter
m<-m+1
si D[j]=T[m] alors
existe<- vrai
case<-m
fin si
jusqu'à existe ou m=t_T
sinon
m<-0
existe<-faux
répéter
m<-m+1
si D[j]=T[m] et m>case alors
existe<- vrai
case<- m
fin si
jusqu'à existe ou m= t_T
fin si
jusqu'à existe= faux ou j=t_D
si j=t_D alors
k<- k+1
C[k]<-0
Pour m de 1 à t_D faire
C[k]<-C[k] + D[m]*10^(m-1)
fin pour
fin si
fin pour
t_C<- k
fin
Très bonne tentative de résolution. J'espère que je pourrais la vérifier le plus tôt possible.
Salutation mes amis j'ai lu cet algorithme de "Mr.Lamice"
mais vraiment j'ai pas le trouvé sympa cet écriture il y a pas mal d'erreurs du genre bizarre, des instructions illogiques, plein de contradiction, manque de déclaration de quelques variables ainsi que la solution est très longue pour une combinaison simple d'un nombre de longueur 3, il y a aussi tant de boucles, boucles,..., et bouclesss
Mais mal grès tout je vous encourage de trouver une autre belle solution ^^
Je crois que décomposer ce problème en module sera mieux et plus facile comme même, c'est illisible du tout pour analyser un algo représenté de cette façon, sans commentaire ni structuration
la programmation est art et le code est un moyen pour représenter cet art alors soyons des artistes
à la prochaine et bon courage
mais vraiment j'ai pas le trouvé sympa cet écriture il y a pas mal d'erreurs du genre bizarre, des instructions illogiques, plein de contradiction, manque de déclaration de quelques variables ainsi que la solution est très longue pour une combinaison simple d'un nombre de longueur 3, il y a aussi tant de boucles, boucles,..., et bouclesss
Mais mal grès tout je vous encourage de trouver une autre belle solution ^^
Je crois que décomposer ce problème en module sera mieux et plus facile comme même, c'est illisible du tout pour analyser un algo représenté de cette façon, sans commentaire ni structuration
la programmation est art et le code est un moyen pour représenter cet art alors soyons des artistes
à la prochaine et bon courage
direct a écrit:Salutation mes amis j'ai lu cet algorithme de "Mr.Lamice"
mais vraiment j'ai pas le trouvé sympa cet écriture il y a pas mal d'erreurs du genre bizarre, des instructions illogiques, plein de contradiction, manque de déclaration de quelques variables ainsi que la solution est très longue pour une combinaison simple d'un nombre de longueur 3, il y a aussi tant de boucles, boucles,..., et bouclesss
Mais mal grès tout je vous encourage de trouver une autre belle solution ^^
Je crois que décomposer ce problème en module sera mieux et plus facile comme même, c'est illisible du tout pour analyser un algo représenté de cette façon, sans commentaire ni structuration
la programmation est art et le code est un moyen pour représenter cet art alors soyons des artistes
à la prochaine et bon courage
Remarques pertinentes, mais, il ne faut pas trop critiquer les autres. J'attends tes propositions.
Sujets similaires
» Recherche de nombres spéciaux
» Exercice (bac pratique): Recherche de nombres spéciaux
» Somme de nombres spéciaux + permutation
» Nombres spéciaux: division par somme des chiffres
» Recherche des nombres premiers palindromes
» Exercice (bac pratique): Recherche de nombres spéciaux
» Somme de nombres spéciaux + permutation
» Nombres spéciaux: division par somme des chiffres
» Recherche des nombres premiers palindromes
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum
|
|