Задачи от изпит по САА – 31.05.2012

Накратко ще представя условията и решенията на задачите от изпита по Синтез и анализ на алгоритми (САА), проведен в ТУ на 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) и изглежда по следния начин:

1. Предната стойност result[index-1] по-малка ли е от текущата curr и index по-голямо ли е от нула? (28)
2. Ако да, премести стойността на result[index-1] в result[index] (29) и намали стойността на index с единица (30).
3. Впиши текущата стойност curr в result на позиция index.

И това е всичко!

Задача 2: Имаме следната рекурсивна редица: х = 5х+7; x₀ = 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, функцията ще върне единица – или стойността на x₀ по условие.

В главната функция викаме x за всяко i в рамките на цикъл for, докато резултатът от действието ни удовлотверява, т.е. докато стойността на x е по-малка от 10000. Оттук насетне подходът е същият, като при първото решение.

Какъв е недостатъкът на това решение? За всяко увеличаване на i ще изчислим повторно и x(i-1), и x(i-2), и x(i-n), чак до x(0). В нашия случай i няма да достигне стойност, надвишаваща 5, което значи 28 позовавания на рекурсивната функция.

Представете си какво ще се случи обаче при работа с по-големи стойности…

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