Увод в Програмирането - Практикум, 2005/2006

Формула на Бул

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

Да разгледаме следната задача:

Потребителят хвърля зар и се пада число между едно и шест. Да се напише програма, която пита дали числото се дели на 2, дали се дели на 3 и дали е по-голямо от три. Въз основа на получената по този начин информация програмата да познава кое число се е паднало.

Очевидно тук трябва да получим шест различни случая в зависимост от отговорите на трите въпроса. Можем да се опитаме да измислим алгоритъм, който да дава отговор посредством вложени if- ове. Макар че при тази задача това не би било чак толкова трудно, в случай че имаме четири или пет различни критерия въз основа на които да се получават десетина – двайсетина случая няма да ни бъде особено лесно. Затова ще използваме метода на Бул.

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

Нека си направим таблица със всичките осем случая които се получават от трите критерия (8 = 2³). Ще означаваме с 0 или 1 ако някой от критериите е съответно лъжа или истина. В първата колона сме записали числото, което съответства на всеки от дадените случаи. Има два случая които са логически невъзможни в нашата ситуация и тях няма да разглеждаме по-нататък, поради което са отбелязани с Х.

На всеки от шестте случая сме съпоставили по един логически израз, който е така конструиран, че да е верен тогава и само тогава когато сме в съответния случай. В изразите е използван синтаксиса на езика C/C+ , като за леснота сме използвали x, y и z като булеви променливи, носещи информация за всеки от трите критерия, които определят отделните случаи.

Сега можем да се възползваме от това че булевите променливи (и изрази) в езика C/C++ се интерпретират като 0 или 1. А нулата и единицата имат някои много удобни свойства. Това което ще ни свърши работа в случая е: 0*a = 0 и 1*a = a за всяко a . И така, ако умножим всеки от изразите в таблицата с числото което съответства на неговия случай и съберем получените произведения ще достигнем до следния израз:

(!x && !y && !z)*1 + (!x && !y && z)*5 + (!x && y && !z)*3 + (x && !y && !z)*2 + (x && !y && z)*4 + (x && y && z)*6

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

int a = (!x && !y && !z)*1 + (x && !y && !z)*2 + (!x && y && !z)*3 + (x && !y && z)*4 + (!x && !y && z)*5 + (x && y && z)*6 ;

Сега можем да използваме оператора switch() за да изведем съответното съобщение за получената стойност:

switch(a)

{

case 1: cout << ”You got one.”; break;

case 2: cout << ”You got two.”; break;

case 3: cout << ”You got three.”; break;

case 4: cout << ”You got four.”; break;

case 5: cout << ”You got five.”; break;

case 6: cout << ”You got six.”; break;

default: cout << ”Incorrect Input!”;

}

В нашия случай вместо default можеше да използваме case 0: но това не се препоръчва, защото се нарушава логиката на алгоритъма – нулата е по-скоро изключение отколкото самостоятелно определен случай.

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

Ето и малко задачки за упражнение:

Да се състави израз по формулата на Бул, за определяне в кой квадрант се намира дадена точка, ако са зададени координатите и. (ще считаме че точките от абсцисата са към І или ІІ квадрант, а тези от ординатата към І или ІV).

Упътване: Съставете израз, използвайки условията (x>=0) и (y>=0)

Да се усложни горната задача, като се въведат и допълнителни условия за точките по абсцисата и ординатата.

Упътване: Използвайте условията (x>0), (y>0), (x==0), (y==0) – получават се 2⁴ = 16 случая, но не всички от тях са коректни.