Greedy algorithm is an algorithmic paradigm that follows the problem solving heuristic of making the locally optimal choice at each stage
with the hope of finding a global optimum. In many problems, a greedy strategy does not in general produce an optimal solution, but nonetheless a
greedy heuristic may yield locally optimal solutions that approximate a global optimal solution in a reasonable time.
/*a horse through the whole chessboard passing once through each
box*/
#define _CRT_SECURE_NO_DEPRECATE
#include <stdio.h>
#include <conio.h>
#include <iostream>
#include <windows.h>
#include <process.h>
using namespace std;
void gotoxy(int, int); // prototype
void clrscr(); // prototype
#define N 8
#define NDIR 8
int plusx[]={0,-2,-2,-1,1,2,2,1,-1};
int plusy[]={0,-1,1,2,2,1,-1,-2,-2};
int a[N+1][N+1];
// function definition -- requires windows.h
void gotoxy(int x, int y)
{
HANDLE hConsoleOutput;
COORD dwCursorPosition;
cout.flush();
dwCursorPosition.X = x;
dwCursorPosition.Y = y;
hConsoleOutput = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleCursorPosition(hConsoleOutput,dwCursorPosition);
}
// function definition -- requires process.h
void clrscr()
{
system("cls");
}
/*se verifica daca coordonatele sunt in interiorul tablei si daca casuta
respectiva este libera(nu s-a mai trecut prin ea).Intoarce 1 daca se verifica
conditia anterioara si 0 in caz contrar*/
int conditie(int lin,int col)
{
return ((lin > 0) && (lin <=N) && (col > 0) && (col <=N) && (a[lin] == 0));
}
/*numara posibilitatea de continuare din pozitia(lin,col):daca numarul de casute
neocupate in care s-ar putea deplasa calul*/
int posib_continuare(int lin,int col)
{
int dir,sum,_lin,_col;
for(dir = 1,sum = 0;dir<=NDIR;dir++)
{
_col = col + plusx[dir];
_lin = lin + plusy[dir];
if(conditie(_lin,_col))
sum++;
}
return sum;
}
/*initializeaza tabla de sah cu 0.Deoarece variabila tablou a este globala
ea este initializata implicit cu 0,insa este mai bine ca un programator sa
se obisnuiasca sa nu lase variabile neinitializate*/
void init_tabla()
{
int lin,col;
for(lin = 1;lin <= N;lin++)
for(col = 1;col <= N;col++)
a[lin] = 0;
}
/*citeste linia si coloana unde va fi plasat calul la initializare*/
void cit_date(int *lin,int *col)
{
clrscr();
printf("Introduceti pozitia initiala: \n");
printf("Linia: ");
scanf("%d",lin);
printf("Coloana: ");
scanf("%d",col);
}
/*functia principala*/
void run(int lin,int col)
{
int new_lin,new_col,i0,j0,k;
int min,dir;
clrscr();
a[lin] = 1;
gotoxy(col * 3,lin);
printf("1");
for(k=1;k<N*N;k++)
{
i0 = 0;
min = 8;
for(dir =1;dir<=NDIR;dir++)
{
new_lin = lin + plusy[dir];
new_col = col + plusx[dir];
if(conditie(new_lin,new_col))
if(k == N*N-1)
{
i0 = new_lin;
j0 = new_col;
}
else
if((posib_continuare(new_lin,new_col) != 0) && (posib_continuare(new_lin,new_col) < min))
{
min = posib_continuare(new_lin,new_col);
i0 = new_lin;
j0 = new_col;
}
}
if(i0 == 0)
{
printf("Nu avem solutie!");
return;
}
lin = i0;
col = j0;
a[lin] = k + 1;
gotoxy(col * 3,lin);
printf("%d\n",a[lin]);
}
}
void main()
{
int l,c;
init_tabla();
cit_date(&l,&c);
run(l,c);
}
37,483 total views, 1 views today
