В данной статье содержится ряд наблюдений, касающихся проблем алгоритмизации, минимизации ошибок, понимания и изучения чужого кода, а также рассуждения о полном изложении алгоритмов и небольшом эксперименте.
Что я подразумеваю под полным описанием алгоритма и зачем это может быть необходимо?
Без открытия Америки не обойтись: полный алгоритм представляет собой последовательность действий над предметами, выполняемую ручкой и бумагой.А полное описание – это каждый шаг, описанный на естественном языке, возможно, с использованием дополнительных математических обозначений, но только как вспомогательных.
Таким образом, полное описание — это не формула и даже не псевдокод и тем более блок-схема.
Из этого очевидного тезиса следует одна и та же очень простая, но важная вещь — понимание реализации даже достаточно простого алгоритма может быть затруднено его аббревиатурой или краткостью формулы.
В этом отношении мне очень понравилось мнение Херба Уилфа о том, что «формула — это на самом деле алгоритм», перепечатанное в этой статье.
статья Игорь Пак.
Возможно, представление одних и тех же алгоритмов в виде разных формул и наблюдение за нашим собственным восприятием этих представлений может пролить свет на то, почему мы понимаем одни алгоритмы лучше, а другие хуже.
Я несколько раз замечал, как часто алгоритмы переписываются с языка на язык чисто механически.
Наверное, это может быть хорошо в коммерческой разработке, когда времени не так много вникать в каждый шаг, а нужно просто быстро получить результат на нужном языке, но для образовательных целей этот метод не очень подходит. Понаблюдав за собой, я заметил, что бывают ситуации, когда смотришь на чужой код и вроде бы понимаешь алгоритм, знаешь язык, на котором он реализован, но не видишь всех шагов.
Автор продумал алгоритм для себя, максимально сократил его и тем самым фактически скрыл пошаговую реализацию от других программистов, внимание которых зачастую больше сосредоточено на средствах реализации, а все усилия направлены на поиск аналогов этих инструментов, необходимых для перекодирования на известный им язык.
Таким образом, реализация и краткое формальное описание алгоритма иногда выглядят как код, сразу понятный только автору.
Что касается описания алгоритмов на естественном языке, то, вероятно, ключ к сложности иногда кроется в самом языке автора, поскольку при описании каждый опирается на свои знания и понимание терминологии и использует набор и сочетание речевых средств с которым они привыкли работать.
Вывод, который я сделал для себя в результате изучения некоторых алгоритмов и наблюдения за переводом с языка на язык, заключается в том, что восприятие формул и алгоритмов может стать темой целого ряда очень серьезных исследований, включающих разработки из совершенно разных областей человеческой деятельности.
.
Нужны ли нам реализации полных алгоритмов?!
Конечно, реализации, например, полных комбинаторных алгоритмов могут быть во много раз медленнее, запутаннее и некрасивее, чем их сокращенные аналоги.На мой взгляд, подобные пошаговые реализации могут служить инструментом своеобразного реверс-инжиниринга - когда нужно получить не код, механически переписанный с языка на язык, а понимание всех шагов, что, кстати, , в будущем может послужить путем к пониманию всех сокращений и витиеватости в более быстрых и коротких аналогах.
Изменение представления алгоритма комбинации без повторений Ни для кого не секрет, что многие комбинаторные алгоритмы, записанные на бумаге, кажутся довольно простыми.
Например, алгоритм генерации комбинаций без повторов (или комбинаций без повторов - они отличаются хотя бы одним элементом) можно вывести практически сразу, не особо задумываясь, фактически интуитивно.
Правда, выписывая на листке все комбинации от n=5 до k=3, я пару раз допустил одну и ту же ошибку, проигнорировав одно из чисел и получив неправильный результат; это привело меня к мысли, что изложение алгоритма на бумаге должно осуществляться более системно, с максимальной наглядностью, с большим количеством проверок при переходе от одного шага к другому, иначе то, что можно реализовать за несколько минут, может оказаться невозможным.
растянулось на несколько часов или даже дней.
Дальше мой эксперимент - презентация полного алгоритма поиска комбинаций.
Кратко алгоритм формирования комбинаций формулируется следующим образом: «.
в текущей комбинации мы найдем самый правый элемент, еще не достигший своего наибольшего значения; затем мы увеличим его на единицу, а всем последующим элементам присвоим наименьшие значения».
Я не особо разбираюсь ни в описании, ни в реализации, поэтому решил немного все усложнить и добавить несколько дополнительных шагов, чтобы компенсировать свою невнимательность к цифрам и сделать описание более подробным.
Описание
Входные данные представляют собой массив А=123456 (например), отсортировано по возрастанию; Н=6 (количество символов в массиве); скажем так К=3, .Использование этого алгоритма требует больше времени, но хранение дополнительного массива позволяет избежать ошибок внимания и делает более короткие реализации более понятными.Перед входом в цикл входной массив предлагается разделить на два - B и C, B хранит значения от 1 элемента (включительно) до K (включительно) и в C все остальное, т.е.
B[123] и C[ 456].
1) Во внешнем цикле перебирает элемент в позиции K в B, т. е.
B[K], ищет элемент, больший на единицу, в массиве C и производит замену.
Вывод на дисплей.
2) Далее условие - если B[K] равен N - последнему элементу массива, то запускается цикл поиска элемента слева от K, для которого в массиве C есть больший элемент одним.
Если мы достигаем индекса 0 и таких элементов нет, то алгоритм завершается.
3) Если элемент в C найден, то ищется его индекс с целью дальнейшего уменьшения элемента в C на единицу, а элемент в B увеличивается на единицу.
Затем массив B разбивается на два (можно обойтись и без этого, см.
сокращенную версию); перед текущим элементом и после.
Все, что находится после текущего элемента, переносится в массив C. Массив B увеличивается до индекса K в порядке возрастания, а лишние элементы удаляются из массива C. Вложенный цикл завершается.
Операции повторяются еще раз.
В результате, разложив алгоритм на большее количество шагов, я смог практически сразу его закодировать.
Однако я должен вас предупредить, что реализация этого не на бумаге, а на таком языке, как PHP, может показаться очень запутанной.
Но, тем не менее, формально алгоритм работает правильно.
Полный нерекурсивный алгоритм генерации комбинаций без повторения.
PHP
Теги: #Алгоритмы #генерация комбинаций #комбинации #комбинации с повторением #комбинации без повторения #генерация плейсментов с повторением #творческий процесс в IT #Алгоритмы<Эphp $a=array(1,2,3,4,5); $k=3; $n=5; $c=array_splice($a, $k); $b=array_splice($a, 0, $k); $j=$k-1; print_r($b); while (1) {
-
Карта С Проекциями Из Proj4Js На Canvas
19 Oct, 24
