Привет всем.
Вот тут есть задачка, требуется решить,есть тут такие кто её решит???
Пасиб!!!!
Привет всем.
Вот тут есть задачка, требуется решить,есть тут такие кто её решит???
Пасиб!!!!
.Набросал тебе по быстрому рекурсивный алгоритм в C++. В псевдокод, думаю, не сложно будет переписать. При помощи "Backtracking" алгоритм отыскивает возможные решения. Полагаю задание с первого курса университета?
#include <stdio.h>
#include <stdlib.h>
int x = 4;
int y = 4;
int c = 0;
int count = 0;
struct knoten {
int oben;
int unten;
int rechts;
int links;
};
struct knoten k[4][4];
void brettausgabe()
{
int i,j;
for(i=0; i<x; i++) {
printf("\n");
for(j=0; j<y; j++){
if(k[i][j].rechts) printf(" +-");
else if(k[i][j].links) printf("-+ ");
else printf(" + ");
}
printf("\n");
for (j=0; j<y; j++){
if(k[i+1][j].oben) printf(" | ");
else printf (" ");
}
}
printf("\n");
}
int pruefen(int i, int j)
{
return !( k[i][j].oben || k[i][j].unten || k[i][j].rechts || k[i][j].links);
}
void u_k_r (int i, int j, int val)
{
k[i][j].rechts = val;
k[i][j].unten = val; // +---+
k[i][j+1].links = val; // |
k[i+1][j].oben = val; // x
}
void r_u (int i, int j, int val)
{
k[i][j].rechts = val; // +---+
k[i][j+1].links = val; // |
k[i+1][j+1].oben = val; // +
}
void u_l (int i, int j, int val)
{
k[i][j].unten = val; // +
k[i+1][j].links = val; // |
k[i+1][j].oben = val; // +---+
k[i+1][j-1].rechts = val;
}
void u_r (int i, int j, int val)
{
k[i][j].unten = val; // +
k[i+1][j].rechts = val; // |
k[i+1][j].oben = val; // +---+
k[i+1][j+1].links = val;
}
void platzieren (int i, int j)
{
if (c == (x*x-1))
{
printf("Loesung %i:\n",count+1);
brettausgabe();
count++;
}
else {
if (pruefen (i,j)){
if (pruefen(i,j+1) && pruefen(i+1,j) && i<y-1 && j<x-1) {
u_k_r(i,j,1);
c = c + 3;
if (j >= x-2) {platzieren(i+1, 0); // +---+
u_k_r(i,j,0); // |
c = c - 3; // x
}
else {platzieren(i, j+1);
u_k_r(i,j,0);
c = c - 3;
}
};
if(pruefen(i,j+1) && pruefen(i+1,j+1) && i<y-1 && j<x-1) {
r_u(i,j,1);
c = c + 3;
if (j >= x-1) {platzieren(i+1, 0); // +---+
r_u(i,j,0); // |
c = c - 3; // +
}
else {platzieren(i, j+1);
r_u(i,j,0);
c = c - 3;
}
};
if (pruefen(i+1,j) && pruefen(i+1,j-1) && i<y-1 && j>0 && j<x) {
u_l(i,j,1);
c = c + 3;
if (j >= x-1) {platzieren(i+1, 0); // +
u_l(i,j,0); // |
c = c - 3; // +---+
}
else {platzieren(i, j+1);
u_l(i,j,0);
c = c - 3;
}
};
if (pruefen(i+1,j) && pruefen(i+1,j+1) && i<y-1 && j<x-1) {
u_r(i,j,1);
c = c + 3;
if (j >= x-2) {platzieren(i+1, 0); // +
u_r(i,j,0); // |
c = c - 3; // +---+
}
else {platzieren(i, j+1);
u_r(i,j,0);
c = c - 3;
}
};
}
else
{
if (j >= x-1) {platzieren(i+1, 0);}
else {platzieren(i, j+1);}}
}
}
int main()
{
platzieren(0,0);
printf("\n");
printf("Anzahl der Loesungen: %i\n\n",count);
return 0;
}
Показать весь код
Так отрабатывает алгоритм для квадрата 4 x 4:
Loesung 1:
+--+ +--+
| |
+ +--+ +
|
+ + +--+
| |
+--+ + +
Loesung 2:
+--+ +--+
| |
+ +--+ +
|
+ + +--+
| |
+--+ + +
Loesung 3:
+--+ +--+
| |
+ +--+ +
|
+ + + +
| |
+--+ +--+
Loesung 4:
+--+ +--+
| |
+ +--+ +
|
+--+ + +
| |
+ + +--+
Loesung 5:
+--+ +--+
| |
+ +--+ +
|
+--+ + +
| |
+ + +--+
Loesung 6:
+--+ + +
| |
+ + +--+
|
+ +--+ +
| |
+--+ +--+
Показать весь код
Сейчас заметил, что алгоритм отыскивает не все возможные решения, если время будет вечерком доработаю!
[/B]Успехов![/B]
Доработал процедуру "platzieren", теперь рекурсивный алгоритм выдаёт все возможные решения. Утром, перед работой, времени мало было;-)
void platzieren (int i, int j)
{
if (c == (x*x-1))
{
printf("Loesung %i:\n",count+1);
brettausgabe();
count++;
}
else {
if (pruefen (i,j)){
if (pruefen(i,j+1) && pruefen(i+1,j) && i<y-1 && j<x-1) {
u_k_r(i,j,1);
c = c + 3;
if (j >= x-2) {platzieren(i+1, 0); // +---+
u_k_r(i,j,0); // |
c = c - 3; // x
}
else {platzieren(i, j+1);
u_k_r(i,j,0);
c = c - 3;
}
};
if(pruefen(i,j+1) && pruefen(i+1,j+1) && i<y-1 && j<x-1) {
r_u(i,j,1);
c = c + 3;
if (j >= x-1) {platzieren(i+1, 0); // +---+
r_u(i,j,0); // |
c = c - 3; // +
}
else {platzieren(i, j+1);
r_u(i,j,0);
c = c - 3;
}
};
if(pruefen(i,j+2) && pruefen(i+1,j+2) && pruefen(i,j+1) && i<y-1 && j<x-2) {
r_u(i,j+1,1);
c = c + 3;
if (j >= x-1) {platzieren(i+1, 0); // ++---+
r_u(i,j+1,0); // |
c = c - 3; // +
}
else {platzieren(i, j+1);
r_u(i,j+1,0);
c = c - 3;
}
};
if (pruefen(i+1,j+1) && pruefen(i+1,j) && pruefen(i,j+1) && i<y-1 && j<x-1) {
u_l(i,j+1,1);
c = c + 3;
if (j >= x-1) {platzieren(i+1, 0); // +...+
u_l(i,j+1,0); // |
c = c - 3; // +---+
}
else {platzieren(i, j+1);
u_l(i,j+1,0);
c = c - 3;
}
};
if (pruefen(i+1,j) && pruefen(i+1,j-1) && i<y-1 && j>0 && j<x) {
u_l(i,j,1);
c = c + 3;
if (j >= x-1) {platzieren(i+1, 0); // +
u_l(i,j,0); // |
c = c - 3; // +---+
}
else {platzieren(i, j+1);
u_l(i,j,0);
c = c - 3;
}
};
if (pruefen(i+2,j) && pruefen(i+2,j-1) && pruefen(i+1,j) && i<y-2 && j>0 && j<x) {
u_l(i+1,j,1);
c = c + 3;
// +
if (j >= x-1) {platzieren(i+1, 0); // +
u_l(i+1,j,0); // |
c = c - 3; // +---+
}
else {platzieren(i, j+1);
u_l(i+1,j,0);
c = c - 3;
}
};
if (pruefen(i+2,j) && pruefen(i+2,j+1) && pruefen(i+1,j) && i<y-2 && j<x-1) {
u_r(i+1,j,1);
c = c + 3;
// +
if (j >= x-2) {platzieren(i+1, 0); // +
u_r(i+1,j,0); // |
c = c - 3; // +---+
}
else {platzieren(i, j+1);
u_r(i+1,j,0);
c = c - 3;
}
};
if (pruefen(i+1,j) && pruefen(i+1,j+1) && i<y-1 && j<x-1) {
u_r(i,j,1);
c = c + 3;
if (j >= x-2) {platzieren(i+1, 0); // +
u_r(i,j,0); // |
c = c - 3; // +---+
}
else {
if (pruefen(i,j+1) && !pruefen(i,j+2) && !pruefen(i-1,j+1)) platzieren(i, j+2);
else platzieren(i, j+1);
u_r(i,j,0);
c = c - 3;
}
};
}
else
{
if (j >= x-1) {platzieren(i+1, 0);}
else {platzieren(i, j+1);}}
}
}
Показать весь код
Все возможные решения для квадрата 4 x 4:
Loesung 1:
+--+ +--+
| |
+ + + +
|
+ +--+ +
| |
+--+ +--+
Loesung 2:
+--+ +--+
| |
+ +--+ +
|
+ + +--+
| |
+--+ + +
Loesung 3:
+--+ +--+
| |
+ +--+ +
|
+ + +--+
| |
+--+ + +
Loesung 4:
+--+ +--+
| |
+ +--+ +
|
+ + + +
| |
+--+ +--+
Loesung 5:
+--+ +--+
| |
+ +--+ +
|
+ + + +
| |
+--+ +--+
Loesung 6:
+--+ +--+
| |
+ +--+ +
|
+--+ + +
| |
+ + +--+
Loesung 7:
+--+ +--+
| |
+ +--+ +
|
+--+ + +
| |
+ + +--+
Loesung 8:
+--+ +--+
| |
+ +--+ +
|
+ + + +
| |
+--+ +--+
Loesung 9:
+--+ +--+
| |
+ +--+ +
|
+ + + +
| |
+--+ +--+
Loesung 10:
+--+ +--+
| |
+ + + +
|
+ +--+ +
| |
+--+ +--+
Loesung 11:
+--+ +--+
| |
+ + + +
|
+ +--+ +
| |
+--+ +--+
Loesung 12:
+--+ + +
| |
+ + +--+
|
+ +--+ +
| |
+--+ +--+
Loesung 13:
+--+ + +
| |
+ + +--+
|
+ +--+ +
| |
+--+ +--+
Loesung 14:
+--+ +--+
| |
+ + + +
|
+ +--+ +
| |
+--+ +--+
Loesung 15:
+ + +--+
| |
+--+ + +
|
+ +--+ +
| |
+--+ +--+
Loesung 16:
+ + +--+
| |
+--+ + +
|
+ +--+ +
| |
+--+ +--+
Anzahl der Loesungen: 16
Показать весь код
Пасиб большое, то что нужно!!!!
:ok: :ok: :ok: :ok: :ok: