Изпит по програмни среди, синтез и анализ на алгоритми и програмиране за мобилни устройства – 30.05.2014

Бях решил повече да не публикувам информация за изпити в Техническия университет в интернет, но покрай собственото ми явяване открих, че мрежата е доста пестелива откъм полезни ресурси. Затова и тук публикувам условията на задачите по дисциплините програмни среди (ПС), синтез и анализ на алгоритми (САА) и програмиране за мобилни устройства от изпита, проведен на 30-и май т.г. за бакалаври-абсолвенти, специалност КСТ.

Програмни среди

Задача 1 (първа група): Да се напише програма с две текстови полета и четири бутона, по един за действията събиране, изваждане, умножение и деление. Да се напишат методите, които осъществяват изчисленията. Резултатът да се извежда в контрола, различна от TextBox.

Задача 2 (втора група): Да се напише програма, която да изчертава линия между две точки, в които е натисната мишката, като първата точка се съвързва с втората, после третата с четвъртата и т.н. Нека дебелината на използваната линия може да се настройва чрез подходяща контрола, а цвета чрез бутон и форма за цвят.

Синтез и анализ на алгоритми

Даден е двумерен масив с n елемента. Да се състави фуккция, която проверява дали намиращите се по вторичния диагонал елементи са членове на монотонно намаляваща редица.

За по-стари задачи вижте:

Програмиране за мобилни устройства

Да се създаде Windows Phone приложение, което да включва две страници. В първата страница на приложението в две колони да се изведат четири малки изображения на ястия от меню на ресторант (в дясната колона) и съответните им названия и цени (в лявата колона). При влачене с пръст по изображение на ястие да се осъществява преход към втора страница на приложението. Във втората страница на приложението в подходящ контрол да се изведе подробна информация за избраното ястие, която да се прочете от съществуващ текстов файл в паметта на приложението (IsolatedStorageFile). Втората страница да съдържа и контрол, в който потребителят да може да въвежда цяло число, представляващо поръчка (брой порции от избраното ястие); да се проверява коректността на въведената информация. Втората страница на приложението трябва да съдържа два бутона-икони от ApplicationBar – единия за потвърждаване на поръчката (извежда се съобщение), а втория за отказ от поръчка; при кликване и на двата бутона да се осъществява връщане към първа страница на приложението.

Решението включва:

  • Скициране на дизайна на екрана на мобилния (вид и разположение на контролите) и работа с приложението
  • Структура на приложението – frame, pages, Grid, StackPanel и т.н. и в каква йерархична връзка са
  • Планиране на ресурсите – .jpg файлове, .png файлове, текстови файлове
  • Планиране на събитията – брой, вид
  • Разпределение на кода между C# и XAML, както и между страниците на приложението
  • Формализирано описание (примерно на псевдо-код) на операциите вътре в методите за обработка на отделните събития.

 

Задача от поправителен изпит по САА – 25.06.2012

Днес се проведе поправителният изпит по Синтез и анализ на алгоритми (САА) и в тази публикация ще разгледаме падналата се задача.

Даден е двумерен масив 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;
}

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

Задачи от изпит по САА – 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; 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 позовавания на рекурсивната функция.

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

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

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

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

Задача 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++.

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