Однажды я хотел вычислить квадратный корень, используя нормальные алгоритмы Маркова (НАС).
Коротко о США:
- Существует список замен одной подстроки на другую, называемый правилами.
- Мы ищем с начала списка первое правило, которое мы можем применить, и применяем его к первому вхождению.
- Если такое правило обнаружено, то вернитесь к предыдущему пункту и сначала просмотрите список правил.
- Если правило было окончательным, то заканчиваем работу
- Если больше нет правил, которые мы можем применять, мы уходим.
- Мы пытаемся написать обычный алгоритм, используя только строки.
- Следим, чтобы последние замены не пересекались с первыми
- Переворачиваем алгоритм и пишем от конца к началу
Мы воспользуемся «детским» методом (он же арифметический), который основан на том простом факте, что квадрат числа — это сумма нечетных чисел от 1 до 2n-1:
- 1 = 1 2 = 1
- 1 + 3 = 2 2 = 4
- 1 + 3 + 5 = 3 2 = 9
Итого уже два счетчика + одна переменная для хранения результата Маленькая особенность США – здесь нет цифр.
И переменных нет. Поэтому нам нужно будет их смоделировать.
Так как мне было лень писать длинную арифметику (да и я сомневаюсь, что это под силу человеку), то арифметические действия я делал по простому принципу – с помощью приращения и убывания.
Я решил убедиться, что моя строка сохранена в формате {Result}.
{Number}{NextOddNumber}{Индикатор конца строки} Я решил сохранить нечетное число в унарной системе счисления и обозначить единицу как «#» — с ней будет гораздо проще работать.
Теперь, как нам вычесть следующее нечетное число из числа, не потеряв данные? Я решил, что между нечетным числом и индикатором конца строки нужно добавить маркер «а», который, перемещаясь по числу, будет дублировать его, но в другом виде (обозначается «-»).
Затем мы переложим все минусы на число и вычтем их.
После того как мы вычли все числа, нам нужно увеличить результат на единицу.
В моей реализации была небольшая особенность — результат всегда выходит округлённым в большую сторону.
Я решил заставить этот алгоритм работать с абсолютной точностью 0,5, а не 1 (как в описании).
Когда в строке остается более половины их первоначального значения, надо уменьшить результат. В результате получается игра «пинг-понг», в которой извлекается квадратный корень из заданного числа.
Очень интересно выглядит зависимость количества замен от количества:
Посмотреть код: Paste.org.ru/?3uweqh
Посмотреть пример выполнения: Paste.org.ru/?34caeb
Скачать программу: site.google.com/site/nsinreal/markovsqrt.zip
Теги: #нормальный алгоритм Маркова #Аномальное программирование
-
Толкать
19 Oct, 24 -
Распространение Пресс-Релизов
19 Oct, 24 -
Mlops — Поваренная Книга, Глава 1
19 Oct, 24