Задача от поправителен изпит по САА – 25.06.2012

Днес се проведе поправителният изпит по Синтез и анализ на алгоритми (САА) и в тази публикация ще разгледаме падналата се задача.

Даден е двумерен масив a с n елемента.
 а) Да се намери сумата от елементите на триъгълниците, заключени между второстепенния диагонал и първия и последен ред и стълб;
 б) да се намери най-големият общ делител на сумите от а)

Най-първо ще отбележим, че масивът ни е квадратен – само и единствено в този случай диагоналът разделя матрицата ни на два триъгълника. Вторичният диагонал започва от най-горния най-десен елемент и върви надолу и наляво, докато не достигне най-лявата колона или най-долния ред на матрицата. Т.е. нашият масив разполага с корен от n колони и също толкова редове.

Подусловие а ще изпълним с два вложени един в друг for цикъла, с помощта на които ще обходим масива. За всеки елемент, разположен между първите и последните редове и колони ще определим от коя страна на второстепенния диагонал се намира (или дали не е част от самия диагонал) и ще прибавим стойността му към съответната сума.

Условието един елемент да се намира в рамките на вторичния диагонал е неговите координати да бъдат (ред, общ брой колони-ред).

Нашият цикъл ще добие следния вид:

    for(i=1; i<COLS-1; i++){
        for(j=1; j<COLS-1; j++){
            if(j < COLS-1-i) left += a[i][j];
            else if(j >= COLS-i) right += a[i][j];
        }
    }

Тук COLS е броят колони (а също и редове), а left и right сумите, натрупани съответно в левия и десния триъгълник. Първоначалните стойности на i и на j са единици, за да пропуснем първите ред и колона, а финалните са с едно по-малки от броя редове и колони минус едно – за да пропуснем последните.

Важно е и да не изпуснем да извадим единица в първото условно разклонение if – иначе програмата ще събере и елементите, изграждащи самия диагонал.

Сега за условие б – да намерим най-големия общ делител на двете суми. Най-голям общ делител наричаме най-голямото число, което дели две цели числа без остатък. Това е една стандартна задача, решена от древногръцкия математик Евклид преди около 2400 години. Забележително е, че решенито му се ползва и до днес!

Евклидовият алгоритъм се базира на наблюдението, че най-големият общ делител не се променя, ако от по-голямото от двете числа извадим по-малкото.

Начините да приложим алгоритъма в програма са няколко и тъй като аз самият имам афинитет към рекурсия, реших да използваме именно такава имплементация.

Евклид в „Атинската школа“ на Рафаело

int gcd(int a, int b){
    if(!b) return a;
    return gcd(b, a%b);
}

Както вече казахме, най-големият общ делител не се променя, когато от по-голямото число извадим по-малкото. Следователно функцията вика сама себе си, изпращайки по-малкото число като първи аргумент и остатъка от делението на двете като втори. Ако b не е нула, цикълът се повтаря.

Поради естеството на действието „деление по модул“, методът ще сработи, независимо дали при извикването му стойността на a е по-голяма от тази на b или точно обратното.

Ето го и цялото решение:

#include <iostream>
#define COLS 5

using namespace std;

int gcd(int a, int b){ // Евклид
	if(!b) return a;
	return gcd(b, a%b);
}

int main() {
	int a[][COLS] = { // Примерен масив
			  { 4, 7,  9, -1, 0 },
			  { 2, 0,  2,  5, 6 },
			  { 9, 7, -4,  9, 11 },
			  { 7, 7,  0, -3, 4, },
			  { 9, 4,  3,  0, 5 }
			},
	left = 0, right = 0, i, j;

	for(i=1; i<COLS-1; i++){
		for(j=1; j<COLS-1; j++){
			if(j < COLS-1-i) left += a[i][j];
			else if(j >= COLS-i) right += a[i][j];
		}
	}

	cout << "Сумата в левия триъгълник е " << left << endl
	<< "В десния пък е " << right << endl
	<< "Най-големият общ делител е " << gcd(left, right) << endl;

	return 0;
}

Може да са ви интересни и двете задачи от редовната изпитна сесия.