Тест по информатике Алгоритмы и исполнители 6 класс
Тест по информатике Алгоритмы и исполнители с ответами для учащихся 6 класса. Тест состоит из 2 вариантов в каждом по 7 заданий.
1 вариант
1. Закончите предложение: «Алгоритмом называется…»
1) нумерованный список
2) маркированный список
3) система команд исполнителя
4) описание конечной последовательности шагов в решении задачи, приводящей от исходных данных к требуемому результату
2. Что можно считать алгоритмом?
1) Правила техники безопасности
2) Список класса
3) Кулинарный рецепт
4) Перечень обязанностей дежурного по классу
3. Закончите предложение: «Блок-схема — форма записи алгоритма, при которой для обозначения различных шагов алгоритма используются…»
1) рисунки
2) списки
3) геометрические фигуры
4) формулы
4. Закончите предложение: «Геометрическая фигура
используется в блок-схемах для обозначения…»
1) начала или конца алгоритма
2) ввода или вывода
3) принятия решения
4) выполнения действия
5. Закончите предложение: «Геометрическая фигура
используется в блок-схемах для обозначения…»
1) начала или конца алгоритма
2) ввода или вывода
3) принятия решения
4) выполнения действия
6. Отметьте галочкой истинные высказывания.
1) Человек разрабатывает алгоритмы.
2) Компьютер разрабатывает алгоритмы.
3) Исполнитель разрабатывает алгоритмы.
4) Человек управляет работой других исполнителей по выполнению алгоритмов.
5) Компьютер управляет работой связанных с ним технических устройств по выполнению алгоритмов.
6) Исполнитель управляет работой связанных с ним технических устройств по выполнению алгоритмов.
7) Человек исполняет алгоритмы.
8) Компьютер сам выполняет алгоритмы (программы).
9) Исполнитель четко и безошибочно выполняет алгоритмы, составленные из команд, входящих в его СКИ.
7. Закончите предложение: «Алгоритм, в котором команды выполняются в порядке их записи, т. е. последовательно друг за другом, называется…»
1) линейным
2) ветвлением
3) циклическим
2 вариант
1. Закончите предложение: «Алгоритмом называется…»
1) нумерованный список
2) описание конечной последовательности шагов в решении задачи, приводящей от исходных данных к требуемому результату
3) блок-схема
4) система команд исполнителя
2. Что можно считать алгоритмом?
1) Правила организации рабочего места
2) Телефонный справочник
3) Схема метро
4) Инструкция по пользованию телефонным аппаратом
3. Закончите предложение: «Графическое представление алгоритма для исполнителя называется…»
1) рисунком
2) планом
3) геометрической фигурой
4) блок-схемой
4. Закончите предложение: «Геометрическая фигура
используется в блок-схемах для обозначения…»
1) начала или конца алгоритма
2) ввода или вывода
3) принятия решения
4) выполнения действия
5. Закончите предложение: «Геометрическая фигура
используется в блок-схемах для обозначения…»
1) начала или конца алгоритма
2) ввода или вывода
3) принятия решения
4) выполнения действия
6. Отметьте галочкой истинные высказывания.
1) Человек исполняет алгоритмы.
2) Компьютер сам выполняет алгоритмы (программы).
3) Исполнитель четко и безошибочно выполняет алгоритмы, составленные из команд, входящих в его СКИ.
4) Человек управляет работой других исполнителей по выполнению алгоритмов.
5) Компьютер управляет работой связанных с ним технических устройств по выполнению алгоритмов.
6) Исполнитель управляет работой связанных с ним технических устройств по выполнению алгоритмов.
7) Человек разрабатывает алгоритмы.
8) Компьютер разрабатывает алгоритмы.
9) Исполнитель разрабатывает алгоритмы.
7. Закончите предложение: «Алгоритм, в котором некоторая группа команд выполняются многократно, пока соблюдается некоторое заранее установленное условие, называется…»
1) линейным
2) ветвлением
3) циклическим
Ответы на тест по информатике Алгоритмы и исполнители
1 вариант
1. Алгоритмом называется описание конечной последовательности шагов в решении задачи, приводящей от исходных данных к требуемому результату.
2. Кулинарный рецепт.
3. Геометрические фигуры.
4. Ввода или вывода.
5. Начала или конца алгоритма.
6. Человек разрабатывает алгоритмы. Человек управляет работой других исполнителей по выполнению алгоритмов. Компьютер управляет работой связанных с ним технических устройств по выполнению алгоритмов. Человек исполняет алгоритмы. Компьютер сам выполняет алгоритмы (программы). Исполнитель четко и безошибочно выполняет алгоритмы, составленные из команд, входящих в его СКИ.
7. Линейным.
2 вариант
1. Алгоритмом называется описание конечной последовательности шагов в решении задачи, приводящей от исходных данных к требуемому результату.
2. Инструкция по пользованию телефонным аппаратом.
3. Блок-схемой.
4. Ввода или вывода.
5. Принятия решения.
6. Человек исполняет алгоритмы. Компьютер сам выполняет алгоритмы (программы). Исполнитель четко и безошибочно выполняет алгоритмы, составленные из команд, входящих в его СКИ. Человек управляет работой других исполнителей по выполнению алгоритмов. Компьютер управляет работой связанных с ним технических устройств по выполнению алгоритмов. Человек разрабатывает алгоритмы.
7. Циклическим.
ГДЗ по информатике 11 класс учебник Босова параграф 5
1. Перечислите основные свойства алгоритмов и проиллюстрируйте их примерами.
2. Почему кулинарный рецепт приготовления торта нельзя считать алгоритмом? Какими свойствами алгоритма он не обладает?
Приготовление не обладает массовостью, так как порядок приготовления торта, не подойдет к приготовлению салата.
3. Переформулируйте описание способа проведения перпендикуляра к прямой в заданной точке так, чтобы оно стало алгоритмом.
1 Проведём окружность с центром в точке А таким радиусом, чтобы она пересекла прямую а в двух точках. Назовём их В и С.
2 С центром в точке В проведем окружность радиусом больше половины длины отрезка ВС.
3 C центром в точке С этим же радиусом проведём окружность. Получим точку D.
4 Через точки А и D проведём прямую. Она будет являться перпендикуляром к прямой а.
4. Есть двое песочных часов: на 3 и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать?
Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира.
5. Исполнитель Вычислитель получает на вход целое число х и может выполнять с ним преобразования по алгоритму, состоящему из любого количества команд: 1) прибавить 5; 2) вычесть 2.
Сколько разных алгоритмов, состоящих из пяти команд, можно составить для этого исполнителя? Сколько из них будут приводить к одинаковым результатам для заданного числа х?
Алгоритмы с разными выходными данными:
1) x + 5 * 5 + 2 * 0 = x + 25
Всего разных алгоритмов : 2^5 = 32
Всего алгоритмов с разными выходными данными: 6
6. Как известно, для каждого исполнителя набор допустимых действий всегда ограничен, иначе говоря, не может существовать исполнителя, для которого любое действие является допустимым. Докажите это утверждение, предположив, что такой исполнитель существует.
Например, исполнитель умеющий только проводить арифметические операции не сможет найти синус числа.
7. Перечислите известные вам способы записи алгоритмов.
словесный (запись на естественном языке);
графический (запись с использованием графических символов);
программный (тексты на языках программирования).
8. Приведите примеры задач и оптимальных способов записи алгоритмов их решения.
Алгоритм по разогреванию супа.
Алгоритм по игре в крестики-нолики
Алгоритм вычисления математической формулы
9. Исполнитель Автомат получает на вход четырёхзначное число. Это число он преобразует по следующему алгоритму:
1) вычисляется сумма первой и второй цифр числа;
2) вычисляется сумма второй и третьей цифр числа;
3) вычисляется сумма третьей и четвёртой цифр числа;
4) из полученных трёх чисел (сумм) выбирается и отбрасывается одно — не превышающее двух других чисел;
5) оставшиеся два числа записываются друг за другом в порядке неубывания без разделителей.
Так, если исходное число 9575, то, преобразуя его, автомат создаст суммы: 9 + 5 = 14, 5 + 7 = 12, 7 + 5 = 12. Сумма, не превышающая двух других, 12. Оставшиеся суммы: 14, 12. Результат: 1214.
Опишите систему команд этого исполнителя.
Могут ли результатом работы этого исполнителя быть числа 1610, 1010, 1019?
Укажите минимальное и максимальное значения результата работы этого исполнителя.
При обработке некоторого числа х автомат выдаёт результат 1418. Укажите наименьшее и наибольшее значения х, при которых возможен такой результат.
Система команд данного исполнителя подразумевает в себе 5 основных действий с 4-значным числом:
1) Сложить 1 и 2 цифру
2) Сложить 2 и 3 цифру
3) Сложить 3 и 4 цифру
4) Найти минимум из этих полученных сумм
5) Отсортировать оставшийся (исходя из 4 пункта) 2 суммы в порядке возрастания.
Могут ли результатом работы этого исполнителя быть чиста 1610, 1010, 1019?
Минимальное число, которое можно получить после обработки данным алгоритмом: 1818 (9999 число до алгоритма)
Минимальное: 01 (1000 число до алгоритма)
Число после алгоритма 1418:
Минимальное число: 1599 (1->6,2->14,3->18,4->6,5->1418)
Максимальное число: 9959 (1->18,2->14,3->14,4->14,5->1418)
10. Подготовьте краткое сообщение об одном из учёных (А. Тьюринг, Э. Пост, А. Н. Колмогоров, А. А. Марков и др.), внёсших вклад в развитие теории алгоритмов.
В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.
Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.
Что собой представляет машина Тьюринга?
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой.
Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).
11. В чём отличие шага алгоритма от команды алгоритма? Приведите пример.
В чём отличие шага алгоритма от команды алгоритма
12. Что такое сложность алгоритма? От чего она зависит в наибольшей степени?
Сложность алгоритма – это объем работы, который выполнится некоторым алгоритмом. Зависит от входных значений.
13. Подсчитайте сложность алгоритма перемножения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n, а второе — из m десятичных цифр.
14. Какой алгоритм считается эффективным?
Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня.
15. Постройте эффективный алгоритм возведения числа х в степень n = 152.
writeln(‘Введите число, которое нужно возвести в степень: ‘);
Презентация по информатике на тему «Алгоритмы обработки информации» 10 класс
Ищем педагогов в команду «Инфоурок»
Описание презентации по отдельным слайдам:
АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ ОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ ОБРАЗЕЦ ЗАГОЛОВКА ОБРАЗЕЦ ПОДЗАГОЛОВКА 10 класс Информатика МК
Пример 2 Алгоритм «Нахождение всех простых чисел не больше заданного числа n по методу Эратосфена» Выписать подряд все целые числа от 2 до n (2, 3, 4, …, n). Присвоить переменной p значение 2 (2 – первое простое число). Зачеркнуть в списке числа, кратные p: 2p, 3p, 4p, … Найти первое незачёркнутое число в списке, большее чем p, и присвоить p соответствующее значение. Повторять шаги 3 и 4, пока возможно (пока p2 ≤ n). Незачёркнутые числа и есть все простые числа от 2 до n. Простые числа от 2 до 100 Выполнить 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 МК Комментарии Кнопка Выполнить – демонстрирует работу алгоритма (по шагам)
Пример 1 Исполнитель: человек Объекты алгоритма: ключ, дверь Алгоритм «Закрыть входную дверь ключом» Вставить ключ в замочную скважину. Повернуть ключ два раза на 180 градусов против часовой стрелки. Вынуть ключ из замочной скважины. МК
Правила выполнения блок-схем, внешний вид графических блоков и их назначение определяются стандартом ГОСТ 19.701–90 (ИСО 5807–85) «Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения». Блок-схема СИМВОЛ ФУНКЦИЯ Пуск/остановка. Начало, конец, прерывание процесса обработки данных или выполнения программы Ввод/вывод. Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов (вывод) Процесс. Выполнение операций или группы операций, в результате которых изменяется значение, форма представления или расположение данных Решение. Выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий Модификация. Выполнение операций, меняющих команды или группу команд, изменяющих программу Предопределённый процесс. Использование ранее созданных и отдельно описанных алгоритмов или программ МК
Пример 4 Алгоритм «Возведение числа в натуральную степень (xn)» Запишем n в двоичной системе счисления. Заменим каждую 1 парой букв КХ, а каждый 0 – буквой К. Вычеркнем крайнюю левую пару КХ. Полученная строка, читаемая слева направо, даёт правило быстрого вычисления хn, если букву К рассматривать как операцию возведения результата в квадрат, а букву X – как операцию умножения результата на х. Вначале результат равен х. К К Х К К К х2 х4 х5 х10 х20 х40 X40 Задание. Найти К Х возведение результата в Квадрат К умножение результата на Х Х 1 0 1 0 0 0 40 = 2 МК
Алгоритм – конечная система правил, сформулированных на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и обладает свойствами дискретности, детерминированности, понятности, результативности, конечности и массовости. Исполнитель алгоритма – субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий. Один и тот же алгоритм может быть записан разными способами: на естественном языке, псевдокодом, с помощью блок-схем, на языке программирования и т. д. Теория алгоритмов предоставляет аппарат анализа различных алгоритмов решения одной и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алгоритм. Самое главное МК
Алгоритм состоит из команд. Команда – отдельная инструкция в описании алгоритма. Шаг алгоритма – отдельное действие, которое исполнитель выполняет по команде. Вычислительным процессом, порождённым алгоритмом, называется последовательность шагов алгоритма, пройденных при его исполнении. Сложность алгоритма – количество элементарных шагов (действий) в вычислительном процессе этого алгоритма. Наряду со сложностью важной характеристикой алгоритма является эффективность. Эффективность оценивается количеством элементарных операций, которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения алгоритма. Самое главное МК
Вопросы и задания Задание 1. Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам: Складываются первая и вторая, а также вторая и третья цифры исходного числа. Полученные два числа записываются друг за другом в порядке убывания (без разделителей). Укажите наименьшее число, в результате обработки которого автомат выдаст число 1711. Решение: Единственный способ разбить запись 1711 на два числа – это 17 и 11. Чтобы число было меньше, надо чтобы сумма первой и второй цифр была наименьшей, в данном случае 11. Сумма значений двух последних цифр равна 17. Не трудно заметить, что 17 = 8 + 9 = 9 + 8. Других вариантов нет. Тогда 11 = 2 + 9 = 3 + 8. Выбираем пару, которая даст меньшее число. Ответ: 298. МК Комментарии Задание из демоверсии ЕГЭ-2017. Рекомендуется на этом этапе рассмотреть решение подобных задач + актуальное задание из ЕГЭ текущего года. Решение – по шагам
Вопросы и задания Задание 2. Подсчитайте сложность алгоритма сложения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n, а второе – из m десятичных цифр. Решение: Сложение двух чисел столбиком в случае, если одно из них состоит из n, а другое – из m цифр требует не более max(n, m) сложений и не более max(n, m) запоминаний (в случае перехода через десяток). Т.е. данный алгоритм имеет сложность порядка O(n+m). Выражение показывает только порядок величины – постоянные факторы в нем не учитываются. МК Комментарии По клику/пробелу появляется решение и ответ
8 3 3 3 3 3 Вопросы и задания Задание 1. Есть двое песочных часов: на 3 и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать? Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира. Графический способ решения: МК Комментарии По клику/пробелу появляется графический способ решения (анимация настроена «после/с предыдущим») Также можно в тетрадях выполнить вторую часть задания – разработать СКИ и записать алгоритм
А 2.1 Свойства алгоритма или Фея печет торт
Торт Прага из сметанного бисквита
Как приготовить торт «Прага»? В миске разотрите сметану, яйца и сахар, добавьте погашенную уксусом соду. Смешайте сгущенное какао с мукой, добавьте измельченный миндаль, кардамон. Если нет кардамона, возьмите черный молотый перец. Полученное тесто нужно разделить на три равных части, испечь из них три коржа, а готовые коржи остудить.
Приготовьте крем. Сгущенное какао взбейте со сливочным маслом. Сделайте сироп из сахара, воды и ликера. Пропитайте каждый корж сиропом и промажьте кремом. Верхний корж залейте глазурью. Чтобы сделать глазурь, растворите сахар в молоке, добавьте к нему какао и сливочное масло и варите на медленном огне, около двух минут.
Классический рецепт торта Прага
Приготовление торта Прага начинается с выпекания бисквитных коржей. Для этого необходимо подготовить разъемную форму для выпечки диаметром 23-25 см, бумагу для выпекания, а также прогреть духовку до 200°С. Муку смешать с какао-порошком и просеять через сито в большую миску. Аккуратно отделить белки от желтков. Половину сахара взбить с желтками миксером (до тех пор, пока масса не побелеет и не станет однородной). Кстати, чем лучше взбить желтки, тем нежнее получится бисквит.
Белки необходимо взбивать миксером около двух минут, затем добавить к ним сгущенное молоко, вторую половину сахара и сметану, после чего взбивать еще три минуты. Белковую массу добавить во взбитые желтки. Легкими движениями снизу вверх перемешать полученную массу. Обратите внимание – очень важно мешать медленно и в одном направлении.
Добавить смесь муки и какао-порошка. Для этого лучше всего использовать сито: просеивать муку с какао над белково-желточной массой и аккуратно перемешивать снизу вверх. Дно формы выстелить бумагой для выпечки, смазать всю форму сливочным маслом. Перелить в нее тесто и поставить в разогретую духовку на один час.
Испечь бисквит, форму вынуть из духового шкафа и дать постоять минут пять на влажном полотенце. Затем аккуратно снять боковые края формы, отделить бисквитный торт от бумаги. Рекомендуется положить «Прагу» на решетку и оставить на 8 часов. В этом случае один пласт будет легко разрезать на несколько коржей.
Для приготовления крема необходимо подготовить пищевую пленку, а сливочное масло заранее достать из холодильника, чтобы оно было мягким. Желток отделить от белка. Смешать желток с водой, постепенно добавить сгущенное молоко. Поставить массу на средний огонь или на водяную баню и, постоянно помешивая, довести до кипения. Затем огонь нужно уменьшить и подержать массу еще 2-3 минуты до загустения.
Крем снять с огня и продолжать помешивать для равномерного охлаждения массы. После этого накрыть крем пищевой пленкой и оставить охлаждаться. Размягченное сливочное масло необходимо взбить с ванильным сахаром. Порциями добавить охлажденный крем в масло, продолжая его взбивать. Добавить какао-порошок и еще раз взбить.
Бисквит разрезать на три коржа, одинаковых по толщине. Пропитать их водкой. Собрать торт, промазывая коржи пражским кремом. Верхний корж промазывать сверху не надо. На него нанести тонким слоем джем. Шоколад растопить на водяной бане, добавить сливочное масло, хорошо перемешать. Полученной шоколадной глазурью смазать верх и бока торта. Готовый торт оставить в холодильнике часов на двенадцать.
Урок 7
§5. Основные сведения об алгоритмах
Содержание урока:
 | САМОЕ ГЛАВНОЕ Вопросы и задания |  |
| 5.3. Понятие сложности алгоритма |  | Материалы к уроку |
САМОЕ ГЛАВНОЕ
Алгоритм — это конечная система правил, сформулированных на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и обладает свойствами дискретности, детерминированности, понятности, результативности, конечности и массовости.
Исполнитель алгоритма — это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий.
Один и тот же алгоритм может быть записан разными способами: на естественном языке, псевдокодом, с помощью блок-схем, на языке программирования и т. д.
Для задачи, имеющей алгоритмическое решение, можно придумать множество различных способов её решения, т. е. алгоритмов. Теория алгоритмов предоставляет аппарат анализа различных алгоритмов решения одной и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алгоритм.
Алгоритм состоит из команд. Команда — это отдельная инструкция в описании алгоритма. Шаг алгоритма — это отдельное действие, которое исполнитель выполняет по команде. Вычислительным процессом, порождённым алгоритмом, называется последовательность шагов алгоритма, пройденных при его исполнении.
Сложность алгоритма — количество элементарных шагов (действий) в вычислительном процессе этого алгоритма. Наряду со сложностью важной характеристикой алгоритма является эффективность. Эффективность оценивается количеством элементарных операций, которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения алгоритма.
Вопросы и задания
1. Перечислите основные свойства алгоритмов и проиллюстрируйте их примерами.
2. Почему кулинарный рецепт приготовления торта нельзя считать алгоритмом? Какими свойствами алгоритма он не обладает?
3. Переформулируйте описание способа проведения перпендикуляра к прямой в заданной точке так, чтобы оно стало алгоритмом.
4. Есть двое песочных часов: на 3 и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать?
Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира.
5. Исполнитель Вычислитель получает на вход целое число х и может выполнять с ним преобразования по алгоритму, состоящему из любого количества команд: 1) прибавить 5; 2) вычесть 2.
Сколько разных алгоритмов, состоящих из пяти команд, можно составить для этого исполнителя? Сколько из них будут приводить к одинаковым результатам для заданного числа х?
6. Как известно, для каждого исполнителя набор допустимых действий всегда ограничен, иначе говоря, не может существовать исполнителя, для которого любое действие является допустимым. Докажите это утверждение, предположив, что такой исполнитель существует.
7. Перечислите известные вам способы записи алгоритмов.
8. Приведите примеры задач и оптимальных способов записи алгоритмов их решения.
9. Исполнитель Автомат получает на вход четырёхзначное число. Это число он преобразует по следующему алгоритму:
1) вычисляется сумма первой и второй цифр числа;
2) вычисляется сумма второй и третьей цифр числа;
3) вычисляется сумма третьей и четвёртой цифр числа;
4) из полученных трёх чисел (сумм) выбирается и отбрасывается одно — не превышающее двух других чисел;
5) оставшиеся два числа записываются друг за другом в порядке неубывания без разделителей.
Так, если исходное число 9575, то, преобразуя его, автомат создаст суммы: 9 + 5 = 14, 5 + 7 = 12, 7 + 5 = 12. Сумма, не превышающая двух других, 12. Оставшиеся суммы: 14, 12. Результат: 1214.
Опишите систему команд этого исполнителя.
Могут ли результатом работы этого исполнителя быть числа 1610, 1010, 1019?
Укажите минимальное и максимальное значения результата работы этого исполнителя.
При обработке некоторого числа х автомат выдаёт результат 1418. Укажите наименьшее и наибольшее значения х, при которых возможен такой результат.
10. Подготовьте краткое сообщение об одном из учёных (А. Тьюринг, Э. Пост, А. Н. Колмогоров, А. А. Марков и др.), внёсших вклад в развитие теории алгоритмов.
11. В чём отличие шага алгоритма от команды алгоритма? Приведите пример.
12. Что такое сложность алгоритма? От чего она зависит в наибольшей степени?
13. Подсчитайте сложность алгоритма перемножения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n, а второе — из m десятичных цифр.
14. Какой алгоритм считается эффективным?
15. Постройте эффективный алгоритм возведения числа х в степень n = 152.
Cкачать материалы урока