Задача №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.
12610 = 11111102 может получиться в результате работы алгоритма из числа 111112.
111112 = 3110.
Ответ: 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
Ты нашел то, что искал? Поделись с друзьями!
Спасибо за то, что пользуйтесь нашими материалами.
Информация на странице «Задача №6. Анализ алгоритма.» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам.
Чтобы успешно сдать необходимые и поступить в высшее учебное заведение или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими материалами из данного раздела.
Публикация обновлена:
08.05.2023