Nickolay.info. Алгоритмы. Устройство с двумя кнопками (2x и x+1)

2. Автоматическое устройство имеет 2 кнопки и экран. При включении на экране загорается число 0. При нажатии на первую кнопку число на экране удваивается (вместо х появляется 2х), при нажатии на вторую число увеличивается на 1 (вместо х появляется х+1). Как надо нажимать кнопки, чтобы на экране появилось:
а) число 5;
б) число 99;
в) число 99, если разрешается нажимать на кнопки не более 10 раз.

а)-б) Простейший порядок действий таков:
Если а - искомое число, х - текущее число на экране, (1),(2) - кнопки умножения на 2 и инкремента соответственно, то


   нажать (2)
   пока х*2<=a, нажимать (1)
   пока х<a, нажимать (2)

в) Попробуем найти более оптимальный алгоритм. Обозначения те же. N - число нажатий кнопок.


   N:=0
   Пока a>1, {начало цикла}
    Если a нечетное, то a:=(а-1)/2; n:=n+2;
    Иначе a=а/2; n:=n+1;
   {конец цикла}
   N:=N+1; {Переход от 1 к 0}

Для числа 99 алгоритм работает так:


   A  99 49 24 12 6 3 1 0
   N  0  2  4  5  6 7 9 10

То есть, требуется ровно 10 нажатий, а именно


   Кнопка     (2) (1) (2) (1) (1) (1) (1) (2) (1) (2)
   Результат  1   2   3   6   12  24  48  49  98  99

Математически самое простое - использовать разложение по степеням двойки.

Рейтинг@Mail.ru

вверх гостевая; E-mail