ТЕМА 6

"Анализ и построение алгоритмов для исполнителей"

Пример 1

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1) Строится двоичная запись числа N.

2) К этой записи дописываются справа ещё два разряда по следующему правилу:

а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;

б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.

Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите максимальное число R, которое не превышает число 75 и может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

Решение

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

74₁₀ = 1001010₂ — не является результатом работы исходного алгоритма.

Два последних разряда добавляются в результате работы алгоритма. Следовательно, число N, которое было на входе алгоритма 10010. Применив данный алгоритм, получится 1001000.

1001000₂ = 72₁₀

73₁₀ = 1001001₂ — не может является результатом, в процессе работы такого алгоритма.

Значит, максимальное число R, которое не превышает число 75, являющееся работой такого алгоритма 72.

Ответ: 72

Пример 2

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

2. К этой записи дописываются ещё два разряда по следующему правилу:

а) если число чётное, то к двоичной записи числа слева дописывается 1, а справа 0. Например, если исходное число 110, то результатом будет являться число 11100;

б) если число нечётное, то к двоичной записи числа слева дописывается 11, а справа дописывается 1.

Например, если исходное число 110, то результатом будет являться число 11101. Полученная таким образом запись является двоичной записью искомого числа R.

Укажите максимальное число N, после обработки которого с помощью этого алгоритма получается число, меньшее, чем 63. В ответе запишите это число в десятичной системе счисления.

Решение

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

62₁₀ = 111110₂ – не может являться результатом работы алгоритма. Справа дописан 0. Значит слева должна быть записана 1, если 1111₂ – чётное. Но 1111₂ = 15₁₀ (нечётное).

61₁₀ = 111101₂ – тоже не может являться результатом работы алгоритма. Справа дописана 1. Значит слева должны быть дописаны две единицы 11, если число 110₂ нечётное. Но 110₂ = 6₁₀ (чётное).

60₁₀ = 111100₂ – является результатом работы исходного алгоритма. Справа дописан 0. Значит слева должна быть записана 1, если 1110₂ – чётное. 1110₂ = 14₁₀ (чётное).

59₁₀ = 111011₂ – результат работы алгоритма. 101₂ = 5₁₀ (нечётное).

58₁₀ = 111010₂ – не подходит.

57₁₀ = 111001₂ – не подходит.

56₁₀ = 111000₂ – является решением. 1100₂ = 12₁₀ (чётное).

55₁₀ = 110111₂ – является решением. 11₂ = 3₁₀ (нечётное).

54₁₀ = 110110₂ – не подходит.

53₁₀ = 110101₂ – не подходит.

52₁₀ = 110100₂ – является решением.1010₂ = 10₁₀ (чётное).

Все последующие числа, являющиеся результатом работы алгоритма, будут иметь меньшее значение. Максимальное число N = 14.

Ответ: 14

Пример 3

У исполнителя Калькулятор две команды, которым присвоены номера:

1. прибавь 2,

2. умножь на 3.

Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, умножает его на 3.

Например, программа 21121 – это программа

умножь на 3,

прибавь 2,

прибавь 2,

умножь на 3,

прибавь 2,

которая преобразует число 2 в число 32.

Запишите порядок команд в программе, которая преобразует число 1 в число 35 и содержит не более пяти команд. Указывайте лишь номера команд. Если таких программ более одной, то запишите любую из них.

Решение

Умножение на число обратимо не для любого числа, поэтому, если мы пойдём от числа 35 к числу 1, тогда однозначно восстановим программу. Полученные команды будут записываться справа налево.

Число 35 не делится на 3, поэтому последняя команда прибавь 2 (35-2=33). Так как алгоритм должен быть реализован с использованием не более пяти команд, то оптимально для получения числа 33 использовать деление на 3 (33:3 =11) – команда умножь на 3.

Число 11 не делится на 3, значит, оно получено прибавлением двойки: 11 = 9 + 2 - команда прибавь 2.

Число 9 делится на 3, значит, оно получено умножением на 3: 9 = 3*3 - команда умножь на 3.

Число 3 получено командой прибавь 2 к 1 или 1 умножь на 3.

Полученные программы: 22121 или 12121. В качестве ответа может быть записана любая программа.

Ответ: 22121

• Примеры, рассмотренные на этой странице в формате pdf: скачать
• Решенные задачи по теме других авторов: скачать
• ссылка на видеоурок по теме: смотреть

Комментарии, отзывы и предложения Вы можете направить на e-mail, указанный в контактах или оставить в гостевой книге, указав тему вопроса: перейти в гостевую книгу