Привет. Придумай идею алгортма для реализации функ...

Question

Привет. Придумай идею алгортма для реализации функций min(x,y), max(x,y) с использованием унарного алфавита (1 и пустой символ: 1-0 ,11-1, 111-2, 1111-3), где x и y разделены пустым символом

Answer 1

Идея алгоритма (уровень «карандаш-и-бумага», без конкретного формата машины)

Универсальная мысль: «вычёркиваем пары 1».
Чем дольше оба отрезка 1-ов «живут» одновременно, тем больше общее количество; тот, у кого 1-ы заканчиваются первым, был меньше. Это же действие сразу даёт и min, и max.

Представление чисел

Число n кодируется как n + 1 символов 1.

text
1        &rarr; 0
11       &rarr; 1
111      &rarr; 2
1111     &rarr; 3
...

Между x и y стоит единственный «пустой» символ 0 (можно думать как о разделителе □).
```
text
⟨…1110 11111…⟩
     &uarr;
     разделитель
```

Шаги алгоритма

Начало и маркировка
Поставьте головку на первый 1 левого числа.
Введите вспомогательный символ, например X, чтобы «помечать» уже обработанные 1.
Попарное вычёркивание

Пока справа и слева от разделителя ещё есть непомеченные 1:
- Замените текущий левый 1 на X.
- Перейдите через разделитель к симметричному правому блоку, замените первый непомеченный 1 там на X.
- Вернитесь к следующему непомеченному 1 слева.
Обе группы убывают синхронно.

Определение результата

После цикла возможны два случая:

Состояние	Что означает	Как получить `max`	Как получить `min`
Слева остались непомеченные `1`, справа — нет	`x > y`	Скопировать все помеченные `X` и оставшиеся непомеченные `1` слева → это `max`	Кол-во `X` (общее число сделанных парных вычёркиваний) справа → это `min`
Справа остались непомеченные `1`, слева — нет	`y > x`	Аналогично, но стороны меняются	Аналогично
Непомеченных `1` не осталось ни слева, ни справа	`x = y`	Любая сторона	Любая сторона

Очистка и финальная запись
- Замените все X обратно на 1 (или стирайте, если хотите полностью удалить промежуточные следы).
- Разместите результат(ы) на ленте:
  Например: min(x,y) 0 max(x,y).

Короткий псевдокод

text
# Лента: 1^{x+1} 0 1^{y+1}
while left(0) == 1 and right(0) == 1:
    mark left 1 -> X
    move to right area
    mark first 1 -> X
    move back to left area
# Теперь хотя бы одна сторона без 1
if left(0) == 1:        # x > y
    max_block = (X + remaining 1's on left)
    min_block = (all X on right)
elif right(0) == 1:     # y > x
    max_block = (X + remaining 1's on right)
    min_block = (all X on left)
else:                   # x == y
    max_block = min_block = (all X on either side)
unmark X -> 1
output: min_block 0 max_block

Почему это работает

Каждая итерация удаляет ровно одну единицу с каждой стороны — эквивалент вычитания 1 из обоих чисел.
Как только «короткое» число истощится, количество сделанных пар (#X) равно min(x, y), а оставшиеся единицы у длинного — max(x, y) – min(x, y); вместе с уже помеченными X они формируют max.

Сложность

Временная: O(x + y) — одна итерация на каждую пару единиц.
Память: только исходная лента; никаких дополнительных ячеек, кроме одного символа-метки.

Как можно развить идею

Детерминизировать шаги для конкретной модели (Тьюринг, Лемма Поста и т.д.).
Оптимизировать: параллельно сканировать оба блока одним проходом вместо постоянного «прыгания» через разделитель.
Обобщить на k чисел: вычёркиваем по кольцу, пока не останется единственный «живой» блок — это max; число вычёркиваний — min.

Используя этот каркас, легко написать конкретный набор правил переписывания или таблицу состояний ТМ.

Привет. Придумай идею алгортма для реализации функ...

Вопрос

Мысль

Designing unary min/max algorithm

Explaining unary min/max algorithm

Ответ