Методи Крістобаля хунти
- Лебедики, - сказав Федір Симеоновіч заклопотано, розібравшись в почерках. - Це ж проблема Бен Бецалеля. Каліостро ж довів, що вона не має рішення.
- Ми самі знаємо, що вона не має рішення, - сказав Хунта, негайно ощетініваясь. - Ми хочемо знати, як її вирішувати.
- Якось дивно ти говориш, Крісто ... Як же шукати рішення, коли його немає? Нісенітниця якась ...
- Вибач, Теодор, але це ти дуже дивно міркуєш. Нісенітниця - шукати рішення, якщо воно і так є. Мова йде про те, як чинити із завданням, яка рішення не має. Це глибоко принципове питання ...
У чому прав і в чому неправий Крістобаль Хозевич? правити
Звичайно ж, з позицій якогось вищого знання Крістобаль Хунта прав: навіщо вирішувати розв'язні завдання, якщо вже відомо, що у неї є рішення? Але не можна забувати, що він - безсмертний маг вищого класу, колишній Великий Інквізитор та інше, та інше. Він уже вміє клацати елементарні завдання, і багато завдань, недоступні для вас, є елементарними для нього. А вам потрібно брати участь в олімпіадах і конкурсах, вчитися, а потім працювати на виробництві, де переважна більшість завдань саме розв'язні (зокрема, на традиційних олімпіадах інших і не дають). Так що знати способи вирішення таких завдань і вміти реалізовувати відповідні алгоритми - найважливіші знання і вміння для тих, хто бажає бути вище «чайника» в інформатиці.
Професіонал часом стикається і з абсолютно іншою ситуацією. Йому ставлять завдання, яка свідомо нерозв'язна. Але її треба вирішувати (це лише один з багатьох подібних випадків в реальному житті: прочитайте книгу [1].
Перший спосіб: заздалегідь зробити все правильно Правити
Припустимо, що вам ставиться завдання побудувати програму, яка буде перевіряти, зациклені чи програми, створювані за допомогою нової системи програмування для якихось приватних додатків (наприклад, нової мови скриптів для собачих нашийників). Тоді потрібно перш за все зрозуміти, якого ж сорту програми будуть писати на даній системі, оскільки, як говорилося в попередній статті, поставлена задача в загальному випадку нерозв'язна. Якщо програми не надто складні, досить всього-на-всього викинути з створюваного міні-мови програмування цикли while і рекурсивні процедури (які, якщо явно не протестувати, системні програмісти заради спільності і крутизни обов'язково вставлять, оскільки «інакше система не буде універсальною»). Тоді будь-яка програма буде закінчувати роботу (просто з побудови не даємо ми їй можливості зациклитися!). Якщо системщики волають, а начальство дивиться на них як на напівбогів, то змусьте їх хоча б видавати для програмістів довгі попередження типу:
А після відповіді Yes на додачу ще (в кращих традиціях ігор, з яких вам хочеться вийти швидше, щоб шеф, або мама, або викладач не застукали, а вам задають купу питань):
І як фінальний акорд щось типу:
Наведене рішення є окремим випадком трьох загальних принципів.
Принцип 1 Правити
Якщо не можна вирішити задачу в повному обсязі, розберіться, що ж насправді потрібно, і вирішите приватну задачу.
Принцип 2 Правити
Якщо щось потрібно гарантувати для вирішення, кращий спосіб - забезпечити це з самого початку, ще в ході побудови програми. Потім навіть перевірити буде важко, а якщо ще до того ж з'ясується, що вимога порушено, то переробляти буде ще важче, ніж писати добре відразу. [2]
Принцип 3 Правити
Якщо вам не вдається заблокувати нерозумне рішення, за допомогою технічних і бюрократичних частковостей зробіть так, щоб користуватися ним було якомога більше огидно. [3]
Цей спосіб вирішення нерозв'язних завдань можна проілюструвати наступним малюнком.
Те, що за парканом, - наші культурні рослини, а зовні все вважається бур'янами і там ми просто не садимо.
Другий спосіб: обмежити завдання Правити
Наведений вище принцип 1 відразу ж призводить до ще одного методу рішення, насправді нерозривно пов'язаного з попереднім, але не що зводиться до нього. Зокрема, якщо ті ж програми для собачих нашийників вже написані, або пишуться закінченими хакерами, яким хоч кіл на голові теши, але від крутизни вони не відмовляться, то залишається подивитися на дану конкретну сукупність програм і будувати алгоритм, який буде працювати саме на ній [4]. Головне, щоб ваш алгоритм успішно шукав помилки в конкретних програмах, а то, що він в загальному випадку не є коректним, варто розглядати як неминуче зло.
Наприклад, якщо ви помічаєте, що програмісти часто опитують один і той же датчик, не провівши повторного вимірювання, то таку помилку можна успішно виловлювати і повідомляти про неї, скажімо, так:
Схематично можна зобразити такий спосіб роботи на наступному малюнку. Те, що за колючим дротом, за визначенням вважається поганим і відстрілюється.
Третій спосіб: працювати неправильно Правити
Оскільки нездійсненне завдання все одно правильно не вирішиш, то потрібно проаналізувати, які ж помилки шкідливіше, і, якщо вже робити, то нешкідливі. У попередніх розділах передбачалося, що нешкідливіше годі й шукати зациклення, ніж знайти зациклення в працюючій програмі. Але, часом, краще видати зайве попередження, ніж пропустити свідомо поганий алгоритм. Далі, часом можна допускати помилки і в дві сторони, якщо ціна помилки не дуже висока і в більшості випадків програма все одно працює правильно.
Схематично можна зобразити такий спосіб роботи на наступному малюнку. Тут межа проведена простіше, але біля її можуть бути помилки в дві сторони.
Якщо цикл зустрічається всередині рекурсії, або рекурсія всередині циклу, то процедура написана некоректно.
У переважній більшості випадків це правило дійсно вказувало на погано продумані процедури, які, навіть якщо і працювали для зовсім простих вхідних даних, розвалювалися на трохи більш складних. Але іноді такий прийом виправданий (особисто я раджу вам таким прийомом не користуватися, якщо хочеться схрестити рекурсию і цикл, значить, майже напевно ви погано продумали структури даних або алгоритм).
Четвертий спосіб: працювати навмання Правити
Найпоширеніші програми перевірки програм намагаються прогнати програму на безлічі підібраних тестів, які повинні начебто забезпечити проходження всіх можливих шляхів виконання програми. Але можливих шляхів занадто багато, тому тести підбираються так, щоб пройти різні шляхи, і частіше за все випадковим чином.
Аналогічно, один із способів ручного тестування програми - генерація випадкових даних і перевірка того, як програма буде себе вести на них.
Насправді ці прийоми мають під собою теоретичну підоснову, яку вперше помітив Трахтенброт в уже згадуваному доповіді. Часто нерозв'язна задача перетворюється в досить просту, якщо ми дозволимо помилятися з малою вірогідністю (в принципі навіть зі як завгодно малої).
В стратегічних шахах два шахіста спілкуються через суддю. Суддя єдиний, хто знає повне становище на дошці. Кожен гравець знає лише співвідношення сил і положення своїх фігур.
Суддя повідомляє гравцям мінімально необхідну інформацію про хід. Він вимовляє приблизно таку послідовність фраз у відповідь на спроби одного з гравців зробити хід (чорні це були або білі, здогадайтеся самі):
- Хід зроблений. Взято тура на поле e1. Пішак перетворилася в ферзя. Шах.
Перший можливий хід вважається зробленим. Причина, по якій неможливий хід (відкривається шах, перекрита лінія, король пішов під удар тощо) не пояснюється. Стратегічні шахи породжують ряд цікавих завдань, пару з яких (одна з них простіша, друга - виключно складна) наведемо зараз:
Король-всезнайка проти ферзя
Король знає все, а король і ферзь грають проти нього за правилами стратегічних шахів. Дати мат.
Король-всезнайка проти тури
Король знає все, а король і тура грають проти нього за правилами стратегічних шахів. Дати мат.
У другій задачі досить просто дати алгоритм і скласти програму, яка буде випадково матовать короля таким чином, що з імовірністю 1 в кінці кінців його заматует (але теоретично король, якщо він не тільки всезнайка, але ще і віщун, що знає майбутнє, може нескінченно уникати мату). Є й алгоритм, матующій з гарантією, але він набагато складніше і в розробці, і в реалізації.
^ Даний принцип не можна застосовувати на практиці традиційних олімпіад з програмування. Там завдання обов'язково потрібно вирішувати в повному обсязі, так, щоб вона працювала при всіх значеннях допустимих параметрів. Це лише один з багатьох випадків, коли практика олімпіад призводить до розвитку навичок, які не просто даремні, а прямо шкідливі для подальшої практичної діяльності фахівця.
^ Це насправді загальний принцип, який можна застосовувати не лише в програмуванні. Так само варто надходити і в житті. Варто пам'ятати, що «розумна людина - той, хто з честю виходить з такої ситуації, в яку мудрий не влучає».
^ Останній принцип (з заміною «нерозумне» на «непотрібне мені, коханому») успішно використовують бюрократи в боротьбі проти всього найкращого; іноді потрібно переймати їх методи, оскільки лізти в лобову атаку - майже завжди найгірше рішення.
^ Хоч вони і круті, але зазвичай досить мало винахідливі насправді, а головне, як було сказано в класичному російською водевілі, такі типи зазвичай помиляються «Кажінний раз на ефтом самому місці».