Малко рекурсия

Време е да дам и последните две задачки по Синтез и анализ на алгоритми – това са два прости примера от областта на рекурсията.

Задача 1: Да се изведат в обратен ред стойностите на едномерен масив.

#include <iostream>
using namespace std;

int arr[] = { 5, 4, 3, 2, 1 };

void izvedi(int arr[], int ndx){
	cout << arr[ndx] << endl;
	if(ndx > 0) izvedi(arr, --ndx);
}

int main(){
	int size=5;
	izvedi(arr, --size);
	return 0;
}

Какво става: имаме функция, на която подаваме масив и номер на негов елемент, който искаме да изведем. Функцията извежда стойността на този елемент и вика себе си, подавайки същия масив и номера на предишния елемент. И така, докато стигнем нулевия елемент…

Задача 2: Да се изведе сумата на цифрите на естествено число.

#include <iostream>
using namespace std;

int poedno(int a){
	if (a) return a%10 + poedno(a/10);
}	

int main(){

	cout << poedno(1234);
	return 0;
}

Съвсем просто. На входа на функцията имаме число и ако то не е нула, извеждаме остатъка от делението на десет (т.е. последната му цифра) и викаме същата функция с аргумент частното на числото и 10.

Това е всичко. От домашното ни остана само една точка – съпоставка на сортиращите алгоритми. Но това следващия път…

Двумерни масиви – седлова точка

Ето я и втората задача за двумерни масиви:

Задача 2: Да се преброят седловите точки на двумерен масив. Седлова точка се нарича елемент, който едновременно е минимален за реда и максимален за стълба, в който се намира, или обратното.

Решение:

#include <iostream>
#include <iostream>
#define ARRA 4
#define ARRB 4
using namespace std;

int main(){

    int arr[ARRA][ARRB];
    int row, r, col, m;

    int br = 0;

    bool fail = false;

	// Въвеждаме масива
    cout << "Въведете двумерен масив (" << ARRA << " на " << ARRB << "):\n";
    for(row=0; row<ARRA; row++)
        for(col=0; col<ARRB; col++){
        cin >> arr[row][col];
    }
    cout << "[Готово]\n" << endl;

    cout << "Намерих следните седлови точки: ";

	// Обхождаме матрицата ред по ред
    for(row=0; row<ARRA; row++){
        m = 0;

	  // Намираме максимална точка за реда
        for(col=0; col<ARRB; col++){
            if(arr[row][col] > arr[row][m])
                m = col;
        }
        fail = false;
      // Проверяваме минимална ли е тя за колоната
        for(r=0; r<ARRA; r++){
            if(arr[r][m] < arr[row][m]) fail = true;
        }
      // Намерили ли сме седлова точка?
        if(!fail){
            br++;
            cout << " (" << row+1 << "," << m+1 << ") стойност=" << arr[row][m];
        }

        m = 0;
      // Намираме минимална точка за реда
        for(col=0; col<ARRB; col++){
            if(arr[row][col] < arr[row][m])
            m = col;
        }
        fail = false;
      // Проверяваме максимална ли е тя за колоната
        for(r=0; r<ARRA; r++){
            if(arr[r][m] > arr[row][m]) fail = true;
        }
      // Намерили ли сме седлова точка?
        if(!fail){
            br++;
            cout << " (" << row+1 << "," << m+1 << ") стойност=" << arr[row][m];
        }

    }

    cout << "\n" << br << " общо";
    return 0;
}

Каква е логиката:

  • За всеки ред (27) откриваме максимална стойност (31-34). Отбелязваме не каква е, а къде е (реда го знаем, записваме колоната), използвайки променливата m (33).
  • Проверяваме дали този максимален елемент се явява минимален в m-тата колона (37-39) и ако  това не е така, fail става истина (33).
  • Ако сме намерили седлова точка (обходили сме всички колони, а fail си е останала лъжа), увеличаваме брояча br с 1. Нямаме го по условие, но извеждаме и коя е самата точка – координатите и стойността ѝ.

За същия ред намираме и минималната стойност. Постъпваме по същия начин, както търсейки комбинация макс-мин, но на мушката ни този път е мин-макс.

Както и в миналия пример, любителите на кратките описания тук също могат да опишат двете действия в едно.

Двумерни масиви – магически квадрат

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

Звучи забавно!

Задача 1: Да се провери дали въведен от клавиатурата двумерен масив представлява магически квадрат. Една матрица е магически квадрат, когато сумите по редове, колони и по двата диагонала са равни.

Решение:

#include <iostream>
#define ARRA 3
using namespace std;

int main(){

	int arr[ARRA][ARRA];
	int i, j;

	int sum = 0;
	int newsum = 0;

	bool fail = false;

	cout << "Въведете двумерен масив (" << ARRA << " на " << ARRA << "):\n";
	for(i=0; i<ARRA; i++)
		for(j=0; j<ARRA; j++){
		cin >> arr[i][j];
	}
	cout << "[Готово]\n" << endl;

	for(i=0; i<ARRA; i++) sum+= arr[i][i];
	for(i=(ARRA-1); i>=0; i--) newsum += arr[i][ARRA-1-i];

	if(!(fail = sum != newsum)){
		for(i=0; (i<ARRA) && !fail; i++){
			for(j=0; j<ARRA; j++){
				if(!j){
					if(i && (sum != newsum)) fail = true;
					newsum = 0;
				 }
				newsum += arr[i][j];
			}
		}
		cout << "\n";
		for(i=0; (i<ARRA) && !fail; i++){
			for(j=0; j<ARRA; j++){
				if(!j){
					if(i && (sum != newsum)) fail = true;
					 newsum = 0;
				 }
				newsum += arr[j][i];
			}
		}
	}
	cout << "Квадратът ";
	if(!fail) cout << "е магически!\n";
	else cout << "не е магически!\n";

	return 0;

}

Този код може и да ви се стори леко объркващ, така че смятам да обясня какво се случва ред по ред. Причината да не правя това в коментари е, че смятам, че в случая това би направило четенето по-трудно.

Същинското действие започва от (22). Преди това сме декларирали променливи и прочели числата от клавиатурата.

Първо намираме сумите по главния (22) и по вторичния (23) диагонал.
Променливата, с която отбелязваме дали условието е било нарушено, fail, приема за стойност „различава ли се сумата по главния от тази по вторичния диагонал?“ (25). Ако разлика не е налице, можем да продължим.

В следващия for (26), където търсим сумите по редове и ги сравняваме, като условие вписваме и „докато fail не е истина“, с което предодвратяваме ненужните изчисления, които биха възникнали при обхождане на целия масив.

Ето какво се случва: четем един по един елементите от всеки ред (26-27) и когато j е нула (28-и ред) (т.е. сме в началото на всеки следващ ред от матрицата), правим сравнениe между sum и newsum (29). Нямаме необходимост да правим подобна съпоставка, когато сме на първия ред (т.е. този с нулев индекс) и указваме това си желание в условието. Веднъж направили сравнението, нулираме newsum, за можем да приютим вътре поредната стойност от реда. Това се случва на ред 32.

Следва да повторим напълно същата процедура и за колоните на матрицата. Любителите на кратките описания биха могли да вместят двете неща в един алгоритъм.

Накрая (46) остава само да оповестим присъдата – магически ли е или не квадратът.

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

  1. Изберете си число, от което да започнете. Например 1.
  2. Представете си квадратна матрица, 5 на 5.
  3. По диагонал, започвайки от първата позиция на третия ред и вървейки нагоре, нанасяйте последователно числата – това, от което сте решили да започнете и поредните му. Например 1, 2, 3.
  4. Следващият диагонал започва от четвъртия ред и от втората му позиция.
  5. Това важи и за последния диагонал – той върви нагоре и надясно от петия ред и третата му позиция.
  6. Досега получихме 5 на 5 матрица с някои празни позиции. Искаме обаче квадратът ни да е с размери 3 на 3. Имаме нанесени точно девет числа или всичко, необходимо за нашия магически квадрат, е налице.
    Затова правим следното – пренасяме всяко число, падащо се извън 3 на 3 матрицата (т.е. на някой от крайните редове и колони) три полета в посока матрицата.
    Резултатът е един прекрасен магически квадрат.

Например

Магически квадрат

Едномерни масиви

Ще поставя начало на категория „Алма матер“, представяйки първата част от решенията си на домашните задания по дисциплината „Синтез и анализ на алгоритми“.

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

Примерите са решени на C++.

Задача 1: Да се провери дали дадена редица е „назъбена“, т.е. изпълнено ли е следното условие:  а0 < a1 > a2 < a3

Решение:

#include <iostream>
#define SIZE 4
using namespace std;

int main(){

	int arr[SIZE], i;
	bool success = false;

	cout << "Въведете, моля, редица от " << SIZE << " числа:" << endl;
	for(i=0; i<SIZE; i++){
		cin >> arr[i];
	}
	cout << "[Готово]\n" << endl;

	for(i=1; i<SIZE && (success = ((arr[i-1] < arr[i]) &&
           ((arr[i] > arr[i+1]) || (i == SIZE-1)))); i+=2);

	if(success) cout << "Редицата отговаря на условията!" << endl;
	else cout << "Редицата НЕ отговаря на условията!" << endl;
	return 0;
}

 Идеята ми тук е следната: на първо място няма необходимост да правим проверка за всеки елемент – можем да „караме“ през едно, като това си намерение описваме във for цикъла.

И понеже обожавам for циклите без тяло, правим условието за продължаване на цикъла така, че с всяко увеличение на i директно да изчисляваме и дали редицата продължава да удовлетворява условието: за всеки четен елемент на масива (започваме от i=1, т.е. от втория елемент, а нечетните елементи прескачаме, увеличавайки i с две при всяко завъртане на цикъла), предхождащият го елемент трябва да е с по-малка стойност, а този след него трябва или да е по-малък, или да не съществува (т.е. i-тият елемент е последен в редицата). Изпълнението ще трае, докато последователността, която имаме по условие, не се наруши (което ще се отрази на булевата променлива success, която ще приеме стойност лъжа).

Накрая остава просто да изведем резултата.

Задача 2: Да се намери броят на площадките в едномерен масив от числа. Площадка е всяка последователност от равни числа.

Решение:

#include <iostream>
#define SIZE 10
using namespace std;

int main(){

	int arr[SIZE], i;
	int br = 0;
	bool in_series = false;

	cout << "Въведете, моля, редица от " << SIZE << " числа:\n";
	for(i=0; i<SIZE; i++){
		cin >> arr[i];
	}
	cout << "[Готово]\n\n";

	for(i=1; i<=SIZE; i++){
		if(arr[i] == arr[i-1]){
			in_series = true;
			if(i == SIZE) br++;
		}
		else{
			if(in_series) br++;
			in_series = false;
		}
	}

	cout << "Намерих " << br << " площадки.\n";
	return 0;
}

Започваме проверката от втория елемент на масива (т.е. от този с индекс нула) и продължаваме до последния включително. Избрал съм да сравняваме текущия елемент с предишния.

Когато текущият елемент и този преди него са равни, отбелязваме това в булева променлива. Логиката е следната: не увеличаваме броя открити площадки, преди да сме стигнали стойност, отличаваща се от предходната. Така броят е точен, с едно изключение – ако достигнем края на масива. А този проблем се решава лесно – добавяме проверката if(i == SIZE) br++.

В следващата част от поредицата ще се занимаем с някои задачи за двумерни масиви.