Pasca;: Đệ Quy Quay Lui Trên Mảng 2 Chiều Và Giải Thuật Cài đặt

Đăng nhập / Đăng ký

• Trang chủ
• Thành viên
• Trợ giúp
• Liên hệ

Đăng nhập

Tên truy nhập Mật khẩu Ghi nhớ   Quên mật khẩu ĐK thành viên

Từ điển trực tuyến

CHỌN TỪ ĐIỂN: TỪ ĐIỂN TRỰC TUYẾN TỪ ĐIỂN ANH - VIỆT TỪ ĐIỂN VIỆT - ANH TỪ ĐIỂN VIỆT - VIỆT TỪ ĐIỂN VIỆT - PHÁP TỪ ĐIỂN PHÁP - VIỆT TỪ ĐIỂN TIN HỌC TỪ ĐIỂN ANH - ANH

Thư viện online

Các ý kiến mới nhất

@Ngô Tùng Toại đã gia nhập blog nha! Chúc khỏe...

Merry Christmas! ...

Chào bạn Trần Huy Hoàng. Tặng bạn bức ảnh quê...

TVM rất vui được gia nhập trang riêng mời chủ...

Em co di du lich o Dn ve. Truong anh...

Thăm thầy giáo. Chúc thầy luôn vui vẻ, hạnh phúc...

Vào link này ủng hộ LN nhé. https://www.facebook.com/thuvienViolet.vn/posts/118357841688292 ...

Tùng Toại kính chúc quí thầy cô giáo: Sức khỏe...

Chỉ còn một ngày (24h) nừa là sang năm mới...

PHAN VIỆT XIN CHÚC TOÀN THỂ ĐẠI GIA ĐÌNH VIOLET...

Sắp đến ngày 20/10, chúc người bạn đời của thầy...

E vẫn khỏe. Hai tuần nay bận quá không lên...

Chúc thầy buổi tối vui nhé!...

Từ Lai Châu em xin chào thầy, chúc thầy cuối...

Liên kết website

Loading...

-Liên kết giáo dục- <---------------------> Ph. GD&ĐT Th.Chương THPT Đặng Thúc Hứa Sở GD&ĐT Nghệ an Tư liệu giáo dục TVDT Sở GD-ĐT NA Thư viện giáo án Thư viện bài giảng Thư viện bài giảng Dạy học trực tuyến Blog giáo viên Đào tạo trực tuyến Trường trực tuyến Download tiếng anh

-Đọc báo online- <--------------------> Báo tuổi trẻ Báo thanh niên Thư viện đề thi Báo tiền phong Báo nhân dân Báo mực tím Báo giáo dục thời đại Nhà sách việt nam Báo thể thao việt nam Báo lao động Báo hoa học trò Báo gia đình Báo văn hóa Viết báo

-Xem phim online - <----------------------> Truyền hình cáp Truyền hình Việt nam Thế giới phim Xưởng phím Clip hài trực tuyến Nhạc số˜ Nhạc mp3 Đường lên đỉnh Olympia Xem tử­ vi trực tuyến Thể thao

-Thư viện sách- <----------------------> Sách tham khảo Tin học văn phòng Tin học Học mãi TW đoàn TNHCM Diễn đàn butnghien Diễn đàn giáo viên Sách nhà xuất bản Trang thư viện Mỗi ngày 1 cuốn sách

-Tuyển sinh ĐH-CĐ - <--------------------> Báo tuổi trẻ» Báo GD-ĐT VNmedia 24H.com.vn Báo dân trí Báo mực tím Báo Vnexpress Thư viện trẻ» Báo tuổi trẻ» Báo lao động Báo hoa học trò Báo mới Trang Web Danh bạ web

Lịch

Du lịch Ảnh

NGHE NHẠC HÌNH

Hỗ trợ trực tuyến

• (Trần Huy Hoàng)
• (Lê Thị Vinh)

Điều tra ý kiến

Trong các môn học bạn thích học môn nào? Tin Toán Lý Hóa Môn khác

Thống kê

281860 truy cập (chi tiết) 34 trong hôm nay

534928 lượt xem 55 trong hôm nay

187 thành viên

Thành viên trực tuyến

1 khách và 0 thành viên

Ngoại hạng anh

Chào mừng quý vị đến với .

Quý vị chưa đăng nhập hoặc chưa đăng ký làm thành viên, vì vậy chưa thể tải được các tư liệu của Thư viện về máy tính của mình. Nếu chưa đăng ký, hãy đăng ký thành viên tại đây hoặc xem phim hướng dẫn tại đây Nếu đã đăng ký rồi, quý vị có thể đăng nhập ở ngay ô bên phải. Gốc > BÀI HỌC TRỰC TUYẾN > Lập trình Pascal >

Tạo bài viết mới Pasca;: Đệ quy quay lui trên mảng 2 chiều và giải thuật cài đặt

Duyệt đệ quy là một trong những chiến lược để giải quyết nhiều bài toán, đặc biệt là các bài toán đòi hỏi liệt kê mọi cấu hình thoả mãn. Thuật toán đệ quy và các vần đề xung quanh đệ quy đã được nhiều tác giả đề cập đến. Trong bài viết này, tôi cũng sẽ trở lại với chủ đề đệ quy, nhưng là đệ quy quay lui trên mảng hai chiều và kỹ năng cài đặt thông qua một số bài toán cụ thể. Yếu tố mấu chốt trong một thủ tục đệ quy là điều kiện duyệt và điểm dừng. Với đặc trưng của mảng hai chiều là phần tử mảng được xác định bằng hai giá trị hàng và cột, thông thường chúng ta vẫn sử dụng cặp giá trị (i,j) (hàng, cột của 1 ô) làm bước duyệt khi gọi thủ tục đệ quy. Một số bài toán như: tìm đường đi từ ô (i0, j0) đến ô (ik, jk) với 4 khả năng đi tới các ô chung cạnh như bài toán Mã đi tuần đã rất quen thuộc với chúng ta. Mặt khác, các bài toán sử dụng thuật giải này đều có điều kiện duyệt hay điểm dừng khá rõ ràng và việc trả lại giá trị cũng không quá phức tạp nên các bạn sẽ dễ dàng cài đặt được. Sau đây, tôi muốn giới thiệu với các bạn một bài toán được giải quyết theo phương pháp duyệt đệ quy quay lui, nhưng trong khi cài đặt chúng ta cũng có đôi điều cần lưu ý. Bài toán như sau: ở một nước nọ do các đội bóng đá thiếu tinh thần thi đấu nên số trận hoà rất nhiều. Ban tổ chức quyết định thay đổi luật để kích thích các đội thi đấu tích cực hơn. Giải sẽ tổ chức thi đấu vòng tròn nghĩa là mỗi đội đều phải thi đấu với tất cả các đội khác đúng một trận. Nếu hoà, cả hai đội đều bị 0 điểm. Đội thắng sẽ được 3 điểm và đội thua cũng được 1 điểm. Do sơ xuất của ban tổ chức, bảng kết quả thi đấu của tất cả các đội đã bị nhoè, một số chỗ không đọc được. Bạn hãy giúp ban tổ chức khôi phục lại những thông tin đã mất. Số đội bóng của giải này là N (N ≤ 20). Bằng kết quả cho bởi mảng số nguyên A[1..N,1..N+1] trong đó A[i,j] bằng số điểm đội i đạt được trong trận thi đấu với đội j. A[i,N+1] bằng tổng số điểm của đội i trong toàn giải. Quy ước A[i,i]=0. Dữ liệu vào cho trong file văn bản với tên INP.TXT. Dòng đầu là số đội bóng N; N dòng tiếp theo là bảng giá trị, những ô bị nhoè được cho bởi giá trị −1. Dữ liệu đưa ra file văn bản OUT.TXT, liệt kê mọi khả năng có thẻ. Mỗi khả năng cách nhau một dòng trắng. Giải thuật như sau: Chúng ta nhận thấy bài toán yêu cầu đưa ra mọi cấu hình thoả mãn nên duyệt mọi khả năng là phương pháp thường được sử dụng. Giả sử sau khi đã khôi phục các thông tin có thẻ, số ô trống còn lại là m ô (trừ ô trống là ô tổng, vì giá trị ô tổng phụ thuộc vào các ô cùng hàng đó). Từ đó suy ra số khả năng là: 3m/2 (mỗi ô bị nhoè có khả năng nhận 3 giá trị). Các yếu tố chính trong thủ tục đệ quy như sau: + Điểm dừng: Mảng A đã được khôi phục đầy đủ có dữ liệu mảng phù hợp đầu vào. + Kết thúc: Khi đã duyệt mọi khả năng hoặc đã đạt đến một ngưỡng nào đó (dùng để kết thúc chương trình khi số khả năng quá lớn). Tuy nhiên, việc trả lại giá trị cho mảng A là không dễ dàng. Sau mỗi lần duyệt, số lượng ô thay đổi giá trị không xác định cụ thể. Vì vậy, chúng ta sẽ sử dụng thêm một mảng trong thủ tục đệ quy. Để trả lại giá trị trước đó cho mảng A, chúng ta dùng một phép gán. Nhưng việc khai báo mảng này sẽ làm tốn không gian bộ nhớ, dễ gây tràn Stack. Song cũng rất phức tạp khi trả lại giá trị mà không dùng thêm mảng này. Các bạn có thể sử dụng duyệt không quay lui để giải quyết bài toán này bằng cách: tìm ra mọi khả năng của tất cả các ô rồi so sánh với dữ liệu vào. Khi đó, số khả năng là: 3N*(N-1)/2 (một con số rất lớn) Dưới đây là chương trình cài đặt: Const inp=’INP.TXT’; out=’OUT.TXT’; Max=21; C1 : Array[1..3] of byte=(0,1,3); C2 : Array[0..3] of byte=(0,3,0,1); Type arr=array[1..Max,1..Max] of shortint; var a : arr; OK: Boolean; n,io,jo : byte; g: text; Procedure Docfile; var i,j: byte; begin fillchar(a,sizeof(a),0); assign(g,inp); reset(g); readln(g,N); for i:=1 to N do begin for j:=1 to N+1 do read(g,a[i,j]); Readln(g); end; close(g); end; Procedure Sualai2(var a:arr); var i,j,d,vt,s: byte; Begin for i:=1 to N do for j:=1 to N do if A[i,j] in [0,1,3] then a[j,i]:=c2[a[i,j]]; for i:=1 to N do begin s:=0; d:=0; for j:=1 to n do if a[i,j]=-1 then begin vt:=j; inc(d); end; if (d=1) and (a[i,n+1] <> -1) then begin a[i,vt]:=a[i,n+1]-s; a[vt,i]:=c2[a[i,vt]; OK:=false; end; if (d=0) and (a[i,n+1]=-1) then begin a[i,n+1]:=s; OK:=false; end; end; end; Procedure Sualai1; var i,j: byte; Begin repeat OK:=True; Sualai2; Until OK; end; Function thulai(a:arr): Boolean; var i,j,s: Byte; Begin thulai:=true; for i:=1 to N do begin s:=0; for j:=1 to N do begin inc(s,a[i,j]); If (a[i,j]<>0) and (a[i,j]<>1) and (a[i,j] <>3) then begin thulai:=false; exit; end; end; if a[i,n+1]<>s then begin thulai:=false; exit; end; end; end; Procedure ghinhan(a:arr); var i,j: byte; Begin If thulai(a) then for i:=1 to N do begin for j:=1 to N+1 do write(g,a[i,j]:3); writeln(g); end; End; Function KT(a:arr):Boolean; var i,j: byte; Begin KT:=true; for i:=1 to N do For j:=1 to N+1 do If a[i,j]=-1 then begin kt:=false; exit; end; end; Procedure Tim(var io,jo: byte); var i,j: byte; Begin io:=0; jo:=0; for i:=1 to N do for j:=1 to N do if a[i,j]=-1 then begin io:=i; jo:=j, exit; end; end; Procedure Duyet(i,j: byte); var k,i1,j1: byte; a:arr; Begin If KT(a) then ghinhan(a) Else for k:=1 to 3 do begin a1:=a; a[i,j]:=C1[k]; a[j,i]:=C2[a[i,j]]; sualai2(a); Tim(i1,j1); Duyet(i1,j1); a:=a1; end; end; {Chuong trinh chinh} BEGIN docfile; Sualai1; Assign(g,out); rewrite(g); Tim(io,jo); Duyet(io,jo); Close(g); END. Mong có ý kiến trao đổi và thảo luận cùng các bạn. Nhắn tin cho tác giả Trần Huy Hoàng @ 21:36 28/10/2009 Số lượt xem: 2150 Số lượt thích: 1 người (Nguyễn Bích Ngọc)   ↓ ↓ Gửi ý kiến

• Pascal: Bài tập về ma trận liên thông (27/10/09)
• BÀI TẬP PHẦN MA TRẬN (06/10/09)
• Phần mềm Pascal (Turbo Pascal & Free Pascal Full) (06/10/09)
• Bài Tập Pascal cơ bản (06/10/09)
• Bài tập tổng hợp (06/10/09)

Xem điểm thi ĐH-CĐ

Website được thừa kế từ Violet.vn, người quản trị: Trần Huy Hoàng