Лекция 4. Основы алгоритмизации и программирования

Лекция 4. ОСНОВЫ АЛГОРИТМИЗАЦИИ И ПРОГРАММИРОВАНИЯ

Содержание темы:

Моделирование. Этапы решения задачи на компьютере. Понятие алгоритма. Свойства алгоритма. Программа. Язык блок-схем. Алгоритмический язык программирования. Моделирование. Этапы решения задачи на компьютере.

Слово «модель» происходит от латинского слова modulus, что означает «мера», «образец». В широком смысле модель - это аналог, образ какого-либо объекта, процесса или явления, сохраняющий его существенные черты.

Среди всех видов моделей особо выделяются математические. Они описывают объекты, процессы и явления с помощью математических соотношений, формул, уравнений. Как правило, математические модели используются в задачах, требующих вычислений.

КОМПЬЮТЕРНАЯ МОДЕЛЬ – математическая модель, реализованная с помощью программно-аппаратных средств.

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

ЭТАПЫ РЕШЕНИЯ ЗАДАЧИ НА КОМПЬЮТЕРЕ

Этапы решения задач с использованием ПК	Описание
Постановка задачи и ее содержательный анализ	1.  Определить условие задачи: что дано? Что необходимо? Какие данные допустимы? Какие результаты и в каком виде должны быть получены? 2.  Повести содержательный анализ, уточнить цели решения задачи, исходные данные и ограничения на них. 3.  определить, при каких условиях возможно получить требуемые результаты, а при каких – нет. 4.  Определить, какие результаты будут считать правильными.
Выбор метода решения (построение математической модели)	1.  Развернутое содержательное описание задачи заменить ее математической моделью при помощи математических зависимостей. 2.  Обоснованно выбрать метод решения задачи.
Составление алгоритма на основе выбранного метода	При составлении алгоритма учитывать все свойства алгоритма. Неправильный алгоритм – требуемый результат получен не будет. Плохой – процесс решения задачи потребует большого количества времени и/или больших затрат ОП. Хороший алгоритм – решение наиболее эффективно.
Составление программы	Программирование (составление программы) – кодирование составленного алгоритма на одном из языков программирования.
Тестирование и отладка программы	Проверка правильности работы с помощью тестов и исправление обнаруженных ошибок. Отладка – процесс выявления ошибок и неточностей в программе. Тестирование – это один из способов верификации, т. проверки правильности программы.
Выполнение программы, анализ полученных результатов	1.  После отладки из программы убрать все отладочные средства. 2.  После окончательного выполнения программы проанализировать результаты. Возможно изменение самого подхода к решению задачи и повторное выполнение всех этапов.

2.  Алгоритм. Свойства алгоритма.

Понятие алгоритма используется давно. В 820 г. н. э. в Багдаде был написан учебник, в котором были представлены правила выполнения четырех арифметических действия над числами в десятичной системе счисления. Автором учебника был арабский математик Мухаммед бен Мусы аль-Хорезми. От имени аль-Хорезми пошло слово «алгоризм», позже перешедшее в «алгоритм» и понимаемое как совокупность правил, приводящих к решению поставленной задачи. Древнейшему записанному алгоритму уже 3800 лет.

В зависимости от характера занятий, в своей повседневной жизни люди встречаются с различными практическими задачами: приготовление супа, проезд в общественном транспорте, решение уравнений, поиск слова в словаре и т. д. При решении любой подобной задачи человек обращается к продуманным заранее со всеми возможными вариантами предписаниям (инструкциям) о том, какие действия и в какой последовательности должны быть выполнены. В подавляющем большинстве случаев успех любой деятельности человека зависит от степени продуманности действий и их последовательности, возможных вариантов. Именно с целью успешного решения какого-либо определенного класса задач люди вырабатывают системы таких предписаний для использования разными людьми.

Алгоритмом называют понятное и точное предписание (указание) исполнителю совершить последовательность действий, направленных на достижение указанной цели или решение поставленной задачи.

3.  Программа. Язык блок-схем. Алгоритмический язык.

Схема – это графическое изображение алгоритма с помощью отдельных блоков, обозначающих то или иное действие.

 

Алгоритмический язык это система обозначений и правил для единообразной и точной записи алгоритмов и их исполнения.

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

Общие правила алгоритмического языка

Наличие словаря, как и другие языки программирования. Основа словаря - слова, употребляемые для записи команд – эти команды называются в алгоритмическом языке простыми командами. Обычно простая команда выглядит как повелительное предложение русского языка в полной или в сокращенной форме, включая, формулы и др. символические обозначения. Использование служебных слов. Ограниченное число слов, смысл этих слов задан раз и навсегда. При записи алгоритма они подчеркиваются и записываются, как правило, в сокращенной форме. Алгоритм должен иметь название. Для выделения названия алгоритма перед ним записывают служебное слово алг (алгоритм) в конце названия алгоритма ставится(;) За названием алгоритма (с новой строки) записываются его команды. Для указания начала и конца алгоритма его команды заключают в пару служебных слов нач (начало) и кон (конец). Команды записываются последовательно. При записи одной команды, если нужно, можно перейти на другую строчку. Если несколько команд записываются на одной строчке, то они разделяются точкой с запятой (;). Последовательность нескольких команд выполняющихся одна за другой называют серией.

Общий вид алгоритма, записанного на алгоритмическом языке:

алг название алгоритма;

нач

команды алгоритма (серия)

кон

Пример

Записать на алгоритмическом языке следующую инструкцию по использованию междугороднего телефона-автомата:

Снимите трубку. Вставьте карточку. Услышав непрерывный сигнал, наберите код нужного вам города, а затем сразу же – номер нужного вам телефона. Услышав ответ абонента, нажмите кнопку «разговор».

алг использование междугороднего телефона-автомата;

нач снимите трубку

вставьте карточку

ждите появления непрерывного сигнала

наберите код нужного вам города

наберите номер нужного вам телефона

ждите ответ абонента

нажмите кнопку «разговор»

говорите

кон

Величины в алгоритмическом языке

Величины делятся на переменные и постоянные.

Постоянной называется величина, значение которой не меняется в процессе исполнения алгоритма.

Переменной называется величина, значение которой меняется в процессе исполнения алгоритма.

При написании алгоритма для переменных величин вводятся обозначения аналогично обозначения переменных в алгебре такое обозначение переменной величины в алгоритмическом языке наз. именем величины.

В качестве имени величины можно использовать произвольные буквы, буквосочетания и любые слова, поясняющие смысл и назначение величины в алгоритме.

Величины могут быть числовыми и литерными.

Литерные величины – это величины, значениями которых являются слова или текст.

Чтобы указать, какие величины являются аргументами, а какие результатами алгоритма, используют служебные слова арг и рез.

Заголовок алгоритма

При записи алгоритма работы с величинами следуют указания имена аргументов и имена результатов алгоритма. Имя величины не всегда указывает тип величины. Для указания типов величин используются служебные слова: лит (литерные), вещ (вещественные), цел (целые), нат (натуральные). Имена аргументов и результатов перечисляются через запятую.

Название алгоритма вместе с перечнем аргументов и результатов с указанием их типов называется заголовков алгоритма.

Пример

алг название алгоритма (вещ имя величины, вещ имя величины);

арг имя аргумента

рез имя результатов

Типы алгоритмов

Из курса алгебры известны разные типы алгоритмов: линейные, разветвляющиеся и циклические.

Линейный тип. Алгоритм, в котором команды выполняются в порядке их естественного следования друг за другом независимо от каких-либо условий.

Разветвляющийся тип. Алгоритм, в котором условие задачи предусматривает в ходе ее решения возможность выполнения некоторых условий.

Циклический тип. Алгоритм, составленный с использованием многократных повторений одних и тех же действий (циклов).

Линейный тип

Блок-схема			Алгоритмический язык
			алг название алгоритма; нач команды алгоритма (серия) кон

Пример 1. Пешеход шел по пересеченной местности. Его скорость движения по равнине v1 км/ч, в гору — v2 км/ч и под гору — v3 км/ч. Время движения соответственно t1, t2 и t3 ч. Какой путь прошел пешеход?

1. Ввести v1, v2, v3, t1, t2, t3. 2. S1 := v1 * t1. 3. S2 := v2 * t2. 4. S3 := v3 * t3. 5. S := S1 + S2 + S3. 6. Вывести значение S. 7. Конец

алг путь пешехода (вещ v1, v2, v3, t1, t2, t3, s1, s2, s3, s); арг v1, v2, v3, t1, t2, t3; рез s1, s2, s3, s; нач S1:=v1*t1; S2:=v2*t2; S3:=v3*t3; S:=S1+S2+S3; кон

Разветвляющийся тип

Блок схема	Алгоритмический язык
полная развилка	неполная развилка	Полная развилка если условие то серия 1 иначе серия 2 все	Сокращенная форма если условие то серия все

Полная развилка

Пример 1. . Вычислить значение функции

1. Ввести x. 2. Если x£–12, то y:=–x2 3. Если x<0, то y:=x4 4. y := x–2 5. Вывести y 6. Конец

Д/з Найти значение функции

Y=

Циклический тип

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

Команда повторения записывается следующим образом:

Блок схема	Алгоритмический язык
цикл с предусловием (цикл Пока)	цикл с постусловием (цикл До)	Цикл с предусловием пока условие нц серия кц

Литература

1.  Меняйленко по основам информатики и вычислительной техники. Ч. 1. Учебное пособие. – Луганск, 1999. – 222с.

2.  Меняйленко по основам информатики и вычислительной техники. Ч. 2. Учебное пособие. – Луганск, 1999. – 222с.

3.  Меняйленко по основам информатики и вычислительной техники. Ч. 3. Учебное пособие. – Луганск, 1999.

4.  Стецура : 100 задач с решениями. – Донецк: Центр подготовки абитуриентов, 1999.

5.  Turbo Pascal: практикум – СПб: Питер, 2001.

6.  , Марченко в среде Turbo Pascal 7.0. Под ред. – 6-е изд., стереотипное, юбилейное. – К.: ВЕК+, 2000.

7.  Основы информатики в определениях, таблицах и схемах: Справочно-учебное пособие. Под ред. канд. физ.-мат. наук . – Харьков: Ранок, 2000.