Днес се проведе поправителният изпит по Синтез и анализ на алгоритми (САА) и в тази публикация ще разгледаме падналата се задача.
Даден е двумерен масив 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; }
Може да са ви интересни и двете задачи от редовната изпитна сесия.
Здравейте, всички материали в сайта са много полезни!
Въпроса ми е дали имате още задачи от изпити по САА?
Благодаря предварително.
Радвам се, че са ви влезли в употреба. За съжаление нямам повече варианти, намерих единствено разни материали от групата на нашия поток във Фейсбук, които биха могли да са ви полезни – https://tsarstva.bg/sh/wp-content/uploads/2014/06/saa_2.zip.
Ще се радвам, ако можете след изпита си да ми изпратите и вашите задачи (по пощата или като ги пуснете в коментар тук), за да имаме още по-подробна информация.