Discussion :

[andjeo]

Voici le problème:

Le langage est le C.

J'ai le tableau suivant de 3 lignes et de cinq colonnes suivant:


40 / 50 / 10 / 00 / 00 / -> 100
00 / 00 / 60 / 00 / 60 / -> 120
00 / 00 / 00 / 90 / 30 / -> 120

40 50 70 90 90

100,120,120 correspondent à la somme de chaque ligne et 40,50,70,90,90 à la somme de chaque colonne
en ajoutant 1 dans une case qui vaut 0 le programme doit changer les cases non nulles sans changer les sommes des lignes et les sommes des colonnes

en ajoutant 1 dans la case de la 3ème ligne et 2ème colonne on obtiendrait grâce au programme le tableau suivant:
40 / 49 / 11 / 00 / 00 / ->100
00 / 00 / 59 / 00 / 61 / ->120
00 / 01 / 00 / 90 / 29 / ->120

40 50 70 90 90

si qqun peut m'aider pour faire se programme...
merci

PS: si vous ne comprenez pas qqch du problème demandez moi
Titre du sujet changé par Miles, "Problème" n'est pas explicite !

[random]

les valeurs négatives sont elles autorisées ?
une ligne ou une colonne comporte telle toujours au départ une valeur
au moins différente de 0 ?

[fearyourself]

Tu auras un autre problème, tu dis que la solution est cela:

40 / 49 / 11 / 00 / 00 / 100
00 / 00 / 59 / 00 / 61 / 120
00 / 01 / 00 / 90 / 29 / 120

Mais, on aurait pu faire juste cela:

41 / 49 / 10 / 00 / 00 / 100
00 / 00 / 60 / 00 / 60 / 120
00 / 01 / 00 / 89 / 30 / 120

Comment faire pour choisir une solution par rapport à l'autre?

Jc

[gangsoleil]

Tu auras un autre problème, tu dis que la solution est cela:

40 / 49 / 11 / 00 / 00 / 100
00 / 00 / 59 / 00 / 61 / 120
00 / 01 / 00 / 90 / 29 / 120

Mais, on aurait pu faire juste cela:

41 / 49 / 10 / 00 / 00 / 100
00 / 00 / 60 / 00 / 60 / 120
00 / 01 / 00 / 89 / 30 / 120

Comment faire pour choisir une solution par rapport à l'autre?

Jc

Très cimple : ta deuxième solution est fausse, puisque la somme des nombres de la colonne 4 change.

Ceci dit, cela nous montre qu'il existe donc des "grilles" sans solution, comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
40 / 50 / 10 / 00 / 00 / 100
00 / 00 / 60 / 00 / 00 /  60
00 / 00 / 00 / 90 / 30 / 120
 
40   50   70   90   30

Auquel on ajoute 1 en 3,3 :

40 / 50 / 10 / 00 / 00 / 100
00 / 00 / 60 / 00 / 00 / 60
00 / 00 / 01 / 90 / 30 / 120

40 50 70 90 30

Je ne vois pas de solution pour garder les mêmes sommes des deux dernières colonnes.

[andjeo]

les valeurs négatives sont elles autorisées ?
une ligne ou une colonne comporte telle toujours au départ une valeur
au moins différente de 0 ?

les valeurs negatives ne sont pas autorisées car ces valeurs correspondent en fait à des quantités...
une ligne ou une colonne comporte toujours au départ une valeur différente de 0 puisque pour chaque ligne et chaque colonne la somme de celles-ci ne doivent pas changer en l'occurence les sommes doivent toujours faire 100 120 120 pr les 3 lignes et 40 50 70 90 90 pour les 5 colonnes.

[andjeo]

Tu auras un autre problème, tu dis que la solution est cela:

40 / 49 / 11 / 00 / 00 / 100
00 / 00 / 59 / 00 / 61 / 120
00 / 01 / 00 / 90 / 29 / 120

Mais, on aurait pu faire juste cela:

41 / 49 / 10 / 00 / 00 / 100
00 / 00 / 60 / 00 / 60 / 120
00 / 01 / 00 / 89 / 30 / 120

Comment faire pour choisir une solution par rapport à l'autre?

Jc

non car dans ta "solution" la somme de ta 4eme colonne change puisquelle fait 89 et non plus 90.

[andjeo]

Tu auras un autre problème, tu dis que la solution est cela:

40 / 49 / 11 / 00 / 00 / 100
00 / 00 / 59 / 00 / 61 / 120
00 / 01 / 00 / 90 / 29 / 120

Mais, on aurait pu faire juste cela:

41 / 49 / 10 / 00 / 00 / 100
00 / 00 / 60 / 00 / 60 / 120
00 / 01 / 00 / 89 / 30 / 120

Comment faire pour choisir une solution par rapport à l'autre?

Jc

Très cimple : ta deuxième solution est fausse, puisque la somme des nombres de la colonne 4 change.

Ceci dit, cela nous montre qu'il existe donc des "grilles" sans solution, comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
40 / 50 / 10 / 00 / 00 / 100
00 / 00 / 60 / 00 / 00 /  60
00 / 00 / 00 / 90 / 30 / 120
 
40   50   70   90   30

Auquel on ajoute 1 en 3,3 :

40 / 50 / 10 / 00 / 00 / 100
00 / 00 / 60 / 00 / 00 / 60
00 / 00 / 01 / 90 / 30 / 120

40 50 70 90 30

Je ne vois pas de solution pour garder les mêmes sommes des deux dernières colonnes.

les valeurs 100 120 120 ne font pas parti du tableau elles correspondent aux sommes des différentes lignes:
si on fait la somme de la premiere ligne on a bien: 40+50+10=100
la 2eme: 60+60=120
et la 3eme: 90+30=120

[FrancisSourd]

Si tu connais les flots, considère le graphe biparti qui a 5 sommets à gauche et 3 sommets à droite. Il y a un arc si la case correspondante de la matrice n'est pas nulle et le flot sur cet arc est égal à la valeur de la matrice.

[andjeo]

Si tu connais les flots, considère le graphe biparti qui a 5 sommets à gauche et 3 sommets à droite. Il y a un arc si la case correspondante de la matrice n'est pas nulle et le flot sur cet arc est égal à la valeur de la matrice.

tu entends quoi par flots, arc et graphe biparti?
j'ai pas tres bien compris ce que tu as écrit...

[ToTo13]

Bonjour,

est ce qu'il ne serait pas plus simple de considérer le tableau comme un système d'équation. Les éléments du tableau sont les inconnues, les sommes sont les égalitées et lorsque l'on bouge un élément on résoud le système.

[random]

toto a raison on peut assimiler cela à un problème classique de programmation linéaire

[ToTo13]

Merci

Donc la résolution serait très rapide. En fait elle serait limitée par le pivot de gauss (O(N^3)) ou tout autre système de résolution.

[andjeo]

Merci

Donc la résolution serait très rapide. En fait elle serait limitée par le pivot de gauss (O(N^3)) ou tout autre système de résolution.

moi je suis d'accord mais on programme ça comment???

[FrancisSourd]

Si tu connais les flots, considère le graphe biparti qui a 5 sommets à gauche et 3 sommets à droite. Il y a un arc si la case correspondante de la matrice n'est pas nulle et le flot sur cet arc est égal à la valeur de la matrice.

tu entends quoi par flots, arc et graphe biparti?
j'ai pas tres bien compris ce que tu as écrit...

Si tu ne connais rien à la théorie des graphes, cela ne va pas être facile de t'expliquer.
Je te conseille ce petit site
http://gilco.inpg.fr/~rapine/Graphe/

Trouver les cases à augmenter et celle à diminuer correspond à trouver un chemin augmentant mais, je ne vois pas comment te l'expliquer en un simple message (cela dépend vraiment de tes connaissances en algorithmique). Et franchement, je ne vois pas comment résoudre ton problème sans parler au moins de graphe. Connais-tu les graphes?

Pour faire le lien avec le message de Toto13, les problèmes de flots peuvent se modéliser comme un programme linéaire.
Ces termes de "graphe", "problème de flots" et "programme linéaire" peuvent t'aider dans tes recherches via google.

[andjeo]

Si tu connais les flots, considère le graphe biparti qui a 5 sommets à gauche et 3 sommets à droite. Il y a un arc si la case correspondante de la matrice n'est pas nulle et le flot sur cet arc est égal à la valeur de la matrice.

tu entends quoi par flots, arc et graphe biparti?
j'ai pas tres bien compris ce que tu as écrit...

Si tu ne connais rien à la théorie des graphes, cela ne va pas être facile de t'expliquer.
Je te conseille ce petit site
http://gilco.inpg.fr/~rapine/Graphe/

Trouver les cases à augmenter et celle à diminuer correspond à trouver un chemin augmentant mais, je ne vois pas comment te l'expliquer en un simple message (cela dépend vraiment de tes connaissances en algorithmique). Et franchement, je ne vois pas comment résoudre ton problème sans parler au moins de graphe. Connais-tu les graphes?

Pour faire le lien avec le message de Toto13, les problèmes de flots peuvent se modéliser comme un programme linéaire.
Ces termes de "graphe", "problème de flots" et "programme linéaire" peuvent t'aider dans tes recherches via google.

c'est trop compliquer mais merci qd même

[andjeo]

Qqun a t-il une autre idée???

[pcaboche]

Qqun a t-il une autre idée???

Oui: Programmation Logique avec Contraintes (sur domaine fini) en Prolog.

Programme en swi-prolog :

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
:- use_module(library('clp/bounds')).
 
resoud(Vars) :-
 
  Vars = 
   [A1, A2, A3, A4, A5,
    B1, B2, B3, B4, B5,
    C1, C2, C3, C4, C5],
 
  Vars in 1..120,
 
  A1 + A2 + A3 + A4 + A5 #= 100,
  B1 + B2 + B3 + B4 + B5 #= 120,
  C1 + C2 + C3 + C4 + C5 #= 120,
 
  A1 + B1 + C1 #= 40,
  A2 + B2 + C2 #= 50,
  A3 + B3 + C3 #= 70,
  A4 + B4 + C4 #= 90,
  A5 + B5 + C5 #= 90,
 
  label(Vars),
 
  write([A1, A2, A3, A4, A5]), nl,
  write([B1, B2, B3, B4, B5]), nl,
  write([C1, C2, C3, C4, C5]), nl.

Son exécution retourne plusieurs solutions.


Ce sera beaucoup plus efficace qu'une approche par essais/erreur comme en C, en plus c'est très facile à programmer comme vous pouvez le constater.

Si quelqu'un connait une bibliothèque de PLC pour le C, qu'il le fasse savoir (Prolog s'interface très bien avec C).

[andjeo]

Qqun a t-il une autre idée???

Oui: Programmation Logique avec Contraintes (sur domaine fini) en Prolog.

Programme en swi-prolog :

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
:- use_module(library('clp/bounds')).
 
resoud(Vars) :-
 
  Vars = 
   [A1, A2, A3, A4, A5,
    B1, B2, B3, B4, B5,
    C1, C2, C3, C4, C5],
 
  Vars in 1..120,
 
  A1 + A2 + A3 + A4 + A5 #= 100,
  B1 + B2 + B3 + B4 + B5 #= 120,
  C1 + C2 + C3 + C4 + C5 #= 120,
 
  A1 + B1 + C1 #= 40,
  A2 + B2 + C2 #= 50,
  A3 + B3 + C3 #= 70,
  A4 + B4 + C4 #= 90,
  A5 + B5 + C5 #= 90,
 
  label(Vars),
 
  write([A1, A2, A3, A4, A5]), nl,
  write([B1, B2, B3, B4, B5]), nl,
  write([C1, C2, C3, C4, C5]), nl.

Son exécution retourne plusieurs solutions.


Ce sera beaucoup plus efficace qu'une approche par essais/erreur comme en C, en plus c'est très facile à programmer comme vous pouvez le constater.

Si quelqu'un connait une bibliothèque de PLC pour le C, qu'il le fasse savoir (Prolog s'interface très bien avec C).

c'est quoi du prolog et swi-prolog?

[pcaboche]

c'est quoi du prolog et swi-prolog?

Au départ, c'était une boutade (parce que, quand quelqu'un dit: "j'ai un problème et j'aimerais une implémentation dans tel langage" (C, VB ou autre), j'aime bien montrer qu'on peut résoudre le problème de manière très simple en Prolog)

Prolog est un véritable langage de programmation (PROgrammation LOGique). Swi-prolog est une implémentation de ce langage (il en existe plusieurs: swi-prolog, gprolog, Sicstus Prolog, Quintus Prolog...). Swi-prolog est gratuit (au contraire de Sicstus, par exemple).

Prolog est un langage assez particulier car il permet de résoudre certains problèmes de manière assez simple (problèmes de logique, de logique avec contraintes, d'IA...). Prolog ne permet pas de faire de jolies interfaces graphiques avec des soucoupes volantes qui volent, pour cela il y a d'autres langages (C, C++, Java...). En revanche Prolog peut s'interfacer avec d'autres langages (suivant les implémentations). Au final, Prolog fait relativement peu de choses, mais il les fait bien; pour le reste, il y a d'autres langages.

Pour plus d'info sur Prolog, il y a mon article: http://pcaboche.developpez.com/artic.../presentation/
et pour la Programmation Logique avec Contraintes: http://pcaboche.developpez.com/artic...og/clp/sudoku/

[andjeo]

c'est quoi du prolog et swi-prolog?

Au départ, c'était une boutade (parce que, quand quelqu'un dit: "j'ai un problème et j'aimerais une implémentation dans tel langage" (C, VB ou autre), j'aime bien montrer qu'on peut résoudre le problème de manière très simple en Prolog)

Prolog est un véritable langage de programmation (PROgrammation LOGique). Swi-prolog est une implémentation de ce langage (il en existe plusieurs: swi-prolog, gprolog, Sicstus Prolog, Quintus Prolog...). Swi-prolog est gratuit (au contraire de Sicstus, par exemple).

Prolog est un langage assez particulier car il permet de résoudre certains problèmes de manière assez simple (problèmes de logique, de logique avec contraintes, d'IA...). Prolog ne permet pas de faire de jolies interfaces graphiques avec des soucoupes volantes qui volent, pour cela il y a d'autres langages (C, C++, Java...). En revanche Prolog peut s'interfacer avec d'autres langages (suivant les implémentations). Au final, Prolog fait relativement peu de choses, mais il les fait bien; pour le reste, il y a d'autres langages.

Pour plus d'info sur Prolog, il y a mon article: http://pcaboche.developpez.com/artic.../presentation/
et pour la Programmation Logique avec Contraintes: http://pcaboche.developpez.com/artic...og/clp/sudoku/

d'accord
le problème c'est qu'il faut que j'utilise ce que j'ai appris cette année et je n'ai appris que les bases du C.