Алгоритм: свойства, способы записи

1.

Алгоритм
Свойства
Способы записи

2.

Алгоритм – конечная последовательность однозначных
предписаний, исполнение которых позволяет получить решение
задачи, однозначно определяемое исходными данными.
Предписание на выполнение каждого определенного действия
называется командой.
Совокупность команд, которые может выполнить исполнитель,
называется системой команд исполнителя (СКИ).
Примеры алгоритмов:
• кулинарные рецепты,
• инструкция по сборке предметов из деталей конструктора,
• инструкция по эксплуатации бытовой техники,
• правила перехода через дорогу,
• правила пользования телефоном-автоматом,
• алгоритм нахождения наибольшего общего делителя двух
натуральных чисел m и n,
• алгоритм деления отрезка АВ пополам
•…

3.

Свойства алгоритма:
• Массовость.
Алгоритм должен быть пригодным для решения целого класса
однородных задач.
• Понятность.
Алгоритм предназначен для конкретного исполнителя, и
поэтому должен включать только те команды, которые
понятны исполнителю, т.е. входят в СКИ.
• Дискретность.
Алгоритм должен состоять из элементарных неделимых
действий.
• Результативность.
Выполнение алгоритма должно привести к некоторому
результату.
• Конечность.
Исполнение алгоритма должно завершиться за конечное число
шагов.

4.

Способы записи алгоритма
- на алгоритмическом языке (АЯ);
- на языке блок-схем;
- на языке программирования.

5.

Запись алгоритма на алгоритмическом языке
алг. <Название>
нач.
1.
2.
3.
…….
кон.
тело алгоритма –
последовательность команд
понятных исполнителю
Пример.
Дано: катеты прямоугольного треугольника a и b.
Найти: гипотенузу с.
алг. Гипотенуза
нач.
1. Ввод a, b
2. с=корень(a2+b2)
3. Вывод с
кон.

6.

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

7.

начало
a,b
c=корень(a2+b2)
c
конец

8.

Базовые
алгоритмические
структуры

9.

• Следование
• Ветвление
• Цикл

10.

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

11.

Этапы решения задач:
•задание исходных данных (присваивание или ввод);
•реализация вычислений или обработка данных;
•вывод результатов.

12.

Задачи на тему «структура следование»
1. Известна длина окружности, найти площадь круга,
ограниченного этой окружностью.
2. Известны длины сторон прямоугольника. Найти его
периметр и площадь.
3. Найти площадь треугольника, если известны длины
сторон а и b и угол между ними в градусах.
4. Дана длина ребра куба. Найти площадь грани, площадь
полной поверхности и объем этого куба.
5. Дана величина А, выражающая объем информации в
байтах. Перевести А в Кбайты, Мбайты, Гбайты.

13.

1. Известна длина окружности, найти площадь круга,
ограниченного этой окружностью.
1. Ввод l
2. R:=l/(2*π)
3. S:= π*R*R
4. Вывод S

14.

2. Известны длины сторон прямоугольника. Найти его периметр
и площадь.
начало
P:=( a + b)*2
S:= a * b
конец

15.

3. Найти площадь треугольника, если известны длины сторон а и
b и угол между ними в градусах.
начало
x:= x*π/180
S:= a * b* sin(x)/2
конец

16.

4. Дана длина ребра куба. Найти площадь грани, площадь полной
поверхности и объем этого куба.
1. Ввод a
2. S:=a*a
3. S1:=6*S
4. V:=a*a*a
5. Вывод S, S1, V

17.

5. Дана величина А, выражающая объем информации в байтах.
Перевести А в Кбайты, Мбайты, Гбайты.
1. Ввод A
2. K := A / 1024
3. M := K / 1024
4. G := M / 1024
5. Вывод K, M, G

18.

Задачи на тему «структура следование»
6. Вычислить расстояние между двумя точками с
заданными координатами (x1; y1) и (x2; y2).
7. Скорость лодки u км/ч, скорость течения реки v км/ч.
Определить путь пройденный лодкой, если t1 ч она
двигалась по озеру и t2 ч против течения реки.
8. Известны стороны основания, угол между ними (в
градусах) и высота параллелепипеда. Найти объем
параллелепипеда.
9. Используя только операцию «*» найти а8 за 3
операции, а10, а16 за 4.

19.

6. Вычислить расстояние между двумя точками с заданными
координатами (x1; y1) и (x2; y2).
начало
AB:= sqrt((x1-x2)2+(y1-y2)2)
конец

20.

7. Скорость лодки u км/ч, скорость течения реки v км/ч.
Определить путь пройденный лодкой, если t1 ч она двигалась по
озеру и t2 ч против течения реки.
1. Ввод u, v, t1,t2
2. S1 := u*t1
3. S2 := (u-v)*t2
4. S := S1+S2
5. Вывод S

21.

8. Известны стороны основания, угол между ними (в градусах) и
высота параллелепипеда. Найти объем параллелепипеда.
начало
x:= x*π/180
S:= a * b* sin(x)
V:= S*h
конец

22.

9. Используя только операцию «*» найти а8 за 3 операции, а10, а16
за 4.
1. Ввод a
1. Ввод a
2. a := a*a
3. a := a*a
4. a :=a*a
5. Вывод a
a:= a *a
b:= a *a
2. a := a*a
3. a := a*a
4. a :=a*a
a:= b *a
5. a :=a*a
a:= a*b
6. Вывод a

23.

Запись алгоритма на языке
программирования
Язык программирования
Питон

24.

Python интерпретируемый высокоуровневый язык программирования
общего назначения с динамической строгой типизацией и
автоматическим управлением памятью
Стандартная библиотека включает большой набор полезных
переносимых функций, начиная с возможностей для работы с
текстом и заканчивая средствами для написания сетевых
приложений.
Дополнительные
возможности,
такие
как
математическое моделирование, работа с оборудованием,
написание веб-приложений или разработка
игр, могут
реализовываться посредством обширного количества сторонних
библиотек, а также интеграцией библиотек, написанных на Си или
C++, при этом и сам интерпретатор Python может интегрироваться в
проекты, написанные на этих языках

25.

Программа - алгоритм, записанный на языке программирования.
Язык программирования – это искусственно созданный
формальный язык для управления компьютером.
Алфавит – это фиксированный набор символов, которые
разрешено использовать для составления текста программы на
языке программирования.
Алфавит языка Питон:
- латинские буквы A … Z, a … z;
- цифры 0, 1 .. 9;
- знаки арифметических операций (+, -, *, /);
- знаки операций отношения (<, >=, >, <=, ==, !=);
- разделители и прочие символы . , ; : $ # ( ) [ ] { } ‘
- …

26.

Синтаксис – это система правил определяющих
допустимые конструкции языка
print (<список идентификаторов через «,»>)
Семантика (в переводе с греческого этот термин
означает "смысл") – это система правил однозначного
толкования отдельных конструкций языка
Отдельная команда языка программирования
называется оператором
Упорядоченная последовательность операторов
образует программу
Для отделения операторов друг от друга
используются специальные разделители

27.

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

28.

Для обращения к переменным используются имена
(идентификаторы).
Правила записи имени переменной:
- может содержать латинские буквы, цифры, знак «_»
- обязательно начинается с буквы или «_»;
- нельзя использовать в качестве имен переменных
зарезервированные слова (обозначения операторов и
функций);
- строчные и прописные буквы различаются

29.

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

30.

Функция задает процедуру определения значения,
зависящего от некоторых аргументов
Основные математические функции
pi — возвращает число π
sin(a) – возвращает синус угла заданного в радианах;
cos(a) - возвращает косинус угла заданного в радианах;
ln(a) – возвращает натуральный логарифм числа (a>0);
exp(a) – возвращает еa;
sqrt(a) – возвращает корень квадратный из числа (a>=0);
abs(a) – возвращает модуль числа;
floor(a) — округление «вверх»;
ceil(a) — округление «вниз»;
Подключение модуля: import math (math.pi, mats.cos()...)
from math import* (pi, cos(), sqrt() ...)

31.

Записать выражения по правилам языка
программирования Паскаль
2
3
a +b
2ab
=(a*a+b*b*b)/(2*a*b)
2
(x− y ) +xy
=((x-y)*(x-y)+x*y)/(x+y-x*y)
x+y− xy
√a − b =sqrt(a*a-b*b*b*b) / sin(a/2)
2
a
sin
2
4

32.

Записать выражения по правилам языка
программирования Паскаль
| ax− tgx | √3ax =abs(a*x-sin(x*x)/cos(x*x))*sqrt(3*a*x)
2
2x− 5 yz
2 =(2*x-5*y*z)/abs(x-y)-2*(sin(x))**2
− 2sin x
| x− y|
√a− √ab− 4a =sqrt(a-(a*b-4*a)**(1/3))/
3
5
3
(a− b) − (a+b)
((a-b)**5-(a+b)**3)

33.

Типы величин
Простые
одной величине соответствует
одно значение
Структурированные
одной величине соответствует
несколько значений
(целый, вещественный,
логический, символьный)
(массивы, строки, файлы)
Тип величины определяет:
- диапазон возможных значений величины;
- набор допустимых операций;
- объем занимаемой памяти.

34.

Стандартный набор простых типов
• Целый
целые числа в некотором диапазоне
*, //, %, +, -, операции отношения
беззнаковый 0..2k-1
знаковый
-2k-1..2k-1-1
• Вещественный
целые и дробные числа в некотором диапазоне
*, /, +, -, операции отношения
формат с плавающей точкой
±M ±n ; 0.1≤ M<1
(знак, мантисса, порядок, знак порядка)
• Логический
True, False
операции отношения, логические операции (not, and, or)
1 байт

35.

Типы величин в языке программирования Питон
Тип
Название
Диапазон
Пример
целый
int
Целые числа
125
Ограничение — -258
объем ОП
вещественный
float
Дробные числа
Ограничение —
объем ОП
строковый
str
логический
bool
25.74
0.14
21.0
-14.254
47.58e-2
'word'
Символы
таблицы Unicod '123'
'S='
True False
True
False

36.

Основные операторы
Оператор присваивания
Служит для изменения значения переменной
<Имя_переменной>= <выражение>

37.

Основные операторы
Оператор вывода данных на экран
print(список выводимых величин через «,»)
Текстовые константы записываются в ‘’
Пример: print(‘S=‘, S)

38.

Основные операторы
Оператор ввода данных,
служит для ввода значений с клавиатуры.
input()
Пример:
a = input()
a = int(input())

39.

Задачи на тему «структура следование»
1. Вычислить расстояние между двумя точками с
заданными координатами (x1; y1) и (x2; y2).
2. Используя только операцию «*» найти а8 за 3
операции, а10, а16 за 4.
3. Дано двузначное число. Найти:
• число десятков в нем
• число единиц в нем
• сумму цифр числа
• произведение цифр числа

40.

Задачи на тему «структура следование»
1. Вычислить расстояние между двумя точками
с заданными координатами (x1; y1) и (x2; y2).

41.

2. Используя только операцию «*» найти а8
за 3 операции, а10, а16 за 4.

42.

3. Дано двузначное число. Найти:
• число десятков в нем

43.

3. Дано двузначное число. Найти:
• число единиц в нем

44.

3. Дано двузначное число. Найти:
• сумму цифр числа

45.

3. Дано двузначное число. Найти:
• произведение цифр числа

46.

4. Дано двузначное число. Получить число,
образованное перестановкой цифр числа.

47.

Задачи для самостоятельного решения
на тему «структура следование»
5. Дано время в секундах. Представить его в виде
h:m:s
6. Дано расстояние в сантиметрах. Найти число
полных метров в нем.
7. Дано расстояние в метрах. Перевести его в см, км.
Решение оформить в текстовом документе, с
указанием формулировки задания

48.

5. Дано время в секундах. Представить его в виде
h:m:s
a = int(input('Введите время в секундах: '))
s = a % 60 #27000 % 60 = 0
a = a // 60 #27000 // 60 = 450
m = a % 60 #450 % 60 = 30
a = a // 60 #450 // 60 = 7
h = a % 60 # 7 % 60 = 7
print(h,':',m,':',s)