[C++, Pascal] Tổng các phần tử không cùng hàng cùng cột lớn nhất (Đệ quy)

Đây là một trong những bài toán đơn giản của đệ quy, nói vậy chứ cũng hơi khó hiểu… hehe… Hôm nay mình sẽ giới thiệu bài toán này tới các bạn. Mình viết theo hai loại ngôn ngữ đó là C++ và Pascal tùy nhu cầu của các bạn để tiện tham khảo.

Đề bài: Cho mảng có kích thước n x n gồm các số nguyên không âm. Hãy chọn ra n số sao cho mỗi hàng, mỗi cột có đúng một số được chọn đồng thời tổng các số được chọn là lớn nhất.

Yêu cầu: Dữ liệu vào được cho trong tập tin văn bản MANGINP.TXT gồm các số nguyên theo quy cách:

– Dòng đầu có số n là số dòng và số cột của mảng.

– Trên n dòng tiếp theo, mỗi dòng có n số nguyên viết cách nhau ít nhất một khoảng trắng.

Dữ liệu ra ghi vào tập tin văn bản MANGOUT.TXT gồm:

– Dòng đầu ghi tổng các số được chọn.

– Các dòng tiếp theo ghi giá trị của các số đó.

Ví dụ input và output

Sourcecode viết bằng C++

#include <iostream> #include <fstream> using namespace std; short n, a[10][10], x[10], ng[10], r, dem; int maxi, tong; bool b[10]; void readf() { ifstream fi("mangi.txt"); if(fi.is_open()) { fi >> n; for(short i = 0; i < n; i++) for(short j = 0; j < n; j++) fi >> a[i][j]; fi.close(); } } void xuly() { if(tong > maxi) { maxi = tong; for(int i = 0; i < n; i++) ng[i] = x[i]; } } void inkq() { ofstream fo("mango.txt"); if(fo.is_open()) { fo << "Gia tri lon nhat la: " << maxi; for(short i = 0; i < n; i++) fo << "nGia tri: " << a[i][ng[i]] << " (" << i << "," << ng[i] << ")"; fo.close(); } } void chon(short i) { for(short j = 0; j < n; j++) if(b[j]) { x[i] = j; tong += a[i][j]; b[j] = false; if(i == n - 1) xuly(); else chon(i + 1); b[j] = true; tong -= a[i][j]; } } int main() { readf(); for(int i = 0; i < n; i++) b[i] = true; chon(0); inkq(); return 0; }

Sourcecode viết bằng Pascal

uses crt; var a: array[1..10, 1..10] of integer; b: array[1..10] of boolean; x, ng:array[1..10] of byte; r, n, i, dem: byte; max, tong: integer; fi, fo: text; procedure doc; var i, j: byte; begin assign(fi, 'D:mangi.txt'); reset(fi); readln(fi, n); for i:=1 to n do for j:=1 to n do read(fi, a[i, j]); close(fi); end; procedure xuly; var i: byte; begin if tong > max then begin max:=tong; ng:=x; end; end; procedure inkq; var i: byte; begin assign(fo, 'D:mangout.txt'); rewrite(fo); writeln(fo, 'gia tri lon nhat cua cac phan tu la: ', max); for i:=1 to n do writeln(fo, 'Gia tri: ', a[i, ng[i]], ' (', i, ',', ng[i], ')'); close(fo); end; procedure chon(i: byte); var j: byte; begin for j:=1 to n do if b[j] then begin x[i]:=j; tong:=tong + a[i, j]; b[j]:=false; if i=n then xuly else chon(i + 1); b[j]:=true; tong:=tong - a[i, j]; end; end; begin clrscr; doc; max:=0; tong:=0; for i:=1 to n do b[i]:=true; chon(1); inkq; readln end.

Input mẫu

3 7 9 6 3 5 8 8 6 9

Output mẫu

gia tri lon nhat cua cac phan tu la: 25 Gia tri: 9 (1,2) Gia tri: 8 (2,3) Gia tri: 8 (3,1)

Nếu có thắc mắc các bạn hãy để lại bình luận. Mình sẽ giúp đỡ.

Share on Google Plus

About phanmem2019