Задачка по информатике

adwokat · 29 Ноя 2008

Привет всем.

Вот тут есть задачка, требуется решить,есть тут такие кто её решит???

Пасиб!!!!

Demo · 1 Дек 2008

.Набросал тебе по быстрому рекурсивный алгоритм в C++. В псевдокод, думаю, не сложно будет переписать. При помощи "Backtracking" алгоритм отыскивает возможные решения. Полагаю задание с первого курса университета?

C

#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]

Demo · 1 Дек 2008

Доработал процедуру "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

Показать весь код

adwokat · 1 Дек 2008

Пасиб большое, то что нужно!!!!

:ok: :ok: :ok: :ok: :ok:

Поделиться