Составьте алгоритм по которому на компьютере будет
Сайт учителя информатики. Технологические карты уроков, Подготовка к ОГЭ и ЕГЭ, полезный материал и многое другое.
Информатика. 9 класса. Босова Л.Л. Оглавление
Ключевые слова:
- постановка задачи
- формализация
- алгоритмизация
- программирование
- отладка и тестирование
Этапы решения задачи на компьютере
Чтобы решать задачи на компьютере, необходимо владеть языком программирования, обладать знаниями в области информационного моделирования и алгоритмизации.
Решение задачи с использованием компьютера включает в себя этапы, показанные на рис. 2.1.
На первом этапе обычно осуществляется постановка задачи, происходит осознание её условия. При этом должно быть чётко определено, что дано (какие исходные данные известны, какие данные допустимы) и что требуется найти в решаемой задаче. Также должны быть чётко выделены существенные свойства рассматриваемого объекта, указаны связи между исходными данными и результатами.
На втором этапе описательная информационная модель формализуется, т. е. записывается с помощью некоторого формального языка.
Для этого требуется:
- понять, к какому классу принадлежит рассматриваемая задача;
- записать известные связи между исходными данными и результатами с помощью математических соотношений;
- выбрать наиболее подходящий способ для решения задачи.
На третьем этапе осуществляется построение алгоритма — чёткой инструкции, задающей необходимую последовательность действий для решения задачи. Алгоритм чаще всего представляется в форме блок-схемы ввиду её наглядности и универсальности.
На четвёртом этапе алгоритм записывается на одном из языков программирования. Вы учитесь записывать программы на языке Паскаль.
На пятом этапе осуществляется отладка и тестирование программы. Этап отладки и тестирования также называют компьютерным экспериментом.
Проверка правильности разработанной программы осуществляется с помощью тестов. Тест — это конкретный вариант значений исходных данных, для которого известен ожидаемый результат.
О правильности разработанной программы свидетельствует также соответствие полученных данных экспериментальным фактам, теоретическим положениям и т. д. При этом может возникнуть необходимость уточнить разработанную математическую модель, полнее учесть особенности изучаемого объекта или процесса. По уточнённой математической модели снова составляется программа, анализируются результаты её выполнения. Так продолжается до тех пор, пока полученные результаты не будут достаточно точно соответствовать изучаемому объекту.
Задача о пути торможения автомобиля
Рассмотрим последовательность прохождения этапов решения задачи на компьютере (см. рис. 2.1) на примере простой задачи.
Водитель автомобиля, движущегося с некоторой постоянной скоростью, увидев красный свет светофора, нажал на тормоз. После этого скорость автомобиля стала уменьшаться каждую секунду на 5 метров. Требуется найти расстояние, которое автомобиль пройдёт до полной остановки.
Первый этап.
- ?0x — начальная скорость;
- ?x — конечная скорость (равна нулю, так как автомобиль остановился);
- ах — ускорение (равно -5 м/с).
Требуется найти: sx — расстояние, которое автомобиль пройдёт до полной остановки.
Второй этап. В данной ситуации мы имеем дело с прямолинейным равноускоренным движением тела. Формула для перемещения при этом имеет вид:
Упростим эту формулу с учётом того, что конечная скорость равна нулю:
При аx = -5 м/с получим:
Третий этап. Представим алгоритм решения задачи в виде блок-схемы:
Четвёртый этап. Запишем данный алгоритм на языке программирования Паскаль:
- program n_1;
- var v0, s: real;
- begin
- writeln(‘Вычисление длины пути торможения автомобиля’);
- write(‘Введите начальную скорость (м/с)»’);
- readln (v0); s:=v0*v0/10;
- writeln (‘До полной остановки автомобиль пройдёт ‘ , s : 8 : 4, ‘ м. ‘)
- end.
Пятый этап. Протестировать составленную программу можно, используя информацию, что при скорости 72 км/ч с начала торможения до полной остановки автомобиль проходит 40 метров.
Выполнив программу несколько раз при различных исходных данных, можно сделать вывод: чем больше начальная скорость автомобиля, тем большее расстояние он пройдёт с начала торможения до полной остановки.
Применяя компьютер для решения задач, всегда следует помнить, что наряду с огромным быстродействием и абсолютной исполнительностью у компьютера отсутствуют интуиция и чувство здравого смысла, и он способен решать только ту задачу, программу решения которой ему подготовил человек.
САМОЕ ГЛАВНОЕ
Этапы решения задачи с использованием компьютера:1) постановка задачи;
2) формализация;
3) алгоритмизация;
4) программирование;
5) компьютерный эксперимент.Для решения задач на компьютере необходимо владеть языком программирования, обладать знаниями в области информационного моделирования и алгоритмизации.
Вопросы и задания к § 2.1. Решение задач на компьютере
1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Какими слайдами вы могли бы дополнить презентацию?
1. Какую структуру имеет алгоритм нахождения большего из двух значений?
2. Почему отношение неравенства можно назвать логическим выражением?
3. В каком случае для числовой переменной следует указывать целый тип, в каком — вещественный?
4. Составьте алгоритм (в виде блок-схемы и на АЯ) нахождения меньшего из двух значений.
5. Составьте алгоритм нахождения наименьшего из трех значений.
6. Для вывода на экран произвольной символьной строки нужно в команде вывода записать эту строку в кавычках. Например, по команде
вывод "ОТВЕТ"
на экран выведется слово ОТВЕТ.
Определите, какая задача решается по следующему алгоритму.
Алг Задача-6
То вывод «отрицательное число»
Иначе вывод «положительное число»
7. Составьте алгоритм, по которому на компьютере будет происходить следующее: в переменную S вводится возраст Саши, в переменную М вводится возраст Маши. В качестве результата на экран выводится фраза «Саша старше Маши» или «Маша старше Саши» (предполагаем, что кто-нибудь из них обязательно старше).
8. Решите предыдущую задачу, учитывая возможность одинакового возраста Саши и Маши. В таком случае может быть получен ответ: «Саша и Маша — ровесники».
9. Составьте алгоритм упорядочения значений трех переменных по возрастанию, т. е. при любых исходных значениях А, B, С отсортируйте их так, чтобы стало: А ≤ В ≤ С. Проверьте алгоритм трассировкой при разных вариантах значений исходных данных.
1. Структуру разветвляющегося алгоритма, так как будет задаваться условие.
2. Можно назвать логическим выражением потому, что резальтатом отношения неравенства/равенства всегда будет true/false (истина/ложь), а не какое-то числовое значение.
3. Целый тип указывается переменным, у которой величина всегда будет целой за всю программу. (Например, числа: 2, 5, 4, 544)
Вещественным типом указываются переменные, которые могут содержать целые или дробные числа. (Например, числа: 2, 5.33, 4.1, 54.4, 123)
1. Как блок-схемой и на алгоритмическом языке представляется команда цикла с предусловием?
2. Как программируется цикл с предусловием на Паскале?
3. Почему алгоритм вычисления N! должен быть циклическим?
4. Из каких этапов состоит работа программиста по решению задачи на компьютере?
5. Что такое математическая формализация задачи?
6. Что такое отладка программы? Что называется тестом?
7. Составьте алгоритм вычисления суммы всех натуральных чисел, не превышающих заданного натурального числа N. Проверьте алгоритм трассировкой. Напишите программу на Паскале.
8. Дано целое число X и натуральное N. Составьте алгоритм вычисления Xn. Проверьте алгоритм трассировкой. Напишите программу на Паскале.
1. Ромб, стрелка вниз если условие сохраняется, стрелка в права, если условие нарушено, и слева приход при следующем цикле.
нц пока условие
3. Потому что необходимо перебрать все значения от 1 до N , совершить N проходов.
4. Решение любой задачи на ЭВМ состоит из нескольких этапов, среди которых основными являются следующие:
постановка задачи
формализация (математическая постановка задачи)
выбор (или разработка) метода решения
разработка алгоритма (алгоритмизация)
составление программы (программирование)
отладка программы
вычисления и обработка результатов
5. Математическая формализация задачи - способ выражения содержания совокупности условий через определенную форму - знаки искусственного языка.
Поиск алгоритмических ошибок в программе производится с помощью тестирования. Тест — это конкретный вариант значений исходных данных, для которого известен ожидаемый результат. Прохождение теста — необходимое условие правильности программы. На тестах проверяется правильность реализации программой запланированного сценария.
7. var sum,n,i:integer;
8. var
x, n, ans:integer;
begin
Readln(x, n);
while (n > 0) do
begin
ans := ans + x;
n:= n - 1;
end;
Writeln(ans);
end.
Приготовление не обладает массовостью, так как порядок приготовления торта, не подойдет к приготовлению салата.
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) x + 5 * 4 - 2 * 1 = x + 18
3) x + 5 * 3 - 2 * 2 = x + 11
4) x + 5 * 2 - 2 * 3 = x + 4
5) x + 5 * 1 - 2 * 4 = x - 3
6) x + 5 * 0 - 2 * 5 = x - 10
Всего разных алгоритмов : 2^5 = 32
Всего алгоритмов с разными выходными данными: 6
Значит, к одинаковым результатам будут приводить: 32 - 6 = 26 алгоритмов
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?
1610 - нет (потому что 2 числа должны идти в порядке возрастания, а 610 в сумме двух чисел мы получить не сможем)
1010 - возможно. Если число будет 5555.
1019 - нет (потому что мы не можем получить в сумме 2 чисел 19 (максимум 18))
Минимальное число, которое можно получить после обработки данным алгоритмом: 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)
В 1936 г. Аланом Тьюрингом для уточнения понятия алгоритма был предложен абстрактный универсальный исполнитель. Его абстрактность заключается в том, что он представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину. Термин «универсальный исполнитель» говорит о том, что данный исполнитель может имитировать любой другой исполнитель. Например, операции, которые выполняют реальные вычислительные машины можно имитировать на универсальном исполнителе. В последствие, придуманная Тьюрингом вычислительная конструкция была названа машиной Тьюринга.
Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.
Что собой представляет машина Тьюринга?
Машина Тьюринга состоит из бесконечной в обе стороны ленты, разделенной на ячейки, и автомата (головки), которая управляется программой.
Программы для машин Тьюринга записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает головка в ячейке (над которой она находится в данный момент), и внутренне состояние головки определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
- Внешний алфавит. Конечное множество (например, А), элементы которого называются буквами (символами). Одна из букв этого алфавита (например, а0) должна представлять собой пустой символ.
- Внутренний алфавит. Конечное множество состояний головки (автомата). Одно из состояний (например, q1) должно быть начальным (запускающим программу). Еще одно из состояний (q0) должно быть конечным (завершающим программу) – состояние останова.
- Таблица переходов. Описание поведения автомата (головки) в зависимости от состояния и считанного символа.
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:
- Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
- Передвигаться на одну ячейку влево или вправо.
- Менять свое внутреннее состояние.
Одна команда для машины Тьюринга как раз и представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Хотя команда может содержать и не все составляющие (например, не менять символ, не передвигаться или не менять внутреннего состояния).
11. В чём отличие шага алгоритма от команды алгоритма? Приведите пример.
В чём отличие шага алгоритма от команды алгоритма
12. Что такое сложность алгоритма? От чего она зависит в наибольшей степени?
Сложность алгоритма – это объем работы, который выполнится некоторым алгоритмом. Зависит от входных значений.
13. Подсчитайте сложность алгоритма перемножения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n, а второе — из m десятичных цифр.
14. Какой алгоритм считается эффективным?
Алгоритм считается эффективным, если потребляемый им ресурс (или стоимость ресурса) на уровне или ниже некоторого приемлемого уровня.
15. Постройте эффективный алгоритм возведения числа х в степень n = 152.
Получим алгоритм решения еще одной задачи: найти наибольшее значение среди трех величин: А, В, С.
Естественно, возникает следующая идея этого алгоритма: сначала нужно найти большее из значений А и B и присвоить его какой-то дополнительной переменной, например D; затем найти большее среди D и С. Это значение можно присвоить той же переменной D.
Решение задачи сводится к двукратному применению уже знакомого алгоритма нахождения большего из двух значений. Блок-схема алгоритма — на рис. 2.5.
Нетрудно догадаться, что «БИТ» обозначает «Большее из трех». В структуре этого алгоритма содержатся два последовательных ветвления: первое — полное, второе — неполное.
Эту же задачу можно решить с помощью алгоритма, имеющего структуру вложенных ветвлений. Его блок-схема приведена в следующем параграфе на рис. 2.6. А вот как выглядят описание этого алгоритма на АЯ и трассировочная таблица при А = 5, B = 7, С = 2.
Коротко о главном
В команде ветвления в качестве условия может использоваться отношение неравенства между величинами.
Числовые величины, которые могут принимать целые и дробные значения, имеют вещественный тип.
Для решения одной и той же задачи можно построить несколько вариантов алгоритмов.
Несколько ветвлений в одном алгоритме могут быть последовательными и вложенными.
Вопросы и задания
1. Какую структуру имеет алгоритм нахождения большего из двух значений?
2. Почему отношение неравенства можно назвать логическим выражением?
3. В каком случае для числовой переменной следует указывать целый тип, в каком — вещественный?
4. Составьте алгоритм (в виде блок-схемы и на АЯ) нахождения меньшего из двух значений.
5. Составьте алгоритм нахождения наименьшего из трех значений.
6. Для вывода на экран произвольной символьной строки нужно в команде вывода записать эту строку в кавычках. Например, по команде
на экран выведется слово ОТВЕТ.
Определите, какая задача решается по следующему алгоритму.
7. Составьте алгоритм, по которому на компьютере будет происходить следующее: в переменную S вводится возраст Саши, в переменную М вводится возраст Маши. В качестве результата на экран выводится фраза «Саша старше Маши» или «Маша старше Саши» (предполагаем, что кто-нибудь из них обязательно старше).
8. Решите предыдущую задачу, учитывая возможность одинакового возраста Саши и Маши. В таком случае может быть получен ответ: «Саша и Маша — ровесники».
9. Составьте алгоритм упорядочения значений трех переменных по возрастанию, т. е. при любых исходных значениях А, B, С отсортируйте их так, чтобы стало: А ≤ В ≤ С. Проверьте алгоритм трассировкой при разных вариантах значений исходных данных.
Следующая страница Уроки 32 - 33. Вопросы и задания
Читайте также: