CHALLENGE #2 : Recherche de nombres spéciaux

Voir le sujet précédent Voir le sujet suivant Aller en bas

25022009

Message 

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
125
152
215
251
512
521

125 = 51 + 52 + 21 + 1

+++++++++++++++++++++++++++++++++++++++++++++

EXCLUSIF au FORUM INFOMATH

Production Personnelle 2009
_______________________________


Dernière édition par methodiX le Jeu 26 Fév - 18:33, édité 1 fois

_________________
Sami - Methodix, tunis
Le génie de Newton a consisté à dire que la lune tombe alors que tout le monde voit bien qu'elle ne tombe pas.
(Paul Valéry)
_____
Cliquer ici: Voir les nouveaux messages depuis votre dernière visite
Cliquer ici: Astuce: Utiliser l'outil "Recherche" du forum
avatar
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 4639
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
1000/1000  (1000/1000)

Revenir en haut Aller en bas

- Sujets similaires
Partager cet article sur : Excite BookmarksDiggRedditDel.icio.usGoogleLiveSlashdotNetscapeTechnoratiStumbleUponNewsvineFurlYahooSmarking

CHALLENGE #2 : Recherche de nombres spéciaux :: Commentaires

avatar

Message le Mer 25 Fév - 21:59 par Napoléon

Bon retour METHODx !

Toujours distingué avec tes Challenges.

Heureux de voir tes participations originales.

A+

Revenir en haut Aller en bas

avatar

Message le Jeu 26 Fév - 18:32 par methodiX

On n'a pas encore des membres ACCRO ... malheureusement Sad

Tout le monde poste la même chose :

"Je veux des exercices corrigés..." Smile

Revenir en haut Aller en bas

avatar

Message le Lun 15 Juin - 0:34 par direct

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 ^^

Revenir en haut Aller en bas

avatar

Message le Lun 15 Juin - 1:13 par direct

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
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

Revenir en haut Aller en bas

avatar

Message le Lun 15 Juin - 11:36 par methodiX

@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.

Revenir en haut Aller en bas

avatar

Message le Lun 15 Juin - 12:03 par direct

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

Revenir en haut Aller en bas

avatar

Message le Mer 17 Juin - 10:54 par methodiX

Tu as attaqué la partie la plus difficile du problème !!! Wink

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 !!!

Revenir en haut Aller en bas

avatar

Message le Mer 17 Juin - 12:35 par direct

Oh oui haha c'est compliqué un peux je vais le réfléchir un peut avec ce problème

Revenir en haut Aller en bas

avatar

Message le Jeu 9 Juil - 13:31 par Lamice

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

Revenir en haut Aller en bas

avatar

Message le Jeu 9 Juil - 15:21 par Lamice

Réponses:

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
 
6.Procédure Ensembe (N, t_C: entier, C: TAB, var exist: booléen)
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
 
7. Procédure Liste (N_MAX: entier, var j: entier, var I: TAB, var e: chaine)
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

Revenir en haut Aller en bas

avatar

Message le Jeu 9 Juil - 23:07 par Napoléon

ça mérite d'être étudié minitieusement. Je le ferai le plus tôt possible. Merci pour la participation.

Revenir en haut Aller en bas

avatar

Message le Ven 10 Juil - 15:12 par cooletzen

methodiX a écrit:On n'a pas encore des membres ACCRO ... malheureusement Sad

Smile
moi je veux bien y devenir accro Cool ! j'apprécie vos initiatives ! Rolling Eyes
en ce qui concerne ce challenge vous pensez qu'il est à la portée d'une bachelière ex - section maths Embarassed pour voir si devrais me mettre à y réfléchir
sinon ....
cordialement vôtre ....

Revenir en haut Aller en bas

avatar

Message le Ven 10 Juil - 21:45 par Napoléon

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.

Revenir en haut Aller en bas

avatar

Message le Jeu 16 Juil - 17:58 par Lamice

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)
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
Je laisserai la partie traduction pour prochainement Smile

Revenir en haut Aller en bas

avatar

Message le Ven 17 Juil - 9:56 par Napoléon

Très bonne tentative de résolution. J'espère que je pourrais la vérifier le plus tôt possible.

Revenir en haut Aller en bas

avatar

Message le Sam 12 Déc - 3:30 par direct

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

Revenir en haut Aller en bas

avatar

Message le Sam 12 Déc - 12:54 par Napoléon

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.

Revenir en haut Aller en bas

Message  par Contenu sponsorisé

Revenir en haut Aller en bas

Voir le sujet précédent Voir le sujet suivant Revenir en haut


 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum