thiet ke website

[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.

tổng phần tử không cùng hàng cùng cột lớn nhất

Đề 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ố đó.

c++ thuat toanVí 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 đỡ.

Thiet ke logo

Bài viết liên quan

10 ngôn ngữ lập trình nên học hiện nay

10 ngôn ngữ lập trình nên học hiện nay

Ngành công nghệ phần mềm đang phát triển như vũ bão trong thời gian qua. Vì vậy, kỹ năng lập trình đang có nhu cầu rất lớn, và các công việc có liên quan đến lập trình thì thường được trả lương cao hơn nhiều…

[Java cơ bản] Bài 46: File Writer

[Java cơ bản] Bài 46: File Writer

Video này sẽ giới thiệu và hướng dẫn các bạn về File Writer trong Java, chúc các bạn học tốt và hiệu quả!

[Java cơ bản] Bài 6: Thuộc tính và biến

[Java cơ bản] Bài 6: Thuộc tính và biến

Video này sẽ giới thiệu cho các bạn sơ lược về thuộc tính và biến, một số phím tắt cơ bản giúp bạn lập trình tốt hơn. Chúc bạn học tốt!

[Java cơ bản] Bài 50: Generic (Phần 1)

[Java cơ bản] Bài 50: Generic (Phần 1)

Bài hôm nay mình sẽ giới thiệu với các một khái niệm là Generic trong Java, cái này hơi là trừu tượng một tý…

Bình luận ()