Кумир-Описание языка-Поляков

Программирование (АлгЯзык)

§ 17. Введение

§ 18. Линейные программы

§ 19. Ветвления

§ 2 0. Программирование циклических алгоритмов

§ 21 . Массивы

§ 22 . Алгоритмы обработки массивов

Программирование (АлгЯзык)

§ 17. Введение

Что такое программирование?

Программирование — это создание программ для компьютеров. Этим занимаются программисты .

Чем занимаются программисты:

анализ задачи (выделение исходных данных, связей между ними, этапов решения задачи)

системные аналитики

разработка алгоритмов

алгоритмисты

написание и отладка программ

кодировщики

тестирование программ

тестировщики

написание документации

технические писатели

Направления в программировании

системный программист

операционные системы, утилиты, драйверы

прикладной программист

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

веб-программист

веб-сайты

программист баз данных

системы управления базами данных

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

название программы

алг Куку

нач | начало программы

| тело программы

кон | конец программы

комментарии после | не обрабатываются

?

Что делает эта программа ?

Вывод на экран

алг Привет

нач

вывод ' Привет! '

кон

оператор вывода

Оператор — это команда языка программирования.

?

вывод ' Привет ' , Вася !

Что плохо?

вывод ' Привет , Вася !'

вся строка в апострофах

Переход на новую строку

вывод ' Привет , Вася !'

вывод ' Привет , Петя !'

ожидание:

Привет , Вася !

Привет , Петя !

реальность:

Привет , Вася ! Привет , Петя !

решение:

новая строка

вывод ' Привет , Вася !' , нс

вывод ' Привет , Петя !'

нс

Системы программирования

Системы программирования — это средства для создания новых программ.

Транслятор — это программа, которая переводит тексты программ, написанных программистом, в машинные коды (команды процессора).

• компилятор — переводит всю программу в машинные коды, строит исполняемый файл ( .exe )

• интерпретатор — сам выполняет программу по частям ( по одному оператору).

алг Привет

нач

вывод ' Привет! '

кон

1010010100

privet.exe

Системы программирования

Отладчик — это программа для поиска ошибок в других программах.

• пошаговый режим — выполнение программы по шагам (по одному оператору)
• просмотр значений переменных во время выполнения программы
• точки останова – операторы в программе, перед выполнением которых нужно остановиться.

Среда программирования ( IDE ) :

• редактор текста программ
• транслятор
• отладчик

Задачи

« B »: Вывести на экран текст «лесенкой»

Вася

пошел

гулять

« C »: Вывести на экран рисунок из букв

Ж

ЖЖЖ

ЖЖЖЖЖ

ЖЖЖЖЖЖЖ

HH HH

ZZZZZ

Программирование (АлгЯзык)

§ 1 9. Линейные программы

Пример задачи

Задача . Ввести два числа и вычислить их сумму.

алг Сумма

нач

| ввести два числа

| вычислить их сумму

| вывести сумму на экран

кон

?

Выполнится?

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

!

Компьютер не может исполнить псевдокод!

Зачем нужны переменные?

алг Сумма

нач

| ввести два числа

| вычислить их сумму

| вывести сумму на экран

кон

Где запомнить?

Переменная — это величина, которая имеет имя, тип и значение. Значение переменной может изменяться во время выполнения программы.

объявление переменных

цел a, b, c

ячейки памяти

Имена переменных

Идентификатор — это имя программы или переменной.

цел a, b, c

заглавные и строчные буквы различаются

МОЖНО использовать

• латинские буквы ( A-Z , a-z) , русские буквы (А-Я , а-я) цифры знак подчеркивания _
• латинские буквы ( A-Z , a-z) , русские буквы (А-Я , а-я)
• цифры
• знак подчеркивания _

!

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

Какие имена правильные?

AXby R&B 4Wheel Вася “PesBarbos” TU154 [QuQu] _ABBA A+B

14

Работа с переменными

Присваивание (запись значения)

a ← 5

a := 5

:=

оператор присваивания

a := 5

a := 18

?

Что будет храниться в a ?

Вывод на экран

?

вывод a

В чём разница?

с:= 14

вывод с

с:= 14

вывод ' с '

14

c

Работа с переменными

Изменение значения

увеличить на 1

i ← i + 1

i:= i + 1

a

b

4

a:= 4

b:= 7

a:= a + 1

b:= b + 1

a:= a + b

b:= b + a

a:= a + 2

b:= b + a

7

5

8

13

21

1 5

36

Ввод с клавиатуры

Цель – изменить исходные данные, не меняя программу.

5

ввод a

!

• Программа ждет, пока пользователь введет значение и нажмет Enter .
• Введенное значение записывается в переменную a .

Ввод с клавиатуры

ввод a, b

через пробел:

25 30

через запятую:

25,30

a

25

b

30

a

25

b

30

Программа сложения чисел

алг Сумма

нач

цел a, b, c

ввод a, b | ввести два числа

c:= a + b | вычислить их сумму

вывод c | вывести сумму на экран

кон

?

Что плохо?

ожидание:

Введите два числа: 5 7

5+7=12

реальность:

5 7

12

?

Как улучшить диалог?

Вывод данных с текстом

значение b

значение a

значение с

5+7=12

текст

вывод a

вывод '+'

вывод b

вывод '='

вывод c

вывод a , '+' , b , '=' , c

Программа сложения чисел

алг Сумма

нач

цел a, b, c

вывод ' Введите два числа: '

ввод a, b

c:= a + b

вывод a , '+' , b , '=' , c

кон

?

Как переделать для 3-х чисел?

Задачи

« A »: Ввести три числа, найти их сумму.

Пример:

Введите три числа:

4

5

7

4+5+7=16

« B »: Ввести три числа, найти их сумму и произведение.

Пример:

Введите три числа:

4

5

7

4+5+7=16

4*5*7=140

Задачи

« C »: Ввести три числа, найти их сумму, произведение и среднее арифметическое.

Пример:

Введите три числа:

4

5

7

4+5+7=16

4*5*7=140

(4+5+7) / 3 =5.33 3333

Арифметические выражения

Линейная запись (в одну строку):

a:=(c+b- 1 )/ 2 *d

Операции :

+ –

* – умножение

/ – деление

** – возведение в степень ( x 2  x**2 )

цел x, a, b

ввод a, b

x:= a / b

?

Что плохо?

a / b

вещ x

24

Порядок выполнения операций

• действия в скобках
• возведение в степень
• умножение и деление, слева направо
• сложение и вычитание, слева направо

1

2

3

4

5

6

a := c + (1 – 2 * b) / 2 * d

Частное и остаток

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

mod – остаток от деления

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

?

175 сек = 2 мин 55 сек

Как получить 2 и 55?

цел t, m, s

• цел t, m, s

t := 17 5

m := div ( t, 6 0 ) | 2

s := mod (t, 6 0 ) | 5 5

• t := 17 5 m := div ( t, 6 0 ) | 2 s := mod (t, 6 0 ) | 5 5

Частное и остаток

?

Что получится?

n := 123

d := div ( n, 10 ) | 1 2

k := mod (n, 10 ) | 3

• n := 123 d := div ( n, 10 ) | 1 2 k := mod (n, 10 ) | 3

При делении на 10 нацело отбрасывается последняя цифра числа.

Остаток от деления на 10 – это последняя цифра числа.

Форматный вывод

цел a= 1 , b= 2 , c= 3

• цел a= 1 , b= 2 , c= 3

вывод a, b, c

• вывод a, b, c

123

1 2 3

вывод a, ' ' ,b, ' ' ,c

• вывод a, ' ' ,b, ' ' ,c

1 2 3

вывод a, b: 3 , c: 5

• вывод a, b: 3 , c: 5

3

5

количество знаков на вывод числа

?

Сколько знаков для вывода a ?

Задачи

« A »: Ввести число, обозначающее количество секунд. Вывести то же самое время в минутах и секундах.

Пример :

Введите число секунд: 175

2 мин. 55 с.

« B »: Ввести число, обозначающее количество секунд. Вывести то же самое время в часах, минутах и секундах.

Пример :

Введите число секунд: 8325

2 ч. 18 мин. 45 с

Задачи

«С»: Занятия в школе начинаются в 8-30. Урок длится 45 минут, перерывы между уроками – 10 минут. Ввести номер урока и вывести время его окончания.

Пример :

Введите номер урока: 6

13-50

Форматный вывод

вещ x= 12.34567891234

• вещ x= 12.34567891234

вывод x

• вывод x

12 . 3 45679

6

вывод x : 10 : 3

• вывод x : 10 : 3

12 . 3 46

по умолчанию

3

всего на число

в дробной части

10

вывод x : 8 : 2

• вывод x : 8 : 2

12 . 3 4

вывод x : 2 : 2

• вывод x : 2 : 2

12 . 3 4

вывод x : 0 : 1

• вывод x : 0 : 1

12 . 3

минимально возможное

Научный формат чисел

вещ x= 123456789

• вещ x= 123456789

вывод x

• вывод x

1 . 23 4568 e+008

1,23 4568  10 8

вещ x= 0.0000 123456789

• вещ x= 0.0000 123456789

вывод x

• вывод x

1 . 23 4568 e-005

1,23 4568  10 –5

Операции с вещественными числами

int – целая часть числа (ближайшее целое слева !)

• int – целая часть числа (ближайшее целое слева !)

вещ x= 1 .5

• вещ x= 1 .5

вывод int ( x )

• вывод int ( x )

1

– 1,5

вещ x= -1.5

• вещ x= -1.5

вывод int ( x )

• вывод int ( x )

-2

x

– 1

– 2

– 3

0

1

sqrt – квадратный корень

• sqrt – квадратный корень

вещ x= 2 . 2 5

• вещ x= 2 . 2 5

вывод sqrt ( x )

• вывод sqrt ( x )

1.5

Операции с вещественными числами

1 /3 = 0,33333…

бесконечно много знаков

!

Большинство вещественных чисел хранятся в памяти компьютера с ошибкой!

вещ x , y, z

• вещ x , y, z

x:= 1 / 2

y:= 1 / 3

z:= 5 / 6 | 5/6=1/2+1/3

вывод x +y-z

• x:= 1 / 2 y:= 1 / 3 z:= 5 / 6 | 5/6=1/2+1/3 вывод x +y-z

-1.110223e-016

Задачи

« A »: Ввести число, обозначающее размер одной фотографии в Мбайтах. Определить, сколько фотографий поместится на флэш-карту объёмом 2 Гбайта.

Пример :

Размер фотографии в Мбайтах: 6.3

Поместится фотографий: 325.

Задачи

« B »: Оцифровка звука выполняется в режиме стерео с частотой дискретизации 44,1 кГц и глубиной кодирования 24 бита. Ввести время записи в минутах и определить, сколько Мбайт нужно выделить для хранения полученного файла (округлить результат в большую сторону).

Пример :

Введите время записи в минутах: 10

Размер файла 152 Мбайт

Задачи

«С»: Разведчики-математики для того, чтобы опознать своих, используют числовые пароли. Услышав число-пароль, разведчик должен возвести его в квадрат и сказать в ответ первую цифры дробной части полученного числа. Напишите программу, которая по полученному паролю (вещественному числу) вычисляет число-ответ.

Пример :

Введите пароль: 1.92

Ответ: 6

потому что 1,92 2 = 3, 6 864…, первая цифра дробной части – 6

Случайные и псевдослучайные числа

Случайные явления

• встретил слона – не встретил слона
• жеребьёвка на соревнованиях
• лотерея
• случайная скорость (направление выстрела ) в игре
• …

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

Случайные и псевдослучайные числа

!

Компьютер неслучаен!

Псевдослучайные числа — похожи на случайные, но строятся по формуле.

следующее

предыдущее

X n+1 : = mod ( a*X n +b, c) | от 0 до c-1

X n+1 : = mod ( X n + 3 , 10 ) | от 0 до 9

 2

 8

 5

 3

 9

 6

X = 0

 0

8

 1

 4

 7

зерно

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

Датчик случайных чисел

Целые числа на отрезке:

цел K , L

K:= ira nd ( 1 , 6 ) | отрезок [1,6]

L := ira nd ( 1 , 6 ) | это уже другое число!

англ. integer – целый

random – случайный

Вещественные числа в полуинтервале:

цел x , y

x:= ra nd ( 0 , 1 0 ) | полуинтервал [ 0 , 10)

y := ra nd ( 0 , 1 0 ) | это уже другое число!

Задачи

« A »: В игре «Русское лото» из мешка случайным образом выбираются бочонки, на каждом из которых написано число от 1 до 90. Напишите программу, которая выводит наугад первые 5 выигрышных номеров.

« B »: + Доработайте программу «Русское лото» так, чтобы все 5 значений гарантированно были бы разными (используйте разные диапазоны).

Задачи

«С»: + Игральный кубик бросается три раза (выпадает три случайных значения). Из этих чисел составляется целое число, программа должна найти его квадрат.

Пример :

Выпало очков:

1 2 3

Число 123

Его квадрат 15129

Задачи

« D »: + Получить случайное трёхзначное число и вывести в столбик его отдельные цифры.

Пример :

Получено число 123

сотни: 1

десятки: 2

единицы: 3

Программирование (АлгЯзык)

§ 19. Ветвления

b то M:= a иначе M:= b все a b? M:= a M:= b вывод M ? Если a = b? конец " width="640"

Выбор наибольшего из двух чисел

полная форма ветвления

начало

ввод a , b

да

нет

если a b то

M:= a

иначе

M:= b

все

a b?

M:= a

M:= b

вывод M

?

Если a = b?

конец

b то иначе все вывод 'Наибольшее число ' , M кон полная форма условного оператора M:=a M:=b " width="640"

45

Вариант 1. Программа

алг Максимум нач цел a, b, M вывод 'Введите два целых числа' , нс ввод a, b если a b то иначе все вывод 'Наибольшее число ' , M кон

полная форма условного оператора

M:=a

M:=b

a? M:= b вывод M конец " width="640"

Выбор наибольшего из двух чисел-2

начало

ввод a,b

неполная форма ветвления

M:= a

да

нет

b a?

M:= b

вывод M

конец

a то M:= b все вывод 'Наибольшее число ', M кон неполная форма условного оператора " width="640"

Вариант 2. Программа

алг Максимум 2 нач цел a, b, M вывод 'Введите два целых числа', нс ввод a, b

M:= a если b a то M:= b все вывод 'Наибольшее число ', M кон

неполная форма условного оператора

Примеры

Поиск минимального :

если a b то

M:= a

все

если b a то

M:= b

все

?

Что плохо ?

?

Когда работает неверно ?

?

если a b то

c := a

a:= b

b:= c

все

Что делает эта программа ?

В других языках программирования

Паскаль :

С :

if a b then begin

c: = a ;

a:= b;

b:= c;

end;

if ( a b ) {

c = a ;

a = b;

b = c;

}

Python:

if a b :

c = a

a = b

b = c

b то вывод 'Андрей старше' иначе вывод 'Борис старше' все " width="640"

Вложенные условные операторы

Задача . В переменной a записан возраст Антона, а в переменной b – возраст Бориса. Определить, кто из них старше.

?

Сколько вариантов ответа ?

если a = b то

вывод 'Одного возраста'

иначе

если a=b то

вывод 'Одного возраста'

иначе

вывод 'Борис старше'

все

все

вложенный условный

оператор

если a b то

вывод 'Андрей старше'

иначе

вывод 'Борис старше'

все

Задачи

« A »: Ввести два целых числа, найти наибольшее и наименьшее из них.

Пример :

Введите два целых числа:

1 5

Наибольшее число 5

Наименьшее число 1

« B »: Ввести четыре целых числа, найти наибольшее из них.

Пример :

Введите четыре целых числа:

1 5 4 3

Наибольшее число 5

Задачи

« C »: Ввести последовательно возраст Антона, Бориса и Виктора. Определить, кто из них старше.

Пример :

Возраст Антона: 15

Возраст Бориса: 17

Возраст Виктора: 16

Ответ: Борис старше всех.

Пример :

Возраст Антона: 17

Возраст Бориса: 17

Возраст Виктора: 16

Ответ: Антон и Борис старше Виктора.

Сложные условия

Задача . Фирма набирает сотрудников от 25 до 40 лет включительно. Ввести возраст человека и определить, подходит ли он фирме (вывести ответ 'подходит' или 'не подходит' ) .

Особенность : надо проверить, выполняются ли два условия одновременно:

возраст  25 возраст  40

?

Можно ли решить известными методами ?

= 25 то если x 40 то вывод 'Подходит!' иначе вывод 'Не подходит.' все иначе вывод 'Не подходит.' все кон вложенный условный оператор " width="640"

Плохое решение

алг Сотрудник

нач

цел x

вывод 'Введите ваш возраст' , нс

ввод x

если x = 25 то

если x 40 то

вывод 'Подходит!'

иначе

вывод 'Не подходит.'

все

иначе

вывод 'Не подходит.'

все

кон

вложенный условный оператор

= 25 и x 40 то вывод 'Подходит!' иначе вывод 'Не подходит.' все кон сложное условие " width="640"

Хорошее решение (операция «И»)

алг Сотрудник

нач

цел x

вывод 'Введите ваш возраст' , нс

ввод x

если x = 25 и x 40 то

вывод 'Подходит!'

иначе

вывод 'Не подходит.'

все

кон

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

Примеры

Задача . Вывести ' Да ' , если число в переменной a – двузначное.

если 10 a и a 99 то

вывод 'Да'

все

Задача . Вывести ' Да ' , если число в переменной a – двузначное и делится на 7.

если 10 a и a 99 и mod (a, 7 )= 0 то

вывод 'Да'

все

Сложные условия

Задача . Самолёт летает по понедельникам и четвергам. Ввести номер дня недели и определить, летает ли в этот день самолёт.

Особенность : надо проверить, выполняется ли одно из двух условий:

день = 1 день = 4

если d = 1 или d = 4 то

вывод 'Летает'

d = 1 или d = 4

иначе

вывод 'Не летает'

все

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

40 если ??? то вывод 'Не подходит!' иначе вывод 'Подходит.' все " width="640"

Ещё пример

Задача . Фирма набирает сотрудников от 25 до 40 лет включительно. Ввести возраст человека и определить, подходит ли он фирме (вывести ответ 'подходит' или 'не подходит' ) . Использовать « ИЛИ ».

x 25 или x 40

если ??? то

вывод 'Не подходит!'

иначе

вывод 'Подходит.'

все

= = Сложное условие – это условие, состоящее из нескольких простых условий (отношений), связанных с помощью логических операций: И – одновременное выполнение условий И – одновременное выполнение условий x = 25 и x x = 25 и x ИЛИ – выполнение хотя бы одного из условий ИЛИ – выполнение хотя бы одного из условий x или x = 40 x или x = 40 НЕ – отрицание, обратное условие НЕ – отрицание, обратное условие не ( x 25 )  ??? не ( x 25 )  ??? равно не равно x " width="640"

Простые и сложные условия

Простые условия (отношения)

= =

Сложное условие – это условие, состоящее из нескольких простых условий (отношений), связанных с помощью логических операций:

• И – одновременное выполнение условий
• И – одновременное выполнение условий

x = 25 и x

• x = 25 и x

• ИЛИ – выполнение хотя бы одного из условий
• ИЛИ – выполнение хотя бы одного из условий

x или x = 40

• x или x = 40

• НЕ – отрицание, обратное условие
• НЕ – отрицание, обратное условие

не ( x 25 )  ???

• не ( x 25 )  ???

равно

не равно

x

=, =, НЕ И ИЛИ , =, =, НЕ И ИЛИ 1 4 2 3 5 6 если не a 2 или c 5 и b то ... все если не a 2 или c 5 и b то ... все " width="640"

Порядок выполнения операций

• выражения в скобках
• выражения в скобках

• , =, =, НЕ И ИЛИ
• , =, =,
• НЕ
• И
• ИЛИ

1

4

2

3

5

6

если не a 2 или c 5 и b то

...

все

• если не a 2 или c 5 и b то ... все

b) не (a b) a и b a c или b c a и b c a c и b d a и b a c или b c a и b c a c и b d не (a = b) или c = d не (a = b) или c = d a = b или не (c a c или b c или b a a = b или не (c a c или b c или b a Да Да Нет Нет Нет Да Да Да " width="640"

Сложные условия

Истинно или ложно при a := 2; b := 3; c := 4;

не (a b)

• не (a b)

a и b

a c или b c

a и b c

a c и b d

• a и b a c или b c a и b c a c и b d

не (a = b) или c = d

• не (a = b) или c = d

a = b или не (c

a c или b c или b a

• a = b или не (c a c или b c или b a

Да

Да

Нет

Нет

Нет

Да

Да

Да

Задачи

« A »: Напишите программу, которая получает три числа - рост трёх спортсменов, и выводит сообщение «По росту.», если они стоят по возрастанию роста, или сообщение «Не по росту!», если они стоят не по росту.

Пример :

Введите рост трёх спортсменов:

165 170 172

По росту.

Пример :

Введите рост трёх спортсменов:

175 170 172

Не по росту!

Задачи

« B »: Напишите программу, которая получает номер месяца и выводит соответствующее ему время года или сообщение об ошибке.

Пример :

Введите номер месяца:

5

Весна.

Пример :

Введите номер месяца:

15

Неверный номер месяца.

Задачи

« C »: Напишите программу, которая получает возраст человека (целое число, не превышающее 120) и выводит этот возраст со словом «год», «года» или «лет». Например, «21 год», «22 года», «25 лет».

Пример :

Введите возраст: 18

Вам 18 лет.

Пример :

Введите возраст: 21

Вам 21 год.

Пример :

Введите возраст: 2 2

Вам 22 года.

Логические переменные

лог b

• лог b

...

b:= да

b:= нет

• ... b:= да b:= нет

только два возможных значения

Пример:

лог выходной

• лог выходной

...

выходной:= (d= 6 или d= 7 )

...

если не выходной то

вывод 'Рабочий день.'

иначе

вывод 'Выходной!'

все

• ... выходной:= (d= 6 или d= 7 ) ... если не выходной то вывод 'Рабочий день.' иначе вывод 'Выходной!' все

Задачи

« A »: Напишите программу, которая получает с клавиатуры целое число и записывает в логическую переменную значение «да» ( True ), если это число трёхзначное. После этого на экран выводится ответ на вопрос: «Верно ли, что было получено трёхзначное число?».

Пример :

Введите число: 165

Ответ: да.

Пример :

Введите число: 1651

Ответ: нет.

Задачи

« B »: Напишите программу, которая получает с клавиатуры трёхзначное число и записывает в логическую переменную значение «да» ( True ), если это число – палиндром, то есть читается одинаково слева направо и справа налево. После этого на экран выводится ответ на вопрос: «Верно ли, что введённое число – палиндром?».

Пример :

Введите число: 165

Ответ: нет.

Пример :

Введите число: 656

Ответ: да.

Задачи

«С»: Напишите программу, которая получает с клавиатуры трёхзначное число и записывает в логическую переменную значение «да» ( True ), если это все его цифры одинаковы. После этого на экран выводится ответ на вопрос: «Верно ли, что все цифры введённого числа одинаковы?»

Пример :

Введите число: 161

Ответ: нет.

Пример :

Введите число: 555

Ответ: да.

Экспертная система

Экспертная система — это компьютерная программа, задача которой — заменить человека-эксперта при принятии решений в сложной ситуации.

База знаний = факты + правила вывода :

• если у животного есть перья, то это птица ;
• если животное кормит детенышей молоком, то это — млекопитающее ;
• если животное — млекопитающее и ест мясо, то это — хищник.

Диалог :

Это животное кормит детей молоком? Нет

Это животное имеет перья? Да

Это птица .

Дерево решений

Кормит детей молоком?

да

нет

млекопитающее

Имеет перья?

Ест мясо?

да

да

нет

нет

?

птица

?

хищник

Программирование экспертной системы

Ответы пользователя: да и нет – символьные строки.

лит ответ

• лит ответ

вывод 'Кормит детей молоком? '

ввод ответ

если ответ = 'да' то

... | вариант 1

иначе

... | вариант 2

все

• вывод 'Кормит детей молоком? ' ввод ответ если ответ = 'да' то ... | вариант 1 иначе ... | вариант 2 все

| вариант 1

• | вариант 1

вывод 'Млекопитающее.' , нс

вывод 'Ест мясо? '

ввод ответ

если ответ = 'да' то

вывод 'Хищник.' , нс

иначе

вывод 'Не знаю.' , нс

все

• вывод 'Млекопитающее.' , нс вывод 'Ест мясо? ' ввод ответ если ответ = 'да' то вывод 'Хищник.' , нс иначе вывод 'Не знаю.' , нс все

Заглавные и строчные буквы

лит ответ

• лит ответ

...

если ответ = 'да' то

...

• ... если ответ = 'да' то ...

не сработает на ' Да '

?

Как исправить ?

если ответ = 'да' или ответ = 'Да' то

...

• если ответ = 'да' или ответ = 'Да' то ...

Ещё лучше:

если нижний регистр (ответ) = 'да' то

...

• если нижний регистр (ответ) = 'да' то ...

преобразовать все заглавные в строчные

если верхний регистр (ответ) = 'ДА' то

...

• если верхний регистр (ответ) = 'ДА' то ...

Программирование (АлгЯзык)

§ 2 0. Отладка программ

Виды ошибок

Синтаксические ошибки – нарушение правил записи операторов языка программирования.

Обнаруживаются транслятором.

Логические ошибки – неверно составленный алгоритм.

Отказ (ошибка времени выполнения) – аварийная ситуация во время выполнения программы.

Отладка – поиск и исправление ошибок в программе.

Пример отладки программы

Программа решения квадратного уравнения

алг КвУр

нач

вещ a, b, c, D, x1, x2

вывод 'Введите a, b, c: '

ввод a, b, c

D:=b*b- 4 *a*a

x1:=(-b+ sqrt (D))/ 2 *a

x2:=(-b- sqrt (D))/ 2 *a

вывод ' x1=' , x1, ' x2=' , x2

кон

• алг КвУр нач вещ a, b, c, D, x1, x2 вывод 'Введите a, b, c: ' ввод a, b, c D:=b*b- 4 *a*a x1:=(-b+ sqrt (D))/ 2 *a x2:=(-b- sqrt (D))/ 2 *a вывод ' x1=' , x1, ' x2=' , x2 кон

Тестирование

Тест 1 . a = 1, b = 2, c = 1.

Реальность:

Ожидание:

x1=-1.0 x2=-1.0

x1=-1.0 x2=-1.0

Тест 2 . a = 1, b = – 5 , c = 6 .

x1=3.0 x2=2.0

x1=4.791 x2=0.209

Найден вариант, когда программа работает неверно. Ошибка воспроизводится !

Возможные причины :

• неверный ввод данных
• неверное вычисление дискриминанта
• неверное вычисление корней
• неверный вывод результатов

Отладочная печать

Идея : выводить все промежуточные результаты.

ввод a, b, c

вывод a, ' ' , b, ' ' , c, нс

D:=b*b- 4 *a*a

вывод ' D=' , D, нс

...

• ввод a, b, c вывод a, ' ' , b, ' ' , c, нс D:=b*b- 4 *a*a вывод ' D=' , D, нс ...

вывод a, ' ' , b, ' ' , c, нс

• вывод a, ' ' , b, ' ' , c, нс

вывод ' D=' , D, нс

• вывод ' D=' , D, нс

Результат:

Введите a, b, c: 1 -5 6

1.0 -5.0 6.0

D=21.0

D=21.0

!

D:=b*b- 4 *a* с ;

• D:=b*b- 4 *a* с ;

с

Одна ошибка найдена!

Отладка программы

Тест 1 . a = 1, b = 2, c = 1.

Ожидание:

Реальность:

x1=-1.0 x2=-1.0

x1=-1.0 x2=-1.0

Тест 2 . a = 1, b = – 5 , c = 6 .

x1=3.0 x2=2.0

x1=3.0 x2=2.0

?

Программа работает верно?

Тест 3 . a = 8 , b = – 6 , c = 1 .

x1= 0 . 5 x2= 0 . 25

x1=3 2 .0 x2= 16 .0

( 2 *a )

x1:=(-b+ sqrt (D))/ 2 *a

x2:=(-b- sqrt (D))/ 2 *a

• x1:=(-b+ sqrt (D))/ 2 *a x2:=(-b- sqrt (D))/ 2 *a

?

Что неверно?

( 2 *a )

Задачи

« A »: Загрузите программу , которая должна вычислять сумму цифр трёхзначного числа:

• « A »: Загрузите программу , которая должна вычислять сумму цифр трёхзначного числа:
• « A »: Загрузите программу , которая должна вычислять сумму цифр трёхзначного числа:

цел N, d1, d2, s

• цел N, d1, d2, s
• цел N, d1, d2, s

ввод 'N = ' ; вывод N

d0:= mod (N, 10 )

d1:= mod (N, 100 )

d2:= div (N, 100 )

d0 + d2 := s

вывод s

• ввод 'N = ' ; вывод N d0:= mod (N, 10 ) d1:= mod (N, 100 ) d2:= div (N, 100 ) d0 + d2 := s вывод s
• ввод 'N = ' ; вывод N d0:= mod (N, 10 ) d1:= mod (N, 100 ) d2:= div (N, 100 ) d0 + d2 := s вывод s

Выполните отладку программы:

• исправьте синтаксические ошибки
• определите ситуации, когда она работает неверно
• исправьте логические ошибки.

Задачи

« B »: Доработайте программу из п. А так, чтобы она правильно работала с отрицательными трёхзначными числами: при вводе числа «–123» программа должна выдавать ответ 6.

• « B »: Доработайте программу из п. А так, чтобы она правильно работала с отрицательными трёхзначными числами: при вводе числа «–123» программа должна выдавать ответ 6.
• « B »: Доработайте программу из п. А так, чтобы она правильно работала с отрицательными трёхзначными числами: при вводе числа «–123» программа должна выдавать ответ 6.

b то M:= a иначе M:= b если c b то M:= b иначе M:= c вывод M ввод 'a = ' ; ввод a вывод 'b = ' ; вывод b ввод 'c = ' ; ввод c если a b то M:= a иначе M:= b если c b то M:= b иначе M:= c вывод M ввод 'a = ' ; ввод a вывод 'b = ' ; вывод b ввод 'c = ' ; ввод c если a b то M:= a иначе M:= b если c b то M:= b иначе M:= c вывод M Выполните отладку программы: исправьте синтаксические ошибки определите ситуации, когда она работает неверно исправьте логические ошибки. " width="640"

Задачи

«С»: Загрузите программу, которая должна вычислять наибольшее из трёх чисел:

• «С»: Загрузите программу, которая должна вычислять наибольшее из трёх чисел:
• «С»: Загрузите программу, которая должна вычислять наибольшее из трёх чисел:

цел a, b, c, M

• цел a, b, c, M
• цел a, b, c, M

ввод 'a = ' ; ввод a

вывод 'b = ' ; вывод b

ввод 'c = ' ; ввод c

если a b то M:= a

иначе M:= b

если c b то M:= b

иначе M:= c

вывод M

• ввод 'a = ' ; ввод a вывод 'b = ' ; вывод b ввод 'c = ' ; ввод c если a b то M:= a иначе M:= b если c b то M:= b иначе M:= c вывод M
• ввод 'a = ' ; ввод a вывод 'b = ' ; вывод b ввод 'c = ' ; ввод c если a b то M:= a иначе M:= b если c b то M:= b иначе M:= c вывод M

Выполните отладку программы:

• исправьте синтаксические ошибки
• определите ситуации, когда она работает неверно
• исправьте логические ошибки.

Программирование (АлгЯзык)

§ 2 0. Программирование циклических алгоритмов

Зачем нужен цикл?

Задача . Вывести 5 раз «Привет!».

вывод 'Привет' , нс

вывод 'Привет' , нс

вывод 'Привет' , нс

вывод 'Привет' , нс

вывод 'Привет' , нс

?

А если 5000?

Цикл « N раз» :

нц 5 раз

вывод 'Привет' , нс

кц

Как работает цикл?

!

Нужно запоминать, сколько раз цикл уже выполнен!

переменная-счётчик

ещё не делали

счётчик:= 0

нц пока счётчик 5

вывод 'Привет' , нс

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

кц

сделали ещё раз

??? вывод 'Привет' , нс счётчик:= счётчик ??? кц 0 - 1 " width="640"

Как работает цикл?

Идея : запоминать, сколько шагов осталось.

счётчик:= 5

нц пока счётчик ???

вывод 'Привет' , нс

счётчик:= счётчик ???

кц

0

- 1

Цикл с предусловием

• условие проверяется при входе в цикл
• как только условие становится ложным, работа цикла заканчивается
• если условие ложно в самом начале, цикл не выполняется ни разу

нц пока условие

...

кц

тело цикла

?

Если условие никогда не станет ложно?

бесконечный цикл (зацикливание)

нц пока да

...

кц

Сумма цифр числа

Задача. Вычислить сумму цифр введённого числа.

123  1 + 2 + 3 = 6

Выделить последнюю цифру числа в переменной N :

d:= mod (N, 10 )

123  3

Отбросить последнюю цифру числа в переменной N :

N:= div (N, 10 )

123  12

Добавить к переменной sum значение переменной d :

sum = 6  6 + 4 = 1 0

d = 4

sum:= sum + d

Сумма цифр числа

• выделяем последнюю цифру числа ( mod )
• увеличиваем сумму на значение цифры ( sum:=sum+d )
• отсекаем последнюю цифру числа ( div )

N

d

123

sum

12

3

0

1

3

2

0

1

5

6

начальные значения

Сумма цифр числа

начало

обнулить сумму

ввод N

sum:= 0

выполнять 'пока N 0 '

нет

N 0 ?

да

вывод sum

d:= mod (N, 10 )

sum:= sum + d

N:= div (N, 10 )

конец

Сумма цифр числа

алг Сумма цифр

нач

цел N, d, sum

вывод 'Введите целое число' , нс

ввод N

sum : = 0

вывод 'Сумма цифр числа ' , N, ' равна' , sum

кон

, N1

; N1:= N

нц пока N 0

d := mod ( N , 10 )

sum:= sum + d

N:= div (N, 10 )

кц

?

Что плохо ?

N1,

Задачи

« A »: Напишите программу, которая получает с клавиатуры количество повторений и выводит столько же раз какое-нибудь сообщение.

Пример :

Сколько раз повторить? 3

Привет!

Привет!

Привет!

« B »: Напишите программу, которая получает с клавиатуры натуральное число и определяет, сколько раз в его десятичной записи встречается цифра 1.

Пример :

Введите число? 311

Единиц: 2

Задачи

« C »: Напишите программу, которая получает с клавиатуры натуральное число и находит наибольшую цифру в его десятичной записи.

Пример :

Введите число : 311

Наибольшая цифра: 3

« D »: Напишите программу, которая получает с клавиатуры натуральное число и определяет, есть ли в его десятичной записи одинаковые цифры, стоящие рядом.

Пример :

Введите число : 553 Введите число : 5 3 5

Ответ: да. Ответ: нет.

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

Задача. Найти наибольший общий делитель (НОД) двух натуральных чисел.

Заменяем большее из двух чисел разностью большего и меньшего до тех пор, пока они не станут равны. Это и есть НОД.

НОД( a,b)= НОД( a-b, b)

= НОД( a, b-a)

Евклид

(365-300 до. н. э.)

Пример:

НОД (14 , 21 ) = НОД (14 , 21-14 ) = НОД (14 , 7 )

= НОД (7 , 7 ) = 7

много шагов при большой разнице чисел:

НОД (1998 , 2 ) = НОД (1996 , 2 ) = … = 2

b? нет да b:=b-a a:=a-b " width="640"

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

начало

a = b?

да

конец

нет

a b?

нет

да

b:=b-a

a:=a-b

b то a:= a - b иначе b:= b - a все кц ? Где будет НОД? Как его вывести? ? Как вывести НОД в формате НОД(14,21) = 7? ? А без дополнительных переменных? " width="640"

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

нц пока a b

если a b

то a:= a - b

иначе b:= b - a

все

кц

?

Где будет НОД? Как его вывести?

?

Как вывести НОД в формате НОД(14,21) = 7?

?

А без дополнительных переменных?

Модифицированный алгоритм Евклида

Заменяем большее из двух чисел остатком от деления большего на меньшее до тех пор, пока меньшее не станет равно нулю . Тогда большее — это НОД.

НОД( a,b)= НОД( mod (a,b), b)

= НОД( a, mod (b,a))

Пример :

НОД (14 , 21 ) = НОД (14 , 7 ) = НОД (0 , 7 ) = 7

b то a:= mod (a, b) иначе b:= mod (b, a) все кц ? Где будет НОД? Как его вывести? если a 0 вывод a иначе вывод b все вывод ??? a +b " width="640"

Модифицированный алгоритм

нц пока a 0 и b 0

если a b то

a:= mod (a, b)

иначе

b:= mod (b, a)

все

кц

?

Где будет НОД? Как его вывести?

если a 0

вывод a

иначе

вывод b

все

вывод ???

a +b

b) a = a % b; else b = b % a; } while (a 0 ) and (b 0 ) do if ab then a:= a mod b else b:= b mod a; Python: while a!= 0 and b!= 0 : if a b: a = a % b else: b = b % a " width="640"

В других языках программирования

С :

Паскаль :

while (a!= 0 && b!= 0 )

{

if (a b)

a = a % b;

else

b = b % a;

}

while (a 0 ) and

(b 0 ) do

if ab then

a:= a mod b

else

b:= b mod a;

Python:

while a!= 0 and b!= 0 :

if a b:

a = a % b

else:

b = b % a

Задачи

« A »: Ввести с клавиатуры два натуральных числа и найти их НОД с помощью алгоритма Евклида.

Пример :

Введите два числа:

21 14

НОД(21,14)=7

« B »: Ввести с клавиатуры два натуральных числа и найти их НОД с помощью модифицированного алгоритма Евклида. Заполните таблицу:

a

b

64168

НОД( a,b )

358853

82678

6365133

691042

17905514

11494962

23108855

549868978

298294835

Задачи

« C »: Ввести с клавиатуры два натуральных числа и сравнить количество шагов цикла для вычисления их НОД с помощью обычного и модифицированного алгоритмов Евклида.

Пример :

Введите два числа:

1998 2

НОД(1998,2)=2

Обычный алгоритм: 998

Модифицированный: 1

Обработка потока данных

Задача . На вход программы поступает поток данных — последовательность целых чисел, которая заканчивается нулём . Требуется найти сумму элементов этой последовательности.

нц пока x 0

| добавить x к сумме

| x := следующее число

кц

?

Откуда возьмётся x в первый раз?

Обработка потока данных

цел x, sum

sum:= 0

ввод x | ввести первое число

нц пока x 0

sum:= sum + x

ввод x | ввести следующее

кц

вывод 'Сумма ' , sum

?

Как найти сумму положительных?

Задачи

« A »: На вход программы поступает неизвестное количество чисел целых, ввод заканчивается нулём. Определить, сколько получено чисел, которые делятся на 3.

« B »: На вход программы поступает неизвестное количество чисел целых, ввод заканчивается нулём. Определить, сколько получено двузначных чисел, которые заканчиваются на 3.

« C »: На вход программы поступает неизвестное количество чисел целых, ввод заканчивается нулём. Найти максимальное из введённых чётных чисел.

0: ' ввод N кц при N 0 N N 0 ? нет условие окончания работы цикла да конец " width="640"

Цикл с постусловием

• условие проверяется после завершения очередного шага цикла
• цикл всегда выполняется хотя бы один раз
• как только условие становится истинным , работа цикла заканчивается

начало

нц

вывод 'Введите N 0: '

ввод N

кц при N 0

N

N 0 ?

нет

условие окончания работы цикла

да

конец

Задачи

« A »: Напишите программу, которая предлагает ввести пароль и не переходит к выполнению основной части, пока не введён правильный пароль. Основная часть – вывод на экран «секретных сведений».

« B »: Напишите программу, которая получает с клавиатуры натуральное число, которое больше 1, и определяет, простое оно или нет. Для этого нужно делить число на все натуральные числа, начиная с 2, пока не получится деление без остатка.

« C »: Напишите программу, которая получает с клавиатуры два целых числа и вычисляет их произведение, используя только операции сложения.

Задачи

« D »: Напишите программу, которая получает с клавиатуры натуральное число и вычисляет целый квадратный корень из него – наибольшее число, квадрат которого не больше данного числа.

Цикл по переменной

Задача . Вывести на экран степени числа 2 от 2 1 до 2 10 .

k:= 1

N:= 2

нц пока k 10

вывод N, нс

N:= N* 2

k:= k + 1

кц

!

k:= 1

Работа с k в трёх местах!

Идея : собрать всё вместе.

k 10

N:= 2

нц для k от 1 до 10

вывод N, нс

N:= N* 2

кц

k:= k + 1

k от 1 до 10

увеличение на 1 по умолчанию

Цикл по переменной

Задача . Найти сумму чисел от 1 до 1000.

цел sum, i

sum:= 0

нц для i от 1 до 1000

sum:= sum + i

кц

Задача . Вывести квадраты чисел от 10 до 1 по убыванию.

нц для k от 10 до 1 шаг –1

вывод k*k, нс

кц

шаг –1

любое целое

Цикл по переменной

Задача . Найти сумму чётных чисел от 2 до 1000.

sum:= 0

нц для i от 1 до 1000

если mod (i, 2 ) = 0 то

sum:= sum + i

все

кц

?

Что плохо?

sum:= 0

нц для i от 2 до 1000 шаг 2

sum:= sum + i

кц

шаг 2

В других языках программирования

С :

Паскаль :

int sum, i;

sum = 0 ;

for (i= 1 ; i 1000 ; i++)

sum += i;

sum:= 0 ;

for i:= 1 to 1000 do

sum:= sum + i;

i=i+1;

шаг только 1 или –1 ( downto )

sum=sum+i;

Python:

Sum = 0

for i in range ( 1 , 1001 ):

S um += i

диапазон [1;1001)

Задачи

« A »: Ипполит задумал трёхзначное число, которое при делении на 15 даёт в остатке 11, а при делении на 11 даёт в остатке 9. Напишите программу, которая находит все такие числа.

« B »: С клавиатуры вводится натуральное число N. Программа должна найти факториал этого числа (обозначается как N!) – произведение всех натуральных чисел от 1 до N. Например,

5! = 1 • 2 • 3 • 4 • 5 = 120.

« C »: Натуральное число называется числом Армстронга , если сумма цифр числа, возведенных в N -ную степень (где N – количество цифр в числе) равна самому числу. Например, 153 = 1 3 + 5 3 + 3 3 . Найдите все трёхзначные Армстронга.

Программирование (АлгЯзык)

§ 21 . Массивы

Что такое массив?

?

Как ввести 10000 переменных?

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

Надо :

• выделять память
• записывать данные в нужную ячейку
• читать данные из ячейки

Выделение памяти (объявление)

!

минимальный индекс

Массив = таблица !

максимальный индекс

целтаб A[ 1 : 5 ]

вещтаб V[ 0 : 5 ]

логтаб L[ -5 : 5 ]

симтаб S[ 65 : 90 ]

Индекс элемента — это значение, которое указывает на конкретный элемент массива.

размер через константу

цел N = 10

целтаб A[ 1 : N ]

?

Зачем?

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

целтаб A [ 10 : 1 ]

...

A[ 5 ] := 4.5 ;

[ 1 : 10 ]

целтаб A[ 1 : 10 ]

...

A[ 15 ] := 'a'

116

Обращение к элементу массива

НОМЕР элемента массива

(ИНДЕКС)

A

массив

3

1

2

3

4

5

15

5

10

15

20

25

A[1]

A[2]

A[3]

A[4]

A[5]

ЗНАЧЕНИЕ элемента массива

НОМЕР (ИНДЕКС) элемента массива : 2

A[2]

ЗНАЧЕНИЕ элемента массива : 10

Обращение к элементу массива

1

2

3

4

5

23

12

7

43

51

цел i

i:= 2

A[ 3 ]:= A[i] + 2 *A[i- 1 ] + A[ 2 *i]

вывод A[ 3 ]+A[ 5 ]

?

Что получится?

101

A[ 3 ]:= A[ 2 ] + 2 *A[ 1 ] + A[ 4 ]

вывод A[ 3 ]+A[ 5 ]

1 52

Что неверно?

целтаб A[ 1 : 5 ]

цел x

...

x:= 2

вывод A[x- 3 ]

A[x+ 4 ]:=A[x- 1 ]+A[ 2 *x]

?

Что плохо?

вывод A[ - 1 ]

A[ 6 ]:=A[ 1 ]+A[ 4 ]

Выход за границы массива — это обращение к элементу с индексом, который не существует в массиве.

Перебор элементов массива

цел N = 10

целтаб A[ 1 : N ]

Перебор элементов : просматриваем все элементы массива и, если нужно, выполняем с каждым из них некоторую операцию.

нц для i от 1 до N

| здесь работаем с A[i]

кц

Заполнение массива

нц для i от 1 до N

A[i]:= i

кц

?

Что произойдёт?

В развёрнутом виде

A[ 1 ]:= 1

A[ 2 ]:= 2

A[ 3 ]:= 3

...

A[N]:= N

1

2

3

N

...

Заполнение массива в обратном порядке

N

…

3

2

1

X:= N

A[ 1 ]:= N

A[ 2 ]:= N- 1

A[ 3 ]:= N- 2

...

A[N]:= 1

нц для i от 1 до N

A[i]:= X

кц

X:= X - 1

кц

?

Как меняется X ?

X = N, N-1, …, 2, 1

уменьшение на 1

начальное значение

Заполнение массива в обратном порядке

A[i]:= X

N

…

3

2

1

?

Как связаны i и X ?

нц для i от 1 до N

A[i]:= N + 1 - i

кц

i

X

1

N

2

3

N-1

N-2

...

...

N

1

– 1

+1

!

Сумма i и X не меняется!

i + X = N + 1

X = N + 1 - i

Вывод массива на экран

нц для i от 1 до N

вывод A[i]

кц

?

, ' '

Что плохо?

интервал между значениями

или так:

нц для i от 1 до N

вывод A[i] , нс

кц

в столбик

или так:

?

Как убрать?

вывод '['

нц для i от 1 до N

вывод A[i] , ','

кц

вывод ']'

[1,2,3,4,5,]

Ввод с клавиатуры

нц для i от 1 до N

вывод A[i]

кц

?

Что плохо?

С подсказкой для ввода:

A[1] =

A[2] =

A[3] =

A[4] =

A[5] =

5

12

34

56

13

нц для i от 1 до N

вывод ' A[ ' ,i, ' ]= '

ввод A[i]

кц

В других языках программирования

Паскаль :

const N = 10;

var i: integer ;

A: array[ 1 ..N] of integer ;

begin

for i:= 1 to N do

A[i]:= i;

for i:= 1 to N do

write(A[i], ' ' );

end.

В других языках программирования

Python:

A = [ 0 ]*N

for i in range (N):

A[i] = i + 1

print(A)

!

Нумерация элементов всегда с нуля !

С ++:

int A[N], i;

for (i = 0 ; i

A[i] = i + 1;

for (i = 0 ; i

cout " " ;

Задачи

« A »: а) Заполните все элементы массива из 10 элементов значением X , введённым с клавиатуры.

б) Заполните массив из 10 элементов последовательными натуральными числами, начиная с X (значение X введите с клавиатуры).

« B »: а) Заполните массив из 10 элементов натуральными числами в обратном порядке, начиная со значения X, введённого с клавиатуры. Последний элемент должен быть равен X , предпоследний равен X – 1 и т.д.

б) Заполните массив из 10 элементов степенями числа 2 (от 2 1 до 2 N ), так чтобы элемент с индексом i был равен 2 i .

Задачи

« C »: а) Заполните массив из 10 элементов степенями числа 2, начиная с конца, так чтобы последний элемент массива был равен 1, а каждый предыдущий был в 2 раза больше следующего.

б) С клавиатуры вводится целое число X . Заполните массив из 11 элементов целыми числами, так чтобы средний элемент массива был равен X , слева от него элементы стояли по возрастанию, а справа – по убыванию. Соседние элементы отличаются на единицу. Например, при X = 3 массив из 5 элементов заполняется так: 1 2 3 2 1.

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

нц для i от 1 до N

A[i]:= irand ( 20 , 100 )

вывод A[i], ' '

кц

сразу вывод на экран

Задачи -2

« A »: Напишите программу, которая заполняет массив из 10 элементов случайными числами в диапазоне [0,10], выводит его на экран, а затем выводит на экран квадраты всех элементов массива.

Пример :

Массив: 5 6 2 3 1 4 8 7

Квадраты: 2 5 36 4 9 1 1 6 6 4 49

« B »: Напишите программу, которая заполняет массив из 10 элементов случайными числами в диапазоне [100,300] и выводит его на экран. После этого на экран выводятся средние цифры (число десятков) всех чисел, записанных в массив.

Пример :

Массив: 142 324 135 257 167 295 126 223 138 270

Число десятков: 4 2 3 5 6 9 2 2 3 7

Задачи -2

« C »: Напишите программу, которая заполняет массив из 10 элементов случайными числами в диапазоне [100,500] и выводит его на экран. После этого на экран выводятся суммы цифр всех чисел, записанных в массив.

Пример :

Массив: 162 425 340 128 278 195 326 414 312 177

Суммы цифр: 9 11 7 11 17 15 11 9 6 15

Программирование (АлгЯзык)

§ 22 . Алгоритмы обработки массивов

Сумма элементов массива

Задача . Найти сумму элементов массива.

цел N = 10

целтаб A[ 1 : N ]

?

Какие переменные нужны?

5

2

8

3

1

sum:= 0

нц для i от 1 до N

sum:= sum + A[i]

кц

вывод sum

i

sum

0

1

5

2

7

3

15

4

1 8

5

19

Сумма не всех элементов массива

Задача . Найти сумму чётных элементов массива.

?

Что делаем с нечётными?

sum:= 0

нц для i от 1 до N

sum:= sum + A[i]

кц

вывод sum

если mod (A[i], 2 )= 0 то

sum:= sum + A[i]

все

кц

вывод sum

если mod (A[i], 2 )= 0 то

Задачи

« A »: Напишите программу, которая заполняет массив из 10 элементов случайными числами на отрезке [–5; 5] и находит сумму положительных элементов.

« B »: Напишите программу, которая заполняет массив из 10 элементов случайными числами на отрезке [–2; 2] и находит произведение ненулевых элементов.

« C »: Напишите программу, которая заполняет массив из 20 элементов случайными числами на отрезке [100; 1000] и находит отдельно сумму элементов в первой и во второй половинах массива.

Подсчёт элементов по условию

Задача . Найти количество чётных элементов массива.

?

Какие переменные нужны?

переменная-счётчик

цел count

count := 0

нц для i от 1 до N

если mod (A[i], 2 )= 0 то

count := count + 1

все

кц

вывод count

?

Что тут делаем?

180 то sum:= sum + A[i] все кц вывод sum/N ? Что плохо? " width="640"

Среднее арифметическое

Задача . Найти среднее арифметическое элементов массива, которые больше 180 (рост в см).

sum:= 0

нц для i от 1 до N

если A[i] 180 то

sum:= sum + A[i]

все

кц

вывод sum/N

?

Что плохо?

180 то count := count + 1 sum:= sum + A[i] все кц вывод sum/ count ? Что тут делаем? " width="640"

Среднее арифметическое

Задача . Найти среднее арифметическое элементов массива, которые больше 180 (рост в см).

?

Какие переменные нужны?

sum:= 0

count:= 0

нц для i от 1 до N

если A[i] 180 то

count := count + 1

sum:= sum + A[i]

все

кц

вывод sum/ count

?

Что тут делаем?

Задачи

« A »: Напишите программу, которая заполняет массив из 20 элементов случайными числами на отрезке [0; 200] и считает число элементов, которые делятся на 10.

« B »: Напишите программу, которая заполняет массив из 20 элементов случайными числами на отрезке [0; 200] и считает число двузначных чисел в массиве.

« C »: Напишите программу, которая заполняет массив из 20 элементов случайными числами на отрезке [10; 100] и считает число пар соседних элементов, сумма которых делится на 3.

0 нужен цикл это цикл с условием (число шагов неизвестно) ? Когда увеличивать счётчик ? ? Какой цикл ? счётчик = 0 пока не введён 0 : если введено число 0 то счётчик: = счётчик + 1 " width="640"

Обработка потока данных

Задача . С клавиатуры вводятся числа, ввод завершается числом 0. Определить, сколько было введено положительных чисел.

• нужен счётчик
• счётчик увеличивается если число 0
• нужен цикл
• это цикл с условием (число шагов неизвестно)

?

Когда увеличивать счётчик ?

?

Какой цикл ?

счётчик = 0

пока не введён 0 :

если введено число 0 то

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

0 то count:= count + 1 все ввод x кц вывод count откуда взять x ? ? Что плохо ? " width="640"

Обработка потока данных

цел x, count

count: = 0

ввод x

нц пока x 0

если x 0 то

count:= count + 1

все

ввод x

кц

вывод count

откуда взять x ?

?

Что плохо ?

0 то count:= count + 1 все ввод x ввод x кц вывод count " width="640"

Найди ошибку!

цел x, count

count: = 0

ввод x

нц пока x 0

если x 0 то

count:= count + 1

все

ввод x

ввод x

кц

вывод count

0 то count:= count + 1 все ввод x кц вывод count " width="640"

Найди ошибку!

цел x, count

count: = 0

count: = 0

ввод x

нц пока x = 0

если x 0 то

count:= count + 1

все

ввод x

кц

вывод count

Обработка потока данных

Задача . С клавиатуры вводятся числа, ввод завершается числом 0. Найти сумму введённых чисел, оканчивающихся на цифру "5".

• нужна переменная для суммы
• число добавляется к сумме, если оно заканчивается на "5"
• нужен цикл с условием

?

Как это записать ?

сумма: = 0

пока не введён 0 :

если число оканчивается на "5" то

сумма: = сумма + число

если mod (x, 10 ) = 5 то

Обработка потока данных

Задача . С клавиатуры вводятся числа, ввод завершается числом 0. Найти сумму введённых чисел, оканчивающихся на цифру "5".

цел x, sum

sum: = 0

ввод x

нц пока x 0

если mod (x, 10 ) = 5 то

sum:= sum + x

все

ввод x

кц

вывод sum

?

Чего не хватает ?

Найди ошибку!

цел x, sum

sum: = 0

ввод x

ввод x

нц пока x 0

если mod (x, 10 ) = 5 то

sum:= sum + x

все

ввод x

кц

вывод sum

Задачи

« A »: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём. Определить, сколько получено чисел, которые делятся на 3.

« B »: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём. Определить, сколько получено двузначных чисел, которые заканчиваются на 3.

Задачи

« C »: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём. Найти среднее арифметическое всех двузначных чисел, которые делятся на 7.

« D »: На вход программы поступает неизвестное количество целых чисел, ввод заканчивается нулём. Найти максимальное из введённых чётных чисел.

Перестановка элементов массива

?

Как поменять местами значения двух переменных a и b ?

вспомогательная переменная

элементы массива:

с:= a

a:= b

b:= c

с:= A[i]

A[i]:= A[k]

A[k]:= c

Перестановка пар соседних элементов

Задача . Массив A содержит чётное количество элементов N. Нужно поменять местами пары соседних элементов: первый со вторым, третий — с четвёртым и т. д.

1

2

7

3

12

4

38

5

N-1

…

N

40

23

1

12

2

3

7

4

5

38

…

N-1

23

N

40

Перестановка пар соседних элементов

нц для i от 1 до N

поменять местами A[i] и A[i+1]

кц

?

Что плохо ?

1

2

7

12

3

4

38

5

5

6

40

23

12

7

38

5

40

23

выход за границы массива

12

38

7

5

40

23

12

38

5

7

40

23

12

38

5

40

7

23

?

12

38

5

40

23

7

Перестановка пар соседних элементов

не трогаем те, что уже переставлены

не выходим за границу

нц для i от 1 до N- 1 шаг 2

| переставляем A[i] и A[i+1]

с:= A[i]

A[i]:= A[i+ 1 ]

A[i+ 1 ]:= c

кц

A[ 1 ]  A[ 2 ], A[ 3 ]  A[ 4 ], …, A[N- 1 ]  A[N]

Реверс массива

Задача . Переставить элементы массива в обратном порядке (выполнить реверс ).

1

2

7

3

12

5

N-2

…

N-1

38

N

40

23

1

23

2

3

40

38

…

N -2

5

N-1

12

N

7

1 + N = N + 1

2 +N- 1 = N+ 1

A[ 1 ]  A[N]

A[ 2 ]  A[N- 1 ]

A[i]  A[N+ 1 -i]

A[N]  A[ 1 ]

i+ ??? = N+ 1

N+ 1 = N+ 1

Реверс массива

div (N ,2)

нц для i от 1 до N

поменять местами A[i] и A[ N+ 1 -i ]

кц

?

Что плохо ?

1

2

7

12

3

4

40

23

i= 1

i= 2

23

12

40

7

i= 3

23

40

12

7

23

12

40

7

i= 4

7

12

40

23

?

Как исправить ?

155

Конец фильма

ПОЛЯКОВ Константин Юрьевич

д.т.н., учитель информатики

ГБОУ СОШ № 163, г. Санкт-Петербург

[email protected]

ЕРЕМИН Евгений Александрович

к.ф.-м.н., доцент кафедры мультимедийной дидактики и ИТО ПГГПУ, г. Пермь

[email protected]

Источники иллюстраций

• иллюстрации художников издательства «Бином»
• авторские материалы