Задача №6. Анализ алгоритма.

Автор материалов - Лада Борисовна Есакова.

Алгоритм – это точно сформулированное исполнителю предписание совершить определенную последовательность действий для решения задачи за конечное число шагов.

Алгоритм может быть задан одним из следующих способов:

-          Словесное описание последовательности действий на естественном языке;

-          Графическое изображение в виде блок-схемы;

-          Запись при помощи псевдокода (алгоритмического языка);

-          Запись на языке программирования.

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

Проверка буквенной последовательности на соответствие алгоритму

Пример 1.

Из букв А, И, 3, У, Т, М, К, С фор­ми­ру­ет­ся слово. Из­вест­но, что слово сфор­ми­ро­ва­но по сле­ду­ю­щим пра­ви­лам:

а) в слове нет под­ряд иду­щих двух глас­ных или двух со­глас­ных;

б) пер­вая буква слова в рус­ском ал­фа­ви­те стоит до буквы «К».

Какое из сле­ду­ю­щих слов удо­вле­тво­ря­ет всем пе­ре­чис­лен­ным усло­ви­ям?

1) АЗИ­МУТ

2) ТУЗИК

3) МУЗА

4) АИСТ

Решение:

Поочередно проанализируем каждое слово:

1) а) выполняется б)  выполняется (буква «А» в рус­ском ал­фа­ви­те стоит до буквы «К»)

2) а) выполняется б)  не выполняется (буква «Т» в рус­ском ал­фа­ви­те стоит после буквы «К»)

3) а) выполняется б)  не выполняется (буква «М» в рус­ском ал­фа­ви­те стоит после буквы «К»)

4) а) не выполняется (две подряд идущие гласные).

Ответ: 1

Поиск числа, соответствующего алгоритму

Пример 2.

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

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

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

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

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

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

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

Решение:

Ал­го­ритм при­пи­сы­ва­ет в конце числа 10, если в дво­ич­ной за­пи­си числа было не­чет­ное ко­ли­че­ство еди­ниц, или 00 если чет­ное. Наименьшее число N найдем, если возьмем наименьший результат, больший 125. Это число 126.

126₁₀ = 1111110₂ может по­лу­чить­ся в ре­зуль­та­те ра­бо­ты ал­го­рит­ма из числа 11111₂.

11111₂ = 31₁₀.

Ответ: 31

Пример 3.

Ав­то­мат по­лу­ча­ет на вход трёхзнач­ное число. По этому числу стро­ит­ся новое число по сле­ду­ю­щим пра­ви­лам.

1. Скла­ды­ва­ют­ся пер­вая и вто­рая, а также вто­рая и тре­тья цифры ис­ход­но­го числа.

2. По­лу­чен­ные два числа за­пи­сы­ва­ют­ся друг за дру­гом в по­ряд­ке убы­ва­ния (без раз­де­ли­те­лей).

При­мер. Ис­ход­ное число: 348. Суммы: 3 + 4 = 7; 4 + 8 = 12. Ре­зуль­тат: 127. Ука­жи­те наи­мень­шее число, в ре­зуль­та­те об­ра­бот­ки ко­то­ро­го ав­то­мат вы­даст число 1412.

Решение:

Наименьшим число будет тогда, когда на первом месте стоит наименьшая возможная цифра. Поскольку сумма первой и второй цифр равна 14 или 12, то наименьшая первая цифра – это 3 (в сумме с 9 даст 12), тогда вторая цифра – это 9. А третья цифра в сумме со второй дает 14, т.е. равна 14-9 = 5.

Получилось число 395.

Ответ: 395

Пример 4.

Автомат получает на вход четырёхзначное десятичное число. По этому числу строится новое число по следующим правилам.

1. Складываются первая и вторая, а также третья и четвёртая цифры.

2. Полученные два числа записываются друг за другом в порядке возрастания (без разделителей).

Пример. Исходное число: 8754. Суммы: 8+7 = 15; 5+4 = 9. Результат: 915. Определите, сколько из приведённых ниже чисел могут быть получены, как результат работы автомата.

1419          1518    406      911

1) 1           2) 2      3) 3      4)4

Решение:

Проанализируем поочередно все числа на соответствие алгоритму:

1419 – не соответствует, т.к. сумма двух цифр не может дать число 19;

1518 – соответствует, например, на вход могло подаваться число 9699;

406 – не соответствует, т.к. 40 < 6 (не соблюдается порядок возрастания);

911 – соответствует, например, на вход могло подаваться число 3656;

Итого, может быть получено два числа из списка.

Ответ: 2