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 15: Cấu trúc vòng lặp For

[Java cơ bản] Bài 15: Cấu trúc vòng lặp For

For là cấu trúc lệnh lặp, như khi muốn in ra 10 phần tử từ 0 đến 9 và khi đó ta sẽ viết ra 10 lệnh in ra màn hình như vậy thì sẽ rất bất tiện. Vậy ta sử dụng vòng lặp để…

[Java cơ bản] Bài 48: ArrayList và Vector

[Java cơ bản] Bài 48: ArrayList và Vector

Ngày hôm nay, mà cũng không biết hôm nào nữa, sẽ học về ArrayList và Vector trong Java, cố gắng xem video và chú ý nha!

[Java cơ bản] Bài 53: toString()

[Java cơ bản] Bài 53: toString()

Hôm nay chúng ta sẽ học về phương thức toString() trong lập trình Java. Chúc các bạn học lập trình Java thật giỏi ^^!

Bình luận ()