Извлечение Квадратных Корней С Использованием Обычных Алгоритмов Маркова

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

Коротко о США:

  • Существует список замен одной подстроки на другую, называемый правилами.

  • Мы ищем с начала списка первое правило, которое мы можем применить, и применяем его к первому вхождению.

  • Если такое правило обнаружено, то вернитесь к предыдущему пункту и сначала просмотрите список правил.

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

Итак, кажется, все просто? Однако как писать программы на NAM? Для себя я сделал что-то вроде этого:
  • Мы пытаемся написать обычный алгоритм, используя только строки.

  • Следим, чтобы последние замены не пересекались с первыми
  • Переворачиваем алгоритм и пишем от конца к началу
Итак, вернемся к вычислению квадратного корня.

Мы воспользуемся «детским» методом (он же арифметический), который основан на том простом факте, что квадрат числа — это сумма нечетных чисел от 1 до 2n-1:

  • 1 = 1 2 = 1
  • 1 + 3 = 2 2 = 4
  • 1 + 3 + 5 = 3 2 = 9
Как мы могли бы реализовать извлечение корня на основе этого свойства? Будем последовательно вычитать из числа сначала 1, затем 3, затем 5 и т. д., пока число не станет меньше нуля, одновременно подсчитывая, сколько вычитаний мы сделали.

Итого уже два счетчика + одна переменная для хранения результата Маленькая особенность США – здесь нет цифр.

И переменных нет. Поэтому нам нужно будет их смоделировать.

Так как мне было лень писать длинную арифметику (да и я сомневаюсь, что это под силу человеку), то арифметические действия я делал по простому принципу – с помощью приращения и убывания.

Я решил убедиться, что моя строка сохранена в формате {Result}.

{Number}{NextOddNumber}{Индикатор конца строки} Я решил сохранить нечетное число в унарной системе счисления и обозначить единицу как «#» — с ней будет гораздо проще работать.

Теперь, как нам вычесть следующее нечетное число из числа, не потеряв данные? Я решил, что между нечетным числом и индикатором конца строки нужно добавить маркер «а», который, перемещаясь по числу, будет дублировать его, но в другом виде (обозначается «-»).

Затем мы переложим все минусы на число и вычтем их.

После того как мы вычли все числа, нам нужно увеличить результат на единицу.

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

Я решил заставить этот алгоритм работать с абсолютной точностью 0,5, а не 1 (как в описании).

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

Очень интересно выглядит зависимость количества замен от количества:

Извлечение квадратных корней с использованием обычных алгоритмов Маркова

Посмотреть код: Paste.org.ru/?3uweqh Посмотреть пример выполнения: Paste.org.ru/?34caeb Скачать программу: site.google.com/site/nsinreal/markovsqrt.zip Теги: #нормальный алгоритм Маркова #Аномальное программирование

Вместе с данным постом часто просматривают: