Запись алгоритмов в виде блок-схем

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

Алгоритмы и программы

I. Понятие алгоритма

Термин алгоритм происходит от имени математика Аль – Хорезми (9 век н.э.), который дал правила выполнения 4 четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий назван алгоризмом. С 1447 года стали применять термин алгорисмус – это комбинирование 4 операций арифметического исчисления. С 1950 года алгорисмус стал алгорифмом.

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

Пример: найти произведение n - натуральных чисел n! C=4!

C= 1*2*3….*n

1. Полагаем С=1 и переходим к следующему пункту.

2. Полагаем i=1 и переходим к следующему пункту (i – номер числа последовательности).

3. Полагаем с=i*c и переходим к следующему пункту.

4. Проверяем равно ли i числу n. Если i=n то вычисления прекращаем, если i<n, то i увеличиваем на единицу и переходим к пункту 3.

Пример 2: Найдем наименьшее число m из последовательности n чисел.

А1, а2, а3,…., аn (n≠0)

1. Полагаем i=1 и переходим к следующему пункту.

2. Полагаем м=ai и переходим к следующему пункту.

3. Сравниваем i с n. Если i<n то переходим к пункту 4, если i=n процесс поиска останавливаем.

4. Увеличиваем I на единицу и переходим к следующему пункту.

5. Сравниваем Ai c M. Если  М≤ Ai переходим к пункту 3. Если М>Ai переходим к пункту 2.

 

 

3, 4, 2, 5

A1 a2 a3 a4

n=4

1) i=1

2) M=a1=3

3) i<n

4) i=i+1=2

5) a1=M  i=2<n         M=a3=2   i=n

a2=4   i=2+1=3       i=3<n   выход

  M=a2   M=3          i=3+1=4

               a3=2          M=a3=2

               M>a3         a4=5

                                   M<a4

 

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

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

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

 

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

1) Дискретность – это разделение выполнений решаемой задачи на отдельные операции (каждое такое указание называется командой).

2) Определенность или точность алгоритма – каждый алгоритм дает возможность исполнителю не вникать в решение задач, а строго следовать указаниям алгоритма. Совокупность команд, которые содержатся в алгоритме и могут быть, выполнены исполнителем называется системой команд исполнителя.

3) Понятность

4) Результативность или конечность алгоритма, т.е. выполнение алгоритма должно закончится за конечное число шагов.

5) Требование массивности (не необходимое свойство)

III. Формы записи алгоритма

a) Запись на естественном языке.

b) Изображение в виде блок-схемы.

c) Запись на алгоритмическом языке.

 

Запись алгоритмов в виде блок-схем

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

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

Основные элементы блок-схем

№ п/п	Блок (символ)	Наименование	Содержание
1		Блок вычислений	Вычислительные действия или последовательность действий
2		Логический блок	Выбор направления выполнения алгоритма в зависимости от некоторого условия.
3		Блоки ввода/вывода дан ных	1. Общие обозначения ввода /вывода данных вне зависимости от носителя. 2. Вывод данных носителем которых является документ.
4		Начало (конец)	Начало или конец алгоритма, вход или выход из программы.
5		Процесс пользователя (подпрограмма)	Вычисление по стандартной программе или подпрограмме
6		Блок модификации	Функция выполняет действия, изменяющие пункты программы (пример: заголовок цикла)
7		Соединитель	Указание связи прерванного потока информации в пределах одного листа.
8		Межстраничное соединение	Указание связи между информации на разных листах.

                                                                                   

Нахождение минимального числа n

 

                                       

 

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

Основные труктуры:

· Линейные

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

· Циклические

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

 

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

 

 

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

 Если тело цикла расположено после проверки условий (цикл с предусловием) то он называется циклом типа «ПОКА».

 

Если тело цикла расположено перед проверкой условия то цикл называется с постусловием или цикл типа «ДО»

 

 

Задача1: найти произведение двух чисел а и в и вывести результат.

 

 

 

                                               

 

 

Дано два числа А и В найти произведение этих чисел если А≥В и сумму этих чисел в противном случае

Вычислить n! 

 

 

20.09.11

Данные. Понятие типа данных

 

Данные – это любая информация, представлена в формализованном виде и пригодное для обработки информации в алгоритме.

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

Конечными или выходными данными является результат решения задачи.

Данные делятся на переменные и константы.

Переменные - это такие данные, значения которых могут изменяться в процессе выполнения алгоритма.

Константы – это данные, значения которых не меняются в процессе выполнения алгоритма.

Идентификатор представляет собой последовательность букв и цифр начинается всегда с букв.

Типы данных

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

Типы данных делятся на простые (базовые) и структурированные.

К основным базовым типам относят:

1. Целый (integer)- определяет подмножество допустимых значений на множестве целых чисел.

2. Вещественный (real) – определяет подмножество допустимых значений из множества вещественных чисел.

3. Логический (Boolean) – множество допустимых значений (истина-ложь, true-false)

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

 

 

Тип Integer

Задает подмножество целых чисел, мощность которого зависит от размера машинного слова. Если для представления целых чисел в машине используется n-разрядов, то допустимые числа должны удовлетворять условию -2 ≤ x ≤ 2.

Все операции с данными этого типа выполняются точно и соответствуют обычным правилам арифметики.

Для целых чисел может быть введен дополнительный стандартный тип целое без знака (целые положительные числа). Числа лежат в диапазоне 0 ≤ x ≤ 2ⁿ

 

Тип Real

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

 

Тип Boolean

 

Обозначаются стандартными идентификаторами (true-false).

 

Тип Chair

Сюда входит множество печатаемых символов – разделителей в соответствии с кодом ASCII.

 

Пример: Задано число 12345. Как оно будет представлено в различных типах данных в 16-ти разрядной ЭВМ???

Integer: 0011000000111001

Char: 00110001 00110010 ….

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

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

 

Д/з:

1. Сост блок схему: найти сумму и произведение всех элементов числовой последовательности состоящей из n-элементов.

2. Найти максимальный элемент числовой последовательности.

 

27.09.11

Структурированные типы

1. Массив – представляет собой упорядоченную структуру однотипных данных, которые называются элементами массива

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

2. Запись – позволяет объединять в одной переменной элементы произвольных типов.

 

Структура программ

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

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

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

3. Раздел оборудования (среда) – это описание типа ЭВМ процессором. Требования к оперативной и внешней памяти, существенных с точки зрения выполнимой программы.

4. Раздел данных – это идентификация переменных, используемых в программе и их типов.

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

К типовым операторам управления вычислительным процессом относят:

· Организация циклов.

· Ветвление программы.

· Блоки операторов.

· Операторы перевода

Типичные функции:

ü Стандартные

ü Алгебраические

ü Арифметические.

ü Стандартные строчные

ü Нестандартные

Операторы присваивания значений:

§ Пересылка значений переменных, констант, функций, принимающую переменную.

§ Принимающую переменную

§ Вычисление значений арифметической переменной

§ Вычисление значений строчной переменной

§ Вычисление логических переменных.

Д/з учить начиная с поколения (после таблицы)

Подпрограммы

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

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

Глобальные объявления принадлежат программе в целом и доступны как самой программе, так и всем ее подпрограммам.

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

 

Системное программирование

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

К средствам разработки относят:

1. Языки программирования

2. Текстовые редакторы

3. Трансляторы

4. Редакторы связей

5. Библиотеки подпрограмм

6. Утилиты

7. Обслуживающие программы

 

 

Переменные и константы

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

Раздел описания констант начинается со служебного слова const  и содержит перечень всех используемых в программе констант (const Radius=4;).

Раздел объявления переменных начинается со служебного слова var и содержит описание всех переменных (var Radius: integer;).

 

 

С понятием данных тесно связанна понятие типа данных. Тип – это такая характеристика данных, которая с одной стороны задает границы изменения данных, а с другой – определяет множество операции над ними. К простым (базовым) типам данных в языке Паскаль относят:

· Целый

· Вещественный

· Логический

· Символьный

· Перечисляемый

· Тип диапазона

Структурированные типы – описывают наборы однотипных или разнотипных данных. Типы данных, образующих набор в свою очередь могут быть как простыми, так и структурированными. К стандартным структурированным типам относят:

v Массив

v Запись

v Строка

v Множество

v Файл

a) Целый тип данных

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

Пример: вычисление функции факториал y=N¹=1*2*3... *n; y,N –

В паскале определен единственный целый тип данных integer

Множества типов integer

Название типа	Область изменения	Занимаемый размер в байтах	Знак числа типа
integer	От –(2^31) до 2^31-1	2 (4)	Целое со знаком
Shortint	От -128 до 127	1	Целое со знаком
Smallint	ОТ -32768 до 32767	2	Целое со знаком
Longint	От –(2^31) до 2^31-1	4	Целое со знаком
Byte	От 0 до 255	1	Целое без знака
Word	От 0 до 2^16-1	2	Целое без знака
Longworg	От 0 до 4294967295	4	Целое без знака

Var

X:byte

Y:smallint

Z:word

X:=200

Y:40000

Z:=-2

Не корректные значения

Б) логический тип данных

Данные логического типа Boolean в стандарте языка могут принимать одно из двух значений true или false. Переменная или константа этого типа занимает 1 байт.

Пример:

Var

Flag: Boolean;

Flag: true;

False;

Голицына «Основы алгоритмизации и программирования»

 

28.11.11

Выражение – это синтаксическая единица языка, задающая порядок и способ вычисления некоторого значения.

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

 

 

Операции подразделяются:

1. Арифметические

2. Операции отношения

3. Логические

4. Операции с битами информации.

Приоритет операции

Операции	Приоритет	Категория
Not, “+”, “-”(смена знака)	Приоритет 1 (высший)	Унарные
*, /, div, mod, and, Shl, Shr.	Приоритет 2	Умножение
“+”, “-”,or,xor	Приоритет 3	Сложение
=, < >, <= =>, in	Приоритет 4 (низший)	отношение

 

Правила определения старшинства операций:

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

2. Операнд, находящийся между двумя операциями с равными приоритетами связывается с операцией, стоящей слева от него.

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

Структура паскаль программы

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

 

Раздел «имя программы»;

Label «раздел меток»

Const «раздел констант»

Type «раздел типов»

Var «раздел переменных»

Procedure… Function «раздел подпрограммы»

Begin «раздел операторов»

End.

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

Алгоритмы и программы

I. Понятие алгоритма

Термин алгоритм происходит от имени математика Аль – Хорезми (9 век н.э.), который дал правила выполнения 4 четырех арифметических действий в десятичной системе счисления. Процесс выполнения арифметических действий назван алгоризмом. С 1447 года стали применять термин алгорисмус – это комбинирование 4 операций арифметического исчисления. С 1950 года алгорисмус стал алгорифмом.

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

Пример: найти произведение n - натуральных чисел n! C=4!

C= 1*2*3….*n

1. Полагаем С=1 и переходим к следующему пункту.

2. Полагаем i=1 и переходим к следующему пункту (i – номер числа последовательности).

3. Полагаем с=i*c и переходим к следующему пункту.

4. Проверяем равно ли i числу n. Если i=n то вычисления прекращаем, если i<n, то i увеличиваем на единицу и переходим к пункту 3.

Пример 2: Найдем наименьшее число m из последовательности n чисел.

А1, а2, а3,…., аn (n≠0)

1. Полагаем i=1 и переходим к следующему пункту.

2. Полагаем м=ai и переходим к следующему пункту.

3. Сравниваем i с n. Если i<n то переходим к пункту 4, если i=n процесс поиска останавливаем.

4. Увеличиваем I на единицу и переходим к следующему пункту.

5. Сравниваем Ai c M. Если  М≤ Ai переходим к пункту 3. Если М>Ai переходим к пункту 2.

 

 

3, 4, 2, 5

A1 a2 a3 a4

n=4

1) i=1

2) M=a1=3

3) i<n

4) i=i+1=2

5) a1=M  i=2<n         M=a3=2   i=n

a2=4   i=2+1=3       i=3<n   выход

  M=a2   M=3          i=3+1=4

               a3=2          M=a3=2

               M>a3         a4=5

                                   M<a4

 

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

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

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

 

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

1) Дискретность – это разделение выполнений решаемой задачи на отдельные операции (каждое такое указание называется командой).

2) Определенность или точность алгоритма – каждый алгоритм дает возможность исполнителю не вникать в решение задач, а строго следовать указаниям алгоритма. Совокупность команд, которые содержатся в алгоритме и могут быть, выполнены исполнителем называется системой команд исполнителя.

3) Понятность

4) Результативность или конечность алгоритма, т.е. выполнение алгоритма должно закончится за конечное число шагов.

5) Требование массивности (не необходимое свойство)

III. Формы записи алгоритма

a) Запись на естественном языке.

b) Изображение в виде блок-схемы.

c) Запись на алгоритмическом языке.

 

Запись алгоритмов в виде блок-схем

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

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

Основные элементы блок-схем

№ п/п	Блок (символ)	Наименование	Содержание
1		Блок вычислений	Вычислительные действия или последовательность действий
2		Логический блок	Выбор направления выполнения алгоритма в зависимости от некоторого условия.
3		Блоки ввода/вывода дан ных	1. Общие обозначения ввода /вывода данных вне зависимости от носителя. 2. Вывод данных носителем которых является документ.
4		Начало (конец)	Начало или конец алгоритма, вход или выход из программы.
5		Процесс пользователя (подпрограмма)	Вычисление по стандартной программе или подпрограмме
6		Блок модификации	Функция выполняет действия, изменяющие пункты программы (пример: заголовок цикла)
7		Соединитель	Указание связи прерванного потока информации в пределах одного листа.
8		Межстраничное соединение	Указание связи между информации на разных листах.

                                                                                   

Нахождение минимального числа n

 

                                       

 

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

Основные труктуры:

· Линейные

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

· Циклические

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

 

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

 

 

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

 Если тело цикла расположено после проверки условий (цикл с предусловием) то он называется циклом типа «ПОКА».

 

Если тело цикла расположено перед проверкой условия то цикл называется с постусловием или цикл типа «ДО»

 

 

Задача1: найти произведение двух чисел а и в и вывести результат.

 

 

 

                                               

 

 

Дано два числа А и В найти произведение этих чисел если А≥В и сумму этих чисел в противном случае

Вычислить n! 

 

 

20.09.11

Данные. Понятие типа данных

 

Данные – это любая информация, представлена в формализованном виде и пригодное для обработки информации в алгоритме.

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

Конечными или выходными данными является результат решения задачи.

Данные делятся на переменные и константы.

Переменные - это такие данные, значения которых могут изменяться в процессе выполнения алгоритма.

Константы – это данные, значения которых не меняются в процессе выполнения алгоритма.

Идентификатор представляет собой последовательность букв и цифр начинается всегда с букв.

Типы данных

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

Типы данных делятся на простые (базовые) и структурированные.

К основным базовым типам относят:

1. Целый (integer)- определяет подмножество допустимых значений на множестве целых чисел.

2. Вещественный (real) – определяет подмножество допустимых значений из множества вещественных чисел.

3. Логический (Boolean) – множество допустимых значений (истина-ложь, true-false)

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

 

 

Тип Integer

Задает подмножество целых чисел, мощность которого зависит от размера машинного слова. Если для представления целых чисел в машине используется n-разрядов, то допустимые числа должны удовлетворять условию -2 ≤ x ≤ 2.

Все операции с данными этого типа выполняются точно и соответствуют обычным правилам арифметики.

Для целых чисел может быть введен дополнительный стандартный тип целое без знака (целые положительные числа). Числа лежат в диапазоне 0 ≤ x ≤ 2ⁿ

 

Тип Real

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

 

Тип Boolean

 

Обозначаются стандартными идентификаторами (true-false).

 

Тип Chair

Сюда входит множество печатаемых символов – разделителей в соответствии с кодом ASCII.

 

Пример: Задано число 12345. Как оно будет представлено в различных типах данных в 16-ти разрядной ЭВМ???

Integer: 0011000000111001

Char: 00110001 00110010 ….

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

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

 

Д/з:

1. Сост блок схему: найти сумму и произведение всех элементов числовой последовательности состоящей из n-элементов.

2. Найти максимальный элемент числовой последовательности.

 

27.09.11

Структурированные типы

1. Массив – представляет собой упорядоченную структуру однотипных данных, которые называются элементами массива

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

2. Запись – позволяет объединять в одной переменной элементы произвольных типов.