11 класс

Слайд 1

Слайд 2

Типы задач 1. «Найти элементы…» for x:=A to B do begin ……… if … then writeln(x); end; 2. «Найти количество…» k:=0; for x:=A to B do begin ……… if … then k:=k+1 ; end; writeln(k); 3. «Найти сумму…» s:=0; for x:=A to B do begin ……… if … then s:=s+x; end; writeln(s); 4. «Найти элементы и их кол-во…» k:=0; for x:=A to B do begin ……… if … then begin writeln(x); k:=k+1; end end; writeln(k);

Слайд 1

Слайд 2

Что такое массив? Массив – фиксированное количество элементов одного типа, объединенных одним именем Назначение: хранение данных -10 -5 2 3 0 -7 -24 Значение элемента 1 2 3 4 5 6 7 Индекс (номер) А: Имя массива

Слайд 3

Размерность Номер элемента – данные любого перечисляемого типа. Число элементов массива ( размерность ) фиксируется при описании и не меняется в процессе выполнения программы

Слайд 4

Обращение к элементам массива a [ i ] a [ 2 ]=-5 -10 -5 2 3 0 -7 -24 Значение элемента 1 2 3 4 5 6 7 Индекс (номер) А: Имя массива

Слайд 5

Описание массива Var a: array [n1..n2] of < тип элементов >; Номер первого элемента Номер последнего элемента

Слайд 6

Примеры описаний

Слайд 7

Операции над элементами массива Те же, что и над элементами данного типа

Слайд 8

Вывод массива По одному элементу For i:= 1 to n do write (a[i]:4); Writeln;

Слайд 9

Ввод массива По одному элементу С клавиатуры С помощью оператора присваивания Из файла Описание массива как константы

Слайд 10

Ввод с клавиатуры Var a: array[1..40] of integer; i, n:integer; Begin writeln(‘ введите размерность массива ’); readln(n); for i:=1 to n do read (a[i]); for i:= 1 to n do write (a[i]:4); writeln; End. Ввод с клавиатуры Вывод массива

Слайд 11

Ввод с помощью оператора присваивания Var a: array[1..40] of integer; i, n:integer; Begin writeln(‘ введите размерность массива ’); readln(n); for i:=1 to n do a[i] := X; for i:= 1 to n do write (a[i]:4); writeln; End. Вывод массива Заполнение массива

Слайд 12

Пример1. Заполнить массив элементами, равными своему порядковому номеру ( 1, 2, 3, 4,…) Var a: array[1..40] of integer; i, n:integer; Begin writeln(‘ введите размерность массива ’); readln(n); for i:=1 to n do a[i] := i; for i:= 1 to n do write (a[i]:4); writeln; End. A: 1 2 3 4 i: 1 2 3 4

Слайд 13

Задания Заполнить массив символом ‘*’. Заполнить массив элементами, равными половине квадрата своего порядкового номера. Заполнить массив по образцу: 123123123123123… 01230123 abcabcabc

Слайд 14

Генератор случайных чисел Randomize; - процедура, задающая начальное значение последовательности случайных чисел. Y:=random(x); – функция, генерирующая целое число из отрезка [0 , x) Y:=random( B-A+1)+A; – функция, генерирующая целое число из отрезка [A,B] Длина отрезка Точка отсчета

Слайд 15

Генератор случайных чисел Y:=random ; – функция, генерирующая вещественное число из отрезка [0 , 1 ) Y:=random * ( B-A+1)+A; – функция, генерирующая вещественное число из отрезка [A,B] Длина отрезка Точка отсчета

Слайд 16

Пример 1 Заполнить массив случайными целыми числами из отрезка [-5,7]. Var a: array[1..40] of integer; i, n:integer; Begin writeln(‘ введите размерность массива ’); readln(n); randomize; for i:=1 to n do a[i] := random(13) - 5; for i:= 1 to n do write (a[i]:4); writeln; End.

Слайд 1

Слайд 2

Что такое массив? Массив – фиксированное количество элементов одного типа, объединенных одним именем

Слайд 3

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

Слайд 4

Типы массивов? Одномерные (линейные, вектор) Двумерные ( таблицы, матрицы) Трехмерные N- мерные -1 -5 2 3 1 0 1 0 0 0 1 1 0 1 0 0

Слайд 5

Двумерные массивы строка столбец 0 0 1 0 1 1 0 0 0 1 0 1 4 3 2 1 3 2 1 Матрицы А ( n , m) : прямоугольные ( n  m ) квадратные ( n=m) кол-во строк кол-во столбцов

Слайд 6

Обращение к элементам массива a [ i , j ] a [ 2,3 ]= 11 Значение элемента Номер строки Имя массива А: 0 2 0 1 0 1 1 1 7 23 12 2 3 1 4 3 2 1 3 2 1 Номер столбца

Слайд 7

Описание массива Var a: array [n1..n2 , m1..m2] of < тип элементов >; Номера строк Номера столбцов

Слайд 8

Примеры описаний Var a , c: array [1.. 40, 1.. 50 ] of integer; b: array [1..100, 1..100] of real;

Слайд 9

Вывод массива for i:= 1 to n do begin for j:= 1 to m do write (a[i,j]:4); writeln; end; А: 0 2 0 1 0 1 1 1 7 23 12 2 3 1 4 3 2 1 3 2 1

Слайд 10

Ввод с клавиатуры Var a: array[1..40,1..40] of integer; i, j,n,m:integer; Begin writeln(‘ введите размерность массива ’); readln(n,m); for i:=1 to n do for j:=1 to m do read (a[i,j]); for i:= 1 to n do begin for j:=1 to m do write (a[i,j]:4); writeln; end; end. А: 0 2 0 1 0 1 1 1 7 23 12 2 3 1 4 3 2 1 3 2 1

Слайд 11

Ввод с помощью оператора присваивания Вывод массива Заполнение массива Var a: array[1..40,1..40] of integer; i,j, n,m:integer; Begin writeln(‘ введите размерность массива ’); readln(n,m); for i:=1 to n do for j:=1 to m do a[i,j]:=random(20) - 12; for i:= 1 to n do begin for j:=1 to m do write (a[i,j]:4); writeln; end; end.

Слайд 12

Обработка массива Найти сумму элементов массива Var a: array[1..40,1..40] of integer; i,j, n,m:integer; Begin readln(n,m); for i:=1 to n do for j:=1 to m do a[i,j]:=random(20) - 12; for i:=1 to n do begin j:=1 to m do write(a[i,j]:4); writeln; end; s:=0; for i:=1 to n do for j:=1 to m do s:=s+a[i,j]; writeln(s) end. if a[i,j]>0 then s:=s+a[i,j];

Слайд 13

Задачи Дана матрица А( N,N) : Найти количество положительных элементов, отрицательных и нулей. Найти сумму четных элементов Найти минимальный и максимальный элементы, Поменять местами минимальный и максимальный элементы. Найти сумму элементов в первой строке. Найти произведение элементов в последнем столбце.

Слайд 1

Слайд 2

Что такое квадратная матрица? Это матрица, в которой количество строк равно количеству столбцов 5 4 3 2 1 5 4 3 2 1 i j

Слайд 3

Квадратные матрицы 5 4 3 2 1 5 4 3 2 1 i j Главная диагональ Побочная диагональ

Слайд 4

Главная диагональ 5 4 3 2 1 5 4 3 2 1 i j i j 1 1 2 2 3 3 4 4 5 5 Главная диагональ i = j

Слайд 5

Главная диагональ 5 4 3 2 1 5 4 3 2 1 i j i j 2<4 5>2 > < i=j

Слайд 6

Побочная диагональ 5 4 3 2 1 5 4 3 2 1 i j i j 1 5 2 4 3 3 4 2 5 1 Побочная диагональ i + j = n +1

Слайд 7

Побочная диагональ 5 4 3 2 1 5 4 3 2 1 i +j n+1 i +j n+1 4+5 > 5+1 > 2+3<5+1 < i +j = n+1

Слайд 8

Заполнение матрицы 5 4 3 2 1 5 4 3 2 1 i < j i=j Var a: array[1..40,1..40] of integer; i, j, n,m:integer; Begin readln(n); for i:=1 to n do for j:=1 to n do if ________ then a[i,j]:=1 else a[i,j]:=0; for i:= 1 to n do begin for j:=1 to n do write (a[i,j]:4); writeln; end; end. i<=j i >=j

Слайд 9

Заполнение матрицы Var a: array[1..40,1..40] of integer; i, j, n,m:integer; Begin readln(n); for i:=1 to n do for j:=1 to n do if ________ then a[i,j]:=1 else a[i,j]:=0; for i:= 1 to n do begin for j:=1 to n do write (a[i,j]:4); writeln; end; end. j>=n div 2 j = n div 2 i=n div 2 i<=n div 2

Слайд 10

Заполнение матрицы Var a: array[1..40,1..40] of integer; i, j, n,m:integer; Begin readln(n); for i:=1 to n do for j:=1 to n do if ________ then a[i,j]:=1 else a[i,j]:=0; for i:= 1 to n do begin for j:=1 to n do write (a[i,j]:4); writeln; end; end. (i

Слайд 11

Задачи Заполнить квадратную матрицу по образцу 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

Слайд 12

Задачи Заполнить квадратную матрицу по образцу 1 2 3 4 5 5 4 3 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 3 4 5 1 2 3 4 1 2 3 1 2 1 1 5 2 4 3 2 4 1 5

Слайд 1

Слайд 2

1 . Формат оператора For I := A to B do for J:= C to D do for K:=E to F do < оператор >;

Слайд 3

2 . Алгоритм выполнения For I := A to B do for J:= C to D do for K:=E to F do < оператор >; Для каждого значения параметра I из промежутка от A до В выполняется тело цикла ……

Слайд 4

3 . Блок - схема I= A,B Оператор J= C,D K= E,F

Слайд 5

4 . Количество повторений I J K For I := 1 to 2 do for J:= 11 to 12 do for K:=21 to 23 do < оператор >; 1 2 11 12 11 12 21 22 23 21 22 23 21 22 23 21 22 23

Слайд 6

5 . Количество повторений For I := 1 to 2 do for J:= 11 to 12 do for K:=21 to 23 do < оператор >; 2 * 2 * 3 For I := A to B do for J:= C to D do for K:=E to F do < оператор >; (B-F+1) * (D-C+1) * (F-E+1)

Слайд 1

Слайд 2

Старинная задача Сколько можно купить быков, коров и телят, если плата за быка - 10 рублей, за корову - 5 рублей, за теленка полтинник (0,5 рубля) и на 100 рублей надо купить 100 голов скота.

Слайд 3

b – количество быков ( по 10 рублей) k – количество коров ( по 5 рублей) t – количество телят ( по 0.5 рублей) k=0,20 t=0,200 b=0,10 b+k+t=100 b*10+k*5+t*0.5=100 b+k+t=100 b* 20 +k* 10 +t= 200

Слайд 4

k=0,20 t=0,200 b=0,10 b+k+t=100 b*20+k*10+t=200 For b:=0 to 10 do …..

Слайд 5

uses crt; var b,k,t:integer; begin clrscr; for b:=0 to 10 do for k:=0 to 20 do for t:= 0 to 200 do if (b+k+t=100) and (20*b+10*k+t=200) then writeln(b,k:4,t:4); readkey; end.

Слайд 6

Сокращение перебора uses crt ; var b,k,t:integer; begin clrscr; for b:=0 to 10 do for k:=0 to 20 do begin t:=100-b-k; if 20*b+10*k+t=200 then writeln ( b, k:4, t:4); end; readkey; end.

Слайд 1

Слайд 2

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

Слайд 3

Художник Василий Тропинин «Золотошвейка» (1826) понимает смысл алгоритма, может его корректировать и изменять, а также отказаться выполнять одну и ту же команду выполняет каждый раз по-разному неформальный исполнитель сам отвечает за свои действия в роли неформального исполнителя чаще всего выступает человек Исполнитель алгоритма Исполнитель алгоритма – это субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить со­держащийся в нём перечень действий. ! не размышляет над выпол ­ няемыми командами, а строго следует пошаговым инструк ­ циям алгоритма одну и ту же команду всегда выполняет одинаково за действия формального исполни­теля отвечает управ ­ ляющий им объект в роли формального исполни­теля чаще всего выступает техническое устройство Неформальный исполнитель Формальный исполнитель

Слайд 4

Понятие алгоритма Алгоритм – точная система предписаний , определяю­щая содержание и порядок действий исполнителя над некоторыми объектами (исходными и промежуточными данными) для получения искомого результата за конечное число шагов. ! ПРИМЕРЫ АЛГОРИТМОВ Закрыть входную дверь ключом Нахождение n первых простых чисел (метод Эратосфена) Построение перпендикуляра к прямой

Слайд 5

Пример 1 Исполнитель : человек Объекты алгоритма : ключ, дверь Алгоритм «Закрыть входную дверь ключом» Вставить ключ в замочную скважину. Повернуть ключ два раза на 180 градусов против часовой стрелки . Вынуть ключ из замочной скважины.

Слайд 6

Пример 2 Алгоритм «Нахождение всех простых чисел не больше заданного числа n по методу Эратосфена » Выписать подряд все целые числа от 2 до n ( 2 , 3 , 4 , …, n ) . Присвоить переменной p значе ­ ние 2 ( 2 – первое простое число) . Зачеркнуть в списке числа, кратные p : 2p , 3p , 4p , … Найти первое незачёркнутое число в списке, большее чем p , и прис ­ воить p соответствующее значение . Повторять шаги 3 и 4, пока возможно ( пока p 2 ≤ n ) . Незачёркнутые числа и есть все простые числа от 2 до n . Простые числа от 2 до 100 Выполнить 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Слайд 7

Пример 2 Алгоритм «Нахождение всех простых чисел не больше заданного числа n по методу Эратосфена » 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 Простые числа от 2 до 100 2 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39 41 43 45 47 49 51 53 55 57 59 61 63 65 67 69 71 73 75 77 79 81 83 85 87 89 91 93 95 97 99 p = 2 2 3 5 7 11 13 17 19 23 25 29 31 35 37 41 43 47 49 53 55 59 61 65 67 71 73 77 79 83 85 89 91 95 97 p = 3 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97 p = 5 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 p = 7 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 Выписать подряд все целые числа от 2 до n ( 2 , 3 , 4 , …, n ) . Присвоить переменной p значе ­ ние 2 ( 2 – первое простое число) . Удалить из списка числа, кратные p : 2p , 3p , 4p , … Найти первое число в списке, большее чем p , и прис ­ воить p соответствующее значение . Повторять шаги 3 и 4, пока возможно ( пока p 2 ≤ n ) . Оставшиеся числа и есть все простые числа от 2 до n .

Слайд 8

Пример 3 Алгоритм «Построение перпендикуляра к прямой, проходящей через заданную точку O , лежащую на прямой с помощью циркуля и линейки» Выполнить Провести окружность с центром в точке O и радиусом 1 см. Обозначить точки пересечения окружности с прямой: левую - A , правую - B . Провести окружность с центром в точке A и радиусом равным A B . Провести окружность с центром в точке В и радиусом равным A B . Обозначить точки пересечения окружностей: верхнюю - C , нижнюю - D . Провести прямую С D .

Слайд 9

Пример 3 Алгоритм «Построение перпендикуляра к прямой, проходящей через заданную точку O , лежащую на прямой с помощью циркуля и линейки» О А В С D Провести окружность с центром в точке O и радиусом 1 см. Обозначить точки пересечения окружности с прямой: левую - A , правую - B . Провести окружность с центром в точке A и радиусом равным A B . Провести окружность с центром в точке В и радиусом равным A B . Обозначить точки пересечения окружностей: верхнюю - C , нижнюю - D . Провести прямую С D .

Слайд 10

Свойства алгоритма Дискретность Детерминированность Понятность Результативность Массовость Дискретность Выполнение алгоритма разбивается на последовательность законченных дейст­вий-шагов. Только выполнив одно действие, можно приступать к выполнению следующего. Произвести каждое отдельное действие исполнителю предписывает специальное указание в записи алгоритма – команда. Детерминированность Каждая команда алгоритма определяет однозначное действие исполнителя, и недвусмысленно указывает , какая команда должна выполняться следую ­ щей . Многократное выполнение алго ­ ритма при одном и том же наборе входных данных, дает одинаковые промежуточные и выходной результаты. Понятность Алгоритм не должен содержать предписаний , смысл которых может восприниматься исполнителем неодно ­ знач­но , т. е. запись алгоритма должна быть настолько чёткой и полной, чтобы у исполнителя не возникло потребности в принятии каких-либо самостоятельных решений. Результативность При точном исполнении команд алгоритма процесс должен прекратиться за конеч ­ ное число шагов, и при этом должен быть получен ответ на вопрос задачи. В качестве одного из возможных ответов может быть установление того факта , что задача решений не имеет. Массовость Алгоритм пригоден для решения любой задачи из некоторого класса задач, т. е. алгоритм правильно работает на неко ­ тором множестве исходных данных, которое называется областью примени ­ мости алгоритма. Алгоритм – конечная система правил, сформулированных на языке исполнителя, которая определяет последовательность перехо­да от допустимых исходных данных к конечному результату и обла­дает свойствами дискретности, детерминированности, понятности, результативности , конечности и массовости. !

Слайд 11

Давайте обсудим Можно ли кулинарный рецепт считать алгоритмом? Ответ обоснуйте с точки зрения свойств алгоритма. ?

Слайд 12

Способы записи алгоритмов словесная запись алгоритма на естественном языке запись алгоритма на языке программирования с помощью блок-схемы – стандартных графических объектов (геометрических фигур) запись алгоритма с помощью формул , рисунков, таблиц Сложение смешанных дробей Привести дробные части чисел к наименьшему общему знаменателю. Сложить только целые части. Отдельно сложить дробные части. Сложить результаты, полученные в п.2 и п. 3. Если при сложении дробных частей получилась неправильная дробь , выделить целую часть из этой дроби и прибавить к полученной целой части. Сократить полученную дробь. Нахождение максимума из 10 целых чисел Нахождение НОД Program NOD; var a, b, n: integer ; Begin writeln (' Введите два числа: '); readln (a, b); while a <> b do if a>b then a := a - b else b := b – a; n:= a; writeln (' НОД = ', n); End . Шахматный этюд Мат в два хода. Белые начинают и выигрывают № Белые Черные 1 Ф f1-a1 K h8-g8 2 Ф a1-a8 № Белые Черные 1 Ф f1-a1 g6-g5 2 K f6-f7 № Белые Черные 1 Ф f1-a1 С h7-g8 2 K f 6 -g6 Решение:

Слайд 13

Правила выполнения блок-­схем, внешний вид графических блоков и их назначение определяются стандартом ГОСТ 19.701–90 (ИСО 5807–85) «Схемы алгоритмов, программ, данных и систем. Обозначения условные и правила выполнения ». Блок-схема СИМВОЛ ФУНКЦИЯ Пуск/остановка. Начало, конец, прерывание процесса обработки данных или выполнения программы Ввод/вывод. Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов (вывод) Процесс. Выполнение операций или группы операций, в результате которых изменяется значение, форма представления или расположение данных Решение. Выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий Модификация. Выполнение операций, меняющих команды или группу команд, изменяющих программу Предопределённый процесс. Использование ранее созданных и отдельно описанных алгоритмов или программ

Слайд 14

Понятие сложности алгоритма Теория алгоритмов предоставляет аппарат анализа различных алгоритмов решения одной и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алгоритм. Вычислительным процессом , порождённым алгоритмом, называется последовательность шагов алгоритма, пройденных при его ис­полнении . Сложность алгоритма – количество элементарных шагов (действий ) в вычислительном процессе этого алгоритма. ! Для решения задачи могут быть разработаны алгоритмы, имеющие разную сложность. Лучшим среди них считается алгоритм , имеющий наименьшую сложность. Эффективность оценивается количеством элементарных операций, которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения алгоритма.

Слайд 15

Временная сложность «Найти книгу с секретом» Сложность алгоритма выражают в виде функции от объёма входных данных. Задание. Оцените сложность алгоритмов: «Поиск в телефонной книге» В сейфе оказался клочок страницы с фамилией и первой цифрой номера телефона. Надо найти страницу с нужной фамилией в телефонном справочнике, в котором 1000 страниц . Сложность алгоритма будет O(log 2 n) . Таким образом, в книге объёмом в 1000 страниц страница с нужной фамилией находится не больше, чем за O(log 2 1000) ≈ 10 раз . В данном случае, за счет сортировки имен по алфавиту, можно сократить поиск, применив метод половинного деления (открыв книгу примерно в середине, мы уменьшаем размер «оставшейся проблемы» вдвое ) . При линейном поиске – последовательной проверки всех книг подряд – сложность, в худшем случае, будет равна количеству книг, т.е . O ( n ) = 1000 . В старинной библиотеке в одном из 10 0 0 томов, посвященных кладам и тайникам, спрятана книга-сейф. Надо найти ее.

Слайд 16

X 40 Задание. Найти Пример 4 Алгоритм «Возведение числа в натуральную степень ( x n ) » Запишем n в двоичной системе счисления. Заменим каждую 1 парой букв КХ , а каждый 0 – буквой К . Вычеркнем крайнюю левую пару КХ . Полученная строка, читаемая слева направо, даёт правило быстрого вычисления х n , если букву К рассматривать как операцию возведения результата в квадрат, а букву X – как операцию умножения результата на х. Вначале результат равен х . К Х К К Х К К К возведение результата в К вадрат К умножение результата на Х Х 1 0 1 0 0 0 40 = 2 х 2 х 4 х 5 х 10 х 20 х 40

Слайд 17

Алгоритм – конечная система правил, сформулированных на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и обладает свойствами дискретности, детерминированности, понятности , результативности, конечности и массовости . Исполнитель алгоритма – субъект или устройство, способные правильно интерпретировать описание алгоритма и выполнить содержащийся в нём перечень действий. Один и тот же алгоритм может быть записан разными способами : на естественном языке, псевдокодом, с помощью блок-схем , на языке программирования и т. д. Теория алгоритмов предоставляет аппарат анализа различных алгоритмов решения одной и той же задачи, на основе которого можно выбрать самый эффективный (наилучший) алгоритм.

Слайд 18

Алгоритм состоит из команд. Команда – отдельная инструкция в описании алгоритма. Шаг алгоритма – отдельное действие , которое исполнитель выполняет по команде. Вычислительным процессом, порождённым алгоритмом, называется последовательность шагов алгоритма, пройденных при его исполнении. Сложность алгоритма – количество элементарных шагов ( действий ) в вычислительном процессе этого алгоритма. Наряду со сложностью важной характеристикой алгоритма является эффективность . Эффективность оценивается количеством элементарных операций , которые необходимо выполнить для решения задачи, а также количеством памяти, требующейся для выполнения алгоритма.

Слайд 19

Вопросы и задания Задание 1. Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам: Складываются первая и вторая, а также вторая и третья цифры исходного числа . Полученные два числа записываются друг за другом в порядке убывания ( без разделителей). Укажите наименьшее число, в результате обработки которого автомат выдаст число 1711 . Решение: Единственный способ разбить запись 1711 на два числа – это 17 и 11. Чтобы число было меньше, надо чтобы сумма первой и второй цифр была наименьшей, в данном случае 11 . Сумма значений двух последних цифр равна 17 . Не трудно заметить, что 17 = 8 + 9 = 9 + 8 . Других вариантов нет. Тогда 11 = 2 + 9 = 3 + 8 . Выбираем пару, которая даст ме́ньшее число. Ответ : 298.

Слайд 20

Вопросы и задания Задание 2. Подсчитайте сложность алгоритма сложения двух натуральных чисел «столбиком» при условии, что одно из них состоит из n , а второе – из m десятичных цифр . Решение: Сложение двух чисел столбиком в случае, если одно из них состоит из n , а другое – из m цифр требует не более max ( n , m ) сложений и не более max ( n , m ) запоминаний (в случае перехода через десяток). Т.е. данный алгоритм имеет сложность порядка O ( n + m ). Выражение показывает только порядок величины – постоянные факторы в нем не учитываются.

Слайд 21

8 3 3 3 3 3 Вопросы и задания Задание 1. Есть двое песочных часов: на 3 и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут . Как это сделать? Придумайте систему команд исполнителя Колдун. Запишите с их помощью план действий исполнителя по приготовлению эликсира. Графический способ решения:

Слайд 22

Информационные источники https://img2.goodfon.ru/original/1920x1080/a/91/zamok-klyuch-otverstie-svet.jpg http://biblo-ok.ru/biblio-ok/Kartiny1/79.files/image001.jpg http://cheeseberry-sibir.ru/photos/vyshivka-na-odejde-izgotovlenie-6259-large.jpg http://europeansectionarcipreste.blogspot.ru/2011_11_01_archive.html http://www.imasitalia.com/wp-content/uploads/2016/04/fogli.jpg http://atotarho12.narod.ru/clipart/k/kar/karanda44.png https://s-media-cache-ak0.pinimg.com/originals/73/96/fd/7396fd0a921a5f895bafd81830adcaa5.jpg https:// chessok.net/zadachi/1165-reshit-legkuyu-dvuhhodovku.html http ://pikabu.ru/story/metod_byistrogo_umnozheniya_karatsubyi_4226758 http ://ozon.ru. Сейф-книга "Вид на реку" https://openclipart.org/image/800px/svg_to_png/171487/1344190891.png http://vamotkrytka.ru/_ph/54/2/531435092.gif http://www.gifmania.ru/Animated-Gifs-Veb-dizayn/Animations-Geometry/Images-Geometric-Stars/Geometric-Stars-89830.gif http://www.freeiconspng.com/free-images/potion-icon-png-15620