Резюме. Основен акцент в статията е пресмятане на времето за изпълнение на програми. С примери от математически ребуси се илюстрира как времето за изпълнение на една програма зависи най-вече от конкретния алгоритъм. Описани са три алгоритъма, които решават един и същ математически ребус. Приведениса резултатите от пресметнатите времена за изпълнение на програмите, написани по тези алгоритми в табличен и графичен формат. В края на статията са представени и няколко идеи за развитие на описания проект.

Ключови думи: program execution time, solving math puzzles, emperical approach

Ребусите са развлекателни задачи, които много хора приемат като интелектуално предизвикателство. Срещат се както в печатни издания, вестници, списания и книги, така и в конкурси и състезания за ученици. Разнообразието им е твърде голямо и се проявява не само в структурата на данните и на съответните отговори, но също така и в областта на знанията, необходими за решаването им. Една голяма част от ребусите са в областта на математиката и е естествено да ги наричаме математически ребуси. Само като един пример ще споменем за масово решаваните математически ребуси, познати с името Sudoku puzzles.

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

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

1. Един специален клас от математически ребуси

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

Общият вид на ребусите, които предстои да разгледаме, се вижда от примерния ребус на фиг. 1. На фиг. 2 е дадено едно негово решение. Да поясним някои от особеностите в структурата на ребуса.

Ребус от ред 3 е квадратна таблица с \(5 \times 5\) клетки и още 6 числа, които ще наричаме коефициенти на ребуса. В някои от клетките на таблицата са записани аритметичните операции \(\{+,-, \times, /, \%\}\), а другите клетки са празни. Има и трети вид клетки, които са празни, но те са маркирани (запълнени с цвят).

Решаването на ребуса се свежда до намирането на елементите на квадратна матрица от 9 ненулеви десетични цифри, които, записани в маркираните клетки на ребуса, определят изрази, стойностите на които са равни на коефициентите, дадени в края на съответните редове и стълбове с нечетни номера.

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

Да отбележим, че със знаците „/“ и „%“ са означени съответно целочислено деление и остатък от целочислено деление и че всички операции са без приоритет и се извършват последователно отляво надясно. Поради наличието на операцията деление, изискването за десетичните цифри, елементи на матрицата, да са само ненулеви числа, е съществено и винаги ще предполагаме, че то е изпълнено без изрично да се споменава за него.

Да разгледаме примера от фиг.2. Вижда се, че:

\[ \begin{array}{ll} 4 \times 7 / 5=5 & (\text { Втори ред }) \\ 6+9 \% 4=3 & (\text { Трети ред }) \\ 8 \times 4-6=26 & (\text { Пьрви стълб }) \end{array} \]

Има още един въпрос, отнасящ се до множеството от операции в този вид ребуси. Тъй като в хода на пресмятане на един израз като междинен резултат може да се получи отрицателно число, то добре е да се определи смисълът на операциите „/“ и „%“ в случаите, когато един или и двата аргумента са отрицателни числа. Това се налага, понеже в различните езици за програмиране тези операции са определени по различен начин. Операцията „%“ (остатък от целочислено деление) в езиците C++ и Java се дефинира чрез израза:

\[ a \% b=a-(a / b) * b \]

Примерите от табл. 1 дават пълна представа за използването на операциите целочислено деление и остатък от целочислено деление.

И така, всеки ребус от ред 3 е определен от 6 коефициента, 12 операции и квадратна матрица с 9 ненулви десетични цифри. По-нататък за по-кратко с \(M P\) ще означаваме произволен математически ребус от ред 3 (МР – Mатематически Ребус или МР – Math Puzzle).

Да отбележим, че математическа задача \(MP\) представлява нелинейна система от 6 уравнения и 9 неизвестни от видa:

\(\begin{array}{|ll} & a_{1} \oplus a_{2} \oplus a_{3}=k_{1} & (1)\\ & b_{1} \oplus b_{2} \oplus b_{3}=k_{2} & (2)\\ & c_{1} \oplus c_{2} \oplus c_{3}=k_{3} & (3)\\ & a_{1} \oplus b_{1} \oplus c_{1}=k_{4} & (4)\\ & a_{2} \oplus b_{2} \oplus c_{2}=k_{5} & (5)\\ & a_{3} \oplus b_{3} \oplus c_{3}=k_{6} & (6), \end{array}\)

където \(\oplus\) е произволна аритметична операция от множеството \(\{+,-, \mathrm{x}, /, \%\}\), а неизвестните \(\left\{a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}, c_{1}, c_{2}, c_{3}\right\}\) са ненулеви десетични цифри.

За решаването на \(M P\) ще конструираме три алгоритъма и ще напишем съответни програми, с които да се пресмятат всичките решения на ребуса. Като основен език за програмиране ще бъде използван езикът за програмиране C++.

За удобство при формулирането на задачите, разглеждани по-долу, ще въведем още няколко означения. Означаваме с \(K\) списъка от коефициентите на ребуса, с \(O\)– списъка от операциите му и с \(M\)– матрицата от 9-те десетични цифри. Тогава, ако матрицата \(M\) е решение на ребуса \(M P\), ще казваме, че \(M\) е съвместима с операциите \(O\) и с коефициентите \(K\) на ребуса. Символично това ще записваме с уравнението \(M P(M, O)=K\).

С така въведения клас от \(M P\) можем да дефинираме следните три основни информатични задачи:

Р1. [Права задача] Да се формулира алгоритъм и да се напише съответна програма, която по дадени операции \(O\) и коефициенти \(K\) на \(M P\) от ред 3 намира всички матрици \(X\) (с 3 реда и 3 стълба от десетични ненулеви цифри), които са решения на \(M P\), т.е. такива, за които \(M P(X, O)=K\).

P2. [Обратна задача] Да се формулира алгоритъм и да се напише съответна програма, която по дадени коефициенти \(K\) и матрица \(M\) от 9 ненулеви десетични цифри на \(M P\) от ред 3 намира всички операции \(Y\), съвместими с \(M\) и \(K\), т.е. онези операции, за които е в сила \(M P(M, Y)=K\).

Р3. [Анализ на времето за решаване на МР] Да се пресметне времето за изпълнение на програмите, решаващи задачи Р1 и Р2.

2. Алгоритми и програми за решаване на МР

2.1. Алгоритми за решаване на задача P1

Алгоритъм A [Девет вложени цикъла]

Системата с уравнения от по-горе подсказва идеята, че стойността на всяко неизвестно може да се получи като стойност на управляващата променлива \(x\) на цикъл от вида:

for(int x = 1; x < 10; x++)

Ако се конструират девет вложени цикъла с управляващи променливи \(a_{1}, a_{2}, a_{3}, b_{1}, b_{2}, b_{3}, c_{1}\), \(c_{2}, c_{3}\) (фиг. 3 3) , тогава в тялото на най-вътрешния цикъл ще се генерират всички възможни 9-торки от цифрите \(1,2, \ldots, 9\). Техният брой е \(9^{9}=387420489\). Може да се провери кои от тях са решения на уравненията (1) – (6). Тази първа идея може съществено да се подобри. Още в тялото на третия цикъл с управляваща променлива \(a_{3}\) може да се тества дали тройката \( \lt a_{1}, a_{2}, a_{3} \gt \) е решение на уравнение (1). Само в случай, че тази тройка е решение, се продължава с изпълнението на следващия цикъл с управляваща променлива \(b_{1}\). Този подход ще се приложи и за следващите две тройки от цикли \( \lt b_{1}, b_{2}, b_{3} \gt \) и \( \lt c_{1}, c_{2}, c_{3} \gt \), b2, b3 > и < c1, c2, c3 >, с които ще се тества дали те са решения съответно на уравненията (2) и (3). Това означава, че тялото на най-вътрешния цикъл ще се изпълнява, когато стойностите на деветте управляващи променливи са решения на първите три уравнения. Сега идва ред да се провери дали тези девет цифри са решения и на следващите три уравнеия (4), (5) и (6).

Алгоритъм B [Декомпозиция на 9-значно число на отделни цифри]

Генерирането на всички възможни 9-орки от цифрите \(1,2, \ldots, 9\) може да се извърши от декомпозирането на отделните цифри на целите числа в интервала [111111111, 999999999]. Понеже тези числа са част от числата на типа данни int (INT_MAX \(=2147483647\) ), те могат да се генерират само с един цикъл от вида: for(int x = 111111111; x < 1000000000; x++)

Всяко от числата \(x\) ще се декомпозира до съставните си цифри, съхранени в едномерен масив. Например това може да се извърши със следната функция:

В случай, че някоя от цифрите е нула, текущото изпълнение на тялото на цикъла се прекъсва и се продължава със следващото число. В тялото на цикъла се извършва проверка дали първите три цифри удовлетворяват уравнението (1). В случай, че те не са решение на уравнението, тялото на цикъла също се прекъсва и се продължава със следващата стойност на управляващата променлива на цикъла. Ако тройката цифри е решение, тогава се проверява дали следващите три цифри са решение на уравнение (2). Следвайки тази процедура, ще се търсят онези 9-значни числа, чиито цифри са решения на всичките шест уравнения.

Алгоритъм C [Подобрен вариант на алгоритьм \(A\) ]

Генерирането на девет цифри, измежду които да се търси решение на ребуса, може да се сведе до генерирането само на три цифри. След това тези три цифри се тестват дали удовлетворяват всяко от уравненията (1), (2) и (3) поотделно (виж по-долу функцията rowSol). Да означим с A, B и C три едномерни масива, в които са съхранени трицифрени числа, чиито цифри са решения съответно на първото, второто и третото уравнение. Например за ребуса от фиг. 1 числата в тези три множества са следните:

A = { 319, 416, 429, 526, 539, 636, 649, 713, 746, 759, 823, 856, 869, 933, 966, 979 }

B = { 151, 252, 283, 353, 374, 395, 443, 454, 475, 486, 497, 511, 522, 533, 544, 555, 566, 576, 577, 587, 588, 598, 599, 656, 667, 678, 689, 734, 745, 756, 757, 768, 779, 823, 846, 857, 858, 869, 935, 947, 958, 959}

C = { 124, 125, 126, 127, 128, 129, 164, 175, 186, 197, 214, 215, 216, 217, 218, 219, 254, 265, 276, 287, 294, 298, 344, 355, 366, 377, 384, 388, 399, 434, 445, 456, 467, 474, 478, 489, 495, 524, 535, 546, 557, 564, 568, 579, 585, 614, 625, 636, 647, 654, 658, 669, 675, 694, 696, 715, 726, 737, 744, 748, 759, 765, 784, 786, 816, 827, 834, 838, 849, 855, 874, 876, 897, 917, 924, 928, 939, 945, 964, 966, 987, 995 }

Понеже решенията на следващите три уравнения (4), (5) и (6) са цифри, които се получават съответно от цифрите на числата от множествата \(\mathrm{A}, \mathrm{B}\) и C, то решението на ребуса се свежда до намиране на всички тройки числа \(\langle a, b, c\rangle\) \(\mathrm{A} \times \mathrm{B} \times \mathrm{C}\), на които първите цифри са решения на уравнението (4), вторите им цифри са решения на уравнението (5), а последните им цифри са решения на уравнението (6). Връщайки се отново към примерния ребус, може да се забележи, че цифрите на числата \(823 \mathrm{~A}, 475\) В и 694ÎC са решения на ребуса.

2.2. Програмна реализация на алгоритъм \(C\)

По-долу следват описанията на константите, структурите от данни и дефиницията на функциите, които са основни за програмата. Кодът е пояснен със съответни коментари.

Константи и прототипи на функциите

Дефиниция на две от основните функции на програмата

Резултат от изпълнението на програмата

Solution #1

Три бележки:

– По-добрата читаемост на програмния код е предпочетена пред по-добрата скорост на изпълнението на програмата.

– Използването на динамични масиви (обекти от класа vector) могат да намалят обема на използваната памет от масива rSol .

– Програмите са изпълнявани в среда на Windows 7, CPU 2.50 GHz и Microsoft Visual C++ 2010 Express Edition.

2.3. Алгоритъм за решаване на задача \(P 2\)

Да се генерира \(M P\) означава програмно по случаен начин да се генерират операциите и коефициентите на ребуса, т.е. да се определят елементите на множествата O и K. Това не е трудна задача. Но направените експерименти подсказват, че много голям процент от така генерираните ребуси нямат решения. Затова е по-добре по случаен начин да се генерират елементите на множествата \(M\) и \(O\) и след това да се пресметнат коефициентите на ребуса. По този начин всеки ребус ще има поне едно решение. По-долу следва примерен код, който меже да се използва за генериране на множествата \(M\) и \(O\).

3. Пресмятане на времето за изпълнение на програми

Времето за изпълнение на всяка програма е нейна важна характеристика. И ако този въпрос не винаги се дискутира явно, това е защото най-вероятно изчислителният процес на съответната програма е с ограничен обем от пресмятания и не създава безпокойство от продължителността на изпълнение на програмата или защото не винаги е лесно да се даде ясен и точен отговор на този въпрос. Не рядко проблемът за скоростта на изпълнение на една програма е интересен и при съпоставянето й със скоростта на други програми, които решават същата задача. Такъв е случаят с трите програми, написани по алгоритмите A, B и C. Те дават идентичен резултат, но времето за изпълнение на всяка от тях е различно. Можем ли отнапред да кажем коя от тях изисква най-малко време за изпълнение и защо? Можем ли да подобрим времето им за изпълнение и как да извършим това? По същността на тези въпроси има теория, която в много случаи помага добре да се опише поведението на функцията, представляваща времето за изпълнение на програмата, когато размерът на данните нараства неограничено. В тази статия ще „заобиколим“ теорията и ще приложим директни методи за пресмятане на времето за изпълнение на произволна програма.

3.1. Как да пресметнем времето за изпълнение на една програма?

Пресмятането на точното време за изпълнение на дадена програма или на част от нея се извършва като се засече времето \(t_{0}\) на нейното начало и времето \(t_{1}\) на завършването й и след това се пресметне разликата \(t_{1}-t_{0}\). Определянето на тези времена изисква използването на съответни библиотеки в конкретните среди за програмиране. Накратко това ще преставим при пресмятане на времето за изпълние на програмен код на езиците C++ и Java.

Пресмятане на времето за изпълнение на програми на езика C++

За целта е необходима библиотеката ctime \({ }^{1}\). От нея се използват типът данни clock_t, функцията clock() и констаната CLOCKS_PER_SEC, с която измереното време се трансформира в секунди.

Пресмятане на времето за изпълнение на програми на езика Java

Съществуват няколко начина за пресмятане на времето за изпълннеие на една програма на езика Java. Ето един от тях, в който времето се пресмята в милисекунди \({ }^{2}\), e:

3.2. Пресмятане на времето за изпълнение на програмите, използващи алгоритмите A, B и C

В табл. 2 са посочени данните на 10 „синтетични“ ребуса, генерирани с програмата, решаваща задача P2. В четвъртата колонка е записан броят на възможните решения на всеки ребус, а в петата – съотношението на мултипликативните към адитивните операции. Времето за решаване на всеки от 10-те ребуса, съответно на всяка от трите програми, е приведено в табл. 3.

Анализът на данните от табл. 1 и табл. 2 дава възможност да се направят няколко коментара:

– Определено алгоритъм C изисква най-малко време за намиране на решенията. Но тук следва да се напомни, че при този алгоритъм се използва и допълнителна памет (три масива).

– Най-продължително време за изпълнението е използвано от програмата, реализирана чрез алгоритъм B. Очевидно декомпозицията на 9-значното число на съставните му цифри е основен фактор, който силно влияе на времето за изпълнение.

– И при трите алгоритъма се вижда, че ребус 6 изисква най-много време за решаването му. Защо? Дали конкретните операции влияят толкова силно на времето (вижте последната колонка на табл. 1)? Вижда се, че в ребус 6 мултиплкативните операции са общо 10, а адитивните са само 2. Времето за изпълнение на ребус 5 и при трите алгоритъма е почти най-малкото, а отношението на мултипликативните към адитивните операции е \(6: 8\).

Като графики, времената за изпълнение на трите програми с 10-те ребуса са представени на фиг. 4. Те са построени със системата MATLAB. Забележете, че поради големите разлики в стойностите на трите графики за оста Oy е използвана логаритмична скала.

4. Проект в развитие 4.1. Идея за още един алгоритъм за решаване на MP Алгоритъм D [Вариант на алгоритъм C]

С алгоритъм C се генерират трите множества A, B и C, всяко от които съдържа 3-цифрени числа, цифрите на които са решения съответно на уравнения (1), (2) и (3). Във функцията rowSol те са представени с един двумерен масив.

Нека \(\langle a, b, c\rangle \mathrm{A} \times \mathrm{B} \times \mathrm{C}\) е произволна тройка, която е решение на уравнения (1), (2) и (3), като \(\mathrm{a}=\overline{a_{2} a_{1} a_{0}}, b=\overline{b_{2} b_{1} b_{0}}\) и \(c=\overline{c_{2} c_{1} c_{0}}\). Да означим с X, Y и Z трите множестава, всяко от които съдържа 3-цифрени числа, цифрите на които са решения съответно на уравнения (4), (5) и (6). Тогава задача P1 се свежда до намиране на всички тройки 3-цифрени числа, за които съществуват тройки от 3-цифрени числа \(\langle x, y, z\rangle \mathrm{X} \times \mathrm{Y} \times \mathrm{Z}\) със свойството \(x=\overline{a_{2} b_{2} c_{2}}, y=\overline{a_{1} b_{1} c_{1}}\) и \(z=\overline{a_{0} b_{0} c_{0}}\).

Пример: Ако цифрите на числата \(a=246, b=531\) и \(c=973\) са решения на уравненията (1), (2) и (3), а цифрите на числата \(x=259, y=437\) и \(z=613\) са решения на уравненията (4), (5) и (6), то цифрите на \(a, b\) и \(c\) са решение на \(M P\).

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

Вместо да се съхраняват тройките числа \( \lt x, y, z \gt \mathrm{X} \times \mathrm{Y} \times \mathrm{Z}\), y, z >Î X x Y x Z, могат да се съхраняват тройките, за които цифрите на числото \(x\) ` са последователно първите цифри на \(x, y z\), y z, цифрите на числото \(y\) ` са съответно вторите им цифри, цифрите на числото \(z\) ` са съответно третите им цифри. По този начин след сортиране на множествата \(\mathrm{X}, \mathrm{Y}\) и Z при търсене на тройките числа \( \lt a, b, c \gt \) от \(\mathrm{A} \times \mathrm{B} \times \mathrm{C}\) съответно в множествата \(\mathrm{X}, \mathrm{Y}\) и Z може да се приложи двоично търсене.

Въпрос. Ако \(T(\alpha)\) е времето за изпълнение на програмата, чиито входни данни са 10-те ребуса (табл. 2), реализирана по алгоритм \(\alpha\), кое от следните неравенства е в сила?

a) \(\quad T(D) \lt T(C) \lt T(A) \lt T(B)\)

b) \(\quad T(C) \lt T(D) \lt T(A) \lt T(B)\)

c) \(\quad T(C) \lt T(A) \lt T(D) \lt T(B)\)

d) \(\quad T(C) \lt T(A) \lt T(B) \lt T(D)\)

Проверете твърдението си чрез експеримент.

Въпрос. Пресметнете времената за изпълнение на програмите, написани по алгоритмите \(\mathrm{A}, \mathrm{B}, \mathrm{C}\) и D, които имат за входни данни ребусите от табл.2 и намират само по едно решение.

Задача. Конструирайте нов алгоритъм и напишете съответна програма. Изпълнете я с данните от табл. 2 и сравнете времето й за изпълнение с това на разгледаните програми.

4.2. Един опит за обобщение

Разгледаните алгоритми трудно могат да бъдат директно обобщени и използвани за решаването на ребуси от ред \(n \gt 3\). Числото 3 е силно „вградено“ в структурата и на трите алгоритъма. Но ако по някакъв начин можем да генерираме всичките \(n\)-мерни вектори, чиито компоненти са ненулеви десетични цифри, тогава е възможно да се продължи с идеята от алгоритъм B.

В (Азълов, 1985) и (Азълов и др., 2003) е описан алгоритъм, реализиран с програми на езиците FORTRAN и Pascal, с който се генерирарат \(n\)-мерни вектори, чиито компоненти принадлежат на дадено множество. Алгоритъмът се базира на идеята за конструиране на нова управляваща структура, реализираща \(n\) вложени цикъла, да я наречем \(n\)-цикъл, в тялото на който при всяка поредна итерация се получава следващият \(n\)-мерен вектор. \(N\)-цикълът може да се онагледи чрез обикновен for цикъл, в който управляващата променлива \(x\), началната стойност \(a\), последната стойност \(b\) и стъпката на нарастване \(c\) са едномерни масиви:

Естествено, реализацията на \(n\)-мерния цикъл ще се извърши чрез функция, чийто прототип би могъл да бъде следният:

bool nLoops(int n, int x[], int a[], int b[], int c[]);

Обръщението към функцията nLoops може да се извърши в цикъл:

Така при всяко следващо обръщение към nLoops в тялото на цикъла ще е достъпен следващият по ред \(n\)-мерен вектор, съдържащ се в масива \(x\).

4.3. Една изледователска задача

Нека с \(\mathrm{P} 1[n]\) да означим задачата P1 за ребус от ред \(n \geq 2\). Напишете съответни програми по идеята на алгоритъм \(C\) за решаване на задачите за \(n=2,3\) и 4 и ги изпълнете с входни данни от табл. 2. Нека \(\mathrm{T}(2), \mathrm{T}(3)\), , и \(\mathrm{T}(4)\) са времената за изпълнение на съответните програми.

След като направите съответните експеримети за \(n=2,3\), 3, и 4, формулирайте Вашата хипотеза, отнасяща се до порядъка на времето \(\mathrm{T}(5)\), необходимо за изпълнение на програмата, решаваща задача P1[5] .

4.4. Две развлекателни задачи

Започнахме статията с ребус от ред 3 и едно негово решение. Да я завършим с предложение за намиране на едно решение на ребусите от ред 3 и 4.

Бележка: С програма, написана по алгоритъм C, всички решения на ребуса от фиг. 5 са пресметнати за 536.1 секунди.

ЛИТЕРАТУРА

1. Азълов, П. (1985). ФОРТРАН в примери и задачи. (Математика – извънкласна работа). София: Народна просвета.

2. Азълов, П., Златарова, Ф. & Тодорова, М. (2003). ИНФОРМАТИКА. Профилирана подготовка. София: Просвета.

БЕЛЕЖКИ

1. Standard C++ Library Overview: http://msdn.microsoft.com/en-us/library/4e2ess30.aspx (сайтът е посетен за последен път на 27 ноември 2012)

2. Java \({ }^{\text {TM }}\) Platform, Standard Edition 7: http://docs.oracle.com/javase/7/docs/api/

(сайтът е посетен за последен път на 27 ноември 2012)