Ваш любимый алгоритм и урок, которым он учил вас

Ответ 1

"Итерировать - это человек, чтобы воздать божественное", - цитируется в 1989 году в колледже.

P.S. Отправленный Woodgnome, ожидая приглашения присоединиться

Ответ 2

Общие алгоритмы:

• Quicksort (и анализ средней сложности) показывает, что рандомизация вашего ввода может быть хорошей!
• сбалансированные деревья (деревья AVL, например, аккуратный способ балансировать затраты на поиск/вставку;
• Dijkstra и Ford-Fulkerson алгоритмы on графики (мне нравится тот факт, что у второго есть много приложений);
• семейство алгоритмов сжатия LZ * (LZW, например), сжатие данных звучало как бы волшебство для меня, пока я его не обнаружил ( давным-давно:));
• FFT, вездесущий (повторно используемый во многих других алгоритмах);
• алгоритм simplex, также вездесущий.

Числовое значение:

• Алгоритм Евклида для вычисления gcd двух целых чисел: один из первых алгоритмов, простой и элегантный, мощный, имеет множество обобщений;
• быстрое умножение целых чисел (Cooley-Tukey, например);
• Итерации Newton для инвертирования/поиска корня, очень мощного мета-алгоритма.

Связанная с теорией чисел:

• AGM-связанные алгоритмы (примеры): ведет к очень простым и изящным алгоритмам вычисления pi (и многое другое!), хотя теория довольно глубокая (Гаусс вводил из нее эллиптические функции и модулярные формы, поэтому вы можете сказать, что она породила алгебраическую геометрию...);
• числовое поле сит (для целочисленной факторизации): очень сложный, но довольно хороший теоретический результат (это также относится к AKS, который показал, что PRIMES находится в P).

Мне также понравилось изучать квантовые вычисления (Shor и Deutsch- Josza): это учит вас думать из коробки.

Как вы можете видеть, я немного склонен к математическим алгоритмам:)

Ответ 3

Алгоритм кратчайших траекторий всех пар 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 может быть на самом деле проще, чем решение задачи А.

Ответ 4

Quicksort. Он показал мне, что рекурсия может быть мощной и полезной.

Ответ 5

Это может показаться тривиальным, но это было откровение для меня в то время. Я был в своем первом классе программирования (VB6), и профессор только что научил нас случайным числам, и он дал следующие инструкции: "Создайте виртуальную лотерейную машину. Представьте себе стеклянный шар, полный 100 шаров пинг-понга с отметкой от 0 до 99. Выберите их случайным образом и покажите их номер до тех пор, пока все они не будут выбраны, никаких дубликатов."

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

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

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

Ответ 6

Кодирование Хаффмана было бы моим, я изначально сделал свою собственную тупую версию, минимизируя количество бит для кодирования текста от 8 до меньшего, но не думал о переменном количестве бит в зависимости от частоты. Затем я нашел кодировку хаффмана, описанную в статье в журнале, и она открыла множество новых возможностей.

Ответ 7

алгоритм рисования линий Bresenham заинтересовал меня графическим рендерингом в реальном времени. Это можно использовать для визуализации заполненных многоугольников, например треугольников, для таких вещей, как рендеринг 3D-модели.

Ответ 8

Рекурсивный анализ спуска - Я помню, что очень впечатлен тем, как такой простой код может сделать что-то настолько сложное.

Ответ 9

Quicksort в Haskell:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Хотя я не мог писать Haskell в то время, я понял этот код и с ним рекурсия и алгоритм быстрой сортировки. Он просто сделал клик и там он был...

Ответ 10

Итерационный алгоритм для Фибоначчи, потому что для меня это прибило тот факт, что самый элегантный код (в данном случае, рекурсивная версия) не обязательно является наиболее эффективным.

Чтобы разработать. Подход "fib (10) = fib (9) + fib (8) означает, что fib (9) будет оцениваться как fib (8) + fib (7). Таким образом, оценка fib (8) (а затем fib7, fib6) будет оцениваться дважды.

Итеративный метод, (curr = prev1 + prev2 в forloop), не генерирует этот путь, и не занимает столько памяти, поскольку он содержит только 3 переходные переменные вместо n кадров в стеке рекурсии.

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

Ответ 11

Minimax научил меня, что шахматные программы не умны, они могут просто думать, что впереди больше, чем вы можете.

Ответ 12

Мне почему-то нравится преобразование Шварца

@sorted = map  { $_->[0] }
          sort { $a->[1] cmp $b->[1] }
          map  { [$_, foo($_)] }
                @unsorted;

Где foo ($) представляет собой выражение с интенсивным вычислением, которое принимает $(каждый элемент списка в свою очередь) и выдает соответствующее значение, которое должно сравниваться в нем.

Ответ 13

Я не знаю, соответствует ли это алгоритму, или просто классическому взлому. В любом случае это помогло мне начать думать за пределами коробки.

Смените 2 целых числа без использования промежуточной переменной (в С++)

void InPlaceSwap (int& a, int &b) {
     a ^= b;
     b ^= a;
     a ^= b;
}

Ответ 14

Quicksort: До тех пор, пока я не поступил в колледж, я никогда не задавался вопросом, был ли самый грубый способ сортировки грубой силы Bubble Sort. Это казалось интуитивно очевидным. Но, сталкиваясь с неочевидными решениями, такими как Quicksort, научил меня смотреть на очевидные решения, чтобы увидеть, доступно ли что-то лучше.

Ответ 15

Для меня это алгоритм слабых-heapsort, потому что он показывает (1), насколько разумная выбранная структура данных (и алгоритмы, работающие над ней) могут влиять на производительность, и (2) что захватывающие вещи могут быть обнаружены даже в старых, хорошо известные вещи. (слабый-heapsort - лучший вариант всех типов кучи, который был доказано спустя восемь лет.)

Ответ 16

Это медленный:)

Я много узнал о C и компьютерах, понимая Duffs Device и XOR свопы

EDIT:

@Джейсон Z, что мой XOR своп:) круто, не так ли.

Ответ 17

У меня нет фаворита - есть так много красивых, чтобы выбрать, но я всегда был интригующим, это Bailey -Borwein-Plouffe (BBP), которая позволяет вам вычислить произвольную цифру pi без знания предшествующих цифр.

Ответ 18

RSA познакомил меня с миром модульной арифметики, который можно использовать для решить a неожиданно номер of интересно проблемы!

Ответ 19

Не многому меня научил, но Johnson-Trotter Algorithm никогда не сбивает меня с ума.

Ответ 20

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

Что они научили меня:

• важно компактное представление любой проблемы; маленький красивый
• для выполнения этого можно использовать небольшой набор ограничений/сокращений, применяемых рекурсивно,
• для задач с симметриями, преобразование в каноническую форму должно быть первым шагом к рассмотрению
• не читается всякая литература. Кнут узнал о BDD через несколько лет после их изобретения/введения. (и провел почти год, исследуя их).

Ответ 21

Для меня простой обмен в Kelly and Pohl A Book на C, чтобы продемонстрировать call-by-reference, перевернул меня, когда я впервые увидел его. Я посмотрел на это, и указатели встали на свои места. Verbatim.,.

void swap(int *p, int *q)
{
   int temp;

   temp = *p;
   *p = *q;
   *q = temp;
}

Ответ 22

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

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

Ответ 23

По какой-то причине Bubble Sort всегда выделялся мне. Не потому, что это элегантно или хорошо, потому что у него было/есть тупой имя, я полагаю.

Ответ 24

Итерационный алгоритм для Фибоначчи, потому что для меня это прибило тот факт, что самый элегантный код (в данном случае, рекурсивная версия) не обязательно является наиболее эффективным.

Итеративный метод, (curr = prev1 + prev2 в forloop), не генерирует этот путь, и не занимает столько памяти, поскольку он содержит только 3 переходные переменные вместо n кадров в стеке рекурсии.

Вы знаете, что фибоначчи имеет закрытое решение формы, которое позволяет прямое вычисление результата с фиксированным числом шагов, правильно? А именно: (phi ⁿ - (1 - phi) ⁿ)/sqrt (5). Мне всегда кажется замечательным, что это должно дать целое число, но оно есть.

phi - это золотое соотношение, конечно; (1 + sqrt (5))/2.

Ответ 25

@Кришна Кумар

Побитовое решение еще более забавно, чем рекурсивное решение.

Ответ 26

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

Ответ 27

Сохранение двух указателей в одном слове для дважды связанного списка упростило мой урок, который вы можете делать очень плохо в C действительно (с которым у консервативного GC будет много проблем).

Ответ 28

Самым гордым я был решением, написав что-то очень похожее на пакет DisplayTag. Это научило меня много о разработке кода, ремонтопригодности и повторном использовании. Я написал это задолго до DisplayTag, и он был погружен в соглашение NDA, поэтому я не мог его открыть, но я все еще могу говорить о том, что на собеседовании.

Ответ 29

Не мой любимый, но Алгоритм Миллера Рабина для проверки первобытности показал мне, что, будучи правым почти все время, достаточно хорошо почти все время. (т.е. не доверяйте вероятностному алгоритму только потому, что он имеет вероятность ошибиться.)

Ответ 30

Map/Reduce. Две простые концепции, которые сочетаются друг с другом, чтобы облегчить рассылку задач обработки данных.

Oh... и это только основа массивно-параллельного индексирования:

http://labs.google.com/papers/mapreduce.html