Алгоритмы: свойства, основные конструкции и блоки.

Линейные алгоритмы.

Материальное обеспечение: компьютерный класс № 412 с набором оборудования для проведения лабораторных занятий.

Теоретический материал

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

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

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

Понятность - составляя запись алгоритма для определенного исполнителя, можно использовать лишь те команды, которые имеются в его системе команд.

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

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

Массовость -  алгоритмы должен обеспечивать решение не одной конкретной задачи, а некоторого класса задач данного типа.

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

1. Словесно-формульное описание.

2. Графическое описание – блок-схема. Блок-схема – это ориентированный граф, указывающий порядок исполнения команд алгоритма.

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

Начало (конец) алгоритма                                      

 

Выполнение операций,

изменяющих команды

(группы команд)

Вызов вспомогательного алгоритма

 

Ввод-вывод данных

 

Проверка условия 

 

 

     a) следование (композиция)     б) ветвление (альтернатива)

S2

S1

S2

S1

                                                                      T            F

 

    

 

                       O                                                                                 

 

       в) цикл с предусловием                          г) цикл с постусловием

 

                                                                                                                                 O

                                                 O

 

                                        T

                               

                                                       F                                                            

                                                                                                                          T

 

                                                                                                                                     F

 

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

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

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

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

Последовательность записи алгоритма:

АЛГ название алгоритма

НАЧ

       Серия команд алгоритма

КОН

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

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

ЕСЛИ условие                  ЕСЛИ условие

    ТО серия 1                      ТО серия

     ИНАЧЕ серия 2   ВСЕ 

ВСЕ

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

ВЫБОР

  ПРИ условие 1:            серия 1

  ПРИ условие 2:            серия 2

  …

  ПРИ условие N:           серия N

  ИНАЧЕ     серия N+1

ВСЕ

  Алгоритмы, при исполнении которых отдельные команды или серии команд выполняются неоднократно, называют циклическими. Для организации циклических алгоритмов в алгоритмическом языке используют специальную составную команду цикла. Она соответствует блок-схемам типа «итерация» и может принимать следующий вид:

  ПОКА условие                                              НЦ

            НЦ                                                                      серия

                        серия                                                     ДО условие

            КЦ                                                            КЦ

Практическое задание 1:

1. Определить конечные значения переменных X и Y в результате выполнения следующих операций:                  

а) Х:=2

Х:= Х * Х

Х:= Х +6

Х:=Х*Х*Х

У:= Х +600

 

б) Х:=5

Х:=2* Х +2

У:= Х /2

У:= Х + У

Х:= У – Х

 

2. Написать алгоритм вычисления по формуле: У =(1– Х ²+2* Х ³)², учитывая следующие ограничения:

а) пользоваться можно только операциями сложение, вычитание и умножение;

б) каждое выражение может содержать только одну арифметическую операцию.

3. Пользуясь ограничениями предыдущей задачи, написать алгоритмы вычисления:

а) у = х ⁸; б) у = х ¹⁰; в) у = х ¹⁵; г) у = х ¹⁹.

4. Записать алгоритм перемещения значений между переменными А и В.

 

5. Записать алгоритм перемещения значений между переменными А, В и С:

 

6. Записать алгоритм перемещения значений между переменными А, В, С и D.

 

7. Записать алгоритм для решения такой задачи:

Даны кувшины для воды объемом 3л и 8л. Как набрать с их помощью 7л воды, если воду из кувшинов можно выливать, доливать в кувшин, переливать из одного кувшина в другой.

8. Составить алгоритм перевоза с одного берега реки на другой в лодке волка, козы и капусты. Одновременно можно перевозить не более 1-го.

9. Составить алгоритм вычисления площади треугольника со сторонами а, b, с.

10. Длины сторон первого прямоугольника А и В, длина одной стороны второго прямоугольника С. Найти длину D второй стороны второго прямоугольника, если известно, что площадь первого прямоугольника в 6 раз меньше площади второго прямоугольника.

11. Длина стороны треугольника равна А, периметр равен Р, длины двух других сторон равны между собой. Найти эти длины.

12. Даны длины двух сторон треугольника А и В и периметр треугольника Р. Найти длину третьей стороны треугольника.

Вопросы и задания для контроля знаний. 1.Что называют алгоритмом? 2. Какими свойствами обладает алгоритм? 3. Какие способы представления алгоритма вы знаете? 4. Какие алгоритмические конструкции присущи графическому представлению алгоритма? 5. Какие алгоритмические конструкции применяют при представлении алгоритма на алгоритмическом языке? 6. Какой алгоритм называют линейным? Разветвляющимся? Циклическим?

Тема 6 «Составление разветвляющихся алгоритмов»

Цель - формирование практических умений и навыков составления разветвляющихся алгоритмов для решения задач.

План

Разветвляющиеся алгоритмы.

Материальное обеспечение: компьютерный класс № 412 с набором оборудования для проведения лабораторных занятий.

Теоретический материал

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

ЕСЛИ условие               ЕСЛИ условие

    ТО серия 1                      ТО серия

     ИНАЧЕ серия 2   ВСЕ 

ВСЕ

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

ВЫБОР

  ПРИ условие 1:            серия 1

  ПРИ условие 2:            серия 2

  …

  ПРИ условие N:           серия N

  ИНАЧЕ     серия N+1

ВСЕ

   a) следование (композиция); б) ветвление (альтернатива)

                                   полная форма                               краткая форма

 

T                  F                                         T                  F

 

    

 

                         

 

                                                       O                                                                                     

 

 

Практическое задание 1:

1. Составить алгоритм нахождения наибольшего из трех чисел А, В, С (в виде блок-схемы).

2. Составить алгоритм определения кислотности раствора (на алгоритмическом языке).

3. Составить алгоритм проверки условия: могут ли три данных числа быть длинами сторон треугольника (в виде блок-схемы)?

4. Составить алгоритм проверки условия: лежит ли точка с координатами (х; у) в 1 четверти координатной плоскости (в виде блок-схемы)?

5. Составить алгоритм проверки условия: является ли треугольник со сторонами А, В, С равнобедренным (в виде блок-схемы)?

6. Определить, является ли треугольник со сторонами А, В, С равносторонним (на алгоритмическом языке)?

7. Проверить, является ли четырехугольник со сторонами A, B, C, D ромбом (на алгоритмическом языке)?

8. Написать алгоритм нахождения максимального среди четырех целых чисел (в виде блок-схемы).

9. Составить алгоритм проверки условия: имеются ли среди трех целых чисел два положительных значения (в виде блок-схемы).

10. Проверить, принадлежит ли число х интервалам [ а; b ] или [ c; d ].

11. Построить график функции у (х), заданной алгоритмом:

а) если х ≤–1            

То у:=1/(х * х)

Иначе

Если х ≤2

То у:= х * х

Иначе у: =4

Все

Все

б) если х < – 0,5

То у:=1/| х |

Иначе

Если х <1

То у:=2

Иначе у:=1/(х –0,5)

Все

Все

 

Вопросы и задания для контроля знаний. 1.Какой алгоритм называется разветвляющимся? 2. Какие формы имеет ветвление в блок-схеме? 3. Какие формы имеет ветвление в алгоритмическом языке?

Тема 7 «Составление циклических алгоритмов»

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

План

Циклические  алгоритмы.

Материальное обеспечение: компьютерный класс № 412 с набором оборудования для проведения лабораторных занятий.

Теоретический материал

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

Для организации циклических алгоритмов в алгоритмическом языке используют специальную составную команду цикла. Она соответствует блок-схемам типа «итерация» и может принимать следующий вид:

ПОКА условие        НЦ                           ДЛЯ I от 1 до N повторять

            НЦ                                   серия        НЦ   

                        серия                   ДО условие       серия

            КЦ                      КЦ                         КЦ

 

а) цикл с предусловием                          б) цикл с постусловием

 

                                                                                                                                                         O

                                                             O

			S1

 

                                           

                                                   T

                                       

                                                   

                                                            F                                                            

                                                                                                                                              T

                                                                                                                                                    F

                                                                                                                                                   

Практическое задание 1:

1. Определить значение переменной S после выполнения алгоритмов:

а) S:=128

для I от 1 до 4 повторять

Нц

S:= S – 3

Кц

б) S:=0

для I от 1 до 2 повторять

нц для j от 2 до 3 повторять

нц

S:= I + j

Кц

Кц

2. Определить значение переменной S после выполнения алгоритмов:

a) S:=l; a:=l

для I от 1 до 3 повторять

нц

S:= S + I *(I +l)* a

а:= а +2

кц

б) для I от 1 до 3 повторять

нц

S:=0

для j от 2 до 2 повторять

нц

S:= I + j

      Кц

Кц

3. Определить значение переменной S после выполнения алгоритмов:

a) S:=0; i:=0; j:=1

пока i <3, повторять

нц

 i:= i +l

S:= S + i * j

Кц

б) I:=1; S:=0

пока I >1, повторять

нц

S:= S +1/ I

I:= I –1

Кц

4. Определить значение переменной S после выполнения алгоритмов:

a) S:=0; i:=l; j: =15

пока i < j, повторять

нц

S:= S + i * j

i:= i +l

j:= j –1

 Кц

б) a:=l; b:=l

пока a + b <10, повторять

нц

а:= а +1

b:= b + a

Кц

S:= a + b

5. Найти сумму первых N натуральных чисел.

6. Найти сумму первых N четных натуральных чисел.

7. Найти сумму первых N нечетных натуральных чисел.

8. Последовательно вводятся N целых чисел. Найти сумму всех положительных из них.

9. Последовательно вводятся N целых чисел. Найти количество всех отрицательных среди них.

10. Получить первые N чисел Фибоначчи: a ₁= a ₂=l; a ₃= a ₁+ a ₂=2; a ₄= a ₂+ a ₃=3 и т.д.

11. Последовательно вводятся N целых чисел. Найти их произведение.

12. Последовательно вводятся N целых чисел. Найти наибольшее из них.

13. Последовательно вводятся N целых чисел. Сосчитать, сколько из них совпадают с первым числом.

14. Последовательно вводятся N целых чисел. Найти разницу между наибольшим и наименьшим из них.

15. Последовательно вводятся N целых чисел. Определить, каких среди них больше: положительных или отрицательных.

16. Вычислить значения функции у = 2* х + 5 при х = 2, 4, 6, 8, 10.

17. Вычислить значения функции у = а + х при х = 1, 4, 7, 10.

 

Вопросы и задания для контроля знаний. 1.Какой алгоритм называется циклическим? 2. Какие формы имеет цикл в блок-схеме? 3. Какие формы имеет цикл в алгоритмическом языке?

 

 

Тема 8 «Основы логики. Логические операции, величины, таблицы истинности»

 

Цель - формирование практических умений и навыков выполнения логических операций и составления таблиц истинности.

План