QReferate - referate pentru educatia ta.
Cercetarile noastre - sursa ta de inspiratie! Te ajutam gratuit, documente cu imagini si grafice. Fiecare document sau comentariu il poti downloada rapid si il poti folosi pentru temele tale de acasa.



AdministratieAlimentatieArta culturaAsistenta socialaAstronomie
BiologieChimieComunicareConstructiiCosmetica
DesenDiverseDreptEconomieEngleza
FilozofieFizicaFrancezaGeografieGermana
InformaticaIstorieLatinaManagementMarketing
MatematicaMecanicaMedicinaPedagogiePsihologie
RomanaStiinte politiceTransporturiTurism
Esti aici: Qreferat » Documente informatica

Backtracking pe tabla de sah



Backtracking pe tabla de sah

1. Problema turelor

1.1. Enuntul si consideratii

Problema: Sa se aranjeze pe o tabla de sah de dimensiuni n x n un numar de n ture astfel incat
oricare doua ture sa nu se ameninte.

Rezolvare: trebuie sa observam mai intai ca nu pot fi doua ture pe aceeasi coloana, caci astfel ar fi
doua ture care s-ar ameninta reciproc, rezulta ca fiecare coloana are exact 1 tura. Fie x[i] linia pe
care se afla tura de pe coloana i. Tinand cont ca nu pot fi doua ture pe aceeasi linie, este:



(xx, x . , xn) = a (xi <>xj)
1 <= i < j <= n

De unde, prin serializare obtinem functia omega corespunzatoare:

Wk(x[1], x[2], , x[k]) = a (x[i]<>x[k])

1<=i<k

1.2. Programul in limbajul Pascal

program problema_turelor;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);


var p: sir;

var np: indicesir;


function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

for i to k do
if x [i]
x [k] then
fi := false

end;

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i, j: indicesir;
begin

writeln ('O noua solutie este:');
for i := l to n do
begin

for j := l to n do
if x [i] = j
then

write ('X')
else

write ('o');
writeln
end
end;

i backtracking implementarea recursiva I
procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level = np + l then

prelucreaza_solutie (np, x)
else

for i := l to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level l, np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := l;
x [k]
O;
while k > O do
begin
repeat

inc (x [k]);

ok fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k]
O;
end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin


case tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

var i: indicesir;
begin

writeln ('Problema turelor pentru o tabla de n x n');

write ('n=');

readln (np);

for i := 1 to np do

p [i] := np;
backtracking (iterativ, np, p)
end.

1.3. Programul in limbajul C

include <stdio.h>

define MAXSIR

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi
int
p [MAXSIR];
int np;

define TRUE 1

define FALSE 0

// functia de continuare

int fi (int k, int x[])

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])


backtracking implementarea recursiva

void btr (int level, int np, int p[], int x[])


void bt (int np, int p[], int x[])

if (x [k] <= p [k])
if (k
np)
prelucreaza_solutie (np, x);
else


else
k--;



void backtracking (int tip, int np, int p[])


void main ()

1.4. Exercitii si probleme

Demonstrati ca problema turelor este echivalenta cu problema generarii permutarilor.

Modificati procedura de afisare astfel incat rezultatul sa apara sub forma:

+ + +

I T | | |
+---- + + +

I I T | |
+---- + + +

| | | T |

1.5. Rezolvarea exercitiilor si problemelor

Avem aceleasi functii 9

Codul sursa este:

i. In limbajul Pascal:

procedure prelucreaza_solutie (n: indicesir; x: sir);
var i, j: indicesir;
begin

writeln ('O noua solutie este:');
for j := 1 to n do

write ');

writeln ('+');
for i := 1 to n do

begin

for j to n do
if x [i] = j then

write ('| T else

write ('| writeln ('|');
for j := 1 to n do

write ');

writeln end
end;

ii. in limbajul C:

// prelucrarea unei solutii x de dimensiune n

void prelucreaza_solutie (int n, int x[])


2. Problema damelor

2.1. Enuntul si consideratii

Problema: Sa se aranjeze pe o tabla de sah de dimensiuni n x n un numar de n dame astfel incat
oricare doua dame sa nu se ameninte.

Rezolvare: trebuie sa observam mai intai ca nu pot fi doua ture pe aceeasi coloana, caci astfel ar fi
doua ture care s-ar ameninta reciproc, rezulta ca fiecare coloana are exact 1 tura. Fie x[i] linia pe
care se afla tura de pe coloana i. Tinand cont ca nu pot fi doua ture pe aceeasi linie sau aceeasi
diagonala, este :

(x x . , xn) = a (xi <>xj A | xi - xj | <> j - i)

1 <= i < j <= n

De unde, prin serializare obtinem functia omega corespunzatoare:

fflk(x[1], x[2], , x[k]) = a (x[i]<>x[k] a I x[i] - x[k] I <> k - i)

1<=i<k

2.2. Programul in limbajul Pascal

program problema_damelor;

const maxsir = 100;

type indicesir = 1..maxsir;

type sir array [indicesir] of integer;

type tipbacktracking = (recursiv, iterativ);


var p: sir;

var np: indicesir;


function fi (k: indicesir; x: sir): boolean;
var i: indicesir;
begin

fi := true;

for i := 1 to k - 1 do

if (x [i] x [k]) or (abs (x [i] x [k]) k i) then
fi := false

end;


procedure prelucreaza_solutie (n: indicesir; x: sir);
var i, j: indicesir;
begin

writeln ('O noua solutie este:');
for i := 1 to n do
begin

for j := 1 to n do
if x [i] = j then

write ('X')
else

write ('o');
writeln
end
end;

procedure btr (level, np: indicesir; p, x: sir);
var i: indicesir;
begin

if level > maxsir then
exit;

if level = np + 1 then

prelucreaza_solutie (np, x)
else

for i := 1 to p [level] do
begin

x [level] := i;

if fi (level, x) then

btr (level + 1, np, p, x)

end

end;

procedure bt (np: indicesir; p, x: sir);
var k: integer;
var ok: boolean;
begin
k := 1;
x [k] := 0;
while k > 0 do
begin
repeat

inc (x [k]);

ok := fi (k, x) or (x [k] > p [k])
until ok;

if x [k] <= p [k] then
if k = np then

prelucreaza_solutie (np, x)
else
begin
inc (k);
x [k] := 0;
end

else

dec (k)
end
end;

procedure backtracking (tip: tipbacktracking; np: indicesir; p:
sir);

var x: sir;
begin


case
tip of

recursiv: btr np, p, x);
iterativ: bt (np, p, x)
end
end;

var i: indicesir;
begin

writeln ('Problema damelor pentru o tabla de n x n');

write ('n=');

readln (np);

for i := 1 to np do

p [i] := np;
backtracking (iterativ, np, p)
end.

2.3. Programul in limbajul C

include <stdio.h>

include <math.h>

define MAXSIR

define RECURSIV 1

define ITERATIV 2

// dimensiunile multimilor Mi
int p [MAXSIR];
int np;

define TRUE 1

define FALSE 0

// functia de continuare

int fi (int k, int x[])

ll prelucrarea unei solutii x de dimensiune n
void prelucreaza_solutie (int n, int x[])
i

printf ('O noua solutie este:n');
for (int
i i <= n; i++)
i

for (int j j <= n; j++)

printf ('%c', x [i] j 'X' 'o');

printf ('n');
j

j

ll backtracking implementarea recursiva
void btr (int level, int np, int p[], int x[])
i

if (level > MAXSIR)

return;
if (level == np + 1)

prelucreaza_solutie (np, x);
else

for (int i i <= p [level]; i++)
i

x [level] = i;

if fi (level, x)

btr (level np, p, x);



void bt   (int np, int p[], int x[])

if (x [k] <= p [k])
if (k
np)
prelucreaza_solutie (np, x);
else


else
k--;



void backtracking (int tip, int np, int p


void main ()

printf ('Problema damelor pentru o tabla de n x nn');

printf ('n=');

scanf ('%d', &np);

for (int i = 1; i <= np; i++)

p [i] = np;
backtracking (ITERATIV, np, p);

2.4. Exercitii si probleme

Problema are solutie pentru orice n natural?

Deeterminati solutiile pentru n<=4.

2.5. Rezolvarea exercitiilor si problemelor

nu, de exemplu, pentru 2 si 3 nu avem solutii

Pentru n=1 avem doar solutia banala, pentru n=2 si n=3 nu avem solutii, pentru n=4 avem
urmatoarele doua solutii:

.X..
X
X
..X.

si:

..X.
X
X
.X.




spunem ca o tura ameninta o alta tura, daca cea de-a doua tura se afla pe aceeasi linie sau coloana cu prima.

Spunem ca o dama ameninta o alta dama, daca cea de-a doua dama se afla pe aceeasi linie sau coloana sau diagonala
cu prima.

Am folosit proprietatea ca (a,b) si (c,d) sunt pe aceeasi diagonala (principala sau secundara) daca si numai daca
la-cl=lb-dl

Nu se poate descarca referatul
Acest document nu se poate descarca

E posibil sa te intereseze alte documente despre:


Copyright © 2024 - Toate drepturile rezervate QReferat.com Folositi documentele afisate ca sursa de inspiratie. Va recomandam sa nu copiati textul, ci sa compuneti propriul document pe baza informatiilor de pe site.
{ Home } { Contact } { Termeni si conditii }