Discussion :

[hachdotnet]

bonjour svp aidez moi je suis un débutant en alogorithme et j'ai un probleme à résoudre:
l'utilisateur entre un nombre X
je dois trouver toutes les combinaisons possibles des opérations de somme possibles qui donnent X et avec (et c de la vient en grande parite ma galère) la determination des coefficients ....exemple:

X=4
coefficient maximal à utiliser(c) : 4
nombre maximal à utiliser (n): 4
les resutats doivent etre : (1*4)(2*2) (4*1) (3*1 + 1*1) (1*3+1*1)

X=4
coefficient maximal à utiliser (c): 1
nombre maximal à uiliser (n): 4
les resutat doit etre : (1*4)

X=4
coefficient maximal à utiliser (c): 3
nombre maximal à uiliser (n): 3
les resutat doit etre : (1*4) (1*3+1*1) (3*1+1*1)

en bref c afficher tous les combinaisons possibles des opérations de l'equation somme(ci*nj)=X avec i allant de 1 à X et j allant de 1 à une valeur récuperable d'un tableau disons que c Y.....Aidez moi svp parcke 7 exercice commence à me rendr fou!!!

merci d'avance

[Trap D]

Ceci me paraît bizarre : (1*4)(2*2) (4*1) (3*1 + 1*1) (1*3+1*1)
Comment écris tu l'expression n * c ou c* n ?

Parceque 3 * 1 + 1 * 1 se lit (n =3) * (c=) 3 + (n= ) 1 * (c = 1) OK
mais 1 * 3 + 1 * 1 se lit (n =) 1 * (c =)3 + (n = 1) * (c = 1)

et alors

pourquoi n'a-t-on pas 1*1 + 1*1 + 1*1 + 1*1 ?
pourqoi n'a-t-on pas 2*1 + 2*1 ?

(Idem pour l'autre manière de lire avec c * n).

Je crois que tu devrais préciser un peu plus les conditions imposées pour cet algo.

[hachdotnet]

Ceci me paraît bizarre : (1*4)(2*2) (4*1) (3*1 + 1*1) (1*3+1*1)
Comment écris tu l'expression n * c ou c* n ?

Parceque 3 * 1 + 1 * 1 se lit (n =3) * (c=) 3 + (n= ) 1 * (c = 1) OK
mais 1 * 3 + 1 * 1 se lit (n =) 1 * (c =)3 + (n = 1) * (c = 1)

et alors

pourquoi n'a-t-on pas 1*1 + 1*1 + 1*1 + 1*1 ?
pourqoi n'a-t-on pas 2*1 + 2*1 ?

(Idem pour l'autre manière de lire avec c * n).

Je crois que tu devrais préciser un peu plus les conditions imposées pour cet algo.

désolé parcke mon msg n'était pas trés clair : l'opération et sous la forme c*n (cofficient * nombre..) et ce couple tel kil est ds une meme opération d'addtion ne doit pas se repeter((1*1+1*1+1*1) est faux (3*1) ou (2*1+1*1) (1*2+ 1*1) sont vrai)...j'espere que un peu plus clair ...

[pseudocode]

Edit: Deuxieme ebauche de code en java d'apres ton énoncé...

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int X=4;
int CMax=4;
int NMax=4;
int[] coefs = new int[100];
int[] values = new int[100];
 
void main(String[] args) {
	AddTerm(0, 1, 0, 0);
}
 
void AddTerm(int nmbterm, int c, int n, int somme) {
 
	// ajoute le terme a la somme actuelle
	if (nmbterm>0) {
		coefs[nmbterm]=c;
		values[nmbterm]=n;
 
		// calcul de la nouvelle valeur de la somme
		somme+=c*n;
	}
 
	// la somme depasse X -> abandon
	if (somme>X) return;
 
	// la somme vaut X -> victoire !
	if (somme==X) {
		System.out.print("(");
		for(int i=1;i<nmbterm;i++)
			System.out.print(coefs[i]+"*"+values[i]+" + ");
		System.out.print(c+"*"+n);
		System.out.println(")");
		return;
	}
 
	// la somme est inferieure a X -> ajoute un nouveau terme c*n
	// (par ordre croissant de c puis n, pour eviter les doublons)
 
	// termes c[i]*n[i] tels que: c[i]=c[i-1] et n[i]>n[i-1] 
	for(int ni=n+1;ni<=NMax;ni++)
		AddTerm(nmbterm+1, c, ni, somme);
 
	// termes c[i]*n[i] tels que: c[i]>c[i-1] et n[i] quelconque 
	for(int ci=c+1;ci<=CMax;ci++)
		for(int ni=1;ni<=NMax;ni++)
			AddTerm(nmbterm+1, ci, ni, somme);
}

Pour X=4, CMax=4 et NMax=4, je trouve:
(1*1 + 1*3)(1*1 + 3*1)(1*2 + 2*1)(1*4)(2*2)(4*1)

Pour X=4, CMax=1 et NMax=4, je trouve:
(1*1 + 1*3)(1*4)

Pour X=4, CMax=3 et NMax=3, je trouve:
(1*1 + 1*3)(1*1 + 3*1)(1*2 + 2*1)(2*2)

Est-ce que c'est bon ?

[Trap D]

Salut, je te propose cet algo

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
 
fonction decompose(val_a_trouver, coef_max, nombre_max, liste_deja_obtenue)
 
val_a_trouver : nombre dont on veut calculer la decomposition
coef_max : le coefficient maximal à utiliser
nombre_max : le nombre maximum à utiliser
liste_deja_obtenue : la liste des produits déjà obtenus par les appels récursifs précédents, forme ((coef1, val1) (coef2, val2) ...
 
début
	si val_a_trouver = 0 alors
		ajouter liste_deja_obtenue à la liste globale des décompositions
	sinon si coef_max = 0 ou nombre_max = 0 alors
		ne rien faire, c'est un "échec"
	sinon
		commentaire : on essye de trouver avec un coeff plus petit ou un nombre pluspetit
		decompose(val_a_trouver, coef_max - 1,  nombre_max, liste_deja_obtenue)
		decompose(val_a_trouver, coef_max,  nombre_max - 1, liste_deja_obtenue)
 
		temp <- coef_max * nombre_max
		si temp <= val_a_trouver alors
			nouvelle_liste <- liste_deja_obtenue Union (coef_max, val_max)
			nouvelle_valeur <- val_a_trouver - temp
 
			decompose(nouvelle_valeur, coef_max - 1,  nombre_max, nouvelle_liste)
			decompose(nouvelle_valeur, coef_max,  nombre_max - 1, nouvelle_liste)
 
		finc si
	fin si
fin

Je ne l'ai pas retranscrit dans un langage mais je pense que ça le fait.

[edit] Je l'ai retranscrit et ça ne le fait pas

[hachdotnet]

Edit: Deuxieme ebauche de code en java d'apres ton énoncé...

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
int X=4;
int CMax=4;
int NMax=4;
int[] coefs = new int[100];
int[] values = new int[100];
 
void main(String[] args) {
	AddTerm(0, 1, 0, 0);
}
 
void AddTerm(int nmbterm, int c, int n, int somme) {
 
	// ajoute le terme a la somme actuelle
	if (nmbterm>0) {
		coefs[nmbterm]=c;
		values[nmbterm]=n;
 
		// calcul de la nouvelle valeur de la somme
		somme+=c*n;
	}
 
	// la somme depasse X -> abandon
	if (somme>X) return;
 
	// la somme vaut X -> victoire !
	if (somme==X) {
		System.out.print("(");
		for(int i=1;i<nmbterm;i++)
			System.out.print(coefs[i]+"*"+values[i]+" + ");
		System.out.print(c+"*"+n);
		System.out.println(")");
		return;
	}
 
	// la somme est inferieure a X -> ajoute un nouveau terme c*n
	// (par ordre croissant de c puis n, pour eviter les doublons)
 
	// termes c[i]*n[i] tels que: c[i]=c[i-1] et n[i]>n[i-1] 
	for(int ni=n+1;ni<=NMax;ni++)
		AddTerm(nmbterm+1, c, ni, somme);
 
	// termes c[i]*n[i] tels que: c[i]>c[i-1] et n[i] quelconque 
	for(int ci=c+1;ci<=CMax;ci++)
		for(int ni=1;ni<=NMax;ni++)
			AddTerm(nmbterm+1, ci, ni, somme);
}

Pour X=4, CMax=4 et NMax=4, je trouve:
(1*1 + 1*3)(1*1 + 3*1)(1*2 + 2*1)(1*4)(2*2)(4*1)

Pour X=4, CMax=1 et NMax=4, je trouve:
(1*1 + 1*3)(1*4)

Pour X=4, CMax=3 et NMax=3, je trouve:
(1*1 + 1*3)(1*1 + 3*1)(1*2 + 2*1)(2*2)

Est-ce que c'est bon ?

Oui c juste merci beaucoup..en effet l'algorithme permet de trouver et d'afficher toutes les opérations de somme de la forme cinj+...=X ...BRAVO!!!

[Trap D]

Pour mon plaisir personnel (et parce que je n'aime pas rester sur un échec) voilà une version en C, itérative et utilisant une file (attention, l'implémentation de la file est à revoir en fonction des besoins exacts) :

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <stdio.h>
#include <memory.h>
#include <stdlib.h>
 
#define MAX_IND 10
typedef struct
{
	int Max;
	int ind;
	int CN[MAX_IND][2];
} Cellule;
 
#define MAX_CELL 200
Cellule File[MAX_CELL];
 
int dep = 0;
int fin = 0;
 
int enfile(Cellule *cell)
{
	memcpy(&File[fin], cell, sizeof(Cellule));
	fin++;
	if (fin == MAX_CELL)
		fin = 0;
 
	return 0;
}
 
Cellule *defile(void)
{
	Cellule *ptr = &File[dep];
	dep++;
	if (dep == MAX_CELL)
		dep = 0;
 
	return ptr;
}
 
void reset_file(void)
{
	dep = 0;
	fin = 0;
}
void decompose(int VAL, int C_MAX, int N_MAX)
{
	int i, j;
	Cellule cel = {0};
 
	reset_file();
	enfile(&cel);
	cel.Max = -1;
	enfile(&cel);
	for(i = 1; i <= C_MAX; i++)
	{
		for(j = 1; j <= N_MAX; j++)
		{
			Cellule *ptr;
			int val;
			int k;
 
			ptr = defile();
 
			while(ptr->Max != -1)
			{
				// on commence par enfiler cette cellule;
				enfile(ptr);
 
				// Les calculs
				val = i * j + ptr->Max;
				if (val == VAL)
				{
					// on a trouve le calcul
					for (k = 0; k < ptr->ind; k++)
					{
						printf("(%d * %d) ", ptr->CN[k][0], ptr->CN[k][1]);
					}
					printf("(%d * %d)\n", i, j);
				}
				else
				if (val < VAL)
				{
					// on ajoute ce qui a été trouve et on l'enfile
					ptr->Max = val;
					ptr->CN[ptr->ind][0] = i;
					ptr->CN[ptr->ind][1] = j;
					ptr->ind++;
					if (ptr->ind == MAX_IND)
					{
						fprintf(stderr, "Tableau CN trop petit\n");
						exit(EXIT_FAILURE);
					}
 
					enfile(ptr);
				}
				ptr = defile();
			}
			enfile(ptr);
		}
	}
	puts("**************************");
}
int main(void)
{
	decompose(4,4,4);
	decompose(4,3,3);
	decompose(4,1,4);
	return 0;
 
}