Муравей Лэнгтона и задача из проекта Эйлер

11.07.23

Клеточный автомат муравей Лэнгтона и решение задачи из проекта Эйлер.

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование		По подписке [?]	Купить один файл
Муравей Лэнгтона и задача из проекта Эйлер: .erf 11,69Kb 1	1	Скачать (1 SM)	Купить за 1 850 руб.

Недавно мне попалась следующая задача.

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

Муравей всегда смотрит в одном из основных направлений (влево, вправо, вверх или вниз) и передвигается на соседнюю клетку по одному из следующих правил:

- если он на черной клетке, то цвет клетки меняется на белый, муравей поворачивается на 90 градусов против часовой стрелки и передвигается прямо на следующую клетку.

- если он на белой клетке, то цвет клетки меняется на черный, муравей поворачивается на 90 градусов по часовой стрелке и передвигается прямо на следующую клетку.

Пусть изначально задано полностью белое поле из клеток. Сколько клеток окрасится в черный цвет после того, как муравей совершит 10¹⁸ переходов?

Решить данную задачу простым перебором всех движений муравья нереально из-за очень большого количества переходов. Значит должна быть формула. Но как ее найти ? Изучение зависимости количества черных клеток от сделанных ходов для ста первых перемещений успехом не увенчалось. Тогда пришла идея визуализировать движения муравья. Это было сделано с помощью несложной обработки. Результат перемещения муравья отображается на поле табличного документа, параллельно происходит запись маршрута в таблицу протокола. После хаотичного блуждания муравей попадает на скоростную магистраль и скрывается за горизонтом. Появление упорядоченного рисунка, говорит о том, что начиная с некоторой точки число черных клеток будет увеличиваться на одно и тоже количество после совершения одинакового количества перемещений. Длину периода по шагам и приращениям черных клеток можно найти пощелкав на повторяющихся фрагментах маршрута. Интерес представляет начало периодической траектории. Если заглянуть на сайт oeis.org , то мы найдем нужную нам формулу, автором которой назван Андрей Заболоцкий. После этого решение задачи из проекта Эйлер не должно представлять особых трудностей.

Обработка для визуализации перемещений муравья содержит две команды Старт (Стоп) и команду отображения области первого периода. Первоначальная позиция муравья задается активацией ячейки табличного поля. В правой части располагается таблица значений с протоколом перемещений.

Тестирование обработки выполнялось на платформе 1С:Предприятие 8.3 (8.3.22.1923).

+6 –

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Программист Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024 3154 stopa85 12

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023 7541 user1959478 51

Математический тренажер через телеграмм (feat 1С)

Математика и алгоритмы Разное Платформа 1С v8.3 Конфигурации 1cv8 Россия Абонемент ($m)

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023 3101 maksa2005 8

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Программист Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023 10893 7 SpaceOfMyHead 18

Мини-обзор разных решений задач

Математика и алгоритмы Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023 4353 RustIG 9

Тестирование средств 1С для решения СЛАУ

Механизмы платформы 1С Математика и алгоритмы Программист Платформа 1С v8.3 Россия Бесплатно (free)

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

23.11.2022 3517 gzharkoj 14

Модель распределения суммы по базе

Математика и алгоритмы Программист Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022 9038 7 kalyaka 11

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Программист Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021 5651 fishca 12

Комментарии

Подписаться на ответы Инфостарт бот

Свернуть все

1. Alxby 1113 11.07.23 09:21 Сейчас в теме

Муравей Лэнгтона - частный случай тьюрмитов https://ru.wikipedia.org/wiki/Тьюрмиты. Кроме упомянутой в статье задачи, есть более интересная: можно ли так раскрасить поле, чтобы муравей никогда не выбрался за его пределы? Пока такая раскраска не найдена - муравей всегда, рано или поздно, начинает строить периодическую "дорогу" за пределы поля

2. Oleg_nsk 279 11.07.23 12:06 Сейчас в теме

С помощью python и turtle, чтобы визуализировать муравья ушло 3 минуты кодинга.
Всё таки 1с достаточно беден для быстрого решения таких задач

import turtle
black = []
turtle.hideturtle()
turtle.tracer(0)
turtle.penup()
L = 4
for i in range(5000):
    x = turtle.xcor()
    y = turtle.ycor()
    if (x, y) in black:
        black.remove((x, y))
        turtle.dot(L,'white')
        turtle.left(90)
        turtle.forward(L)
    else:
        black.append((x, y))
        turtle.dot(L,'black')
        turtle.right(90)
        turtle.forward(L)

turtle.update()
turtle.mainloop()

Показать

Прикрепленные файлы:

3. scientes 295 11.07.23 12:24 Сейчас в теме

(2)

Всё таки 1с достаточно беден для быстрого решения таких задач

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

4. Oleg_nsk 279 11.07.23 13:18 Сейчас в теме

(3)

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

Суть не в коротком коде, а во времени его написания. Можно короткий код писать долго и длинный быстро.
Отображение для этой задачи это как раз самое важное. Далее дело техники подсчитать паттерн.
С помощью рисунка легко вычислить, что перед началом паттерна есть 724 черные клетки на 10024 хода, далее достаточно просто подобрать, что каждые 104 хода добавляется 12 клеток. В результате:
12 * (10**18-10024) / 104 + 724 = 115384615384614952

5. Alxby 1113 11.07.23 13:40 Сейчас в теме

(4) Теперь можно приступить к решению задачи из моего первого комментария;)

6. Alxby 1113 11.07.23 13:49 Сейчас в теме

(2)

Всё таки 1с достаточно беден для быстрого решения таких задач

Правильно я понимаю, что краткость решения на python обусловлена наличием turtle? И если бы в 1С был аналог turtle, решение было бы таким же коротким?

7. Oleg_nsk 279 12.07.23 05:12 Сейчас в теме

(6)

turtle позволяет быстро визуализировать ход муравья, а далее скорость вычисления не будет отличаться. Если бы автор задачи не сказал, что где-то пойдет повторение рисунка (а для этого нужно пройти более 10000 ходов), возможно, я бы не решил данную задачу, однако, владея только 1с, в табдоке рисовать всё это пришлось бы гораздо дольше.
Что касается python, то там помимо turtle (это вообще инструмент для школьников) есть гораздо более серьезные библиотеки: типа tkinter и pygame. Вообще же язык лишь инструмент для реализации задачи. Может быть топор, а может бензопила. Назначения одинаковые, но скорость выполнения отличается в разы.

8. DrAku1a 1745 14.07.23 16:31 Сейчас в теме

Для любителей посравнивать 1С и Питона, например - прошу, решите простую задачку: (9 в 9 степени) в 9 степени (важны все знаки).
(64-битное целое вмещает значения гораздо меньшего размера)

Прикрепленные файлы: