semakin Основы программирования / Семакин_Основы программирования
Входным языком такого исполнителя является язык програм мирования Паскаль.
Независимо от того, на каком языке программирования будет написана программа, алгоритм решения любой задачи на ЭВМ может быть составлен из команд:
• обращения к вспомогательному алгоритму;
Для описания алгоритмов в дальнейшем мы будем использо вать блок-схемы и учебный алгоритмический язык, применяемый в школьном курсе информатики.
1.2. Линейные вычислительные алгоритмы
Основным элементарным действием в вычислительных алгорит мах является присваивание значения переменной величине. Если значе ние константы определено видом ее записи, то переменная вели чина получает конкретное значение только в результате присваи вания. Присваивание может осуществляться двумя способами: с помощью команды присваивания и с помощью команды ввода.
Рассмотрим пример. В школьном учебнике математики правила деления обыкновенных дробей описаны так:
1. Числитель первой дроби умножить на знаменатель второй дроби.
2. Знаменатель первой дроби умножить на числитель второй дроби.
3. Записать дробь, числитель которой есть результат выполне ния пункта 1, а знаменатель — результат выполнения пункта 2.
В алгебраической форме это выглядит следующим образом:
Построим алгоритм деления дробей для ЭВМ. В этом алгоритме сохраним те же обозначения для переменных, которые использо ваны в записанной выше формуле. Исходными данными являются
целочисленные переменные а, Ь, с, d. Результатом — также целые величины тип. Блок-схема и текст алгоритма на учебном алго ритмическом языке приведены ниже (в дальнейшем для краткос ти будем обозначать учебный алгоритмический язык буквами АЯ).
алг Деление дробей
Формат команды присваивания следующий:
Знак «:=» нужно читать как «присвоить».
Команда присваивания обозначает следующие действия, вы полняемые компьютером:
1. Вычисляется выражение.
2. Полученное значение присваивается переменной.
В приведенном выше алгоритме присутствуют две команды при сваивания. В блок-схемах команда присваивания записывается в пря моугольнике. Такой блок называется вычислительным блоком.
В описаниях алгоритмов необязательно соблюдать строгие пра вила в записи выражений. Их можно писать в обычной математи ческой форме. Это еще не язык программирования со строгим синтаксисом.
В приведенном алгоритме присутствует команда ввода:
ввод a , b , c , d
В блок-схеме команда ввода записывается в параллелограмме — блоке ввода-вывода. При выполнении данной команды процес сор прерывает работу и ожидает действий пользователя. Пользо ватель должен набрать на устройстве ввода (клавиатуре) значе ния вводимых переменных и нажать на клавишу ввода Enter. Зна чения следует вводить в том же порядке, в каком соответствующие переменные расположены в списке ввода. Обычно с помощью команды ввода присваиваются значения исходных данных, а команда присваивания используется для получения промежуточ ных и конечных величин.
Полученные компьютером результаты решения задачи долж ны быть сообщены пользователю. Для этих целей предназначена команда вывода:
С помощью этой команды результаты выводятся на экран или на устройство печати на бумагу.
Поскольку присваивание является важнейшей операцией в вы числительных алгоритмах, обсудим ее более подробно.
Рассмотрим последовательное выполнение четырех команд при сваивания, в которых участвуют две переменные величины а и Ь.
В приведенной ниже таблице напротив каждой команды при сваивания указываются значения переменных, которые устанав ливаются после ее выполнения.
Этот пример иллюстрирует три основных свойства команды присваивания:
• пока переменной не присвоено значение, она остается неопре деленной;
• значение, присвоенное переменной, сохраняется в ней вплоть до выполнения следующей команды присваивания этой переменной;
• новое значение, присваиваемое переменной, заменяет ее пре дыдущее значение.
Рассмотрим один очень полезный алгоритм, который прихо дится часто использовать при программировании. Даны две вели чины: Хм Y. Требуется произвести между ними обмен значениями. Например, если первоначально было Х= 1, Y= 2, то после обме на должно стать: Х=2, У= 1.
Хорошей моделью для решения этой задачи является следую щая ситуация: имеются два стакана — один с молоком, другой с водой. Требуется произвести обмен их содержимым. Всякому ясно, что в этом случае нужен дополнительный третий пустой стакан. Последовательность действий будет следующей: 1) перелить из первого стакана в третий; 2) перелить из второго в первый; 3) перелить из третьего во второй. Цель достигнута!
По аналогии для обмена значениями двух переменных нужна третья дополнительная переменная. Назовем ее Z. Тогда задача
обмена решается последовательным выполнением трех команд
Аналогия со стаканами не совсем точна в том смысле, что при переливании из одного стакана в другой первый становится пус тым. В результате же присваивания (Х:= Y) переменная, стоящая справа (У), сохраняет свое значение.
Алгоритм для деления дробей имеет линейную структуру. В нем все команды выполняются в строго однозначной последователь ности, каждая по одному разу. Линейный алгоритм составляется из команд присваивания, ввода, вывода и обращения к вспомога тельным алгоритмам (об этом позже).
При описании алгоритмов в блок-схемах типы, как правило, не указываются (но подразумеваются). В алгоритмах на АЯ для всех переменных типы указываются явно. Описание типов переменных производится сразу после заголовка алгоритма. В них используют ся следующие обозначения типов: цел — целый тип, вещ — веще ственный тип, лит — символьный (литерный) тип, лог — логи ческий тип. В алгоритме для деления дробей для всех переменных указан целый тип.
1.3. Ветвления и циклы в вычислительных алгоритмах
Составим алгоритм решения квадратного уравнения
Задача хорошо знакома из математики. Исходными данными здесь являются коэффициенты а, Ь, с. Решением в общем случае будут два корня х, и х 2 , которые вычисляются по формуле:
Все используемые в этой программе величины вещественного
алг корни квадратного уравнения вещ а,Ь,с,xl,x2,d
нач ввод а,Ь,с d:=b 2 -4ac xl:=(-b+>/d ) / (2а)
Слабость такого алгоритма видна невооруженным глазом. Он не обладает важнейшим свойством, предъявляемым к качественным алгоритмам, — универсальностью по отношению к исходным дан ным. Какими бы ни были значения исходных данных, алгоритм дол жен приводить к определенному результату и завершать работу.
Результатом может быть число, но может быть и сообщение о том, что при определенных данных задача решения не имеет. Не допустимы остановки в середине алгоритма из-за невозможности выполнить какую-то операцию. Упомянутое свойство в литерату ре по программированию называют результативностью алгоритма (в любом случае должен быть получен какой-то результат).
Чтобы построить универсальный алгоритм, сначала требуется тщательно проанализировать математическое содержание задачи.
Цикл с предусловием. Как блок — схемой и на алгоритмическом языке представляется команда цикл с предусловием?
Вначале предусловие (с выходом) , потом работа, потом переход на предусловие.
Похожие вопросы
Ваш браузер устарел
Мы постоянно добавляем новый функционал в основной интерфейс проекта. К сожалению, старые браузеры не в состоянии качественно работать с современными программными продуктами. Для корректной работы используйте последние версии браузеров Chrome, Mozilla Firefox, Opera, Microsoft Edge или установите браузер Atom.
Как блок-схемой и на алгоритмическом языке представляется команда цикла с предусловием
Учебник по Информатике 9 класс Семакин
Как блок-схемой и на алгоритмическом языке представляется команда цикла с предусловием? Блок-схема цикла с предусловием:
Цикл с предусловием на алг. языке:
пока повторять
нц
кц
Уроки 42 — 45
Циклы на языке Паскаль
(§ 15. Программирование циклов)
Разработка программ c использованием цикла с предусловием
Проследим все этапы технологии решения задачи на компьютере на примере конкретной задачи.
1. Постановка задачи. Дано N кубиков, на которых написаны разные буквы. Сколько различных N-буквенных слов можно составить из этих кубиков (слова не обязательно должны иметь смысл)?
Искомую целочисленную величину обозначим буквой F. Тогда постановка задачи выглядит так:
2. Математическая формализация. Получим расчетную формулу. Сначала рассмотрим несколько конкретных примеров. Имеются два кубика с буквами «И» и «К». Ясно, что из них можно составить два слова:
ИК КИ
Добавим к ним третью букву, «С». Теперь число разных слов будет в три раза больше предыдущего, т. е. равно 6:
ИКС КИС ИСК КСИ СКИ СИК
Если добавить четвертую букву, например «А», то число слов возрастет в четыре раза и станет равным 24:
КИСА КИАС КСИА КСАИ КАИС КАСИ ИКСА ИКАС ИСКА ИСАК ИАКС ИАСК СКИА СКАИ СИКА СИАК САКИ САИК АКИС АКСИ АИКС АИСК АСКИ АСИК.
Попробуйте записать все варианты слов из пяти букв: И, К, С, А, У. Сделать это непросто. Ясно лишь, что количество таких слов будет в пять раз больше 24, т. е. равно 120. Из шести букв можно составить 720 различных слов. С ростом числа букв число слов быстро растет. Например, для 10 букв получается 3 628 800 слов.
Подобные задачи решает раздел математики, который называется комбинаторикой.
Количество различных комбинаций из N предметов, получаемых изменением их порядка, называется числом перестановок. Это число выражается функцией от N, которая называется факториалом и записывается так:
Читается: «эн факториал». Для любого натурального N значение N! вычисляется как произведение последовательности натуральных чисел от 1 до N. Например:
1! = 1; 2! = 1*2 = 2; 3! = 1*2*3 = 6; 4! = 1*2*3*4 = 24; 5! = 1*2*3*4*5 = 120 и т. д.
Теперь вернемся к формулировке задачи. Если N обозначает количество букв, а F — количество слов из этих букв, то расчетная формула такова:
3. Построение алгоритма. Поскольку алгоритм должен быть независимым от данного значения N, то его нельзя сделать линейным. Дело в том, что для разных N надо выполнить разное число умножений. В таком случае с изменением N линейная программа должна была бы менять длину.
Алгоритм решения данной задачи будет циклическим. С циклическими алгоритмами вы уже познакомились, работая с графическим исполнителем.
Цикл — это команда исполнителю многократно повторить указанную последовательность команд.
Рассмотрим блок-схему на рис. 2.7 и алгоритм на АЯ.
Здесь применена знакомая вам алгоритмическая структура «цикл с предусловием». Выполняется она так: пока истинно условие цикла, повторяется выполнение тела цикла.
Тело цикла составляют две команды присваивания, заключенные между служебными словами нц и кц. Условие цикла — это отношение R
В данном алгоритме переменная R выполняет роль множителя, значение которого меняется от 1 до N через единицу. Произведение накапливается в переменной F, начальное значение которой равно 1. Цикл заканчивается, когда R становится равным N + 1. Это значение в произведение уже не попадет.
Для проверки правильности алгоритма построим трассировочную таблицу (для случая N = 3):
Из этой таблицы хорошо видно, как менялись значения переменных. Новое значение, присвоенное переменной, стирает ее старое значение (в данной таблице не повторяется запись значения переменной, если оно не изменяется; в таком виде таблица менее загромождена числами). Последнее значение F равно 6. Оно выводится в качестве результата. Очевидно, что результат верный: 3! = 6.
4. Составление программы. Чтобы составить программу решения нашей задачи, нужно научиться программировать циклы на Паскале. Основной циклической структурой является цикл с предусловием (цикл-пока). С помощью этой структуры можно построить любой циклический алгоритм. Оператор цикла с предусловием в Паскале имеет следующий формат:
while do
Служебное слово while означает «пока», do — «делать», «выполнять».
Оператор, стоящий после слова do, называется телом цикла. Тело цикла может быть простым или составным оператором, т. е. последовательностью операторов между служебными словами begin и end.
А теперь запрограммируем на Паскале алгоритм решения нашей задачи (добавив к нему организацию диалога).
Снова бросается в глаза схожесть алгоритма на АЯ и программы на Паскале. Обратите внимание на то, что в Паскале нет специальных служебных слов для обозначения конца цикла (так же как и конца ветвления). Во всех случаях, где это необходимо, используются слова begin и end.
Что такое отладка и тестирование программы
5. Отладка и тестирование. Под отладкой программы понимается процесс испытания работы программы и исправления обнаруженных при этом ошибок. Обнаружить ошибки, связанные с нарушением правил записи программы на Паскале (синтаксические и семантические ошибки), помогает используемая система програм- жирования. Пользователь получает сообщение об ошибке, исправляет ее и снова повторяет попытку исполнить программу.
Поиск алгоритмических ошибок в программе производится с помощью тестирования.
Тест — это конкретный вариант значений исходных данных, для которого известен ожидаемый результат. Прохождение теста — необходимое условие правильности программы. На тестах проверяется правильность реализации программой запланированного сценария.
Нашу программу, например, можно протестировать на значении N = 6. На экране должно получиться:
Введите число букв: 6
Из 6 букв можно составить 720 слов.
6. Проведение расчетов и анализ полученных результатов — этот этап технологической цепочки реализуется при разработке практически полезных (не учебных) программ. Например, программы «Расчет прогноза погоды». Ясно, что ею будут пользоваться длительное время, и правильность ее работы очень важна для практики. А поэтому в процессе эксплуатации эта программа может дорабатываться и совершенствоваться.
Коротко о главном
Последовательность этапов работы программиста при решении задачи на компьютере называется технологией решения задачи на компьютере.
Таких этапов шесть:
1) постановка задачи;
2) математическая формализация;
3) построение алгоритма;
4) составление программы на языке программирования;
5) отладка и тестирование программы;
6) проведение расчетов и анализ полученных результатов.
Количество различных комбинаций из N предметов, получаемых изменением их порядка, называется числом перестановок. Число перестановок равно N! (N факториал):
Любой циклический алгоритм может быть построен с помощью команды «цикл-пока» (цикл с предусловием).
Формат оператора цикла с предусловием в Паскале: while do
Оператор, составляющий тело цикла, может быть простым или составным.
Вопросы и задания
1. Как блок-схемой и на алгоритмическом языке представляется команда цикла с предусловием?
2. Как программируется цикл с предусловием на Паскале?
3. Почему алгоритм вычисления N! должен быть циклическим?
4. Из каких этапов состоит работа программиста по решению задачи на компьютере?
5. Что такое математическая формализация задачи?
6. Что такое отладка программы? Что называется тестом?
7. Составьте алгоритм вычисления суммы всех натуральных чисел, не превышающих заданного натурального числа N. Проверьте алгоритм трассировкой. Напишите программу на Паскале.
8. Дано целое число X и натуральное N. Составьте алгоритм вычисления Xм. Проверьте алгоритм трассировкой. Напишите программу на Паскале.
Следующая страница Дополнительный материал к главе II (§§ 8 — 21). Программа перевода двоичного числа в десятичную систему счисления