J’ai mettons 10 variables i1, i2, …, i10, qui peuvent aller chacune
de 0 a n-1. Comment faire pour avoir une boucle qui parcourt toutes les
possibilites, sachant que la somme doit etre inferieure a une valeur
donnee ?
En fait il me faudrait l’equivalent de:
for (i1=0;i1< n;i1++) {
for (i2=0;i2< n;i2++) {
....
for (i10=0;i10< n;i10++) {
if (i1+i2+...+i10< somme) { trucs a faire }
}
.....
}
}
Mais sans parcourir toutes les valeurs possibles (parce que sinon j’ai une complexite en n^10 ouch).
Ce message a été édité par Cybernoid le 19/12/2003
Je sais pas si j’ai bien compris mais bon…
pour tout n de 1 à k-1 faire
val = 0;
pour tout m de 1 à 10 faire
val += tab[m][n]
Si val > somme faire
.....
Fsi
fait
fait
[/quote]En considérant que tes variables sont dans un tableau....
edit : je suis un boulet, j’ai vu > à la place de < …m’enfin ça change pas grand chose suffit de mettre un while
Ce message a été édité par kaneloon le 19/12/2003
Si n est supérieur à la somme à attendre et que les combinaisons que tu
dois trouver ne sont pas ordonnées (c’est à dire que la solution i1 =
1, i2 = 2, i(3à10)=1 est identique à i1=2, i(2=10)=1 ?), je pense qu’il
vaut mieux effectuer ta boucle dans le sens enverse en partant de la
valeu max possible
Avec s la somme à atteindre ca donne un truc du genre :
for(i0=s, i0>=0;i0--)
{ for(i1=s-i0; i1>=0;i1--)
{ for(i2=s-i1-i0;i2>0;i2--) {
....
}
}
}
[/quote]
Je pense que ca reduit considérablement la combinatoire !
Ce message a été édité par JeromeV le 19/12/2003
Ce message a été édité par JeromeV le 19/12/2003
Méthode ultra brute (dite du bourrin extra) :
int i[10];
function Calcule(int index, int n)
{
int j = 0;
int somme = 0;
for (i[index] = 0; i < n; i[index]++)
{
while (j < 10)
{
somme = somme + i[j];
j++;
}
if (somme < n) {/* Insert Code Here */}
else {Calcule(index + 1, n);}
}
}
Ca devrait normalement calculer toutes les possibilités (si jme suis pas planté...),
et le langage utilisé doit gerer sans problème la récursivité.
Bon par contre je suis pas sur que la fonction arrive à sortir d’elle même de la récursivité ^^;
A mon tour d’essayer.
On veut calculer la somme des A[j] avec
A [j] étant un entier positif
j étant un entier de 1 à 10.
Si la somme des A[j] est inférieur à un nombre, on doit faire une action, sinon on ne fait rien.
1ere remarque si somme A[k] > somme_max, avec k < j . alors ce n’est pas la peine de tester les séquences entre k et j.
En gros si A[1]+A[2] > somme, alors la somme A[1]+A[2]+A[3] sera suppérieur quelque soit la valeur de A[3]
Connaissant la somme des A[k], alors il n’est utile de tester que les A[k+1] de 0 à somme_max - somme (A[k]).
ça pourait donner quelque chose comme ça (en C soyont fout)
Somme_debile (int rang, int somme, int rang_max, int somme_max, int n_max)
{
n=somme_max-somme rang_max) et ça devrait rouler. j'ai pas de compilo pour tester.
Ok, merci pour les réponses. Est-ce qu’il y a un moyen de faire des boucles avec un niveau d’imbrication variable sans utiliser la récursivité ?
Du style pouvoir faire
for (i[0]=0;i[0]<10;i[0]++) {
for (i[1]=0;i[1]<10;i[1]++) {
....
for (i[n]=0;i[n]<10;i[n]++) {
blablabla
}
....
}
}
[/quote]avec un n variable ?
Salut, voici ma proposition:
Parcours toutes les valeurs, mais interromps la boucle si la somme des ixx est plus grande que la limite car en allant dans l’ordre croissant avec tes for() si tu dépasses somme, tu es sûr qu’avec tous les i10 suivants tu dépasseras encore plus! (Comme je l’ai fait ci-dessous, ça ne fonctionne que si ta condition initiale sur ix est zéro.)
Pour ce faire, tu peux utiliser la conditions de fin de la boucle for() en mettant comme condition que la somme des ixx doit être plus petite que somme:
int i1toix = 0; /* pour mémoriser la somme des ix en amont de la boucle courante pour s'abstenir de faire i1+i2+i3+i4+... à chaque fois*/
for (i1=0; i1<n,
Salut,
Si n est variable, tu peux toujours utiliser une seule While loop :
//initialisation
for (j=0;j<n;j++) i[j] =0;
pas_fini = 1;
//While loop
while (pas_fini)
{
blablabla
//Passe a l’elt suivant
for (j=0;j<n;j++)
{
if (++(i[j]) != 10) break;
else i[j] = 0;
}
//Verifie si on doit sortir de la boucle
if (j==n) pas_fini = 0;
}
Sinon je suis d’accord avec Zoomastigophore