Это 2 из 3 алгоритмов вычисления последней цифры во всяких нужных последовательностях. У вас может возникнуть правильный вопрос: "А нахуя нужен еще один?" Фича в том, что предыдущий код, как было написано в конце прошлого поста, не может в пары одинаковых чисел, и иногда он путается, показывая лютую поебень, поэтому люди мутят новые алгоритмы, которые бы исправляли недочеты прошлых. Алгоритм Верхуффа лучше алгоритма Луна в 4 из 8 пунктах и хуже в 3 (сравнение этих алгоритмов будет в следующем посте). Этот алгоритм самый сложный их 3, так что тут надо будет подумать (я понимаю, что ты не привык, но надо).

Посмотрите на 1 картинку. Вы видите таблицу, де на пересечениях двух цифр стоят другие цифры, причем, если поменять местами те, по которым мы ищем (то есть взять (4, 5) или (5, 4)), то иногда получаются разные значения. Также видна еще одна странность – строк всего 8, в то время, когда столбцов 10. Это сделано для большей точности, а число, которое мы должны взять относительно строки должно быть модульно разделено на 8 (остаток деления на 8). Теперь давайте называть строки i, а столбцы x_i, а результат этой хуйни будем называть p(i + 1, x_i). Где i – позиция этой цифры, модульно разделена на 8, а x_i – сама цифра (это будет нужно потом). Дальше мы возьмем еще одну таблицу, которая есть на 2 пикче. Тут тоже есть асимметрия относительно главной диагонали, но это нам не помешает. Итак, давайте теперь мы пока что назовем строки – х, а столбцы – y, а саму операцию поиска цифры d(x, y).

Теперь давайте всю хуйню собирать воедино. Она будет выглядеть так:
c = d(c, p(i + 1, x_i))
Давайте поясню, если непонятно. с – это наша контрольная (последняя) цифра в ряду. В первый раз мы подставляем вместо нее 0, а в операцию p(i, x_i) первую цифру нашего ряда. Давай посмотрим, что у нас получится.

Так как я неебически ленивый, то возьмем четырехзначное число 1234. Как пишут 2 сайта (2 САЙТА БЛЯТЬ СУКА, ГДЕ ВСЯ ИНФА НАХУЙ), нужно идти справа-налево.
c = d(0, p(5, 4)) – это мы подставили все в формулу.
с = d(0, 5) – вычислили по таблице p.
с = 5 – вычислили по таблице d.
Дальше проделываем то же самое с последующими цифрами, только вместо с = 0 ставим такое с, которое у нас получилось в прошлый раз:
с = d(5, p(4, 3))
c = d(5, 3)
c = 7.
с = d(7, p(3, 2))
c = d(7, 1)
c = 6
c = d(6, p(2, 1))
c = d(6, 8)
c = 3 – это последние число, которое у нас получилось.
Теперь посмотрим на еще одну таблицу (3 пикча) и по ней вычислим, какую цифру нужно добавить. В моем случае, это 2. То есть у меня получилось число:
12342
Чтобы проверить, нам нужно просто сделать так:
c = d(3, 2)
c = 0
Все сошлось.

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

Алгоритм Луна: https://vk.com/wall-147914213_9346





Спасибо за то, что вы с нами.
С любовью, Рителлинг favorite