Опции

За четирите години, прекарани в ТУ, така и не се сблъсках със сериозната корупция, за която бях слушал. Никой не ми е искал, поне досега, пари, за да ми даде изпита си. Срещал съм само по-леките форми на нечестно придобиване на средства с цел гарантиране на по-добра оценка. А именно – доцентът, който предлага да си купите сборника му, дори вече да го имате, за да не ви прати на поправка, когато оценката ви е слаба. Но пък срещнах доста измамници сред студентите – пращащи други хора по изпитите вместо тях или преписващи със слушалка в ухото. По начало тази неправда ме ядосваше. После свикнах. Действително това дали мамите или не не е от значение. Можете да си научите каквото ви трябва и без да си „губите времето“ с университета. Както бихте могли и нищо да научите, дори съвестно да сте ходили по лекции и упражнения. Бихте могли да оправдаете част от мързела си с убеждението, че в университета не ви учат на каквото трябва и както трябва, но от един момент нататък просто ставате нагли.

Нямах представа за колко се търгува един взет изпит до преди седмица, когато в пощата ми се озова едно интересно писмо.

Първи имейл

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

email2

Което надмина очакванията ми – мислех си, че за тези пари можете да си купите изпита директно от преподавателя. Колко съм бил наивен! Преди известно време си бях играл да проверя за колко се търгува една фалшива диплома и писах на един от хората в бранша, подвизаващи се в Продавалник. Казаха ми, че за 1300 лева можете да се сдобиете с диплома от кой да е български университет, от кото година и с какъвто успех желаете. Доколко е „качествена“ услугата не знам – но хората предлагат да платите директно при получаването, както и убеждават, че разполагат с всички защитени знаци на документа. Бих посъветвал младежа (?) от писмата да се обърне направо към тези добри хора – ще му излезе по-евтино от пълния комплект по-тежки изпити, ала знам ли – може би търси студентския живот. Легендарният студентски живот с дюнерите, чалгата и долнопробните нощни заведения, животът, където баварци със сини номера „дрифтират“ пред „Фантастико“, животът „с изпити тежки/с нощи горещи.“ А може да преследва нещо друго.

Аз мога единствено да си пожелая тук да идват по-малко от тези хора и повече от тези, които искат да постигнат нещо в живота си.

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

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

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

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

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

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

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

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

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

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

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

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

 

Изгубена студентска книжка – ръководство за оцеляване

Изгубили сте си студентската книжка? И сега се чудите какво да правите. Спокойно, на всекиго може да се случи, от най-разсеяния тип (в мое лице), до някой, който не изважда носа си от записките по цифрова схемотехника или някаква подобна глупост.

Точно така, аз също имах неудоволствието да попадна в такава ситуация и да ви кажа, никак не беше приятно. За щастие случката се размина без пострадали и убити, нито пък изгубих прекалено много време и не ме изключиха от университета.

Така, на първо място щом установите, че студентската ви книжка я няма, потърсете добре да не сте я забутали някъде, помислете си къде сте я носили, откъде сте минавали, на кого сте я давали. Може да е у някой колега или да пък да сте я оставили в кафене. Нека приемем, че я няма на никое от тези места и че сте съвсем убедени, че е изгубена.

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

След като вече знаете, че студентската книжка няма да се намери, трябва да я обявите за изгубена. Знам, че ако не сте патили, само сте чували за това и ви се е сторило смешно. Е, не е така, това с обнародването не е отживелица и днес още си е в сила. И дори не се практикува само и единствено от нашия винаги в крак с модата университет, напротив, ако отворите вестника, недейте да се изненадвате, когато попаднете на известия за изчезнали дипломи, свидетелства и други документи. Доколко това е нужно не се знае и може да се спори. Но сега нямате време за това, особено ако сте имали нещастието да останете без книжка в края на семестъра.

Изискванията са да пуснете обявата в издание с национално покритие. Тоест вашият градски седмичник не става. Относно това дали можете да пуснете обява в интернет издание, служителките в канцеларията не бяха сигурни. Тук също имате национално покритие и новината е далеч по-видима. Ако някой напише името ви в търсачката, веднага ще разбере колко сте завеян :) Решите ли да публикувате в интернет, първо попитайте в канцеларията. Реално номерът понякога минава, понеже в интернет съществуват такива обяви.

Стига да разполагате с дебитна или кредитна карта, няма да е необходимо да се разкарвате където и да било, а ще си свършите работата бързо и лесно (ако имате карта от университета, на която ви изпращат стипендиите, и тя става). Ето и моето

walkthrough

  1. Реших, че ще рекламирам във вестник „24 часа“ и затова и съветът ми е за там. Отивате на сайта на Вестникарска Група България (ВГБ) и регистрирате акаунт. Регистрацията иска всевъзможни данни, включително ЕГН и други неща, които можете да не давате, понеже явно не се прави валидация. Имайте предвид обаче, че данните ви ще се ползват за фактурата и ако тя ви трябва, ще е добре да ги попълните коректно.
  2. След като се регистрирате, потвърдите акаунта си и влезете в системата, отидете на „Е-Магазин“ и от опциите изберете „Свободен текст“ в категорията „Малки обяви“. Изберете си издание, аз, както вече казах, се спрях на „24 часа“. Рубликата е „МО“, подрубликата „Разни“, под-подрубликата „Други“.
  3. На страницата „Конфигурация на поръчка“ попълвате и данните на самата обява – оформлението е стандартно, за дата на публикация дайте най-близката възможна и я запомнете (на по-късен етап няма да можете да я видите), а текстът е следният (не е необходимо да е едно към едно, понеже никъде не ми казаха точни изисквания, трябва просто от него да става ясно на кого е въпросната студентска книжка):

    [dark_box]Изгубена студентска книжка с ф. № XXXXXXXXX към ТУ-София на Иван Петров Драгостинов, НЕВАЛИДНА[/dark_box]

    Удоволствието от това, към днешна дата (18-и януари 2013 г.), ще ви струва 7,20 лв. И това е само началото, но да не сте били толкова разсеяни :)

  4. Щом платите, ще имате възможност незабавно да видите вашата фактура. Ако много бързате можете да представите нея в канцеларията. Имайте предвид обаче, че не е изключено и да ви откажат, понеже в нея не фигурира текстът на обявата, нито датата, на която ще излезе вестникът.

    Фактура, издавана от ВГБ при онлайн поръчка на обява

    Фактура, издавана от ВГБ при онлайн поръчка на обява

  5. Докато чакате да излезе вестникът, отидете до книжарницата на ТУ и си купете нова студентска книжка. Ще ви питат само книжката ли искате или пълния комплект документи за записване. Вземете само книжката – ще ви струва 5 лв. Попълнете си данните в нея.
  6. Отидете в касата на вашия факултет и внесете такса „Издаване на дубликат на студентска книжка“. 20 лв. (припомням, цените са към 18-и януари 2013 г.) Ще получите квитанция и касова бележка, които, едва ли е нужно да казвам, трябва да запазите.
  7. Когато дойде време вестникът ви да излезе (нормално първата възможна дата, в която можете да публикувате, е 2-3 дни след деня на плащането) отидете до най-близката будка и си го купете. Намерете текста си на страница „Малки обяви“ :)
    Възможно е обявата да я няма в деня, за който сте се разбрали. Няма страшно обаче – не са ви забравили, просто си има в кои дни излизат тези обяви. Може да се наложи да си купите вестника и на следващия ден. В този ред на мисли, „24 часа“ в събота струва 1 лв., а в неделя 80 ст.
    Ако известието ви го няма и се притеснявате, можете да се свържете с хората – телефонните номера в сайта им дават свободно и в последствие заето в събота, но пък в делничен ден непременно ще ви звъннат и ще ви пратят имейл. Ползвайте формата за контакт.
  8. Вземете вестника, квитанциите и новата студентска книжка (да не забравите снимката) и отидете с тях в канцеларията. Всичко ще е готово или на следващия ден, или на този след него :)
  9. Вземете си книжката, когато е готова. Общо похарчени 7,20 + 5 + 20 + 1 = 33,20 лв.

Ами ако намеря книжката си?

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

  1. Носите квинтанцията в канцеларията, където казвате, че документът е намерен, на квинтанцията ви написват „Намерена“ и удрят един печат.
  2. На касата давате квитанцията и касовата бележка и получавате към нея разписка, която носите при някой по-високо в йерархията на университетските служители (ще ви кажат къде, в моя случай беше една врата в края на същия коридор), където получавате подпис, одобряващ връщането.
  3. Отивате на разплащателната каса, която също ще ви посочат. Не забравяйте да се подпишете. Ще ви върнат двайсетте лева и за вас ще останат само приятните спомени :)

Финалната ми препоръка е освен да внимавате къде си оставяте документите, да сложите в книжката си една хартийка с телефонен номер. Аз бих звъннал, ако намеря някъде такава книжка.

ТУ: Компютърна периферия и Операционни системи

При изготвянето на курсови задачи, проекти и други този семестър се сблъскахме за пореден път, но като че ли този път с по-голяма сила, с проблема за недостъпността на необходимата информация на български. Както и с нехайството на преподавателите относно положения труд. И понеже именно тези преподаватели са основната аудитория на този труд, най-често оставащ да прашлясва в някой архив (а в случая с цифрово представените материали – на някой сървър), решихме, че е най-добре създадените данни да се споделят с евентуалните си ползватели, а именно безчетните потребители на интернет.

Представяме ви:

Компютърна периферия: Мастиленоструйни принтери

Доклад и презентация от Любов Нейчева и Ивайло Маринков.

Проектът разглежда устройството, функционалността и проблемите на мастиленоструйните принтери. Спира се на мастилата, които се използват, говори за войната между производителите и компаниите, които си вадят хляба, зареждайки касети с мастило на много по-ниски от оригиналните цени. Става дума за дюзи, използвани портове и професионални модели.

[ pdf изтегли доклада (pdf)] [ tarball изтегли доклада и презентацията (tarball)]

 

Операционни системи: The Stack Frame

Презентация на Ивайло Маринков (на английски). Създадена е с идеята да бъде представена на чуждестранните студенти на ТУ, изучаващи дисциплината ОС, но към тази дата не е показвана.

Изясняват се понятия като call stack, subroutine, stack frame и debugger и се дава нагледен пример за употребата на GDB.

[ pdf изтегли презентацията (pdf)]

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

Честита 2013!

Предполагам, че това е и последната публикация за тази година, така че завършвам с надежда 2012 да е била добра за вас и с пожелания за прекрасна нова 2013 година :)

До нови срещи!

Задача от поправителен изпит по САА – 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++.

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