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

[Java cơ bản] Bài 34: Overload (Phần 2)

[Java cơ bản] Bài 34: Overload (Phần 2)

Video ngày hôm nay sẽ tiếp tục phần 2 của overload, có thắc mắc các bạn có thể để lại bình luận, mình sẽ giải đáp thắc mắc nếu biết, hehe.

[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 để…

[Lập trình C++] Bài toán rơi chữ và bắt chữ!

[Lập trình C++] Bài toán rơi chữ và bắt chữ!

Đây là một bài toán dạng game đơn giản, từng chữ cái 1 rơi xuống, và công việc của chúng ta là nhập vào chữ cái đang rơi trước khi nó chạm vào vạch… và tất nhiên là phải nhập đúng rồi, các bạn có…

Tải DevExpress 16.1.2 full mới nhất, hướng dẫn cài đặt

Tải DevExpress 16.1.2 full mới nhất, hướng dẫn cài đặt

Ban đầu, DevExpress phát triển UI Controls cho Borland Delphi/C++ Builder, ActiveX Controls cho Microsoft Visual Studio. Hiện nay, DevExpress hướng tới lập trình viên sử dụng Delphi/c++ Builder, Visual Studio và HTML5/Javascript. DevExpress là bộ công cụ hữu ích hỗ trợ các lập trình…

Bình luận ()