Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Найти кратчайшую последовательность комманд

Автор: MarMar 17.6.2016, 20:53

Добрый день.
Подскажите, не могу понять, где собака зарыта. Задача выглядит как обычная олимпиадная для школьников, но тем не менее.

Даны начальные значения A = 0, Z = 1.

Также две команды A: A = 2 * A - Z
Также две команды Z: Z = 2 * Z - A

На вход дают число N, и надо сделать так, чтобы из начальных значений A = 0, Z = 1 с помощью выше обозначенных команд (A,Z) дойти до N, при чем не важно, кто из переменных А, Z дойдет первым до N, т.е.:

N = 21
Начальные значения: A = 0, Z = 1
Команда А: А = -1; Z = 1
Команда А: А = -3; Z = 1
Команда Z: А = -3; Z = 5
Команда А: А = -11; Z = 5
Команда Z: А = -11; Z = 21

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

Автор: ksnk 17.6.2016, 22:40

Решения пока нет, но вот пара утверждений

- если оба числа A и Z - попарно четные или нечетные, то применение любой операции A или Z оставит их четными или нечетными, соответственно.
Отсюда следует, что решение для нечетных чисел должно начинаться с операции A - выходим к комбинации {-1,1} ; решение для четного числа - с операции Z - {0,2}

- С этой стартовой позиции мы можем получить пару чисел - отрицательное -положительное, либо, применяя только Z - { 0, `2 в степени`}, После применения А получим пару разнознаковых чисел. Итого, если требуется найти положительное число - "достигнуть его" способно только Z. Отрицательное решение будет только А.

- если число A меньше нуля, а Z - больше нуля, то любая операция А или Z не изменит знак чисел А и Z результата, а только сделает его бОльшим по модулю.
Очень похоже, что если для какого то числа и можно получить решение - оно будет кратчайшим.
Скорость увеличения модуля довольно велика, так что действительно, все возможные числа получить, вероятнее всего, не выйдет.

P.S. В последней строке приведенного решения для 21 - ошибка. Число `-12` нужно заменить на `-11`

Автор: MarMar 18.6.2016, 20:25

Цитата(ksnk @ 17.6.2016, 22:40

)

P.S. В последней строке приведенного решения для 21 - ошибка. Число `-12` нужно заменить на `-11`

Да, там ошибка, Спасибо!

Рассуждения, может, и верны, но начальные значения даны именно "разномастные": чет и нечет)

Мне,вроде, один человечек ответил. Сейчас посмотрю, если окажется верным, и пойму, то могу сюда выложить ради интереса!)

Автор: ksnk 19.6.2016, 22:18

Если на javascript описать, то решение вот такое

Код


           function convert(n) {
                if (n >= 0 && n < 2) {
                    return '';
                } else if (n > 0) {
                    return (n - 1).toString(2)
                            .split('').reverse().join('')
                            .replace(/1/g, 'Z').replace(/0/g, 'A');
                } else {
                    return (0 - n).toString(2)
                            .split('').reverse().join('')
                            .replace(/1/g, 'A').replace(/0/g, 'Z');
                }
            }

http://output.jsbin.com/jovijorayi
или
http://jsbin.com/jovijorayi/edit?html,output