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

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

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

Примерите са решени на 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++.

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

Leave a comment

Your email address will not be published. Required fields are marked *