Какой алгоритм научил вас больше всего о программировании или конкретной языковой функции?
У всех нас были моменты, когда мы внезапно знаем, просто знаем, что мы выучили важный урок для будущего, основанный на окончательном понимании алгоритма, написанного программистом, на пару шагов вверх по эволюционной лестнице. Чьи идеи и код наделили вас волшебным прикосновением?
"Итерировать - это человек, чтобы воздать божественное", - цитируется в 1989 году в колледже.
P.S. Отправленный Woodgnome, ожидая приглашения присоединиться
Общие алгоритмы:
Числовое значение:
Связанная с теорией чисел:
Мне также понравилось изучать квантовые вычисления (Shor и Deutsch- Josza): это учит вас думать из коробки.
Как вы можете видеть, я немного склонен к математическим алгоритмам:)
Алгоритм кратчайших траекторий всех пар Floyd-Warshall
procedure FloydWarshall ()
for k := 1 to n
for i := 1 to n
for j := 1 to n
path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );
Вот почему это круто: когда вы впервые узнаете о проблеме кратчайшего пути в своем курсе теории графов, вы, вероятно, начинаете с алгоритма Дейкстры, который решает одиночный -строчный кратчайший путь. Сначала это довольно сложно, но потом вы преодолеваете это, и вы полностью это понимаете.
Затем учитель говорит: "Теперь мы хотим решить ту же проблему, но для ВСЕ источников". Вы думаете себе: "О боже, это будет намного сложнее! Это будет по крайней мере в N раз сложнее, чем алгоритм Дейкстры!!!".
Тогда учитель дает вам Флойда-Варшалла. И ваш ум взрывается. Затем вы начинаете разрываться на том, насколько красивым является алгоритм. Это всего лишь трижды вложенная петля. Он использует простой массив для своей структуры данных.
Самая открытая для меня часть - это следующая реализация: скажем, у вас есть решение проблемы A. Тогда у вас есть большая "суперзадача" B, которая содержит проблему A. Решение проблемы B может быть на самом деле проще, чем решение задачи А.
Quicksort. Он показал мне, что рекурсия может быть мощной и полезной.
Это может показаться тривиальным, но это было откровение для меня в то время. Я был в своем первом классе программирования (VB6), и профессор только что научил нас случайным числам, и он дал следующие инструкции: "Создайте виртуальную лотерейную машину. Представьте себе стеклянный шар, полный 100 шаров пинг-понга с отметкой от 0 до 99. Выберите их случайным образом и покажите их номер до тех пор, пока все они не будут выбраны, никаких дубликатов."
Все остальные написали свою программу следующим образом: выберите мяч, поместите его номер в "уже выбранный список", а затем выберите другой мяч. Проверьте, не выбран ли его уже выбранный, если он выбрал другой шар, если не поместить его номер в "уже выбранный список" и т.д....
Конечно, к концу они делали сотни сравнений, чтобы найти несколько шаров, которые еще не были выбраны. Это было похоже на то, чтобы отбросить мячи обратно в банку после их выбора. Мое откровение заключалось в том, чтобы выбросить мячи после сбора.
Я знаю, что это звучит ошеломляюще, но это был момент, когда "программирующий переключатель" перевернулся в моей голове. Это был момент, когда программирование исходило от попыток выучить странный иностранный язык, пытаясь понять приятную загадку. И как только я сделал эту психологическую связь между программированием и развлечениями, мне действительно не мешало.
Кодирование Хаффмана было бы моим, я изначально сделал свою собственную тупую версию, минимизируя количество бит для кодирования текста от 8 до меньшего, но не думал о переменном количестве бит в зависимости от частоты. Затем я нашел кодировку хаффмана, описанную в статье в журнале, и она открыла множество новых возможностей.
алгоритм рисования линий Bresenham заинтересовал меня графическим рендерингом в реальном времени. Это можно использовать для визуализации заполненных многоугольников, например треугольников, для таких вещей, как рендеринг 3D-модели.
Рекурсивный анализ спуска - Я помню, что очень впечатлен тем, как такой простой код может сделать что-то настолько сложное.
Quicksort в Haskell:
qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
Хотя я не мог писать Haskell в то время, я понял этот код и с ним рекурсия и алгоритм быстрой сортировки. Он просто сделал клик и там он был...
Итерационный алгоритм для Фибоначчи, потому что для меня это прибило тот факт, что самый элегантный код (в данном случае, рекурсивная версия) не обязательно является наиболее эффективным.
Чтобы разработать. Подход "fib (10) = fib (9) + fib (8) означает, что fib (9) будет оцениваться как fib (8) + fib (7). Таким образом, оценка fib (8) (а затем fib7, fib6) будет оцениваться дважды.
Итеративный метод, (curr = prev1 + prev2 в forloop), не генерирует этот путь, и не занимает столько памяти, поскольку он содержит только 3 переходные переменные вместо n кадров в стеке рекурсии.
Я стараюсь стремиться к простому, элегантному коду, когда я программирую, но это алгоритм, который помог мне понять, что это не конец для всех для написания хорошего программного обеспечения, и что в конечном итоге конец пользователям все равно, как выглядит ваш код.
Minimax научил меня, что шахматные программы не умны, они могут просто думать, что впереди больше, чем вы можете.
Мне почему-то нравится преобразование Шварца
@sorted = map { $_->[0] }
sort { $a->[1] cmp $b->[1] }
map { [$_, foo($_)] }
@unsorted;
Где foo ($) представляет собой выражение с интенсивным вычислением, которое принимает $(каждый элемент списка в свою очередь) и выдает соответствующее значение, которое должно сравниваться в нем.
Я не знаю, соответствует ли это алгоритму, или просто классическому взлому. В любом случае это помогло мне начать думать за пределами коробки.
Смените 2 целых числа без использования промежуточной переменной (в С++)
void InPlaceSwap (int& a, int &b) {
a ^= b;
b ^= a;
a ^= b;
}
Quicksort: До тех пор, пока я не поступил в колледж, я никогда не задавался вопросом, был ли самый грубый способ сортировки грубой силы Bubble Sort. Это казалось интуитивно очевидным. Но, сталкиваясь с неочевидными решениями, такими как Quicksort, научил меня смотреть на очевидные решения, чтобы увидеть, доступно ли что-то лучше.
Для меня это алгоритм слабых-heapsort, потому что он показывает (1), насколько разумная выбранная структура данных (и алгоритмы, работающие над ней) могут влиять на производительность, и (2) что захватывающие вещи могут быть обнаружены даже в старых, хорошо известные вещи. (слабый-heapsort - лучший вариант всех типов кучи, который был доказано спустя восемь лет.)
Это медленный:)
Я много узнал о C и компьютерах, понимая Duffs Device и XOR свопы
EDIT:
@Джейсон Z, что мой XOR своп:) круто, не так ли.
У меня нет фаворита - есть так много красивых, чтобы выбрать, но я всегда был интригующим, это Bailey -Borwein-Plouffe (BBP), которая позволяет вам вычислить произвольную цифру pi без знания предшествующих цифр.
RSA познакомил меня с миром модульной арифметики, который можно использовать для решить a неожиданно номер of интересно проблемы!
Не многому меня научил, но Johnson-Trotter Algorithm никогда не сбивает меня с ума.
Двоичные диаграммы решений, хотя формально не алгоритм, а структура данных, приводят к изящным и минимальным решениям для различных видов (логических) логических задач, Они были изобретены и разработаны для минимизации количества ворот в чип-дизайне и могут рассматриваться как одна из основ кремниевой революции. Полученные алгоритмы удивительно просты.
Что они научили меня:
Для меня простой обмен в Kelly and Pohl A Book на C, чтобы продемонстрировать call-by-reference, перевернул меня, когда я впервые увидел его. Я посмотрел на это, и указатели встали на свои места. Verbatim.,.
void swap(int *p, int *q)
{
int temp;
temp = *p;
*p = *q;
*q = temp;
}
Башни ханойского алгоритма - один из самых красивых алгоритмов. Он показывает, как вы можете использовать рекурсию для решения проблемы гораздо более элегантным способом, чем итеративный метод.
В качестве альтернативы, алгоритм рекурсии для рядов Фибоначчи и вычислительных степеней числа демонстрирует обратную ситуацию рекурсивного алгоритма, используемого для рекурсии, а не для обеспечения хорошего значения.
По какой-то причине Bubble Sort всегда выделялся мне. Не потому, что это элегантно или хорошо, потому что у него было/есть тупой имя, я полагаю.
Итерационный алгоритм для Фибоначчи, потому что для меня это прибило тот факт, что самый элегантный код (в данном случае, рекурсивная версия) не обязательно является наиболее эффективным.
Итеративный метод, (curr = prev1 + prev2 в forloop), не генерирует этот путь, и не занимает столько памяти, поскольку он содержит только 3 переходные переменные вместо n кадров в стеке рекурсии.
Вы знаете, что фибоначчи имеет закрытое решение формы, которое позволяет прямое вычисление результата с фиксированным числом шагов, правильно? А именно: (phi n - (1 - phi) n)/sqrt (5). Мне всегда кажется замечательным, что это должно дать целое число, но оно есть.
phi - это золотое соотношение, конечно; (1 + sqrt (5))/2.
@Кришна Кумар
Побитовое решение еще более забавно, чем рекурсивное решение.
Алгоритм, который генерирует список простых чисел, сравнивая каждое число с текущим списком простых чисел, добавляя его, если он не найден, и возвращает список простых чисел в конце. Разумный изгиб несколькими способами, не последним из которых является идея использования частично завершенного вывода в качестве основного критерия поиска.
Сохранение двух указателей в одном слове для дважды связанного списка упростило мой урок, который вы можете делать очень плохо в C действительно (с которым у консервативного GC будет много проблем).
Самым гордым я был решением, написав что-то очень похожее на пакет DisplayTag. Это научило меня много о разработке кода, ремонтопригодности и повторном использовании. Я написал это задолго до DisplayTag, и он был погружен в соглашение NDA, поэтому я не мог его открыть, но я все еще могу говорить о том, что на собеседовании.
Не мой любимый, но Алгоритм Миллера Рабина для проверки первобытности показал мне, что, будучи правым почти все время, достаточно хорошо почти все время. (т.е. не доверяйте вероятностному алгоритму только потому, что он имеет вероятность ошибиться.)
Map/Reduce. Две простые концепции, которые сочетаются друг с другом, чтобы облегчить рассылку задач обработки данных.
Oh... и это только основа массивно-параллельного индексирования: