1. Может ли быть так, что задача для Удвоителя решается с помощью нескольких различных программ одинаковой длины? Если да, то приведите примеры.
Да, задача для Удвоителя может решаться с помощью нескольких различных программ одинаковой длины. Например, чтобы получить число 6 из числа 1, можно использовать следующие программы: Команда: Удвой, Удвой, Прибавь 1 (1 → 2 → 4 → 6) Команда: Прибавь 1, Удвой, Удвой (1 → 2 → 3 → 6)
Обе программы имеют одинаковую длину — три команды.
2. Как можно доказать, что построенная программа для Удвоителя действительно самая короткая?
Чтобы доказать, что построенная программа для Удвоителя самая короткая, можно использовать метод обратного хода. Сначала фиксируется конечное число и пошагово выясняется, какие числа могут быть его предшественниками (деление на 2, если число чётное, или вычитание 1). Так продолжается до достижения начального числа. Если любая другая программа имеет больше шагов, она не является самой короткой.
3. Какие числа можно и какие нельзя получить из натурального числа N с помощью Удвоителя? Из нуля? Из отрицательного числа?
С помощью Удвоителя можно получить из натурального числа N любое большее натуральное число, которое представимо в виде суммы удвоений и единичных приращений. Из нуля можно получить только те числа, которые равны 2^k −1 (где k — количество удвоений, а 1 — результат добавлений). Например, 1 (0 → +1), 3 (0 → +1 → *2 → +1), 7. Из отрицательного числа получить что-либо нельзя, так как команды Удвоителя предполагают только положительные приращения.
4. Как быстро построить самую короткую программу для получения некоторого числа N из нуля с помощью Удвоителя? Когда эта задача не имеет решений?
Для построения самой короткой программы нужно использовать обратный ход от числа N к 0, выполняя обратные операции (деление на 2 для чётных чисел или вычитание 1 для нечётных). Задача не имеет решения, если N меньше 0, так как Удвоитель не умеет уменьшать числа.
5. Исполнитель Калькулятор работает с целыми числами и умеет выполнять команды
1. прибавь 1
2. раздели на 2
Команда 2 может применяться только к чётным числам. Нужно составить самую короткую программу для Калькулятора, с помощью которой из числа а можно получить число б. Как лучше перебирать варианты программ, от начального числа к конечному или наоборот? Почему?
Для Калькулятора составление самой короткой программы из числа a в число b проще осуществить в обратном направлении: Начать с b и выяснить, какие числа могут быть его предшественниками (умножение на 2, если чётное, или вычитание 1). Этот метод быстрее, так как ветвлений в обратном направлении меньше, чем в прямом. Например, чтобы получить число 8 из 1, проще двигаться от 8:8→4→2→1