^{Самарский Международный Аэрокосмический Лицей}

Материалы по информатике для 10 класса «Программирование»

Алгоритм и его свойства

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

Исполнитель алгоритма — это тот объект или субъект, для управления которым составлен алгоритм.

Система команд исполнителя (СКИ) — это вся совокупность команд, которые исполнитель умеет выполнять.

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

Дискретность- алгоритм состоит из отдельных команд, выполняемых исполнителем

Понятность- алгоритм составляется только из команд, входящих в СКИ исполнителя.

Точность (определенность): каждая команда алгоритма управления определяет однозначное действие исполнителя.

Конечность (или результативность): выполнение алгоритма должно приводить к результату за конечное число шагов.

Алгоритмы работы с величинами

Величина — это отдельный информационный объект, который имеет имя, значение и тип.

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

Величины бывают постоянными и переменными. Постоянная величина (константа) не изменяет своего значения в ходе выполнения алгоритма. Константа может обозначаться собственным значением (числа 10, 3.5) или символическим именем (число п).

Переменная величина может изменять значение в ходе выполнения алгоритма. Переменная всегда обозначается символическим именем (X, A, R5 и т.п.).

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

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

Например: А+В; 2*X-Y; K + L- sin(X).

Команда присваивания - команда исполнителя, в результате которой переменная получает новое значение. Формат команды:

<имя переменной>:=<выражение>

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

Пример 1. Пусть переменная А имела значение 6. Какое значение получит переменная А после выполнения команды: А:= 2 * А - 1.

Решение. Вычисление выражения 2 А - 1 при А = 6 даст число 11. Значит новое значение переменной А будет равно 11.

Пример 2. Написать последовательность команд присваивания, в результате выполнения которых переменные А и В поменяются значениями.

Решение. Для решения этой задачи потребуется еще одна дополнительная переменная С. В следующей таблице приведен алгоритм и таблица исполнения алгоритма для начальных значений А = 3, В = 7.

Алгоритм	А	В	С
	3	7	-
С:=А	3	7	3
А:=В	7	7 .	3
В:=С	7	3	3

Задачи

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

   а)Х:=2	б)Х: = 1.5
   Х:=Х*Х Х:= Х*Х*Х Х:= Х*Х*Х*Х	Х:=2*Х + 1 Y:=X/2 Y:=X + Y Х:=Х – Y

2. Написать алгоритм вычисления по формуле: у = (1 - х2 4- 2,5х3 + х4)2, учитывая следующие ограничения:

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

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

3. Пользуясь ограничениями предыдущей задачи, написать наиболее короткие алгоритмы вычисления: а) у = х8; б) у = х10; в) у = х15; г) у = х19. Постараться использовать минимальное число дополнительных переменных. Выполнить трассировку алгоритмов для х = 2.

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

Команда ввода — команда, по которой значения переменных задаются через устройства ввода (например, клавиатуру). Пример: ввод А -- ввод значения переменной А с клавиатуры компьютера.

Команда вывода: команда, по которой значение величины отражается на устройстве вывода компьютера (например, на экран дисплея).

Пример: вывод X — значение переменной X выводится на экран.

Команда ветвления - разделяет алгоритм на два пути в зависимости от некоторого условия; затем исполнение алгорит­ма выходит на общее продолжение. Ветвление бывает полное и неполное. Выше дано описание ветвления в блок-схемах, ниже на Алгоритмическом языке:

Если <условие> то <серия 1> иначе <серия 2> кв

Если <условие> то <серия> кв

Здесь под серией понимается одна или несколько последовательных команд; кв -- конец ветвления.

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

Цикл с предусловием — цикл, выполнение которого повторяется, пока истинно условие цикла:

Пока <условие>, повторять нц

<тело цикла> кц

Ц икл с параметром — повторное выполнение тела цикла, пока целочисленный параметр пробегает множество всех значений от начального (In) до конечного (Ik):

для i от In до Ik, повторять нц

<тело цикла> кц

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

Р ешение. В алгебраической форме решение задачи выглядит следующим образом:

Исходными данными являются четыре целые величины: а, b, с, d. Результат — два целых числа тип.

алг деление дробей

цел а, b, с, d, m, n

нач ввод а, b, с, d

m:=a*d

n:=b*c

вывод "Числитель=", m

вывод "Знаменатель=", n

кон

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

Пример 4. Даны три вещественных числа А, В, С. Найти наибольшее среди них.

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

Блок схема алгоритма дана ниже.

Пример 5. Дано целое положительное число N. Вычислить факториал этого числа: N! = lx2x3x...xN.

Решение. Задача решается с помощью циклического алгоритма. Составим два варианта алгоритма: с применением цикла с предусловием и цикла с параметром.

алг Факториал 1 цел F, N, R нач ввод N F:=l; R:=l пока R<N, повторять нц F:=FxR R:=R+1 кц вывод "Факториал=",F кон	алг Факториал 2 цел F, N R нач ввод N F:=l для R от 1 до N повторять нц F:=FxR кц вывод "Факториал=", F кон

Блок- схема решения данной задачи:( цикл с параметром)

Задачи.

1. Составить алгоритм вычисления площади треугольника со сторонами a, b, c (a, b, c – вещественные положительные числа).

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

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

4. Периметр треугольника равен Р, длина одной стороны равна А, другой — В. Найти длину третьей стороны.

5. Найти площадь поверхности куба со стороной А.

6. Написать алгоритм нахождения максимального среди четы­рех целых чисел.

7. Написать алгоритм проверки условия: имеются ли среди трех целых чисел два положительных значения?

8. Написать алгоритм проверки условия: могут ли три данных числа быть длинами сторон треугольника?

9. Написать алгоритм проверки условия: лежит ли данная точка с координатами (х,у) в первой четверти координатной плоскости?

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

11. Проверить, является ли четырехугольник со сторонами а, b, с, d ромбом.

12. Определить, является ли треугольник со сторонами а, b, с равнобедренным.

13. Определить, является ли треугольник со сторонами а, b, с равносторонним.

14. Среди чисел а, b, с определить количество отрицательных.

15. Среди чисел а, b, с определить количество положительных.

16. Числа а и b — катеты одного треугольника, end — катеты другого. Определить являются ли эти треугольники равновеликими.

17. Определить, принадлежит ли заданная точка (х,у) плоской фигуре, являющейся кольцом с центром в начале координат, с внутренним радиусом r, и внешним радиусом r1.

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

a) b)

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

a) b)

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

a) b)

^Да

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

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

24. Получить первые N чисел Фибоначчи: а1 = а2 = 1, а3 = a1 + а2 = 2, а4 = а2 + а3 = 3 и т.д.

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

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

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

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

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

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