Накратко ще представя условията и решенията на задачите от изпита по Синтез и анализ на алгоритми (САА), проведен в ТУ на 31-ви май в рамките на редовната изпитна сесия.
Задача 1: Даден е двумерен масив, състоящ се от 25 елемента. Нека в друг масив се запишат елементите по двата диагонала, основен и вторичен, подредени в обратен ред.
Решение:
#include <iostream> #define SIZE 5 using namespace std; int main() { int arr[][SIZE] = { { 1, 4, 0, -1, 6 }, { 9, 2, -5, 7, 6 }, { 0, -9, 8, 1, 9 }, { 4, 9, -7, 4, 0 }, { 3, 8, -2, 4, 5 } }; int result[ SIZE*2 ], curr, i, index; for(i=0; i < SIZE*2; i++) { if(i < SIZE) { result[i] = arr[i][i]; // Главен диагонал } else { result[i] = arr[SIZE-1-(i-SIZE)][i-SIZE]; // Вторичен } index = i; curr = result[i]; while((index > 0) && (result[index-1] < curr)) { result[index] = result[index-1]; index--; } result[index] = curr; } return 0; }
Ето и обяснението (в скоби са дадени номерата на редовете, където се извършват съответните действия). Приемаме, че частта, в която се декларират променливите и двумерният масив се инициализира с примерни стойности не се нуждае от обяснение.
За всеки елемент от едномерния масив (17) извличаме стойност от един от диагоналите на двумерния масив и я вписваме. Започваме от главния диагонал (19) и продължаваме с вторичния (22). Разграничаването от кой диагонал кога трябва да четем правим лесно, защото знаем, че половината елементи на едномерния масив съдържат числата от единия диагонал, а другата – от втория.
Веднъж въвели стойността от диагонала, отбелязваме същата и числото, съхранявано в i, съответно в променливите curr (26) и index (25). Ще ги използваме при сортировката.
За подреждането бихме могли да се доверим на всеки прост алгоритъм за сортиране, а аз в конкретния случай реших да ползвам сортиране чрез вмъкване.
Примерът за този алгоритъм, който дава книгата „Основи на алгоритмите“ от Саймън Харис и Джеймс Рос, е за играчи на карти. Държите няколко карти и при раздаване получавате още. Най-вероятно ще ги сортирате именно чрез вмъкване – ще прецените къде се падат измежду другите по боя и стойност и ще ги пъхнете именно там, измествайки останалите надясно – това е и нашият принцип.
Това нещо става в рамките на четири реда (28-32) и изглежда по следния начин:
- Предната стойност result[index-1] по-малка ли е от текущата curr и index по-голямо ли е от нула? (28)
- Ако да, премести стойността на result[index-1] в result[index] (29) и намали стойността на index с единица (30).
- Впиши текущата стойност curr в result на позиция index.
И това е всичко!
Задача 2: Имаме следната рекурсивна редица: х = 5х+7; x0 = 1.
Да се намери средноаритметичното на сумата на елементите, намиращи се между първия по-голям от 1000 и последния по-малък от 10000 елемент от редицата.
I решение – без рекурсия:
#include <iostream> using namespace std; int main() { int x = 1, // по условие x(0) = 1 br = 0, sum = 0; while((x = 5*x + 7) < 10000) { if(x > 1000) { sum += x; br++; } } if(br) cout << "Средноаритметичната стойност е " << sum/br << endl; return 0; }
Подходът тук е много прост. Инициализираме x със стойност 1 и в цикъл с предусловие while за всяка стъпка го преизчисляваме на база предходната му стойност, докато не достигне 10000.
Ако x е по-голямо от 1000 го добавяме към общия сбор и увеличаваме брояча br, който показва колко са елементите, отговарящи на нашите условия.
Накрая извеждаме средната стойност, като предварително сме се защитили от евентуално деление на нула.
II решение – с рекурсия
#include <iostream> using namespace std; int x(int n){ if(!n) return 1; return 5*x(n-1) + 7; } int main() { int element, sum = 0, i = 0, br = 0; for(i=0; (element = x(i)) < 10000; i++) { if(element > 1000) { sum += element; br++; } } if(br) cout << "Средноаритметичната стойност е " << sum/br << endl; return 0; }
Нека решим задачата по друг начин.
x(int n) е рекурсивна функция, която в общия случай връща 5x+7, където x е обръщение на функцията сама към себе си, при което стойността на аргумента n е понижена с едно.
В момента, в който n достигне стойност 0, функцията ще върне единица – или стойността на x0 по условие.
В главната функция викаме x за всяко i в рамките на цикъл for, докато резултатът от действието ни удовлотверява, т.е. докато стойността на x е по-малка от 10000. Оттук насетне подходът е същият, като при първото решение.
Какъв е недостатъкът на това решение? За всяко увеличаване на i ще изчислим повторно и x(i-1), и x(i-2), и x(i-n), чак до x(0). В нашия случай i няма да достигне стойност, надвишаваща 5, което значи 28 позовавания на рекурсивната функция.
Представете си какво ще се случи обаче при работа с по-големи стойности…
Може да ви е интересна и задачата от поправителната изпитна сесия.
Leave a comment