Программирование на алгоритмическом языке. Массивы. (Часть 2. Тема 1. 8 класс)

1. Программирование на алгоритмическом языке. Часть II

1.
2.
3.
4.
5.
6.
7.
К. Поляков, 2010 -2012
Массивы
Максимальный элемент массива
Обработка массивов
Символьные строки
Матрицы
Алгоритмы-функции
Построение графиков функций
http://kpolyakov.narod.ru

2. Программирование на алгоритмическом языке. Часть II

Тема 1. Массивы
К. Поляков, 2010 -2012
http://kpolyakov.narod.ru

3. Массивы

Программирование на алгоритмическом языке. Часть II
3
Массивы
Массив – это группа однотипных элементов,
имеющих общее имя и расположенных в памяти
рядом.
Особенности:
• все элементы имеют один тип
• весь массив имеет одно имя
• все элементы расположены в памяти рядом
Примеры:
• список учеников в классе
• квартиры в доме
• школы в городе
• данные о температуре воздуха за год
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

4. Массивы

Программирование на алгоритмическом языке. Часть II
4
Массивы
A
массив
1
НОМЕР
элемента массива
(ИНДЕКС)
2
5
10
A[1]
A[2]
33
15
15
4
5
20
25
A[3]
A[4]
ЗНАЧЕНИЕ
A[5]
элемента массива
НОМЕР (ИНДЕКС)
элемента массива: 2
A[2]
ЗНАЧЕНИЕ
элемента массива: 10
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

5. Объявление массивов

Программирование на алгоритмическом языке. Часть II
5
Объявление массивов
Зачем объявлять?
• определить имя массива
• определить тип массива
• определить число элементов
• выделить место в памяти
Массив целых чисел:
тип
элементов
имя
целтаб
начальный
индекс
конечный
индекс
A[ 1 : 5 ]
Размер через переменную:
цел N = 5
целтаб A[ 1 : N ]
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

6. Объявление массивов

Программирование на алгоритмическом языке. Часть II
6
Объявление массивов
Массивы других типов:
вещтаб X[1:10], Y[1:20] | вещественные
X[1] := 4.25
симтаб S[1:20]
| символьный
S[1] := "z"
логтаб L[1:5]
| логический
L[1] := да
| да или нет
Другой диапазон индексов:
целтаб Q[0:9]
вещтаб C[-5:13]
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

7. Что неправильно?

Программирование на алгоритмическом языке. Часть II
7
Что неправильно?
целтаб A [1:10]
[10:1]
...
A[5] := 4.5;
целтаб A[1:10]
...
A[15] := "a"
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

8. Как обработать все элементы массива?

Программирование на алгоритмическом языке. Часть II
8
Как обработать все элементы массива?
Объявление:
цел N = 5
целтаб A[1:N]
Обработка:
|
|
|
|
|
?
обработать
обработать
обработать
обработать
обработать
A[1]
A[2]
A[3]
A[4]
A[5]
1) если N велико (1000, 1000000)?
2) при изменении N программа не должна меняться!
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

9. Как обработать все элементы массива?

Программирование на алгоритмическом языке. Часть II
9
Как обработать все элементы массива?
Обработка с переменной:
i:= 1
| обработать
i:= i + 1
| обработать
i:= i + 1
| обработать
i:= i + 1
| обработать
i:= i + 1
| обработать
A[i]
A[i]
A[i]
A[i]
A[i]
Обработка в цикле:
i:= 1
нц пока i <= N
| обработать A[i]
i:= i + 1
кц
Цикл с переменной:
нц для i от 1 до N
| обработать A[i]
кц
i:= i + 1
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

10. Простейшая программа

Программирование на алгоритмическом языке. Часть II
10
Простейшая программа
Объявление:
цел N = 5, i
целтаб A[1:N]
Ввод с клавиатуры:
нц для i от 1 до N
вывод "A[",i,"]="
ввод A[i]
кц
Обработка каждого элемента:
нц для i от 1 до N
A[i]:= A[i]+1
кц
A[1] = 5
A[2] = 12
A[3] = 34
A[4] = 56
A[5] = 13
Вывод на экран:
вывод "Массив A", нс
нц для i от 1 до N
вывод A[i], " "
кц
Массив A:
6 13 35 57 14
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

11. Задания

Программирование на алгоритмическом языке. Часть II
11
Задания
«3»: Ввести c клавиатуры массив из 5 элементов,
умножить их на 2 и вывести на экран.
Пример:
Введите пять чисел:
4
15
3
10
14
Результат: 8 30 6 20 28
«4»: Ввести c клавиатуры массив из 5 элементов,
найти среднее арифметическое всех элементов
массива.
!
Пример:
Введите пять чисел:
4
15
3 10
14
среднее арифметическое 9.200
При изменении N остальная программа не должна изменяться!
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

12. Задания

Программирование на алгоритмическом языке. Часть II
12
Задания
«5»: Ввести c клавиатуры массив из 5 элементов,
найти минимальный из них.
Пример:
Введите пять чисел:
4
15
3
10
14
минимальный элемент 3
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

13. Программирование на алгоритмическом языке. Часть II

Тема 2. Максимальный
элемент массива
К. Поляков, 2010 -2012
http://kpolyakov.narod.ru

14. Максимальный элемент

Программирование на алгоритмическом языке. Часть II
14
Максимальный элемент
Задача: найти в массиве максимальный элемент.
Алгоритм:
Решение:
1) считаем, что первый элемент – максимальный
2) просмотреть остальные элементы массива:
если очередной элемент > M,
то записать A[i] в M
3) вывести значение M
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

15. Максимальный элемент

Программирование на алгоритмическом языке. Часть II
15
Максимальный элемент
начало
начать со 2-ого
пока считаем,
что первый –
максимальный
M:= A[1]
i:= 2
i <= N?
нет
да
A[i] > M?
нет
i:= i + 1
К. Поляков, 2010-2012
да
конец
нашли новый
максимум
M:= A[i]
перейти к
следующему
http://kpolyakov.narod.ru

16. Максимальный элемент

Программирование на алгоритмическом языке. Часть II
16
Максимальный элемент
алг Максимум
нач
цел i, N = 5, M
целтаб A[1:N]
| здесь заполнить массив
M:= A[1] | пока максимальный – A[1]
нц для i от 2 до N
если A[i] > M то M:= A[i] все
кц
вывод "Максимальный элемент ", M
кон
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

17. Максимальный элемент

Программирование на алгоритмическом языке. Часть II
17
Максимальный элемент
Дополнение: как найти номер максимального элемента?
M:= A[1] | пока первый – максимальный
iMax:= 1
нц для i от 2 до N | проверяем остальные
если A[i] > A[iMax]
M
то | нашли еще больше
M:= A[i] | запомнить A[i]
iMax:= i | запомнить i
Как упростить?
все
кц
A[iMax]
вывод "Максимальный элемент A[",iMax,"]=",M
?
По номеру элемента iMax всегда можно найти его значение
A[iMax]. Поэтому везде меняем M на A[iMax] и убираем
переменную M.
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

18.

Программирование на алгоритмическом языке. Часть II
18
Задания
«3»: Ввести с клавиатуры массив из 5 элементов, найти в нем
минимальный элемент и его номер.
Пример:
Исходный массив:
4
-5
10 -10 5
мимимальный A[4]=-10
«4»: Ввести с клавиатуры массив из 5 элементов, найти в нем
максимальный и минимальный элементы и их номера.
Пример:
Исходный массив:
4
-5
10 -10 5
максимальный A[3]=10
минимальный A[4]=-10
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

19.

Программирование на алгоритмическом языке. Часть II
19
Задания
«5»: Ввести с клавиатуры массив из 5 элементов, найти в нем
два максимальных элемента и их номера.
Пример:
Исходный массив:
4
-5
10 -10 5
максимальные A[3]=10, A[5]=5
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

20. Программирование на алгоритмическом языке. Часть II

Тема 3. Обработка массивов
К. Поляков, 2010 -2012
http://kpolyakov.narod.ru

21. Случайность и ее моделирование

Программирование на алгоритмическом языке. Часть II
21
Случайность и ее моделирование
Случайно…
1) встретить друга на улице
2) разбить тарелку
3) найти 10 рублей
4) выиграть в лотерею
Случайный выбор:
1) жеребьевка на
соревнованиях
2) выигравшие номера
в лотерее
Как получить случайность?
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

22. Случайные числа на компьютере

Программирование на алгоритмическом языке. Часть II
25
Генератор случайных чисел
Вещественные числа в интервале [0,10):
вещ X, Y
X:= rand(0, 10) | интервал от 0 до 10 (<10)
Y:= rand(0, 10) | это уже другое число!
англ. random – случайный
Целые числа в интервале [0,10]:
цел K, L
K:= irand(0, 10) | интервал от 0 до 10 (<10)
L:= irand(0, 10) | это уже другое число!
англ. integer – целый
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

23. Распределение случайных чисел

Программирование на алгоритмическом языке. Часть II
26
Заполнение массива случайными числами
цел i, N = 5
целтаб A[1:N]
вывод "Массив ", нс
нц для i от 1 до N
A[i]:= irand(10, 30);
вывод A[i], " "
кц
?
Зачем сразу выводить?
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

24. Распределение случайных чисел

Программирование на алгоритмическом языке. Часть II
27
Подсчет элементов
Задача: заполнить массив случайными числами в
интервале [-1,1] и подсчитать количество
нулевых элементов.
Идея: используем переменную-счётчик.
Решение:
1) записать в счётчик ноль
2) просмотреть все элементы массива:
если очередной элемент = 0,
то увеличить счётчик на 1
3) вывести значение счётчика
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

25. Генератор случайных чисел

Программирование на алгоритмическом языке. Часть II
28
Подсчет элементов
начало
начать с 1-ого
пока ни одного
не нашли
count:= 0
i:= 1
нет
i <= N?
конец
да
A[i] = 0?
нет
нашли еще 1
count:= count + 1
i:= i + 1
К. Поляков, 2010-2012
да
перейти к
следующему
http://kpolyakov.narod.ru

26. Заполнение массива случайными числами

Программирование на алгоритмическом языке. Часть II
29
Подсчет элементов
цел count, i, N = 10
целтаб A[1:N]
| здесь надо заполнить массив
count:= 0
нц для i от 1 до N
перебираем все
элементы массива
если A[i] = 0
то count:= count + 1
все
кц
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

27. Подсчет элементов

Программирование на алгоритмическом языке. Часть II
30
Задания
«3»: Заполнить массив случайными числами в
интервале [-2,2] и подсчитать количество
положительных элементов.
«4»: Заполнить массив случайными числами в
интервале [20,100] и подсчитать отдельно
число чётных и нечётных элементов.
«5»: Заполнить массив случайными числами в
интервале [1000,2000] и подсчитать число
элементов, у которых вторая с конца цифра –
четная.
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

28. Подсчет элементов

Программирование на алгоритмическом языке. Часть II
31
Сумма выбранных элементов
Задача: заполнить массив случайными числами в
интервале [-10,10] и подсчитать сумму
положительных элементов.
Идея: используем переменную S для накопления
суммы.
S:=0 S:= A[1] S:= A[1]+A[2]
S:= A[1]+A[2]+A[3]
S:= A[1]+A[2]+…+A[N]
Решение:
1) записать в переменную S ноль
2) просмотреть все элементы массива:
если очередной элемент > 0,
S:= S+A[i]
то добавить к сумме этот элемент
3) вывести значение суммы
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

29. Подсчет элементов

Программирование на языке Паскаль. Часть II
32
Сумма выбранных элементов
начало
начать с 1-ого
пока ни одного
не нашли
S:= 0
i:= 1
i <= N?
нет
конец
да
A[i] > 0?
нет
i:= i + 1
К. Поляков, 2010-2011
да
нашли еще 1
S:= S + A[i]
перейти к
следующему
http://kpolyakov.narod.ru

30. Задания

Программирование на алгоритмическом языке. Часть II
33
Сумма выбранных элементов
цел S, i, N = 10
целтаб A[1:N]
| здесь надо заполнить массив
S:= 0
нц для i от 1 до N
перебираем все
элементы массива
если A[i] > 0
то S:= S + A[i]
все
кц
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

31. Сумма выбранных элементов

Программирование на алгоритмическом языке. Часть II
34
Задания
«3»: Заполнить массив из 10 элементов случайными
числами в интервале [-10,10] и подсчитать
сумму всех отрицательных элементов.
«4»: Заполнить массив из 10 элементов случайными
числами в интервале [0,100] и подсчитать
среднее значение всех элементов, которые <50.
«5»: Заполнить массив из 10 элементов случайными
числами в интервале [10,12] и найти длину
самой длинной последовательности стоящих
рядом одинаковых элементов.
Пример:
Исходный массив:
10 10 11 12 12 12 10 11
Длина последовательности: 3
К. Поляков, 2010-2011
11
12
http://kpolyakov.narod.ru

32. Сумма выбранных элементов

Программирование на алгоритмическом языке. Часть II
35
Поиск в массиве
Задача – найти в массиве элемент, равный X, или
установить, что его нет.
Пример: если в классе ученик с фамилией Пупкин?
Алгоритм:
1) начать с 1-ого элемента (i:=1)
2) если очередной элемент (A[i]) равен X, то
закончить поиск
иначе перейти к следующему элементу:
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

33. Сумма выбранных элементов

Программирование на алгоритмическом языке. Часть II
36
Поиск элемента, равного X
начало
начать с 1-ого
i:= 1
i <= N?
нет
“Не нашли”
да
A[i] = X?
нет
i:= i + 1
да
“Есть!”
перейти к
следующему
конец
?
К. Поляков, 2010-2012
Как найти номер?
http://kpolyakov.narod.ru

34. Задания

Программирование на алгоритмическом языке. Часть II
37
Поиск в массиве
алг Поиск
нач
цел i, N = 5, X
целтаб A[1:N]
| здесь нужно заполнить массив
вывод нс,"Что ищем? "
ввод X
выход из цикла
i:= 1
нц пока i <= N
если A[i] = X то выход все
i:= i + 1
кц
i – номер нужного
если i <= N то
элемента в массиве
вывод "A[", i, "]=", X
иначе
Как определить,
вывод "Не нашли!"
все
нашли или нет?
кон
?
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

35. Поиск в массиве

Программирование на алгоритмическом языке. Часть II
38
Задания
«3»: Заполнить массив из 10 элементов случайными числами
в интервале [10..20] и найти элемент, равный X.
Пример:
Исходный массив:
13 10 18 12 20 11 13 14 15 20
Что ищем? 20
A[5] = 20
«4»: Заполнить массив из 10 элементов случайными числами
в интервале [0..4] и вывести номера всех элементов,
равных X.
Пример:
Исходный массив:
4 0 1 2 0 1 3 4 1 0
Что ищем? 0
A[2], A[5], A[10]
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

36. Поиск элемента, равного X

Программирование на алгоритмическом языке. Часть II
39
Задания
«5»: Заполнить массив из 10 элементов случайными числами
в интервале [0..4]и определить, есть ли в нем
одинаковые соседние элементы.
Пример:
Исходный массив:
4 0 1 2 0 1
Ответ: есть
К. Поляков, 2010-2012
3
1
1
0
http://kpolyakov.narod.ru

37. Поиск в массиве

Программирование
на алгоритмическом
языке. Часть II
Тема 4. Символьные строки
К. Поляков, 2010 -2012
http://kpolyakov.narod.ru

38. Задания

Программирование на алгоритмическом языке. Часть II
41
Чем плох массив символов?
Это массив символов:
симтаб s[1:10]
• каждый символ – отдельный объект;
• массив имеет длину, которая задана при
объявлении
Что нужно:
• обрабатывать последовательность символов как
единое целое
• строка должна иметь переменную длину
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

39. Задания

Программирование на алгоритмическом языке. Часть II
42
Символьные строки
Объявление строки:
s[3]
1
лит s
s[4]
2
П р и в е
т
!
¤
рабочая часть
s[1]
s[2]
Длина строки:
цел n
К. Поляков, 2010-2012
n:= длин(s)
http://kpolyakov.narod.ru

40. Программирование на алгоритмическом языке. Часть II

43
Символьные строки
Задача: ввести строку с клавиатуры и заменить все
буквы «а» на буквы «б».
алг Замена а на б
нач
лит s
вывод "Введите строку: "
ввод s
цел i
нц для i от 1 до длин(s)
если s[i] = "а"
длина строки
то s[i]:= "б"
все
кц
вывод s
кон
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

41. Чем плох массив символов?

Программирование на алгоритмическом языке. Часть II
44
Задания
«3»: Ввести символьную строку и заменить все буквы «а» на
буквы «б», как заглавные, так и строчные.
Пример:
Введите строку:
ааббссААББСС
Результат:
ббббссББББСС
«4»: Ввести символьную строку и заменить все буквы «а» на
буквы «б» и наоборот, как заглавные, так и строчные.
Пример:
Введите строку:
ааббссААББСС
Результат:
ббаассББААСС
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

42. Символьные строки

Программирование на алгоритмическом языке. Часть II
45
Задания
«5»: Ввести символьную строку и проверить, является ли она
палиндромом (палиндром читается одинаково в обоих
направлениях).
Пример:
Пример:
Введите строку:
Введите строку:
АБВГДЕ
КАЗАК
Результат:
Результат:
Не палиндром.
Палиндром.
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

43. Символьные строки

Программирование на алгоритмическом языке. Часть II
46
Операции со строками
лит s, s1, s2
Запись нового значения:
s:= "Вася"
Объединение: добавить одну строку в конец другой.
s1:= "Привет"
s2:= "Вася"
s := s1 + ", " + s2 + "!" | "Привет, Вася!"
Подстрока: выделить часть строки в другую строку.
s:= "123456789"
s1:= s[3:8]
| "345678"
| "456"
s2:= s1[2:4]
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

44. Задания

Программирование на алгоритмическом языке. Часть II
47
Удаление и вставка
Удаление части строки:
6 штук
s:= "123456789"
s:= удалить(s, 3, 6);
строка
меняется!
Вставка в строку:
начиная с 3-его символа
'12ABC3456789'
куда
вставляем
s:= вставить( "Q", s, 5 )
К. Поляков, 2010-2012
'129'
с 3-его символа
s:= "123456789"
s:= вставить("ABC", s, 3)
что
вставляем
'123456789'
'12ABQC3456789'
http://kpolyakov.narod.ru

45. Задания

Программирование на алгоритмическом языке. Часть II
48
Поиск в строке (найти)
Поиск в строке:
s[3]
цел n
s:= "Здесь был Вася."
n:= найти("е", s)
3
если n > 0 то
вывод "Буква е – это s[", n, "]"
иначе вывод "Не нашли"
все
n = 11
n:= найти("Вася", s)
s1:= s[n:n+3]
Вася
Особенности:
• функция найти возвращает номер символа, с
которого начинается образец в строке
• если образец не найден, возвращается -1
• поиск с начала (находится первое слово)
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

46. Операции со строками

Программирование на алгоритмическом языке. Часть II
49
Примеры
s:= "Вася Петя Митя"
n:= найти( "Петя", s )
s:= удалить(s, n, 4)
s:= вставить("Куку", s, n )
6
'Вася Митя'
'Вася Куку Митя'
s:= "Вася Петя Митя"
n:= длин( s )
s1:= s[1:4]
s2:= s[11:14]
s3:= s[6:9]
s:= s3 + s1 + s2
n:= длин( s )
14
'Вася'
'Митя'
'Петя'
'ПетяВасяМитя'
12
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

47. Удаление и вставка

Программирование на алгоритмическом языке. Часть II
50
Пример решения задачи
Задача: Ввести имя, отчество и фамилию. Преобразовать их к
формату «фамилия-инициалы».
Пример:
Введите имя, отчество и фамилию:
Василий Алибабаевич Хрюндиков
Результат:
Хрюндиков В.А.
Алгоритм:
• найти первый пробел и выделить имя
• удалить имя с пробелом из основной строки
• найти первый пробел и выделить отчество
• удалить отчество с пробелом из основной строки
• «сцепить» фамилию, первые буквы имени и фамилии,
точки, пробелы…
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

48. Поиск в строке (найти)

Программирование на алгоритмическом языке. Часть II
51
Программа
использовать Строки
алг ФИО
нач
лит s, имя, отчество
цел n
вывод "Введите имя, отчество и фамилию"
ввод s
n:= найти(" ", s);
имя:= s[1:n-1] | вырезать имя
s:= удалить(s, 1, n)
n:= найти(" ", s)
отчество:= s[1:n-1] | вырезать отчество
s:= удалить(s, 1, n) | осталась фамилия
s:= s + " " + имя[1] + "." + отчество[1] + "."
вывод s
кон
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

49. Примеры

Программирование на алгоритмическом языке. Часть II
52
Задания
«3»: Ввести в одну строку фамилию, имя и отчество, разделив
их пробелом. Вывести инициалы и фамилию.
Пример:
Введите фамилию, имя и отчество:
Иванов Петр Семёнович
Результат:
П.С. Иванов
«4»: Ввести имя файла (возможно, без расширения) и изменить
его расширение на «.exe».
Пример:
Введите имя файла:
qqq
Результат:
qqq.exe
К. Поляков, 2010-2012
Введите имя файла:
qqq.com
Результат:
qqq.exe
http://kpolyakov.narod.ru

50. Пример решения задачи

Программирование на алгоритмическом языке. Часть II
53
Задания
«5»: Ввести путь к файлу и «разобрать» его,
выводя каждую вложенную папку с новой строки
Пример:
Введите путь к файлу:
C:\Мои документы\10-Б\Вася\qq.exe
Результат:
C:
Мои документы
10-Б
Вася
qq.exe
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

51. Программа

Программирование на алгоритмическом языке. Часть II
54
Задачи на обработку строк
Задача: с клавиатуры вводится символьная строка,
представляющая собой сумму двух целых чисел,
например:
12+35
Вычислить эту сумму:
12+35=47
Алгоритм:
1) найти знак «+»
2) выделить числа слева и справа в отдельные строки
3) перевести строки в числа
4) сложить
5) вывести результат
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

52. Задания

Программирование на алгоритмическом языке. Часть II
55
Преобразования «строка»-«число»
Из строки в число:
да или нет
s:= "123"
N:= лит_в_цел(s, OK)
если не OK то вывод
s:= "123.456";
X:= лит_в_вещ(s, OK)
если не OK то вывод
цел N, вещ X,
лит s, лог OK
| N = 123
"Ошибка!" все
| X = 123.456
"Ошибка!" все
Из числа в строку:
N:= 123
s:= цел_в_лит(N) | "123"
X:= 123.456
s:= вещ_в_лит(X) | "123.456"
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

53. Задания

Программирование на алгоритмическом языке. Часть II
56
Программа
использовать Строки
алг Калькулятор слагаемые-строки
нач
лит s, s1, s2 слагаемые-числа
цел n, n1, n2, sum
сумма
лог OK
вывод "Введите выражение (сумму двух чисел): "
ввод s
n:= найти("+", s)
s1:= s[1:n-1]
слагаемые-строки
s2:= s[n+1:длин(s)]
n1:= лит_в_цел(s1, OK)
слагаемые-числа
n2:= лит_в_цел(s2, OK)
sum:= n1 + n2
вывод n1, "+", n2, "=", sum
кон
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

54. Задачи на обработку строк

Программирование на алгоритмическом языке. Часть II
57
Задания
«3»: Ввести арифметическое выражение: разность двух
чисел. Вычислить эту разность.
Пример:
25-12
Ответ: 13
«4»: Ввести арифметическое выражение: сумму трёх
чисел. Вычислить эту сумму.
Пример:
25+12+34
Ответ: 71
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

55. Преобразования «строка»-«число»

Программирование на алгоритмическом языке. Часть II
58
Задания
«5»: Ввести арифметическое выражение c тремя числами,
в котором можно использовать сложение и
вычитание. Вычислить это выражение.
Пример:
25+12+34
Ответ: 71
Пример:
25+12-34
Ответ: 3
Пример:
25-12+34
Ответ: 47
Пример:
25-12-34
Ответ: -21
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

56. Программа

Программирование на алгоритмическом языке. Часть II
59
Задания
«6»: Ввести арифметическое выражение c тремя числами,
в котором можно использовать сложение, вычитание
и умножение. Вычислить это выражение.
Пример:
25+12*3
Ответ: 61
Пример:
25*2-34
Ответ: 16
Пример:
25-12+34
Ответ: 47
Пример:
25*2*3
Ответ: 150
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

57. Задания

Программирование
на алгоритмическом
языке. Часть II
Тема 5. Матрицы
К. Поляков, 2010 -2012
http://kpolyakov.narod.ru

58. Задания

Программирование на алгоритмическом языке. Часть II
61
Матрицы
Задача: запомнить положение фигур на шахматной доске.
1
a
b
2
c
d
e
3
f
g
4
h
5
6
1
2
3
4
5
6
7
8
8
8
0
0
0
0
2
0
0
0
7
7
0
0
0
0
0
0
0
0
6
6
0
0
3
0
0
0
0
0
5
5
0
0
0
0
0
0
0
0
4
0 A[6,3]
0 0 0
0
0
4
0
3
3
0
0
0
0
0
0
0
0
2
2
0
0
0
0
0
0
0
0
1
1
0
0
0
0
0
0
0
0
4
c6
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

59. Задания

Программирование на алгоритмическом языке. Часть II
62
Матрицы
Матрица – это прямоугольная таблица чисел (или других
элементов одного типа).
Матрица – это массив, в котором каждый элемент имеет
два индекса (номер строки и номер столбца).
столбец 3
A
1
2
3
4
5
1
1
4
7
3
6
2
2
-5
0
15 10
3
8
9
строка 2
11 12 20
ячейка A[3,4]
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

60. Программирование на алгоритмическом языке. Часть II

63
Матрицы
Объявление:
цел N = 3, M = 4
целтаб A[1:N,1:M]
целтаб B[-3:0,-8:M]
Ввод с клавиатуры:
нц для i
j от 1 до N
M
нц для j
i от 1 до M
N
вывод "A[", i, ",", j, "]="
ввод A[i,j]
кц
кц
?
К. Поляков, 2010-2012
j
i
A[1,1]=
A[1,2]=
A[1,3]=
...
A[3,4]=
25
14
14
54
Если переставить циклы?
http://kpolyakov.narod.ru

61. Матрицы

Программирование на алгоритмическом языке. Часть II
64
Матрицы
Заполнение случайными числами
цикл по строкам
нц для i от 1 до N
нц для j от 1 до M
цикл по столбцам
A[i,j]:= irand(20,80)
кц
кц
вывод строки
Вывод на экран
нц для i от 1 до N
21 65 41 43
нц для j от 1 до M
56 71 32 47
вывод A[i,j], " "
кц
31 45 22 23
Что плохо?
вывод нс
кц
Если переставить циклы?
?
К. Поляков, 2010-2012
?
http://kpolyakov.narod.ru

62. Матрицы

Программирование на алгоритмическом языке. Часть II
65
Обработка всех элементов матрицы
Задача: заполнить матрицу из 3 строк и 4 столбцов
случайными числами и вывести ее на экран. Найти
сумму элементов матрицы.
алг Сумма
нач
цел N = 3, M = 4, i, j
целтаб A[1:N,1:M]
| заполнение матрицы и вывод на экран
цел S = 0
нц для i от 1 до N
нц для j от 1 до M
S:= S + A[i,j]
кц
кц
вывод "Сумма элементов матрицы: ", S
кон
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

63. Матрицы

Программирование на алгоритмическом языке. Часть II
66
Задания
Заполнить матрицу из 8 строк и 5 столбцов случайными
числами в интервале [10,90] и вывести ее на экран. Затем
…
«3»: Удвоить все элементы матрицы и вывести её на
экран.
«4»: Найти минимальный и максимальный элементы в
матрице их номера. Формат вывода:
Минимальный элемент A[3,4]=11
Максимальный элемент A[2,2]=89
«5»: Вывести на экран строку, сумма элементов которой
максимальна. Формат вывода:
Строка 2: 13 25 18 79 38
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

64. Матрицы

67
Программирование
на алгоритмическом
языке
Тема 7. Алгоритмы-функции
К. Поляков, 2010-2011
http://kpolyakov.narod.ru

65. Обработка всех элементов матрицы

Программирование на алгоритмическом языке. Часть II
68
Максимум из трех
начало
a
нет
b
a > b?
x:= b
x
да
x:= a
c
x
нет
c > x?
да
x:= c
?
Где ответ?
К. Поляков, 2010-2012
конец
http://kpolyakov.narod.ru

66. Задания

Программирование на алгоритмическом языке. Часть II
69
Максимум из трех
результат – целое число
алг цел Макс3(цел a, b, c)
нач
цел x
внутренняя (локальная)
если a > b
переменная
то x:= a
иначе x:= b
все
если c > x то x:= c все
знач := x
кон
результат (значение)
функции
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

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

Программирование на алгоритмическом языке. Часть II
70
Максимум из трех
алг Максимум
нач
цел Z, X, C, M
вывод "Введите три числа "
ввод Z, X, C
M:= Макс3(Z, X, C)
вызов функции
вывод "Максимум: ", M
кон
алг цел Макс3(цел a, b, c)
нач
...
имена параметров
кон
могут быть любые!
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

68. Максимум из трех

Программирование на алгоритмическом языке. Часть II
71
Максимум из пяти
?
Как с помощью этой функции найти максимум из
пяти чисел?
алг Максимум
нач
цел Z, X, C, V, B, M
ввод Z, X, C, V, B
???
M:= Макс3( Макс3(Z,X,C),
V, B)
вывод "Максимум: ", M
кон
алг цел Макс3(цел a, b, c)
нач
...
кон
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

69. Максимум из трех

Программирование на алгоритмическом языке. Часть II
72
НОД трёх чисел
Задача: ввести три числа и найти наибольший общий
делитель (НОД). Используйте формулу
НОД(a,b,c) = НОД(НОД(a,b), c)
!
Нужно два раза применить один и тот же алгоритм
вычисления НОД двух чисел.
Решение: построить вспомогательный алгоритм для
вычисления НОД двух чисел и применить (вызвать) его
два раза.
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

70. Максимум из трех

Программирование на алгоритмическом языке. Часть II
73
Общий вид программы
алг НОД трёх чисел
нач
цел a, b, c, N
вывод "Введите три числа", нс
ввод a, b, c
N:= НОД(НОД(a,b),
??? c)
вывод N
кон
основной
алгоритм
алг цел НОД(цел x, y)
нач
| здесь нужно вычислить НОД(x,y)
кон
вспомогательный
алгоритм
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

71. Максимум из пяти

Программирование на алгоритмическом языке. Часть II
74
Блок-схема алгоритма Евклида
начало
a = b?
да
нет
нет
b:=b-a
К. Поляков, 2010-2012
a > b?
конец
да
a:=a-b
http://kpolyakov.narod.ru

72. НОД трёх чисел

Программирование на алгоритмическом языке. Часть II
75
Алгоритм Евклида
алг цел НОД(цел x, y)
нач
цел a, b
a:= x; b:= y | копии параметров
нц пока a <> b
если a > b
то a:= a - b
иначе b:= b - a
все
кц
знач:= a | результат функции
кон
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

73. Общий вид программы

Программирование на алгоритмическом языке. Часть II
76
Рекурсивные функции
Факториал:
1,
N!
N ( N 1)!,
1! 1, 2! 2 1! 2 1,
если N 1,
если N 1.
3! 3 2! 3 2 1,
алг цел Факт(цел N)
нач
если N < 2
то знач:= 1
иначе знач:= N*Факт(N-1)
все
кон
!
4! 4 3! 4 3 2 1
алг цел Факт(цел N)
нач
цел i
знач:= 1
нц для i от 2 до N
знач:= знач*i
кц
кон
Алгоритм без рекурсии, как правило, работает
быстрее и требует меньше памяти.
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

74. Блок-схема алгоритма Евклида

Программирование на алгоритмическом языке. Часть II
77
Задания
«3»: Составить функцию, которая определяет
НАИМЕНЬШЕЕ из трёх чисел и привести пример ее
использования.
Пример:
Введите три числа:
28 15 10
Наименьшее число 10.
«4»: Составить функцию, которая вычисляет
НАИМЕНЬШЕЕ из четырёх чисел и привести
пример ее использования.
Пример:
Введите четыре числа:
10 20 5 25
Наименьшее число 5.
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

75. Алгоритм Евклида

Программирование на алгоритмическом языке. Часть II
78
Задания
«5»: Составить функцию, которая определяет сумму
всех чисел от 1 до N и привести пример ее
использования.
Пример:
Введите число:
100
Сумма чисел от 1 до 100 = 5050
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

76. Рекурсивные функции

Программирование на алгоритмическом языке. Часть II
79
Логические функции
Задача: составить функцию, которая определяет, верно
ли, что заданное число – четное.
Особенности:
• ответ – логическое значение (да или нет)
• результат функции можно использовать как
логическую величину в условиях (если, пока)
Алгоритм: если число делится на 2, оно четное.
если mod(N,2)= 0
то
| число N четное
иначе | число N нечетное
все
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

77.

Программирование на алгоритмическом языке. Часть II
80
Логические функции
логическое значение (да или нет)
алг лог Четное(цел N)
нач
если mod(N,2) = 0
то знач:= да
иначе знач:= нет
все
кон
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

78.

Программирование на алгоритмическом языке. Часть II
81
Логические функции
алг Проверка четности
нач
цел x
вывод "Введите целое число: "
ввод x
если Четное(x)
то вывод "Число четное."
иначе вывод "Число нечетное."
все
кон
алг лог Четное(цел N)
нач
...
кон
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

79. Логические функции

Программирование на алгоритмическом языке. Часть II
82
Задания
«3»: Составить функцию, которая определяет, верно
ли, что число оканчивается на 0.
Пример:
Введите число: Введите число:
170
237
Верно.
Неверно.
«4»: Составить функцию, которая определяет, верно
ли, что в числе вторая цифра с конца больше 6.
Пример:
Введите число: Введите число:
178
237
Верно.
Неверно.
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

80. Логические функции

Программирование на алгоритмическом языке. Часть II
83
Задания
«5»: Составить функцию, которая определяет, верно
ли, что переданное ей число – простое (делится
только на само себя и на единицу).
Пример:
Введите число: Введите число:
29
28
Простое число. Составное число.
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

81. Логические функции

Программирование
на алгоритмическом
языке. Часть II
Тема 8. Построение графиков
функций
К. Поляков, 2010 -2012
http://kpolyakov.narod.ru

82. Задания

Программирование на алгоритмическом языке. Часть II
85
Построение графиков функций
Задача: построить график функции y = x2 на интервале
от -2 до 2.
Y
Анализ:
максимальное значение
ymax = 4 при x = ±2
минимальное значение
ymin = 0 при x = 0
X
Проблема: функция задана в математической системе
координат, строить надо на экране, указывая
координаты в пикселях.
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

83. Задания

Программирование на алгоритмическом языке. Часть II
86
Преобразование координат
Математическая
система координат
Экранная система
координат (пиксели)
(0,0)
Y
x
y0
(x,y)
x0
yэ
xэ
(xэ,yэ)
y
(0,0)
X
k – масштаб (длина
изображения единичного
отрезка на экране)
К. Поляков, 2010-2012
xэ = x0 + kx
yэ = y0 - ky
http://kpolyakov.narod.ru

84. Программирование на алгоритмическом языке. Часть II

87
Программа
цикл
построения
графика
использовать Рисователь
на экране
алг График
нач
цел x0=150, y0=250, k=50, xe, ye
вещ xmin=-2, xmax=2, x, y, h
в точку(0,y0)
h – шаг изменения x
линия в точку(x0+150,y0)
в точку(x0,0)
оси координат
линия в точку(x0,y0+20)
x:=xmin; h:=0.02
нц пока x <= xmax
y:= x*x
xe:= x0 + int(k*x)
ye:= y0 - int(k*y)
пиксель(xe,ye,"красный")
x:=x+h
кц
Что плохо?
кон
?
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

85. Построение графиков функций

Программирование на алгоритмическом языке. Часть II
88
Как соединить точки?
Алгоритм:
Если первая точка
перейти в точку (xэ,yэ)
иначе
линия в точку (xэ,yэ)
выбор
варианта
действий
К. Поляков, 2010-2012
Программа:
логическая
переменная
лог первая
...
начальное значение
первая:= да
нц пока x <= xmax
...
если первая то
в точку(xe, ye)
первая:= нет
иначе
линия в точку(xe, ye)
все
кц
http://kpolyakov.narod.ru

86. Преобразование координат

Программирование на алгоритмическом языке. Часть II
89
Задания
«3»: Построить график функции
y x2
на интервале [-2,2].
«4»: Построить графики функций
y x2
и
y x2
на интервале [-2,2].
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

87. Программа

Программирование на алгоритмическом языке. Часть II
90
Задания
«5»: Построить графики функций
x y2
и
x y2
на интервале [-2,2]. Соединить точки линиями.
К. Поляков, 2010-2012
http://kpolyakov.narod.ru

88. Как соединить точки?

Программирование на алгоритмическом языке. Часть II
91
Конец фильма
ПОЛЯКОВ Константин Юрьевич
д.т.н., учитель информатики высшей
категории,
ГОУ СОШ № 163, г. Санкт-Петербург
[email protected]
К. Поляков, 2010-2012
http://kpolyakov.narod.ru