Презентация на тему Для 9 А класса

свойства

действий, которые должен выполнить исполнитель для решения задачи за

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

Формальные исполнители: не понимают (и не могут понять) смысл команд.

каждая из которых выполняется за конечное время.
Детерминированность (определённость) —

2
шаг 3

2 3 4 5
5 4 3 2
дискретный
объект
25

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

«стоп»
принять команду
выполнить команду
завершить сеанс связи
установить соединение
нц

= "stop";
closeConnection;
программа

// тело программы
end. // конец программы
Комментарии

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

перехода
writeln('2=?'); // на новую строку
writeln('Ответ: 4');
end.
Протокол:

пошел

и найти их сумму.
Протокол:
Введите два целых числа
25

компьютер

пользователь

компьютер считает сам!

2 переменные для хранения 2х чисел
begin
write(‘Введите целое число

{ вычислить их сумму }
{ вывести сумму на

Псевдокод: алгоритм на русском языке с элементами Паскаля.

значение. Значение переменной можно изменять во время работы программы.


a
Значение
Имя

Другой

строчные буквы НЕ различаются
НЕЛЬЗЯ использовать
русские буквы
пробелы
скобки, знаки +, =,

имя не может начинаться с цифры

Какие имена правильные?
AXby R&B 4Wheel Вася “PesBarbos” TU154 [QuQu] _ABBA A+B

переменных:
var a, b, c: integer;
выделение места в памяти
variable –

тип – целые

список имен переменных

предотвращения случайных ошибок

a, b );
Ввод значений двух переменных (через пробел или

:= a + 2;
a := (a + 2)*(b –

a

?

5

5

b

?

5+2

7

a

5

7*4

28

b

7

7+1

8

переменной a и переход на новую строку}
{ вывод текста

{вывод текста и значения переменной c}

write( a );

writeln( a );

writeln( 'Привет!' );

writeln( 'Ответ: ', c );

writeln ( a, '+', b, '=', c );

integer;
begin
read ( a, b );
c

integer;
begin
writeln('Введите два целых числа');
read (

Протокол:
Введите два целых числа
25 30
25+30=55

компьютер

пользователь

выражений:
writeln ( a, '+', b, '=', a+b );
a+b

целый 0..65535
longint целый –2147483648..2147483647
Integer

2 * d;
Приоритет (старшинство):
скобки
умножение и деление
сложение и вычитание
2
1
3
4
5
6

a:= (c

?

3;
var a: single;
0.6666…


div – деление нацело (остаток отбрасывается)
mod –

var a, b, d: integer;
...
d := 85;
b := d div 10; // 8
a := d mod 10; // 5

',');
write(-7 mod 2);
-3
-1
-7 = (-3)*2 + (-1)


-7 = (-4)*2

остаток ≥ 0

);
write( a/3:7:3 );
3.333333E-001
3,333333 ⋅ 10-1 = 0,3333333
всего знаков
в дробной

квадрат числа
sin(x) — синус угла, заданного в радианах
cos(x) —

в лотерею
Случайный выбор:
жеребьевка на соревнованиях
выигравшие номера в лотерее
Как получить

результаты

318458191041
564321
209938992481
458191
938992
малый период (последовательность повторяется через 106 чисел)
Метод середины квадрата

в квадрате

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

зерно

X, Y: double;
...
X:= random; // интервал от 0 до

англ. random – случайный

Целые числа в интервале (0,9):

var K, L: integer;
...
K:= random( 10 ); // интервал от 0 до 9 (<10)
L:= random( 10 ); // это уже другое число!

random*10; { расширение интервала: (0,10) }
X:= random*10 + 5;

var K, X, a, b: integer;
...
K:= random(10) + 5; { (5,14) }
X:= random(b-a+1) + a; { (a,b) }

Целые числа:

их сумму, произведение и среднее арифметическое.
Пример:
Введите три целых

«B»: Ввести с клавиатуры координаты двух точек (A и B) на плоскости (вещественные числа). Вычислить длину отрезка AB.
Пример:
Введите координаты точки A:
5.5 3.5
Введите координаты точки B:
1.5 2
Длина отрезка AB = 4.272

запятую его отдельные цифры.
Пример:
Получено число 123.
Его цифры 1,

выполнения некоторого условия.

полная форма ветвления
Если (iF)
ТО
THEN
ИНАЧЕ
ELSE

M:= a
else
M:= b;
if a

if b > a then
M:= b;
M:= a;

ТО
THEN

Если (iF)

Да +

Нет -

с:= a;
a:= b;
b:= c
end;
4
6
?
4
6
4
a
b
3
2
1
c

старше')
else





if a = b then
writeln('Одного возраста')
else
writeln('Борис старше');
вложенный

Задача: в переменных a и b записаны возрасты Андрея и Бориса. Кто из них старше?

else if a = b then write('=') else write('Б');
if

них.
Пример:
Введите три целых числа:
1 5 4
Максимальное число 5
«B»:

Определить, кто из них старше.
Пример:
Возраст Антона: 15
Возраст

(включительно).
if

and

or

not

Приоритет :
not
and
or, xor
отношения (<, >, <=, >=, =, <>)

xor

исключающее «ИЛИ»

(v >= 25) and (v <= 40)

сложное условие

выводит количество одинаковых чисел в этой цепочке.
Пример:
Введите три

выводит соответствующее ему время года или сообщение об ошибке.

число, не превышающее 120) и выводит этот возраст со

Напишите условие, которое определяет заштрихованную область.

m = 2 then
write('февраль');
...
if m = 12

case m of
1: write('январь');
2: write('февраль');
...
12: write('декабрь');
else write('ошибка');
end;

d:= 28; { невисокосный год }
1,3,5,7,8,10,12: d:=

Число дней в месяце:

Социальный статус:

case v of
0..6: write('дошкольник');
7..17: write('школьник');
else write('взрослый');
end;

begin
writeln('антилопа');

несколько операторов в блоке

действий.

тело цикла


Цикл с постусловием
т.е. сначала описывается
тело цикла а

Циклы бывают

do
begin
A:=A+1;
end;
while
do
begin
end;
A

…
program IvanovTK;
var A,B: integer;
Begin
write(‘Введите А=’);
readln(A);
write(‘Введите В=’);
readln(B);
while A

A

B

A

B

('Привет');
writeln ('Привет');
...
writeln ('Привет');

…
program IvanovTK;
var A,B: integer;
Begin
write(‘Введите А=’);
readln(A);
write(‘Введите В=’);
readln(B);
while A

+

-

увеличить счётчик на 1
счётчик:= 10
пока счётчик > 0

✔

результат операции автоматически сравнивается с нулём!

записи целого положительного числа, записанного в переменную n.
счётчик:= 0
пока

n:= n div 10

счётчик:= счётчик + 1

begin


end;
n:= n div 10;
count:= count + 1

тело цикла
начальное значение

n > 0

условие продолжения

заголовок цикла

begin
writeln('привет');
k:= k + 1;
end;
При известном количестве шагов:
k:=

Зацикливание:

< b do a:= a + 1;
2 раза
a =

a:= 4; b:= 6;
while a < b do a:= a + b;

1 раз
a = 10

a:= 4; b:= 6;
while a > b do a:= a + 1;

0 раз
a = 4

a:= 4; b:= 6;
while a < b do b:= a - b;

1 раз
b = -2

a:= 4; b:= 6;
while a < b do a:= a - 1;

зацикливание

цикла
write('Введите n > 0: ');
read(n);
n > 0
тело цикла
при входе

A и B (0 < A < B) и

«B»: Напишите программу, которая получает два целых числа и находит их произведение, не используя операцию умножения. Учтите, что числа могут быть отрицательными.
Пример:
Введите два числа:
10 -15
10*(-15)=-150

всех чисел Фибоначчи, меньших N. Предусмотрите защиту от ввода

цифр.
Пример:
Введите натуральное число:
12345
Сумма цифр 15.
«B»: Ввести натуральное число

что в его записи есть две одинаковые цифры (не

21 до 210.
 
n:= 2;
while   do
begin
writeln(n);

k:= 1;

k <= 10

k:= k + 1

n:= 2;
for do
begin
writeln(n);
n:= n * 2
end;

k:= 1 to 10

1 do
begin
writeln(n);
n:= n * 2;
end;

3 do a := a+1;
a = 4
a := 1;
for

a = 1

a := 1;
for i:=1 downto 3 do a := a+1;

a = 1

a := 1;
for i:=3 downto 1 do a := a+1;

a = 4

на 133 дают в остатке 125, а при делении

последним цифрам своего квадрата. Например, 252 = 625. Напишите

2 до 1000.
для n от 2 до 1000

число n простое

нет делителей [2.. n-1]: проверка в цикле!

count:= 0;



if count = 0 then

for k:= 2 to n-1 do
if n mod k = 0 then
count:= count + 1;

вложенный цикл

to i do
writeln(i, ' ', k);
1 1
2

do begin
if n mod k

while k <= sqrt(n) do begin
...
end;

while (k*k <= n) and
do begin
...
end;

k*k <= n

(count = 0)

и B (A

натуральные числа, не превосходящие N и делящиеся на каждую

read(n);
if n < 0 then Error;
...
end.
procedure

вызов процедуры

некоторые действия.
текст (расшифровка) процедуры записывается до основной программы
в программе

числа (0..255) в 8-битном двоичном коде.
много раз!
Алгоритм:
178
⇒
101100102
7 6

1 0 1 1 0 0 1 02

разряды

n:=

n div 128

n mod 128

n1 div 64

числа (0..255) в 8-битном двоичном коде.
Алгоритм:
k:= 128;
while k

178

⇒

10110010

integer;
begin
k:= 128;
while k > 0 do begin

Параметры – данные, изменяющие работу процедуры.

локальная переменная

значение параметра
(аргумент)

b: integer);
begin
write((a+b)/2);
end.
procedure printSred(a,

число N – и выводит на экран линию из

переданного ей числа в римской системе счисления.
Пример:
Введите натуральное

двух переменных.
program Exchange;
var x, y: integer;






begin
x:= 2;

procedure Swap(a, b: integer);
var c: integer;
begin
c:= a; a:= b; b:= c;
end;

2 3

передача по значению

c: integer;
begin
c:= a; a:= b; b:= c;
end;
var
передача по

переменные могут изменяться

var a, b: integer;
...
Swap(a, b); { правильно }
Swap(2, 3); { неправильно }
Swap(a, b+3); { неправильно }

Вызов:

числа в порядке возрастания.
Пример:
Введите три натуральных числа:
10 15

и наименьшее общее кратное двух натуральных чисел и возвращает

возвращает значение-результат (число, символ или объект другого типа).
Задача. Написать

Алгоритм:

сумма:= 0;
while n <> 0 do begin
сумма:= сумма + n mod 10;
n:= n div 10
end;

;
var sum: integer;
begin
sum:= 0;
while

sumDigits:= sum

передача результата

integer

тип результата

2 = 0 then begin
writeln('Сумма цифр чётная');
writeln('Она

двух натуральных чисел.
Пример:
Введите два натуральных числа:
7006652 112307574
НОД(7006652,112307574) =

возвращает число, в котором цифры стоят в обратном порядке.

от 2 до 100.
program PrimeNum;
var i: integer;
begin
for

i - простое

функция, возвращающая логическое значение (True/False)

isPrime(i)

;
var count, k: integer;
begin
count:= 0;
k:=

boolean

логическое значение (True/False)

isPrime:= (count = 0)

if count = 0 then
isPrime:= True
else isPrime:= False

число');
read(n)
end;

переданное ей число совершенным, то есть, равно ли оно

два переданные ей числа взаимно простыми, то есть, не

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

любил, Она съела кусок мяса, он её убил, В землю закопал, Надпись

определения множества объектов через само это множество на основе

Числа Фибоначчи:

1, 1, 2, 3, 5, 8, 13, 21, 34, …

меньший диск на больший
третий стержень вспомогательный
перенести (n-1, 1, 2)
1

перенести (n, 1, 3)

integer);
var p: integer;
begin
p := 6 - k –

номер вспомогательного стержня (1+2+3=6!)

сколько

откуда

куда

рекурсия

рекурсия

это процедура (функция), которая вызывает сама себя напрямую или

proceduer Hanoi(n, k, m: integer);
var p: integer;
begin

p := 6 - k – m;
Hanoi(n-1, k, p);
writeln(k, ' -> ', m);
Hanoi(n-1, p, m)
end;

if n = 0 then exit;

условие выхода из рекурсии

program HanoiTower;
...
begin
Hanoi(4, 1, 3)
end.

= 0 then exit;
printBin ( n div 2

условие выхода из рекурсии

напечатать все цифры, кроме последней

вывести последнюю цифру

10011

printBin( 19 )

printBin( 9 )

printBin( 4 )

printBin( 2 )

printBin( 1 )

printBin( 0 )

integer;
нач
sum:= n mod 10;
if n >= 10

рекурсивный вызов

последняя цифра

sumDig( 1234 )

4 + sumDig( 123 )

4 + 3 + sumDig( 12 )

4 + 3 + 2 + sumDig( 1 )

4 + 3 + 2 + 1

чисел, нужно вычитать из большего числа меньшее до тех

function NOD(a, b: integer): integer;
begin
if (a = 0) or (b = 0) then begin

exit
end;
if a > b then
NOD:= NOD(a - b, b)
else NOD:= NOD(a, b - a)
end;

NOD:= a + b;

рекурсивные вызовы

условие окончания рекурсии

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

вывести на экран количество всех возможных различных способов представления

= ', N);
if N

-> N = 3
-> N = 2
-> N = 1
<- N = 1
<- N = 2
<- N = 3

Факториал:

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

расходуется память в стеке (возможно переполнение стека)
затраты на выполнение

программа становится более короткой и понятной

возможно переполнение стека
замедление работы

function Fact(N: integer): integer;
var i, F: integer;
begin
F:= 1;
for i:= 1 to N do
F:= F * i;
Fact:= F
end;

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

163, г. Санкт-Петербург
kpolyakov@mail.ru
ЕРЕМИН Евгений Александрович
к.ф.-м.н., доцент кафедры мультимедийной