Giải thuật và lập trình

[tronghan_vu]

Xin chào các bạn thích nghiên cứu giải thuật!
Chắc có lẽ cũng có nhiều bạn giống như mình, với suy nghĩ đó mình tạo chủ đề này để chúng ta cùng trao đổi và học hỏi lẫn nhau về giải thuật
Chắc các bạn cũng biết, Khi nói về giải thuật không thể không kể đến một vấn đề rất quan trọng: Sự đệ quy. Chúng ta sẽ cùng thảo luận về sự đệ quy: Đệ quy là gì? Đệ quy hỗ tương là gì? đệ quy quay lui là gì? truy hồi là gì?

Xin mời các bạn hãy tham gia xây dựng thuật giải có sử dụng đệ quy cho các bài toán sau:
1/ Dãy số ****nacy được định nghĩa: F(0)=F(1)=1, F(n)=F(n-1)+F(n-2) với n>=2
Viết chương trình tìm số F(n) với n nguyên dương được nhập từ bàn phím
2/ Viết chương trình sắp 8 quân Hậu lên bàn cờ vua sao cho không quân nào ăn được quân nào. Có bao nhiêu cách sắp như vậy (Xem bàn cờ vua là đối xứng, hai phương án đối xứng nhau xem như là 1)
3/ Có một bàn tròn n chỗ ngồi và n hiệp sĩ. Tình trạng thân thiện của các hiệp sĩ được mô tả trong một ma trận vuông đối xứng cấp n như sau:
+ Các ô của ma trận chỉ nhận 1 trong 2 giá trị: 0 hoặc 1
+ i=j thì ô (i,j)=1
+ i<>j: 2 ô (i,j)=(j,i)=0: Hai hiệp sĩ i và j là kẻ thù của nhau;
2 ô (i,j)=(j,i)=1: Hai hiệp sĩ i và j là bạn của nhau.
Viết chương trình nhập vào số nhuyên dương n (n<=10) và ma trận vuông đối xứng cấp n thỏa mô tả trên. Tìm cách sắp n hiệp sĩ vào chỗ ngồi của bàn sao cho không có hiệp sĩ nào ngồi cạnh kẻ thù của mình. Có bao nhiêu cách sắp xếp như vậy?

Nào! Mời các bạn tham gia thảo luận!
Bạn nào có vấn đề cần trao đổi trực tiếp với mình, hãy gửi mail cho mình.
tronghan_vu@yahoo.com.vn

[quangtq]

Bài 1:


Function F(n:LongInt):LongInt;
Begin
If (n=1) or (n=2) then F:=1
Else F:=F(n-1)+F(n-2);
End;

Bài này đệ quy rất chậm với n lớn. Dùng 3 biến là tính được mà.
Bài 2:


// thử cột thôi
Procedure Try(i:Integer);
Var j:integer;
Begin
For j:=1 to n do
If Free[j] and M[i+j] and N[i-j] then // mảng đánh dấu
Begin
A[i]:=j;
If i=n then PrintResult // in kết quả
Else
Begin
Free[j]:=False; M[i+j]:=False; N[i-j]:=False;
Try(i+1);
Free[j]:=True; M[i+j]:=True; N[i-j]:=True;
End;
End;
End;

Thủ tục PrintResult cho 1 biến đếm. Mỗi lần in kq thì tăng lên 1.
3 mảng đánh dấu lúc đầu cho fillchar là True.
Bài 3:


Function Next(I:Integer);
Begin
If I=n then Next:=1 else Next:=I+1;
End;

Function Previous(I:Integer);
Begin
If i=1 then Previous:=n else Previous:=I-1;
End;

Procedure Try(i:Integer)
Begin
For j:=1 to n do If Free[j] and (Previous(i) là bạn của j và Next(i) là bạn của j) then
Begin
A[i]:=j;
If i=n then PrintResult
Else
Begin
Free[i]:=False;
Try(Next(i));
Free[i]:=True;
End;
End;
End;

Tư tưởng đó rồi :D