ОКП (Основы конструирования программ) Контрольная вариант 8

Содержание

Содержание	1
Введение	2
1. Теоретическое задание	3
2. Практическое задание	8
Блок-схема задания №1	9
Блок-схема задания №2	13
Список использованных источников	18

Введение

Алгоритмизация задачи – процесс разработки (проектирования) алгоритма для решения задачи с помощью ЭВМ.

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

1. Теоретическое задание

1.1 Определение алгоритма

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

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

1.2 Свойства алгоритмов

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

Свойства:

Понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.

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

Определенность (точность) – точные сведения о том, что после выполнения каждой очередной команды завершено выполнение алгоритма, либо о том, какая следующая команда должна выполняться, т.е. алгоритм должен предусматривать определенный порядок выполнения действий, так как ЭВМ должно быть указано, какую следующую команду исполнять после завершения текущего указания. В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных.

Массовость — алгоритм должен быть применим к разным наборам исходных данных.

Результативность — завершение алгоритма определёнными результатами.

1.3 Способы описания алгоритма

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

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

Графическое изображение алгоритма широко используется перед программированием задачи вследствие его наглядности, так как зрительное восприятие обычно облегчает процесс написания программы, ее корректировки при возможных ошибках, осмысливание процесса обработки информации.

Графический способ представляет собой изображение логико-математической структуры алгоритма, при которой все этапы обработки данных представляются с помощью определённого набора геометрических фигур (блоков), и имеющих строго определённую конфигурацию в соответствии с характером выполняемых действий.

Задание и запись алгоритма для решения задачи с помощью ЭВМ при программировании ведутся с использованием некоторого алгоритмического языка, который должен описывать алгоритм с любой степенью детализации. Недостатки: громоздкость описания (как следствие низкая наглядность), отсутствие строгой формализации в силу неоднозначности восприятия естественного языка.

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

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

1.4 Базовые структуры блок-схем

Базовые структуры блок-схем строятся на основе элементарных блоков. К базовым структурам относятся:

Линейный алгоритм – набор команд (указаний), выполняемых последовательно во времени друг за другом.

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

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

Вспомогательный (подчиненный) алгоритм (процедура) – алгоритм, ранее разработанный и целиком используемый при алгоритмизации конкретной задачи.

1.5 Структурированные блок-схемы и их построение

1.6 Типы циклов

Циклы делятся на два вида:

С постусловием – цикл, в котором сначала выполняется тело цикла, а потом идет проверка уловия для выполнения следующей итерации.

С предусловием – сначала выполняется проверка условия и только в случае его истинности выполняется тело цикла.

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

1.7 Предопределенные процессы. Рекурсия

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

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

2. Практическое задание

Составить блок-схемы 2-х задач (одна на одномерные массивы, вторая на двумерные) и описать решение каждой задачи на конкретном примере:

Задача №1

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

Задача №2

Найти в матрице первую строку, все элементы которой равны нулю. Все элементы столбца с таким же номером уменьшить вдвое.

Задача № 1. Одномерные массивы

1

Да

Нет

) Основная программа

2) Вспомогательная подпрограмма ввод одномерного массива

inc(i)

i:=1

3) Вспомогательная подпрограмма поиска 1-ого нечетного элемента.

(i≤n) and (flag=false)

i:=1

number:=0

flag:=false

Нет

Да

inc(i)

4) Вспомогательная подпрограмма поиска максимального четного элемента.

i<number

max:=a[1]

i:=2

Да Нет

inc(i)

Задача № 2. Двухмерные массивы

1) Основная программа

Да

Нет

Нет

Да

2) Вспомогательная подпрограмма ввода двухмерного массива

inc(j)

i:=1

inc(i)

j:=1

3) Вспомогательная подпрограмма поиска первой строки, все элементы которой равны 0.

flag:=false

number:=0

(i≤n) and

(flag=false)

i:=1

j≤m

stroka:=true

Да

Нет

inc(j)

j:=1

Да

Нет

inc(i)

4) Вспомогательная подпрограмма уменьшения элементов столбца вдвое.

i:=1

inc(i)

Список использованных источников

	С. И. Бобровский, Delphi 7. Учебный курс, издательский дом «Питер» 2007 г.
	М.А. Сухарев, Turbo Pascal 7.0: теория и практика, изд. Наука и техника, 2004 г.
	В.В. Фаронов, Delphi: программирование на языке высокого уровня, изд. ПИТЕР, 2005 г.
	http://wikipedia.org

17