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

этапы создания алгоритмов, научиться осуществлять проверку правильности и эффективности созданных

алгоритмов.
Задания для самостоятельной подготовки.
Познакомится с основными понятиями, связанными с алгоритмами.
Изучить различные приемы решения алгоритмических задач.

ее работы и представления этого алгоритма в виде программы.

Создание алгоритма — это, как правило, наиболее сложный этап в процессе разработки программного обеспечения. В конце концов, создать алгоритм означает найти метод решения задачи, в решении которой и состоит назначение этого алгоритма. Поэтому, чтобы понять, как создаются алгоритмы, необходимо понять процесс решения задач.

не являются аспектами, специфическими только для компьютерных наук. Напротив, это

важно практически для любой области науки. Решение задач является скорее искусством, чем наукой. Доказательством этого может служить тот факт, что представленные ниже, весьма расплывчато определенные фазы решения задач, предложенные математиком Дж. Полиа в 1945 году, остаются теми основными принципами, на которых и сегодня базируется обучение навыкам решения задач.
Фаза 1. Понять существо задачи.
Фаза 2. Разработать план решения задачи.
Фаза 3. Выполнить план.
Фаза 4. Оценить точность решения, а также его потенциал в качестве
средства для решения других задач.
Применительно к процессу разработки программ эти фазы выглядят следующим образом:
Фаза 1. Понять существо задачи.
Фаза 2. Предложить идею, какая алгоритмическая процедура позволила бы
решить задачу.
Фаза 3. Сформулировать алгоритм и представить его в виде программы.
Фаза 4. Оценить точность программы и ее потенциал в качестве средства для
решения других задач.

фазы не являются этапами, которым надо следовать при решении задачи.

Скорее это те фазы, которые должны быть когда-либо выполнены в процессе ее решения. Следовательно, настаивать на том, что нужно вначале полностью осознать задачу, прежде чем предлагать какое-либо ее решение, — это чистый идеализм.
В качестве примера рассмотрим следующую задачу:
Предположим, что некто А хочет определить возраст трех детей некоего В. Этот В сообщает А, что произведение возрастов его детей равно 36. Обдумав эту подсказку, А отвечает, что необходима еще подсказка, и В сообщает ему сумму возрастов его детей. Затем А отвечает, что требуется еще подсказка, и В говорит ему, что старший из детей играет на пианино. Услышав эту подсказку, А сообщает В возраст всех трех его детей. Сколько лет детям?

Это означает, что искомые значения образуют одну из троек, перечисленных

на рисунке 1, а. Следующая подсказка указывала сумму искомых значений. Нам неизвестно, чему именно равна эта сумма, но мы знаем, что этой информации оказалось недостаточно, чтобы А смог выбрать правильную тройку. Следовательно, искомая тройка должна быть одной из тех, которые имеют одинаковые суммы в списке на рисунке 1, б. Таких троек на рисунке две: (1, 6, 6) и (2, 2, 9); сумма членов каждой из них равна 13. Это та информация, которая была известна А на момент, когда он получил последнюю подсказку. Именно на данном этапе мы осознаем важность последней подсказки. Собственно умение играть на пианино не имеет никакого значения, важен тот факт, что в семье есть старший ребенок. Это позволяет отбросить тройку (1,6,6) и заключить, что одному ребенку 9 лет, а двум — по 2 года.







Рисунок 1 – Иллюстрация к задаче о трех детях: а – тройки чисел, произведение которых равно 36; б – суммы троек чисел из части (а)

шаг и занять оптимальную позицию, — совсем не то же

самое, что сказать, как это сделать. Первоначальный прорыв, а затем осознание того, как закрепить полученный успех, чтобы суметь найти окончательное решение задачи, потребуют значительных усилий от того, кто ее решает. Однако существует несколько общих подходов, предложенных математиком Полиа и другими исследователями, подсказывающими, как можно осуществить этот первоначальный прорыв

том, чтобы работать с задачей в обратном порядке. Например, если

задача заключается в том, чтобы найти способ получения определенного конечного результата из заданного начального, можно начать поиск с конечного результата и попытаться пройти путь к заданному начальному. Этот подход будет полезен, если потребуется найти алгоритм складывания бумажной птички, например. Логично начать с попытки развернуть сложенную птичку с целью понять, как она была сделана.

в поиске связанных с ней проблем, которые или легче решаются,

или уже были решены раньше. Позже предпринимается попытка применить способ их решения к данной задаче. Этот метод особенно важен в контексте разработки программ. Часто при разработке программы основная трудность заключается в создании общего алгоритма для решения всех разновидностей данной задачи. Другими словами, если нам необходимо разработать программу для упорядочения списка имен в алфавитном порядке, наша задача не сводится к сортировке отдельного списка, а заключается в нахождении алгоритма, пригодного для сортировки любого списка имен.

ряд подзадач. Идея заключается в том, что при разбиении исходной

задачи на подзадачи появляется возможность найти общее решение как последовательность этапов, на каждом из которых решается задача, более простая по сравнению с исходной. Поэтапное уточнение подразумевает также, что каждый из этапов, в свою очередь, можно разбить на меньшие, а те — на еще меньшие, так что в конце концов вся задача сводится к набору легко разрешимых подзадач.
Решениям, полученным с помощью метода поэтапного уточнения, свойственна естественная модульная структура. Именно в этом кроется основная причина популярности этого метода при разработке алгоритмов. Если алгоритм имеет естественную модульную структуру, то он легко реализуется в модульном представлении, способствующем созданию удобных в сопровождении программ.

небольшая: в ней может поместиться крестьянин, а с ним или

только коза, или только волк, или только капуста. Но если оставить волка с козой, то волк сьест козу, а если оставить козу с капустой, то коза сьест капусту. Как перевез свой груз крестьянин?
Имеется две кучки спичек. В первой 7 спичек, во второй - 5. За один ход разрешается взять любое количество спичек, но из одной кучки. Проигрывает тот, кому нечего брать. Кто выигрывает при правильной игре - начинающий или его партнер? И как для этого ему надо играть? 
На сковороде могут одновременно жариться две котлеты. Каждую котлету нужно обжаривать с двух сторон, при этом на обжаривание ее с одной стороны требуется 2 мин. Голодный студент мечтает побыстрее поджарить три котлеты. Какое наименьшее время ему потребуется? 
Два игрока кладут по очереди пятаки на круглый стол так, чтобы пятаки не накладывались друг на друга. Проигрывает тот, кто не сможет положить пятака. Кто выигрывает при правильной игре и как он должен для этого играть?

стола. Вы хотите пеpевеpнуть их в одну стоpону: или все

ввеpх или все вниз. Вы можете взять любые два стакана, и должны пеpевеpнуть один или два из них. Есть два условия: у вас завязаны глаза, и стол повоpачивается на произвольное число оборотов каждый pаз, когда вы дотpагиваетесь до стаканов. Так что вы будете делать? 
Семья (папа, мама, сын и бабушка) ночью подошла к мосту, способному выдержать только двух человек одновременно. По мосту можно двигаться только с фонариком. Известно, что папа может перейти мост в одну сторону за минуту, мама - за две, сын - за пять и бабушка - за десять минут. Фонарик у них один. Светить издали нельзя. Носить друг друга на руках тоже. Если по мосту идут двое, время перехода определяется наиболее медлительным членом семьи. Как семье переправиться за 17 минут?
Три актера готовятся к спектаклю. С ними работают два опытных гримера. Каждый актер должен быть накрашен и причесан. Макияж у каждого актера продолжается полчаса, а причесывание только 10 минут. Как быстро три актера смогут подготовиться к выходу на сцену?

так: За один ход ты берешь одну монету, переносишь ее через

две соседние монеты (монеты, а не стопки!) и кладешь на третью. За четыре хода должны получиться четыре стопки по две монеты в каждой.



Трое учеников пошли на рыбалку, взяв с собой лодку, выдерживающую нагрузку до 100 кг. Как перебраться ученикам с берега реки на остров, если их массы равны 40 кг, 50 кг, 70 кг? 
На столе лежат 37 спичек. Каждому из двух игроков разрешается по очереди брать не более 5 спичек. Выигрывает тот, кто возьмет последнюю. Кто выигрывает при правильной стратегии - начинающий игру или второй игрок? Какова выигрышная стратегия?
Три миссионера и три каннибала должны пересечь реку в лодке, в которой могут поместиться только двое. Миссионеры должны соблюдать осторожность, чтобы каннибалы не получили на каком-либо берегу численное преимущество. Как переплыть реку? 

нет мостов, и ни один солдат не пожелал переплывать реку

вплавь. Тут командир увидел лодку, в которой сидели два мальчика. Лодка могла удержать либо двоих мальчиков, либо одного солдата. Как командир переправил солдат на другой берег, используя лодку?
Вам нужно переправить через реку с помощью одного плота семью (мать, отца, 2-х дочерей и 2-х сыновей) и полицейского с заключенным. Правила:
На плоту могут одновременно перемещаться максимум 2 человека.
Папе не разрешается находиться с дочерьми без присутствия матери.
Маме не разрешается находиться с сыновьями без присутствия отца.
Заключённого нельзя оставлять без полицейского ни с одним из членов семьи.
Управлять плотом могут только полицейский и родители. 
Трём хирургам необходимо последовательно прооперировать в полевых условиях больного, страдающего заразным заболеванием. Сами хирурги тоже больны, причём все - разными болезнями. В распоряжении хирургов есть лишь две пары стерильных перчаток. Подскажите план операции, после которой ни хирурги, ни больной не заразятся друг от друга. (Помогать друг другу во время операций хирурги не должны. Оперировать одной рукой нельзя.) 

 

- 3000 бананов. Но вот незадача - ближайшее место, где

их можно продать, находится за 1000 км. За один раз верблюд может унести не более 1000 бананов, при этом за каждый километр пути он съедает 1 банан. Какое максимальное количество бананов может продать верблюд?
Четыре шахтера, которые имеют один фонарь, должны пройти через шахту. Одновременно по шахте могут двигаться не больше двух человек, и каждый шахтер, двигаясь в шахте, должен иметь фонарь. Шахтеры, имена которых Эндрю, Блэйк, Джонсон и Келли, могут пройти шахту за одну, две, три и четыре минуты соответственно. Когда два шахтера идут вместе, они движутся со скоростью более медленного из них. Каким образом шахтеры могут пройти через шахту за 15 минут? После того как вы решите задачу, объясните, с чего вы начали решение.
Допустим, у нас есть большой и маленький стаканчики для вина. Сначала наполним вином маленький стаканчик и перельем его в большой стакан. Затем наполним водой маленький стакан, перельем некоторое количество воды в большой стакан и смешаем его с вином. Теперь будем переливать смесь обратно в маленький стакан, пока он не наполнится. Чего теперь больше в маленьком стакане — воды в вине или вина в воде?

высокой башни. Они весили 195, 105 и 90 фунтов соответственно.

Еду им поднимали в двух корзинах, прикрепленных к концам длинного каната. Канат был перекинут через балку, вбитую под самой крышей. Получалось так, что, когда одна корзина находилась на земле, вторая находилась на уровне оконца в камере пленников. Эти корзины оставались единственной надеждой на спасение. Естественно, как только одна корзина становилась тяжелее другой она опускалась. Однако если разница в весе превышает 15 фунтов, корзина стремительно неслась вниз. Единственное что помогло бы пленникам бежать из плена, было находившееся в камере пушечное ядро весом 75 фунтов - его можно было попытаться использовать как противовес. Как пленникам удалось бежать? 
Две пчелы, живут в разных ульях, но они встретились и полюбили друг друга. Однажды безветренным весенним утром они одновременно вылетели из своих ульев, чтобы слетать друг к другу в гости. В 50-ти метрах от ближайшего улья они встретились, но не заметили друг друга и полетели дальше. Прибыв к месту своего назначения, они потратили одинаковое время, чтобы выяснить, что того, к кому они прилетели, нет дома, и повернуть назад. На обратном пути они встретились в точке, находящейся на расстоянии 20 метров от ближайшего улья. На этот раз они увидели друг друга и устроили пикник, прежде чем возвратиться домой. На каком расстоянии друг от друга расположены их улья?

кучки: 11, 7 и 6 яблок соответственно, но они хотят

поделить их поровну. Один из этих второклассников, хитрый математик, предложил двум другим такое пари: - Вы должны будете уравнять количество яблок в кучках, но строго по моей системе: из одной кучки берёте столько яблок, сколько их в той кучке, куда вы добавлять собираетесь. Но сделать это вы должны строго за 3 перекладывания. Сможете - все яблоки ваши, нет - они мои.  - Давай! - согласились двое. Подумали с минутку и сумели так сделать. И вот они, довольно хрумкая яблоками, утопали от вредного математика. А вы бы смогли так сделать?

женами к берегу реки, нашли там лодку, в которую не

могло вмещаться более двух человек. Как им переплыть через реку так, чтобы ни одна жена не переезжала с чужим мужем и ни оставалась одна на берегу?
  Обозначим пары через Аа, Бб, Вв (маленькими буквами обозначим женщин). Вот схема перевозок, реализующая нужную переправу за 11 рейсов: (стрелки указывают направление движения лодки).

л. Необходимо составить алгоритм, с помощью которого, пользуясь только этими

двумя кувшинами, можно набрать 7 л воды.
Можно предположить, что кувшин емкостью 3 л необходимо ис­пользовать для того, чтобы отлить в него 1 л из полного кувшина емкостью 8 л. Таким образом, решение задачи сводится к поиску возможно­сти поместить, например, 2 л воды в трехлитровый кувшин, затем на­полнить восьмилитровый и перелить из него воду в трехлитровый кувшин, в котором до полного заполнения не хватает ровно I л. Задача реализуется следующим линейным алгоритмом (А — количество воды в трехлитровом кувшине, В — количество воды в восьмилитровом кув­шине):

работы;
описание хода выполнения работы;
результат выполнения работы;
ответы на контрольные вопросы;
выводы о

проделанной работе.

процессе решения задачи.
Являются ли эти фазы этапами, которым нужно непременно

следовать при решении задачи?
Что понимали под понятием алгоритм?
В чем состоит различие между численны­ми алгоритмами и логическими алгоритмами?
Перечислите свойства алгоритмов.
Какова важная особенность алгоритмов?
С помощью чего реализуется цикл со счетчиком?
На какие этапы может разбиваться процесс разработки сложного алгоритма и как они называются?