Administratie | Alimentatie | Arta cultura | Asistenta sociala | Astronomie |
Biologie | Chimie | Comunicare | Constructii | Cosmetica |
Desen | Diverse | Drept | Economie | Engleza |
Filozofie | Fizica | Franceza | Geografie | Germana |
Informatica | Istorie | Latina | Management | Marketing |
Matematica | Mecanica | Medicina | Pedagogie | Psihologie |
Romana | Stiinte politice | Transporturi | Turism |
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.
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 } |
Documente similare:
|
ComentariiCaracterizari
|
Cauta document |