giải thuật đệ quy quay lui,

Thảo luận trong 'Dòng họ c , c++ , c#' bắt đầu bởi Nguyễn Thánh Tiền, 11 Tháng một 2018.

Lượt xem: 408

  1. Nguyễn Thánh Tiền

    Nguyễn Thánh Tiền Mr Favoirite 2012 Thành viên

    Bài viết:
    1,933
    Điểm thành tích:
    324
    Nơi ở:
    Hà Nội
    Trường học/Cơ quan:
    cO VUA
    Sở hữu bí kíp ĐỖ ĐẠI HỌC ít nhất 24đ - Đặt chỗ ngay!

    Đọc sách & cùng chia sẻ cảm nhận về sách số 2


    Chào bạn mới. Bạn hãy đăng nhập và hỗ trợ thành viên môn học bạn học tốt. Cộng đồng sẽ hỗ trợ bạn CHÂN THÀNH khi bạn cần trợ giúp. Đừng chỉ nghĩ cho riêng mình. Hãy cho đi để cuộc sống này ý nghĩa hơn bạn nhé. Yêu thương!

    Để hiểu được giải thuật đệ quy quay lui, trước hết ta nhắc lại khái niệm về đệ qui.
    1. Đệ quy
    1.1 Khái niệm về đệ qui.
    Ta nói một khái niệm là đệ qui nếu nó gao gồm chính nó như một bộ phận hoặc nó được định nghĩa dưới dạng của chính nó.
    Ví dụ:
    1. Số tự nhiên:
    a./ 1 là số tự nhiên
    b./ X là số tự nhiên nếu X – 1 là số tự nhiên..
    2. Hàm n giai thừa ( n!)
    a./ o! =1
    b./ n!=n(n-1)! nếu n > 0
    1.2 Giải thuật đệ quy và thủ tục đệ qui
    Nếu lời giải của một bài toán T được thực hiện bằng lời giải của bài toán T’ có dạng giống như T, thì đó là lời giải đệ qui.Giải thuật tương ứng với lời giải như vậy gọi là giải thuật đệ qui.( T’ ở đây hiểu theo nghĩa nó phải nhỏ hơn T)
    Thủ tục đệ qui( chương trình con đệ qui) là thủ tục mà trong thủ tục đó có lời gọi tới chính thủ tục đó.
    Đặc điểm của thủ tục đệ qui:
    a./ Trong thủ tục đệ qui có lời gọi đến chính thủ tục đó.
    b./ Mỗi lần gọi lại thủ tục đó thì kích thước bài toán đã thu nhỏ hơn trước.
    c./ Có một trường hợp đặc biệt: đó là trường hợp suy biến.
    Ví dụ:
    1. Tính n!
    n! =1.2.3…n
    function gt(x:integer):longint;
    begin
    if x = 0 then
    gt:=1
    else
    gt:=x*gt(x-1);
    end;
    2. Số FIBONACCI.
    Dãy số a1, a2, a3 , …, an… được gọi là dáy số fibonacci nếu a1=a2=1, còn từ số thứ 3 trở đi bằng tổng của 2 số đứng ngay trước nó.
    Ta có thủ tục đệ quy sau:
    function fibo(x: integer): longint;
    var
    f1,f2 : integer;
    Begin
    if x<=2 then
    fibo:=1
    else
    fibo:=f(x-2)+ f(x-1);
    end;
    Cả hai thủ tục trên ta thấy rất rõ 3 đặc điểm trên của thủ tục đệ quy.
    – Thủ tục có lời gọi đến chính thủ tục đó.
    – Lần gọi sau kích thước bài toán nhỏ hơn( lần trước tính n!, nhưng lần sau chỉ tính (n-1)!)
    – Có trường hợp suy biến( Nếu n=1; gt=1; nếu n ≤ 2 fibo =1).
    1.3 Hiệu lực của đệ quy:
    Ưu điểm: Sáng sủa, dễ hiểu, thủ tục rất gọn, đơn giản
    Nhược điểm: Tính toán nhiều, thời gian thực hiện rất lâu.
    1.4 Ví dụ về giải thuật đệ qui trên lưới ô vuông.
    Xét bài toán sau:
    Cho lưới ô vuông cấp NxM. Trên mỗi ô [i,j] của lưới ghi một số nguyên a[i,j]. Hai ô được gọi là liên thông trực tiếp nếu nó chung cạnh và giá trị tuyệt đối của tổng 2 số ghi trên 2 ô đó là số chẵn. Hãy lập trình giải quyết các công việc sau:
    a) Cho biết lưới ô vuông đó có bao nhiêu vùng liên thông( vùng liên thông gồm các ô liên thông trực tiếp hoặc liên thông qua một số trung gian nào đó)
    b) Vùng liên thông lớn nhất (có nhiều ô nhất)
    Dự liệu vào: Cho trong tệp văn bản LUOI.txt có cấu trúc như sau:
    – Dòng đầu tiên ghi hai số nguyên dương n, m là kích thước của lưới
    – Dòng thứ i trong N dòng tiếp theo ghi M số nguyên dương là các số ghi trên dòng thứ i của lưới theo thứ tự từ trái qua phải.
    Kết quả: Đưa ra tệp văn bản LUOI.out, có cấu trúc như sau:
    – Dòng đầu tiên ghi số S là số vùng liên thông của lưới.
    – Dòng thứ i trong S dòng tiếp theo là ghi toạ độ của các ô của vùng liên thông thứ i
    – Dòng thứ s+2 ghi toạ độ các ô của vùng liên thông lớn nhất.
    Cả hai File dự liệu các số trên một dòng ghi cách nhau một dấu cách.
    Ví dụ
    LUOI.inpLUOI.out
    4 5
    0 1 3 1 5
    1 1 5 7 8
    2 2 4 1 5
    0 5 9 10 2
    6
    (1 1)
    (1 2) (1 3) (1 4) (1 5) (2 1) (2 2) (2 3) (2 4) (2 5) (3 4) (3 5)
    (2,5)
    (3 1) (3 2) (3 3) ( 4 1)
    ( 4 2) (4 3)
    (4 4) (4 5)
    (1 2) (1 3) (1 4) (1 5) (2 1) (2 2) (2 3) (2 4) (2 5) (3 4) (3 5)
    Nếu chỉ giải quyết câu a thì chương trình là:
    Uses crt;
    Const
    fi = ‘luoi.txt’;
    fo = ‘luoi.out’;
    d : array[1..4] of integer=(-1,0,1,0);
    c : array[1..4] of integer=(0,1,0,-1);
    Var
    a : array[0..101,0..101] of integer;
    b : array[0..101,0..101] of integer;
    f : text;
    n,m,sh,r,s : integer;
    procedure nhap;
    var i,j : integer;
    begin
    assign(f,fi); reset(f);
    readln(f,n,m);
    for i:=1 to n do
    begin
    for j:=1 to m do
    read(f,a[i,j]);
    readln(f);
    end;
    for i := 0 to n+1 do
    for j := 0 to m+1 do
    if (i = 0) or (i = n+1)or(j = 0)or( j = m+1) then
    b[i,j] :=-1
    else
    b[i,j] := 0;
    sh := 0;
    close(f);
    end;
    function kiemtra(p,q : integer) : boolean;
    var t : integer;
    begin
    t :=abs(p+q);
    if t mod 2 = 0 then
    kiemtra := true
    else
    kiemtra :=false;
    end;
    procedure lt(x,y : integer);
    var k : integer;
    begin
    b[x,y] := sh;
    for k := 1 to 4 do
    if (kiemtra(a[x,y],a[x+d[k],y+c[k]]))and(b[x+d[k],y+c[k]] = 0) then
    lt(x + d[k], y + c[k]);
    end;
    procedure thong_bao;
    var t,i,j : integer;
    begin
    assign(f,fo);rewrite(f);
    writeln(f,’ so vung lien thong la: ‘,sh);
    for t := 1 to sh do
    begin
    write(f, ‘vung lien thong thu ‘, t,’ : ‘);
    for i := 1 to n do
    for j := 1 to m do
    if b[i,j] = t then
    write(f,'(‘,i,’,’,j,’)’,’ ‘);
    writeln(f);
    end;
    end;
    {============= Chuong trinh chinh ====================}
    BEGIN
    nhap;
    for r:=1 to n do
    for s:=1 to m do
    if b[r,s] = 0 then
    begin
    inc(sh);
    lt(r,s);
    end;
    thong_bao;
    close(f);
    END.
    Ta chú ý thủ tục procedure lt(x,y : integer); trong thủ tục này gọi tới chính thủ tục này
    Để giải quyết trọn vẹn bài toán này( tức là cả câu b, ta đưa thêm biến DEM để đếm số ô của từng vùng, biến MAX để lưu vùng có số ô lớn nhất và bién VMAX để lưu thứ tự vùng có số ô lớn nhất. Khi được một vùng ta được số ô lưu trong biến DEM, ta so sánh DEM với MAX để lưu vùng có ô lớn nhất và thứ tự của vùng này.
    Chương trình sau giải quyết trọn ven bài toán trên.
    Uses crt;
    Const
    fi = ‘luoi.txt’;
    fo = ‘luoi.out’;
    d : array[1..4] of integer=(-1,0,1,0);
    c : array[1..4] of integer=(0,1,0,-1);
    Var
    a : array[1..100,1..100] of integer;
    b : array[0..101,0..101] of integer;
    f : text;
    n,m,sh,max : integer;
    vmax,dem,r,s : integer;
    procedure nhap;
    var i,j : integer;
    begin
    assign(f,fi);reset(f);
    readln(f,n,m);
    for i:=1 to n do
    begin
    for j:=1 to m do
    read(f,a[i,j]);
    readln(f);
    end;
    for i := 0 to n+1 do
    for j := 0 to m+1 do
    if (i = 0) or (i = n+1)or(j = 0)or( j = m+1) then
    b[i,j] :=-1
    else
    b[i,j] := 0;
    max := – maxint;
    sh := 0;
    close(f);
    end;
    function kiemtra(p,q : integer) : boolean;
    var t,i : integer;
    begin
    t :=abs(p+q);
    if t mod 2 = 0 then
    lienthong := true
    else
    kiemtra :=false;
    end;
    procedure lt(x,y : integer);
    var k : integer;
    begin
    b[x,y] := sh;
    for k := 1 to 4 do
    if (kiemtra(a[x,y], a[x+d[k],y+c[k]]))and(b[x+d[k],y+c[k]]= 0) then
    begin
    inc(dem);
    lt(x + d[k], y + c[k]);
    end;
    if dem > max then
    begin
    max : = dem;
    vmax : =sh;
    end;
    end;
    procedure thong_bao;
    var t,i,j : integer;
    begin
    assign(f,fo);rewrite(f);
    writeln(f,’ so vung lien thong la: ‘,sh);
    for t := 1 to sh do
    begin
    write(f, ‘vung lien thong thu ‘, t,’ : ‘);
    for i := 1 to n do
    for j := 1 to m do
    if b[i,j] = t then
    write(f,'(‘,i,’,’,j,’)’,’ ‘);
    writeln(f);
    end;
    writeln(f,’ so vung lien thong lon nhat la: ‘);
    for i:=1 to n do
    for j:=1 to m do
    if b[i,j] = vmax then
    write(f,'(‘,i,’,’,j,’)’,’ ‘);
    end;
    {============= Chuong trinh chinh ====================}
    BEGIN
    nhap;
    for r:=1 to n do
    for s:=1 to m do
    if b[r,s] = 0 then
    begin
    dem:=1;
    inc(sh);
    lt(r,s);
    end;
    thong_bao;
    close(f);
    END.
    Giờ ta trở lại với giải thuật đệ quy quay lui
    Có tài liệu còn gọi nó là ” Thử và sai”. đã là đệ quy quay lui thì trong thủ tục của nó là thủ tục đệ quy và có “quay lui”. Ta tìm hiểu quay lui ở đâu và như thế nào?
    Trước hết ta xét ví dụ:
    Một từ được gọi là chân chính loại M, N nếu nó được xây dựng từ tập hợp gồm M ký tự, có độ dài N và không có 2 từ con nào liên tiếp giống nhau.
    Giả sử tập M={‘1’, ‘2’, ‘3’}
    Ví dụ: 1232; 2123; 1231 là những từ chân chính loại 3,4; còn 1123;1212;1233 là những từ không phải là từ chân chính loại 3,4.

    Tất nhiên ở đây không phải là ta xây dựng tất cả các từ có độ dài N, sau đó loại trừ những từ không thoả mãn, mà ta lần lượt xây dựng các xâu.
    Khởi tạo ban đầu là xâu rỗng, ta tiến hành ghép các ký tự , tại mỗi bước ghép ta kiểm tra xem nó có thoả mãn điều kiện bài toán không( có hai từ con liền nhau giống nhau không). Nếu thoả mãn ta kiểm tra xem xâu có độ dài bằng N hay chưa. Nếu xâu đã có độ dài bằng N ta in kết quả, nếu chưa có độ dài bằng N ta ghép bước tiếp. Nếu tất cả các ký tự được chọn để ghép đều không thoả mãn điều kiện bài toán thì việc chọn ký tự trước đó sai, ta phải xoá ký tự trước đó đi và thay bởi ký tự khác để bước ghép tiếp được thành công. Việc xoá ký tự trước đó để tìm ký tự khác ghép vào người ta gọi là quay lui. Trong trường hợp xâu có độ dài bằng N( đã thoả mãn bài toán) thì ta được một kết quả. Để tìm kết quả khác, ta xoá ký tự cuối cùng này đi rồi tìm ký tự khác để ghép vào cũng gọi là quay lui.
    Việc đó thể hiên ở thủ tục procedure find( x : integer);
    Còn hàm function ok(i : integer):boolean; là để kiểm tra xem có hai từ con liền nhau giống nhau hay không
    function ok(i : integer):boolean;
    var k : integer;
    begin
    ok := true;
    for k := 2 to i div 2 do
    if copy(s,i-2*k+1,k) = copy(s,i-k+1,k) then
    begin
    ok := false;
    exit;
    end;
    end;
    procedure find( x : integer);
    var i : integer;
    begin
    if x > n then
    xuat
    else
    for i := 1 to m do
    if s[length(s)] <> st then
    begin
    s := s + st;
    if ok(s) then
    begin
    find(x+1);
    delete(s,length(s),1);{ xoá để quay lại bước trước}
    end
    else
    delete(s,length(s),1); { xoá để quay lại bước trước}
    end;
    end;
    Ta xét ví dụ 2: Đường đi trên lưới ô vuông
    Cho lưới ô vuông cấp NxM. Trên mỗi ô (i,j) của lưới ghi một số nguyên a[i,j]. Ô (x,y) đi được sang ô (x’,y’) nếu 2 ô này chung cạnh và a[x,y]<= a[x’,y’]. Hãy lập trình giảI quyết các công việc sau:
    a) Tìm tất cả các đường đi từ ô (x,y) đến ô(r,s).
    b) Tìm đường đi qua ít ô nhất
    ( giả thiết rằng có đường đi)
    Ta lần lượt xây dựng các bước đi, bắt đầu từ ô (x,y), tại mỗi bước kiểm tra xem có đi qua được một trong các ô chung cạnh với nó hay không? Nếu tồn tại một bước đI thì ta ghi nhận bước đi và đi sang ô mới, tại ô mới này ta kiểm tra xem đã đến đích hay chưa. Nếu đã đến đích ta thông báo kết quả, sau đó lùi lại bước trước để tìm đường đI khác( quay lui). Còn trong trường hợp chưa đến đích thì tìm ô chung cạnh đi tiếp( đệ quy).
    Thủ tục sau minh hoạ giảI thuật này.
    Procedure Try (x,y: integer);
    Var j: integer;
    If (x = p) and (y = q) then
    Thong_bao
    else
    Begin
    For j := 1 to 4 do
    Begin
    u := x + dong[j];
    v := y + cot[j];
    If (A[u, v] <= A[x, y])and(b[u,v]=0) then
    Begin
    Inc(count);
    d[count] := u;
    c[count] := v;
    B[u,v]:=1
    Try (u,v);
    dec(count);
    b[u,v]:=0;
    End;
    End;
    End;
    Bây giờ ta xét bài toán đặt 8 con hậu trên bàn cờ vua để không con nào ăn được nhau.
    Ta lần lượt đặt từng con hậu, giả sử ta đặt được con hậu thứ k, ta tiến hành đặt con hậu thứ k+1. Giả sử ta định đặt con hậu thứ k+1 tại ô (x,k+1) của bàn cờ( ta lần lượt xét x=1..8), chúng ta tiến hành kiểm tra xem trên dòng x của bàn cờ và trên 2 đường chéo đi qua ô (x,k+1) đã có quân hậu nào chưa, nếu có một vị trí đặt hậu thoả mãn ta ghi nhận bước đặt hậu này, còn nếu không có bước nào thoả mãn thì phảI đặt lại con hậu thứ k( quay lui). Tại mỗi bước ta lùi lại bước trước để lấy tất cả các nghiệm.
    Thủ tục thể hiện như sau:
    procedure find( x : integer);
    var y : integer;
    begin
    if x = 9 then
    xuat
    else
    for y := 1 to 8 do
    if ok(x,y)and(a[x,y]=0) then
    begin
    a[x,y] := 1;
    find(x+1);
    a[x,y] := 0;
    end;
    end;
    Ta xét bài toán mã đi tuần: Trên bàn cờ vua con mã đang ở ô (x,y), hãy cho biết con mã có đi qua tất cả các ô, mỗi ô đi đúng một lần hay không?
    Khởi tạo ban đầu con mã đang ở ô (x,y), ta duyệt qua các nước đi có thể của nó, tại một ô con mã có thể đi đến 8 ô như luật của đi của con mã. Tại một ô giả sử đó là bước đI thứ k của con mã, Ta chon một trong các nước đi của nó, kiểm tra xem bước đi tiếp có thoả mãn hay không ( ô đI tiếp đã đI qua lần nào chưa, có đI ra ngoài bàn cờ không.Nếu thoả mãn ghi nhận nước đI, sau đó ta kiểm tra xem bàn cờ đã đI hết chưa, nếu hết in kết quả, ngược lại đi tiếp.Nếu không còn bước đI tiếp thì phảI đI lại bước trước đó để đi tiếp được bước sau.
    Thủ tục sau thể hiện thuật giảI trên.
    procedure try(i:integer);
    var j,dong,cot:integer;
    begin
    if i> n*n then
    xuat
    else
    begin
    if kt = 1 then
    exit;
    for j:=1 to 8 do
    begin
    dong:=x+d[j];
    cot:=y+c[j];
    if (dong in s)and(cot in s)and(a[dong,cot] = 0)then
    begin
    a[dong,cot]:=i;
    x:=dong;
    y:=cot;
    try(i+1);
    x:=dong-d[j];
    y:=cot-c[j];
    a[dong,cot]:=0;
    end;
    end;
    end;
    end;
    Từ các ví dụ trên ta có sơ đồ thuật giải đệ quy quay lui:
    Procedure TRY(i: integer);
    Var k: integer;
    Begin
    For k:=1 to n do
    Begin
    Chọn nước đi thứ k
    If đi được THEN
    Begin
    Ghi nhận nước đi
    If i<n THEN
    Try(i+1)
    Else
    In kết quả
    Bỏ việc ghi nhận
    End;
    End;
    End;
     
  2. Tạ Đặng Vĩnh Phúc

    Tạ Đặng Vĩnh Phúc Cựu Trưởng nhóm Toán Thành viên

    Bài viết:
    1,562
    Điểm thành tích:
    386
    Nơi ở:
    Cần Thơ
    Trường học/Cơ quan:
    Đại học Cần Thơ

    Quá hay a ơi, a rỗi thì inbox anh em mình bàn luận nhé a!!!
     
    Thiên Thuận thích bài này.
Chú ý: Trả lời bài viết tuân thủ NỘI QUY. Xin cảm ơn!

Draft saved Draft deleted

CHIA SẺ TRANG NÀY

-->