Thuật toán quay lui - Liệt kê các xâu NP có độ dài n

[meohoang8x]

Không biết là có bác nào post bài này lên chưa nữa.Bài này rất quen thuộc với các bác mà: Liệt kê các xâu NP có độ dài n.

#include <stdio.h>
#include <conio.h>
int b[100],n=5,count=0;
void result(void)
  {
    printf("\nKet qua buoc thu %d: ",++count);
    for (int i=1;i<=n;i++)
      printf("%3d",b[i]);
  }
void try(int i)
 {
    int j;
    for (j=0;j<=1;j++)
      {
	 b[i]=j;
	 if(i==n) result();
	 else try(i+1);
      }
 }
void main(void)
 {
  clrscr();
  try(1);
  getch();
 }

Bài này tui đã chạy thử, hiện ra kết quả đúng.Ở đây tui đã gán n=5,bác nào thích thì nhập n cũng được.

[coolkid]

bài này bạn ấy dùng đệ quy thôi bạn. Trong lập trình C thì theo mình biết điều tối kỵ nhất là dùng biến global. Các biến n,count và mảng b bạn có thể đưa vào hàm main.

[serivn]

bài này bạn ấy dùng đệ quy thôi bạn. Trong lập trình C thì theo mình biết điều tối kỵ nhất là dùng biến global. Các biến n,count và mảng b bạn có thể đưa vào hàm main.

Hi`, với cái thuật toán Quay lui này thì việc dùng biến Global là tối ưu nhất đó, vì nó luôn được sử dụng trong các hàm, các biến có liên quan, và phụ thuộc giá trị của nhau (thông thường là hàm Try(), và hàm Init()) - Vì vậy ko thê nỏi là tối kị dùng biến global ở đây được!

[6220119]

thế sao cậu ko thử bỏ global mà hàm chạy vẫn đúng ? để global mình ko thấy "tối ưu" gì hơn so với để local cả (bad practice), tối kị vì code của cậu sẽ depend on nó hoàn toàn, khó kiểm soát khi gặp biến trùng tên trong namespace khác, ...v.v.

[hieu_lenin]

{
Đề bài: Dùng thuật toán đệ quy quay lùi và giải bài toán sau:

- Có một sàn nhà gồm 2^k * 2^k ô vuông trong đó có một ô dùng thoat nước. Hãy dùng những viên gạch thước thợ (Một viên lót được 3 ô vuông), mổi viên gạch được đáng số từ thứ tự từ 1, hãy dùng đủ số gạch đễ lót đủ số ô vuông trên nền nhà là: 2^k*2^k ô vuông. Ô thoát nước thì ghi số 0.
- Với k nhập từ bàn phím, i, j là tọa độ của ô thonuo7o71c cũng nhập từ bàn phím.
- Ví dụ nhập: k=2, i=1, j=1 thì xuất kết qua như sau

0 2 3 3
2 2 1 3
5 1 1 4
5 5 4 4

Bài toán mình dùng thuật toán đệ quy quay lùi để giải, khi tét với k= 2 và i=1 , j= 1 thì thấy kết quả đúng nhưng khi tế với k=3 và i, j là tọa độ khác thì sai.
Xin các anh chị vui lòng giàng chút thời gian giúp mình giải bài toán càng sớm càng tốt, . Xin cảm ơn.
}


const max=1000;
fi='latgach.inp';
fo='latgach.out';
var a,b:array[1..max,1..max] of integer;
sh,i,j,k,phu,s:integer;
u,v:integer;
vtcong:integer;
procedure nhap;
begin
Assign(input,fi);
reset(input);
read(k,i,j);
close(input);
end;

procedure init;
begin
sh:=0;
phu:=2;
for s:=1 to k do phu:=phu*s;
end;
procedure latphu(x1,x2,y1,y2:integer);
var m,n:integer;
begin
for m:=y1 to y2 do
for n:=x1 to x2 do
if (a[m,n]<>1) then a[m,n]:=sh;

end;

procedure tim(x1,x2,y1,y2:integer; vt:integer);
var h,c:integer;
begin
h:=(x2-x1)div 2;
c:=(y2-y1)div 2;
if (i<=h) and (j<=c) then vt:=1;
if (i>h) and (j<=c) then vt:=2;
if (i>h) and (j>c) then vt:=3;
if (i<=h) and (j>c) then vt:=4;
vtcong:=vt;
end;

procedure hien;
var m,n:integer;
begin
a[i,j]:=0;
for m:=1 to phu do begin
for n:=1 to phu do write(a[m,n]:2);
writeln;
end;
end;

procedure lat(x1,x2,y1,y2:integer; k:integer);
var vt:integer;
begin
inc(sh);
if k=1 then
begin
latphu(x1,x2,y1,y2);
end
else
begin
tim(x1,x2,y1,y2,vt);

v:=x1+((x2-x1)div 2);
u:=y1+((y2-y1)div 2);

if vtcong=1 then begin
a[u,v+1]:=sh;
a[u+1,v]:=sh;
a[u+1,v+1]:=sh;
end
else
if vtcong=2 then begin
a[u,v]:=sh;
a[u+1,v]:=sh;
a[u+1,v+1]:=sh;
end
else
if vtcong=3 then begin
a[u,v]:=sh;
a[u+1,v]:=sh;
a[u,v+1]:=sh;
end
else
if vtcong=4 then begin
a[u,v]:=sh;
a[u,v+1]:=sh;
a[u+1,v+1]:=sh;
end;

lat(x1,v,y1,u,k-1);
lat(x1,v,u+1,y2,k-1);
lat(v+1,x2,y1,u,k-1);
lat(v+1,x2,v+1,y2,k-1);

if sh=((phu*phu-1)div 3) then hien;
end;

end;

begin
nhap;
init;
Assign(output,fo);
rewrite(output);
lat(1,phu,1,phu,k);
close(output);
end.