начало http://www.proza.ru/2015/07/16/1738
назад http://www.proza.ru/2015/07/16/1738
Доказательная алгоритмика
Глава 2
Получив в предыдущей главе опыт составления (и доказательства) алгоритмов на примере простой (и усложнённой) задач, мы теперь, пожалуй, готовы к решению еще более сложной алгоритмической задачи, а именно задачи3:
найти (=вывести) идентификатор минимального числа (или чисел) из произвольного количества чисел.
Интуитивно понятно, что должны делать что-то похожее на то, что делали в предыдущих алгоритмах, но много раз. А сравнение алгоритма
If a1<a2 then write(‘a1’)
ElseIf a1>a2 then write(‘a2’)
Else write(‘a1 and a2’)
И алгоритма
If a1<a2 then
If a1<a3 then write(‘a1’)
ElseIf a1 >a3 then write(‘a3’)
else write(‘a1 and a3’)
Else If a1>a2 then
If a2<a3 then write(‘a2’)
ElseIf a2>a3 write(‘a3’)
else write(‘a2 and a3’)
else
If a1<a3 then write(‘a1 and a2’)
elseIf a1>a3 then write(‘a3’)
else write(‘a1 and a2 and a3’)
Приводит еще и к гиптотезе о том, что эти алгоритмы имеют между собой фрактальную связь, а это значит, что все последующие алгоритмы (для всё более увеличивающегося количества чисел) будут не в разы, а в разы в квадрате сложнее, чем предыдущие алгоритмы. А поэтому простой способ записи алгоритма (при котором запись алгоритма совпадает с записью процесса его выполнения) нам будет непригоден.
Хотя уже и при применении управляющей структуры «условие» такого совпадения уже нет (ибо при этом ход выполнения содержит меньшее количество шагов, чем описано в самом алгоритме. То есть алгоритм выполняется как бы частично.) Но нам нужно теперь другое: чтобы запись алгоритма была бы более короткой чем запись процесса его выполения. Такую возможность даёт управляющая структура «цикл». Отсюда вывод: в алгоритме для задачи3 нам предстоит применение цикла.
Всё вышесказанное приводит к следующему алгоритму:
N=count(a)
For k=1 to n do
F=1
For i=1 to k-1, k+1 to n do
If a(k)<=a(i) then
Else
F=0
Break
End if
Endfor
If f=1 then add(b,k)
Endfor
Рис. 4а. Алгоритм №1 для задачи3
(здесь – новведение: count(a) – количество элементов массива a (для динамического массива - просто незаменимая вещь)
А также f – это флаг того, что в цикле по i не случилось ни одного события
a(k)>a(i))
Идея этого алгоритма такова:
Поскольку доказано (в главе 1), что элемент, имеющий минимальное значение для данного множества элементов проходит проверку условия a(k)<a(i) or a(k)=a(i) в отношении любого элемента множества, то, подвергнув такой проверке по очереди все элементы множества и не обнаружив при этом (для данного элемента a(k)) ни одного случая a(k)>a(i), мы заносим данный элемент в множество b элементов множества a, имеющих минимальное значение для данного множества элементов. В противном случае на данном элементе a(k) мы выходим из цикла по i.
Этот алгоритм, конечно, проще, чем предполагалось. Но, тем не менее, не идеал. Поэтому, в порядке подготовки к решению задачи3, решим еще одну задачу, попроще, а именно задачу4:
Найти минимальное значение элементов множества чисел с произвольным количеством элементов.
В связи с данной формулировкой приходит в голову следующая алгоритмическая идея: предположим, что минимальное значение имеет a(1). Запомним значение a(1) в переменной min. Тогда, сравнивая значение переменной min с последующими элементами множества a(k) и получая результат min<a(k) or min=a(k), мы будем подтвердждать текущую гипотезу об элементе, имеющем минимальное значение. Но, если получен результат min>a(k), текущая гипотеза об элементе, имеющем минимальное значение, отвергается и мы переходим к новой текущей гипотезе: минимальное значение имеет элемент a(k) и запоминаем значение a(k) в переменной min. Таким образом, проведя сравнение значения min со значениями всех элементов множества, мы придём к ситуации, когда значение min действительно будет соответствовать минимальному значению элементов множества чисел. А поэтому на этом выполнение алгоритма завершается.
Если эту идею записать на псевдокоде, то получится следующее:
Min=a(1)
For k=2 to n do
If min<a(k) or min=a(k) then
elseIf min>a(k) then min=a(k)
endif
endfor
Рис.5. Алгоритм для задачи4
Нетрудно понять, что алгоритмическая идея, реализованная в алгоритме, и является доказательством этого алгоритма. (или у вас есть сомнения? Тогда укажу вам на следующее: в саму идею алгоритма уже заложен метод доказательства: предположим, что А, тогда как мы это проверим? И.т.д.)
А поскольку условия min<a(k) or min=a(k) и min>a(k) образуют полную систему событий и при выполнении 1-го условия ничего делать не надо, алгоритм упрощается до следующего:
Min=a(1)
For k=2 to n do
If min>a(k) then min=a(k)
endif
endfor
Рис.6. Упрощенный алгоритм для задачи4
завершающие скобки endif и endfor также могут быть опущены, поскольку тела цикла условия не явлеются сложными, поэтому, с точки зрения синтаксиса, завершающие скобки не нужны. (точнее можно обойтись без них) В итоге получаем:
Min=a(1)
For k=2 to n do
If min>a(k) then min=a(k)
Рис.7. Упрощенный с точки зрения синтаксиса алгоритм для задачи4
Теперь, будучи вдохновленными успешным решением (и доказательством решения) этой вспомогательной задачи, мы можем приступить к решению собственно задачи3. В связи с чем возникает идея: пользуясь алгоритмом для задачи4, найдём минимальное значение элементов множества и сохраним его в переменной min. Теперь, сравнивая значение min со значениями всех по очереди (то есть в соответствии с некоторым правилом обхода множества a) элементов множества a и получив результат min=a(k), мы придём к выводу, что элемент a(k) имеет минимальное значение и, следовательно, нужно индекс элемента a(k) занести в список искомых (согласно условию задачи) элементов b(), что и сделаем: add(b,k)
Таким образом, проведя сравнение значения min со значениями всех элементов множества, мы придём к ситуации, когда в списке b будут находиться индексы всех элементов множества a, имеющие минимальное значение элементов множества a. Следовательно, выполнение алгоритма на этом завершается.
Вот как реализация этой а-идеи записывается на псевдокоде:
Min=a(1)
N= count(a)
For k=2 to n do
If min>a(k) then min=a(k)
For k=1 to n do
If a(k)=min then add(b,k)
(здесь – новведение: count(a) – количество элементов массива a (для динамического массива просто незаменимая вещь))
Рис.8. Алгоритм для задачи 3
Не правда ли, более чем изящное решение задачи, первоначально казавшейся суперсложной! И за счёт чего же оно получено? За счёт того, что мы ввели промежуточное (для задачи) понятие: минимальное значение элементов массива, и реализовали его в виде (вспомогательного) алгоритма. Это примерно аналогично тому, когда математики, желая доказать теорему, сначала доказывают лемму (иногда и не одну) Или тому, когда при решении геометрической задачи, мы делаем вспомогательные построения.
Что же касается доказательства этого алгоритма, то оно, понятно, тоже совпадает с алгоритмической идеей алгоритма.
вперёд http://www.proza.ru/2015/07/21/1600