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 7: Từ khóa trong Java

[Java cơ bản] Bài 7: Từ khóa trong Java

Từ khóa (key word) là các từ mà ta không thể dùng để đặt tên. Primitive data: char, byte, short, int, long, float, double, boolean. Modifier: Access modifier: public, protected, private. Non- Access modifier: final, stactic, abstract, transient, volatile. Other: for,while, do, if, else, void,…

[Java cơ bản] Bài 49: Map

[Java cơ bản] Bài 49: Map

Ở bài hôm nay mình sẽ hướng dẫn cho các bạn về một loại đối tượng nữa trong Java, đó là Map. Nó cho phép chúng ta lưu trữ các loại object khác nhau.

[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 24: Interface

[Java cơ bản] Bài 24: Interface

Video clip này sẽ giới thiệu tới các bạn về Interface trong lập trình Java. Chúc các bạn học tốt.

Bình luận ()