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 20: Hướng đối tượng OOP

[Java cơ bản] Bài 20: Hướng đối tượng OOP

Tóm tắt nội dung: Giới thiệu hướng đối tượng trong Java Nội dung: Trong lập trình hướng đối tượng thì có 3 đặc điểm cơ bản chính sau: – Thừa kế (Inheritance). – Đa hình (Polymorphism). – Đóng gói (Encapsulation). Thừa kế: Cho phép các…

[Java cơ bản] Bài 23: Inner class

[Java cơ bản] Bài 23: Inner class

Video này sẽ giới thiệu tới các bạn về Inner class trong lập trình Java, các bạn hãy coi video, nếu có thắc mắc gì có thể để lại comment, chúc các bạn vui vẻ!

[Java cơ bản] Bài 12: Biểu thức Boolean

[Java cơ bản] Bài 12: Biểu thức Boolean

Giới thiệu các biểu thức boolean và cách sử dụng biểu thức boolean. Đối với biểu thức && đúng khi và chỉ khi hai biểu thức điều kiện đều đúng nên ở if – else thứ nhất sẽ có kết quả là false vì a>10 là sai….

[Java cơ bản] Bài 27: Static

[Java cơ bản] Bài 27: Static

Giới thiệu từ khóa Static ở trong Java. Trong class của Java có hai thành phần là thuộc tính và phương thức. Thuộc tính và phương thức phụ thuộc vào đối tượng tạo ra.

Bình luận ()