Problèmes des n reines sur un echiquier n *n
Résolu
pipleton
Messages postés
23
Date d'inscription
Statut
Membre
Dernière intervention
-
ccm81 Messages postés 10909 Date d'inscription Statut Membre Dernière intervention -
ccm81 Messages postés 10909 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
Je dois réaliser un échiquier 4 * 4 dans lequel je dois placer une reine par colonne. Ensuite je dois calculer le nombre de conflit présent dans l'échiquier. Je m'explique une reine peut se déplacer en ligne, colonne ou diagonale. Chaque déplacement possible compte pour 1 ( soit le conflit).
Ainsi, l'échiquier (R = reine, 0 = pions) ci dessous possède 5 conflits.
R 0 R 0
0 R 0 R
0 0 0 0
0 0 0 0
J'ai réussi à implémenter l'échiquier ci dessus mais je n'arrive pas a calculer le nombre de conflits. En effet, si je ne compte pas les diagonales j'arrive à 4 ce qui est normal mais lorsque je compte les diagonales j'arrive à 6. En effet, il me compte deux fois la même prise! J'ai bien essayé une condition composé mais rien n'y fait! Par la suite l'échiquier sera généré aléatoirement (mais la ce n'est pas la question!). Pouvez vous m'aider?
Voici l'algorithme
#include <stdio.h>
#include <stdlib.h>
int main()
{
//partie déclarative
int tableau[4][4] = {{1,0,1,0},
{0,1,0,1},
{0,0,0,0},
{0,0,0,0}};// 0=pion, 1 = reine
int i,j,conflit;
//calcul du nombre de prise
conflit = 0;
//pour chaque ligne
for(i=0;i<4;i++){
//pour chaque colonne
for(j=0;j<4;j++){
if(tableau[i][j]==1)
{
if(tableau[i][j+1]==0)
{
conflit = conflit +1;
}
if(tableau[i+1][j+1]==0)
{
conflit = conflit +1;
}
}
}
}
printf("%s %d","H="conflit);
return 0;
}
Je dois réaliser un échiquier 4 * 4 dans lequel je dois placer une reine par colonne. Ensuite je dois calculer le nombre de conflit présent dans l'échiquier. Je m'explique une reine peut se déplacer en ligne, colonne ou diagonale. Chaque déplacement possible compte pour 1 ( soit le conflit).
Ainsi, l'échiquier (R = reine, 0 = pions) ci dessous possède 5 conflits.
R 0 R 0
0 R 0 R
0 0 0 0
0 0 0 0
J'ai réussi à implémenter l'échiquier ci dessus mais je n'arrive pas a calculer le nombre de conflits. En effet, si je ne compte pas les diagonales j'arrive à 4 ce qui est normal mais lorsque je compte les diagonales j'arrive à 6. En effet, il me compte deux fois la même prise! J'ai bien essayé une condition composé mais rien n'y fait! Par la suite l'échiquier sera généré aléatoirement (mais la ce n'est pas la question!). Pouvez vous m'aider?
Voici l'algorithme
#include <stdio.h>
#include <stdlib.h>
int main()
{
//partie déclarative
int tableau[4][4] = {{1,0,1,0},
{0,1,0,1},
{0,0,0,0},
{0,0,0,0}};// 0=pion, 1 = reine
int i,j,conflit;
//calcul du nombre de prise
conflit = 0;
//pour chaque ligne
for(i=0;i<4;i++){
//pour chaque colonne
for(j=0;j<4;j++){
if(tableau[i][j]==1)
{
if(tableau[i][j+1]==0)
{
conflit = conflit +1;
}
if(tableau[i+1][j+1]==0)
{
conflit = conflit +1;
}
}
}
}
printf("%s %d","H="conflit);
return 0;
}
A voir également:
- Problèmes des n reines sur un echiquier n *n
- Télécharger la reine des neiges 1 le film en entier en français complet gratuit - Télécharger - Streaming vidéo
- Chanson dans "Les reines du shopping" - Forum Musique / Radio / Clip
- La reine des neiges - Forum Lecteurs et supports vidéo
- Musique du début des reines du shopping semaine du 08/06 au 12/06/2020 ✓ - Forum Musique / Radio / Clip
- La reine des bisous exploitation maternelle - Forum Virus
15 réponses
Et moi Je ne comprends pas le raisonnement employer pour arriver à ces résultats.
EDIT :
Si ont prend ton dernier exemple...
1 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
conflit = 3
Moi je verrais..
Conflit 1 > A1/B2
Conflit 2 > C1/B2
Conflit 3 > B2/A1
Conflit 4 > B2/C1
??
L'expérience instruit plus sûrement que le conseil. (André Gide)
Si tu te cognes à un pot et que ça sonne creux, c'est pas forcément le pot qui est vide. ;-)(Confucius)
NOTE : Je ne répond pas aux MP pour les questions techniques.
Ça doit se passer sur le forum pour que tous puisse y participer ou en profiter.
EDIT :
Si ont prend ton dernier exemple...
1 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
conflit = 3
Moi je verrais..
Conflit 1 > A1/B2
Conflit 2 > C1/B2
Conflit 3 > B2/A1
Conflit 4 > B2/C1
??
L'expérience instruit plus sûrement que le conseil. (André Gide)
Si tu te cognes à un pot et que ça sonne creux, c'est pas forcément le pot qui est vide. ;-)(Confucius)
NOTE : Je ne répond pas aux MP pour les questions techniques.
Ça doit se passer sur le forum pour que tous puisse y participer ou en profiter.
re
pour comptage à la main, sur l'exemple
1 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
on note (ligne, colonne) les coordonnées
- reine (1,1) en conflit avec (1,3), et (2,2)
- reine (1,3) en conflit avec (1,1) et (2,2)
- reine (2,2) en conflit avec (1,1) et (1,3)
- reine (3,4) en conflit avec personne
donc 6 conflits orientés
et 3 conflits non orientés
pour comptage à la main, sur l'exemple
1 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
on note (ligne, colonne) les coordonnées
- reine (1,1) en conflit avec (1,3), et (2,2)
- reine (1,3) en conflit avec (1,1) et (2,2)
- reine (2,2) en conflit avec (1,1) et (1,3)
- reine (3,4) en conflit avec personne
donc 6 conflits orientés
et 3 conflits non orientés
si !
d'ailleurs avec la sienne aussi, sauf que comme il compte les conflits orientés et donc 6+4 = 10 donc 5 conflits non orientés
le hic, c'est qu'on a du mal a savoir si c'est le comptage a la main ou l'algorithme qui lui pose pb
au passage, j'ai envoyé une demande sur "comment mettre les titres sur les axes excel 2010", et comme ça ne répond pas, est ce que tu connais?
d'ailleurs avec la sienne aussi, sauf que comme il compte les conflits orientés et donc 6+4 = 10 donc 5 conflits non orientés
le hic, c'est qu'on a du mal a savoir si c'est le comptage a la main ou l'algorithme qui lui pose pb
au passage, j'ai envoyé une demande sur "comment mettre les titres sur les axes excel 2010", et comme ça ne répond pas, est ce que tu connais?
mais non je suis pas d'accord si je boucle de 0 à 3 je ne fais que les valeur 0,1,2!!!
Pour mon histoire de conflit, c'est le nombre de prise possible par une reine en gros. Ainsi une reine peut se déplacer, verticalement, horizontalement et en diagonale mais ne peut pas revenir sur ses pas! Ai je été pus clair?
Merci tout de même
Pour mon histoire de conflit, c'est le nombre de prise possible par une reine en gros. Ainsi une reine peut se déplacer, verticalement, horizontalement et en diagonale mais ne peut pas revenir sur ses pas! Ai je été pus clair?
Merci tout de même
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
bonjour a tous les trois
peut être : si pour chaque reine tu compte le nombre de conflits (orientés) , tu devrais trouver le double du total des conflits (non orientés)
bonne suite
peut être : si pour chaque reine tu compte le nombre de conflits (orientés) , tu devrais trouver le double du total des conflits (non orientés)
bonne suite
Je suis tout a fait d'accord avec vous.Je préfererai pour ma part compter les conflits orientés. Pour le premier echiquier je suis passé par un tableau temporaire et cela fonctionne. Par contre si je prends les echiquiers ci dessous je en trouve pas le nombre de conflit voulus! Pouvez vous m'aider?
1 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
conflit = 3
1 0 1 0
0 0 0 0
0 0 0 1
0 1 0 0
conflit = 1
Merci d'avance
je remets mon code :
#include <stdio.h>
#include <stdlib.h>
int main()
{
//partie déclarative
int tableau[4][4] = {{1,0,1,0},
{0,1,0,1},
{0,0,0,0},
{0,0,0,0}};// 0=pion, 1 = reine
int temp[4][4] = {{0,0,0,0},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0}};// 0=pion, 1 = reine;
int i,j,conflit;
//affichage du tableau
for(i=0;i<4;i++){
for(j=0;j<4;j++){
printf("%d",tableau[i][j]);
}
printf("\n");
}
//calcul du nombre de prise
conflit = 0;
//pour chaque ligne
for(i=0;i<4;i++){
//pour chaque colonne
for(j=0;j<4;j++){
if(tableau[i][j]==1)
{
if(tableau[i][j+1]==0)
{
temp[i+1][j]=2;
conflit ++;
if(tableau[i+1][j+1]==0 && temp[i][j+1]!=2)
{
conflit ++;
}
}
}
}
}
printf("%s%d","H=", conflit);
return 0;
}
1 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
conflit = 3
1 0 1 0
0 0 0 0
0 0 0 1
0 1 0 0
conflit = 1
Merci d'avance
je remets mon code :
#include <stdio.h>
#include <stdlib.h>
int main()
{
//partie déclarative
int tableau[4][4] = {{1,0,1,0},
{0,1,0,1},
{0,0,0,0},
{0,0,0,0}};// 0=pion, 1 = reine
int temp[4][4] = {{0,0,0,0},
{0,0,0,0},
{0,0,0,0},
{0,0,0,0}};// 0=pion, 1 = reine;
int i,j,conflit;
//affichage du tableau
for(i=0;i<4;i++){
for(j=0;j<4;j++){
printf("%d",tableau[i][j]);
}
printf("\n");
}
//calcul du nombre de prise
conflit = 0;
//pour chaque ligne
for(i=0;i<4;i++){
//pour chaque colonne
for(j=0;j<4;j++){
if(tableau[i][j]==1)
{
if(tableau[i][j+1]==0)
{
temp[i+1][j]=2;
conflit ++;
if(tableau[i+1][j+1]==0 && temp[i][j+1]!=2)
{
conflit ++;
}
}
}
}
}
printf("%s%d","H=", conflit);
return 0;
}
re
je suis d'accord avec tes resultats sur les deux exemples ci-dessus
je ne connais pas le C++
mais une autre idée
si on compte (bestial) comme conflit une reine avec elle même ça nous fait 3 fois plus d'orientés que de non orientés et on n'a plus a s'embeter pour les plages de boucle
bon, c'est intéressant, je vais tenter en VBA
je suis d'accord avec tes resultats sur les deux exemples ci-dessus
je ne connais pas le C++
mais une autre idée
si on compte (bestial) comme conflit une reine avec elle même ça nous fait 3 fois plus d'orientés que de non orientés et on n'a plus a s'embeter pour les plages de boucle
bon, c'est intéressant, je vais tenter en VBA
Bonjour,
Quand tu "prend" un pion, remplacer la valeur de la case, par exemple par "S" cette case ne serait plus prise en compte.
A+
Quand tu "prend" un pion, remplacer la valeur de la case, par exemple par "S" cette case ne serait plus prise en compte.
A+
Tout a fait c'est ce que j'ai fait!Mais ça ne marche pas! car pour un echiquier donner suivant on doit trouver un conflit = 3 et un conflit = 1
1 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
conflit = 3
1 0 1 0
0 0 0 0
0 0 0 1
0 1 0 0
conflit = 1
Je ne comprends pas comment les trouver!
Merci d'avance
1 0 1 0
0 1 0 0
0 0 0 1
0 0 0 0
conflit = 3
1 0 1 0
0 0 0 0
0 0 0 1
0 1 0 0
conflit = 1
Je ne comprends pas comment les trouver!
Merci d'avance
re
tu ne comprends pas quoi
- comment on les compte sur le papier ?
- comment on programme l'histoire ?
tu ne comprends pas quoi
- comment on les compte sur le papier ?
- comment on programme l'histoire ?
Bizarre mais ok. Enfin pas tout a fait puisque j'ai cru comprendre qu'elles ne pouvaient que descendre donc (1,1) ne devrait pas etre en conflit avec (2,2). De meme pour (1,3) avec (2,2).
Si elles peuvent descendre. Si je les laisser comprendre auparavant je m'en excuse. Mais comment peut on faire pour l'algorithme??? Parce que le miens n'a pas l'air bon, pouvez vous m'éclairer mes erreurs et m'aider à résoudre ce problème?
re
en VBA , ceci fonctionne (à priori)
- n est le nombre de lignes/colonnes de l'échiquier
- T est le tableau echiquier rempli de "" ou de "R"
- on ne compte que les conflits non orientés , donc en descendant (c'est finalement plus simple et moins bestial)
- à toi de traduire en C
bonne suite
en VBA , ceci fonctionne (à priori)
- n est le nombre de lignes/colonnes de l'échiquier
- T est le tableau echiquier rempli de "" ou de "R"
- on ne compte que les conflits non orientés , donc en descendant (c'est finalement plus simple et moins bestial)
- à toi de traduire en C
Function NbConflits2(n As Long) As Long
Dim nc As Long, li As Long, co As Long, c As Long, l As Long
Dim T
T = Range("echiquier").Value
nc = 0
For li = 1 To n
For co = 1 To n
If T(li, co) = "R" Then
' conflits dans ligne li
For c = co + 1 To n
If T(li, c) = "R" Then
nc = nc + 1
End If
Next c
' conflits dans colonne co
For l = li + 1 To n
If T(l, co) = "R" Then
nc = nc + 1
End If
Next l
' conflits dans diagonale1 \ en descendant à droite
l = li: c = co
While l < n And c < n
l = l + 1: c = c + 1
If T(l, c) = "R" Then
nc = nc + 1
End If
Wend
' conflits dans diagonale2 / en descendant à gauche
l = li: c = co
While l < n And c > 1
l = l + 1: c = c - 1
If T(l, c) = "R" Then
nc = nc + 1
End If
Wend
End If
Next co
Next li
NbConflits2 = nc
End Function
bonne suite
C'est bon j'ai enfin réussi à faire ce que je voulais!Merci de votre aide à tous
Bonne soirée ou plutot bonne nuit
Bonne soirée ou plutot bonne nuit
tu as compté 2 fois le conflit C1/B2
d'où la distinction (importante) orienté et non orienté