Передача параметров в подпрограмму

Глава 8. Алгоритмизация и программирование

Практические работы

«Каждый из нас лишь выиграет, создавая время от времени "игрушечные программы" с заданными искусственными ограничениями, заставляющими нас до предела напрягать свои способности... Искусство решения мини-задач на пределе своих возможностей оттачивает наше умение для реальных задач».

Д. Кнут.

Практическая работа № 25.
Простые вычисления

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

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

5 7 8

5+7+8=20

5*7*8=280

(5+7+8)/3=6.667

Уровень B. Ввести с клавиатуры координаты двух точек (A и B) на плоскости (вещественные числа). Вычислить длину отрезка AB. Пример:

Введите координаты точки A:

5.5 3.5

Введите координаты точки B:

1.5 2

Длина отрезка AB = 4.272

Уровень C. Получить случайное трехзначное число и вывести через запятую его отдельные цифры. Пример:

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

Его цифры 1, 2, 3.

Практическая работа № 26.
Ветвления

Уровень A. Ввести три целых числа, найти максимальное из них. Пример:

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

1 5 4

Максимальное число 5

Уровень B. Ввести пять целых чисел, найти максимальное из них. Пример:

Введите пять целых чисел:

1 5 4 3 2

Максимальное число 5

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

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

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

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

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

Пример:

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

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

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

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

Практическая работа № 27.
Сложные условия

Уровень A. Напишите программу, которая получает три числа и выводит количество одинаковых чисел в этой цепочке.

Пример:

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

5 5 5

Все числа одинаковые.

Пример:

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

5 7 5

Два числа одинаковые.

Пример:

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

5 7 8

Нет одинаковых чисел.

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

Пример:

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

Весна.

Пример:

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

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

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

Пример:

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

Вам 18 лет.

Пример:

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

Вам 21 год.

Пример:

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

Вам 22 года.

Практическая работа № 28.
Множественный выбор

Уровень A. Напишите программу, которая получает номер месяца и выводит его название и время года.

Пример:

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

Этот месяц – май, время года - весна.

Пример:

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

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

Уровень B. Напишите программу, которая получает день и номер месяца и определяет дату следующего дня. Считайте, что год невисокосный (365 дней).

Пример:

Введите день и месяц: 25 12

Следующий день: 26 декабря

Пример:

Введите день и месяц: 28 2

Следующий день: 1 марта

Уровень C. Напишите программу, которая получает день и номер месяца, а выводит количество дней, оставшихся до Нового Года. Считайте, что год невисокосный (365 дней). Учтите, что слово «дней» может иметь также формы «день» и «дня».

Пример:

Введите день и месяц: 25 12

Осталось 7 дней до Нового Года.

Пример:

Введите день и месяц: 1 1

Осталось 364 дня до Нового Года.

Пример:

Введите день и месяц: 31 2

Неверная дата.

Практическая работа № 29.
Задачи на ветвления

Уровень A. Напишите условие, которое определяет заштрихованную область. Проверьте свой ответ, используя программу C1.exe.

Уровень B. Напишите условие, которое определяет заштрихованную область. Проверьте свой ответ, используя программу C1.exe.

Уровень C. Напишите условие, которое определяет заштрихованную область. Проверьте свой ответ, используя программу C1.exe.

Практическая работа № 30.
Циклы с условием

Уровень A. Напишите программу, которая получает два целых числа A и B (0 < A < B) и выводит квадраты всех натуральных чисел в интервале от A до B.

Пример:

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

10 12

10*10=100

11*11=121

12*12=144

Уровень B. Напишите программу, которая получает два целых числа и находит их произведение, не используя операцию умножения. Учтите, что числа могут быть отрицательными.

Пример:

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

10 -15

10*(-15)=-150

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

Пример:

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

10000

Сумма 17710

Практическая работа № 31.
Циклы с условием – 2

Уровень A. Ввести натуральное число и найти сумму его цифр.

Пример:

Введите натуральное число:

12345

Сумма цифр 15.

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

Пример:

Введите натуральное число:

12342

Нет.

Пример:

Введите натуральное число:

12245

Да.

Уровень C. Ввести натуральное число и определить, верно ли, что в его записи есть
две одинаковые цифры (не обязательно стоящие рядом).

Пример:

Введите натуральное число:

12342

Да.

Пример:

Введите натуральное число:

12345

Нет.

Практическая работа № 32.
Циклы с переменной

Уровень A. Найдите все пятизначные числа, которые при делении на 133 дают в остатке 125, а при делении на 134 дают в остатке 111.

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

Уровень C. Натуральное число называется автоморфным, если оно равно последним цифрам своего квадрата. Например, 25² = 625. Напишите программу, которая получает натуральное число N и выводит на экран все автоморфные числа, не превосходящие N.

Пример:

Введите N:

1000

1*1=1

5*5=25

6*6=36

25*25=625

76*76=5776

Практическая работа № 33.
Вложенные циклы

Уровень A. Напишите программу, которая получает натуральные числа A и B (A<B) и выводит все простые числа в интервале от A до B.

Пример:

Введите границы диапазона:

10 20

11 13 17 19

Уровень B. В магазине продается мастика в ящиках по 15 кг, 17 кг, 21 кг. Как купить ровно 185 кг мастики, не вскрывая ящики? Сколькими способами можно это сделать?

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

Пример:

Введите N:

1 2 3 4 5 6 7 8 9 11 12 15

Практическая работа № 34.
Процедуры

Уровень A. 7. Напишите процедуру, которая принимает параметр – натуральное число N – и выводит на экран линию из N символов '–'.

Пример:

Введите N:

----------

Уровень B. Напишите процедуру, которая выводит на экран в столбик все цифры переданного ей числа, начиная с первой.

Пример:

Введите натуральное число:

1234

Уровень C. Напишите процедуру, которая выводит на экран запись переданного ей числа в римской системе счисления.

Пример:

Введите натуральное число:

2013

MMXIII

Практическая работа № 35.
Процедуры с изменяемыми параметрами

Уровень A. Напишите процедуру, которая переставляет три переданные ей числа в порядке возрастания.

Пример:

Введите три натуральных числа:

10 15 5

5 10 15

Уровень B. Напишите процедуру, которая сокращает дробь вида M/N. Числитель и знаменатель дроби передаются как изменяемые параметры.

Пример:

Введите числитель и знаменатель дроби:

25 15

После сокращения: 5/3

Уровень C. Напишите процедуру, которая вычисляет наибольший общий делитель и наименьшее общее кратное двух натуральных чисел и возвращает их через изменяемые параметры.

Пример:

Введите два натуральных числа:

10 15

НОД(10,15)=5

НОК(10,15)=30

Практическая работа № 36.
Функции

Уровень A. Напишите функцию, которая определяет сумму цифр переданного ей числа.

Пример:

Введите натуральное число:

123

Сумма цифр числа 123 равна 6.

Уровень B. Напишите функцию, которая находит наибольший общий делитель двух натуральных чисел.

Пример:

Введите два натуральных числа:

7006652 112307574

НОД(7006652,112307574) = 1234.

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

Пример:

Введите натуральное число:

1234

После переворота: 4321.

Практическая работа № 37.
Логические функции

Уровень A. Напишите логическую функцию, которая определяет, является ли переданное ей число совершенным, то есть, равно ли оно сумме своих делителей, меньших его самого.

Пример:

Введите натуральное число:

Число 28 совершенное.

Пример:

Введите натуральное число:

Число 29 не совершенное.

Уровень B. Напишите логическую функцию, которая определяет, являются ли два переданные ей числа взаимно простыми, то есть, не имеющими общих делителей, кроме 1.

Пример:

Введите два натуральных числа:

28 15

Числа 28 и 15 взаимно простые.

Пример:

Введите два натуральных числа:

28 16

Числа 28 и 16 не взаимно простые.

Уровень C. Простое число называется гиперпростым, если любое число, получающееся из него откидыванием нескольких цифр, тоже является простым. Например, число 733 – гиперпростое, так как и оно само, и числа 73 и 7 – простые. Напишите логическую функцию, которая определяет, верно ли, что переданное ей число – гиперпростое. Используйте уже готовую функцию isPrime, которая приведена в учебнике.

Пример:

Введите натуральное число:

733

Число 733 гиперпростое.

Пример:

Введите натуральное число:

Число 19 не гиперпростое.

Практическая работа № 38.
Рекурсия

Уровень A. Напишите рекурсивную функцию, которая вычисляет НОД двух натуральных чисел, используя модифицированный алгоритм Евклида.

Пример:

Введите два натуральных числа:

7006652 112307574

НОД(7006652,112307574) = 1234.

Уровень B. Напишите рекурсивную функцию, которая раскладывает число на простые сомножители.

Пример:

Введите натуральное число:

378

378 = 2*3*3*3*7

Уровень C. Дано натуральное число N. Требуется получить и вывести на экран количество всех возможных различных способов представления этого числа в виде суммы натуральных чисел (то есть, 1 + 2 и 2 + 1 – это один и тот же способ разложения числа 3). Решите задачу с помощью рекурсивной функции.

Пример:

Введите натуральное число:

Количество разложений: 4

Практическая работа № 39.
Стек

Из учебника (§ 61) вы уже знаете, что при вызове процедур важнейшую роль играет стек – область оперативной памяти, в которой хранятся адрес возврата из процедуры и локальные переменные. В этой практической работе мы познакомимся с работой стека на примере учебного компьютера «ЛамПанель», с которым вы уже встречались при изучении глав 4 и 5.

Возможности программы «ЛамПанель»

Программа «ЛамПанель» – это модель процессора, который управляет ламповой панелью, то есть, может с помощью специальных команд зажигать и гасить определенные лампочки.

Стек в программе «ЛамПанель» размещается в оперативной памяти, вместе с программой и данными. Оперативная память имеет размер 256 байт, адреса ячеек (байтов) изменяются от 0 до 255 = FF₁₆. Программа начинается с адреса 0 (в начале области памяти), данные обычно расположены сразу за ней. Стек находится в самом конце оперативной памяти и «растет вверх». Это значит, что первое записанное в стек 16-битное слово имеет адрес FE₁₆ (последние два байта памяти), следующее записанное слово – адрес FC₁₆ и т.д. Как же компьютер разбирается, где начинается стек и сколько чисел туда записано?

В процессоре есть специальный регистр SP (от англ. Stack Pointer – указатель стека), в котором хранится адрес вершины стека, то есть последнего записанного в стек 16-битного значения. При запуске программы в регистр SP записывается значение 100₁₆ (область 1 на рисунке). Этот адрес находится за границами оперативной памяти и говорит о том, что стек пуст.

Для того, чтобы записать значение из регистра общего назначения в стек, используется команда PUSH (от англ. push – втолкнуть). Например, при выполнении этих команд в стек будет записано значение регистра R0:

MOV 1234,R0

PUSH R0

Обратите внимание на значение регистра SP – оно стало равно FE₁₆ и теперь указывает на последнее слово памяти (область 2 на рисунке), в котором записано число 1234₁₆ – значение регистра R0 (сначала младший байт, потом старший).

Добавим к программе еще одну команду, которая «снимает» 16-битное значение с вершины стека и записывает его в регистр R2:

POP R2

После этого наблюдаем следующее (см. рисунок ниже):

в регистре R2 находится то же значение 1234₁₆, которое было в R0 (область 1)
регистр SP содержит значение 100₁₆, которое говорит о том, что стек пуст (область 2)
в последних двух байтах памяти осталось значение 1234₁₆, которое было записано в стек (область 3), но теперь оно уже не является часть стека, поскольку регистр SP изменен.

Вызов подпрограмм

Как вы знаете, подпрограммы – это вспомогательные алгоритмы. Напишем подпрограмму, которая возводит в квадрат значение регистра R0. Эта подпрограмма содержит всего одну команду умножения (умножить R0 на R0, записать результат в R0):

MUL R0, R0

В начале подпрограммы нужно поставить метку (имя подпрограммы), а в конце – команду возврата RET (от англ. return – возврат), по которой процессор возвращается в точку вызова. Таким образом, вся подпрограмма, которую мы назовём SQR, выглядит так:

SQR:

MUL R0, R0

RET

«Паспорт» этой подпрограммы такой:

Вход: число в регистре R0

Выход (результат): квадрат числа в регистре R0

Подпрограмма располагается ниже основной программы. Чтобы вызвать подпрограмму, используют команду CALL (от англ. call – вызвать), после которой записывают имя подпрограммы – метку, с которой она начинается, адрес точки входа. Вот вся программа вместе с подпрограммой:

MOV 12,R0; записать начальное значение в R0

CALL SQR ; вызвать подпрограмму SQR

STOP ; конец основной программы

SQR: ; точка входа подпрограммы

MUL R0, R0; тело подпрограммы – возведение R0 в квадрат

RET ; возврат из подпрограммы

Остается один вопрос: как процессор определяет адрес возврата из подпрограммы, когда выполняется команда RET? Заметим, что в самой команде RET адрес не указан. Дело в том, что адрес перехода заранее определить нельзя (нельзя поставить команду безусловного перехода JMP), потому что подпрограмма может вызываться из разных мест программы, в том числе из других подпрограмм. Эту проблему оказалось просто решить с помощью стека:

команда CALL записывает в стек адрес возврата из подпрограммы, то есть адрес команды, следующей за командой CALL; поскольку регистр PC (программный счётчик) всегда содержит адрес следующей команды, процессору достаточно просто скопировать содержимое регистра PC в стек;
после этого в регистр записывается адрес указанной подпрограммы и ей передается управление;
команда RET снимает с вершины стека адрес возврата и записывает его в регистр PC, таким образом управление передается следующей команде вызывающей программы.

Сохранение регистров

Теперь напишем более сложную подпрограмму, которая возводит R0 в куб. Теперь для вычисления придется задействовать ещё один регистр, например, R1:

MOV R0,R1; скопировать R0 в R1

MUL R0,R0; возвести R0 в квадрат

MUL R1,R0; умножить R1 на R0

Все хорошо, но… мы стерли значение регистра R1, которое было до вызова подпрограммы. Чтобы при вызове подпрограммы регистры не стирались, их нужно сохранять при входе в подпрограмму и восстанавливать перед самым выходом. Где сохранять? Самый простой выход – использовать стек, сохранять командой PUSH, и восстанавливать командой POP. Таким образом полный текст подпрограммы CUBE выглядит так:

CUBE:

PUSH R1 ; сохраняем R1

MOV R0,R1 ; скопировать R0 в R1

MUL R0,R0 ; возвести R0 в квадрат

MUL R1,R0 ; умножить R1 на R0

POP R1 ; восстанавливаем R1

RET

Передача параметров в подпрограмму

В предыдущих примерах вы уже увидели, что параметры (дополнительные данные) могут передаваться в подпрограмму через регистры общего назначения R0-R3. Но этих регистров всего четыре, поэтому таким способом можно передать только четыре 16-битных числа. А что, если нужно передать, например, массив из 100 элементов? В этом случае на помощь приходит стек.

Перед вызовом подпрограммы в стек записываются все передаваемые параметры. рассмотрим сначала «игрушечную» задачу – написать подпрограмму, которая возводит число в квадрат, причем это число передается через стек. Результат должен быть помещен в регистр R0.

Перед вызовом подпрограммы запишем в стек значение R0:

0000 MOV 12,R0; это число нужно возвести в квадрат

0004 PUSH R0 ; запишем его в стек

0006 CALL SQR ; вызов подпрограммы

000A STOP

000C SQR:

... ; здесь будет подпрограмма

Если посмотреть на стек (в нижней части оперативной памяти), то после выполнения команды PUSH R0 он выглядит так:

SP-> 00FE 0012

Указатель стека SP содержит адрес 00FE и указывает на последнее 16-битное слово памяти. В стеке находится число 12₁₆ – значение, передаваемое в подпрограмму.

Когда выполнится команда CALL, в стек запишется адрес возврата из подпрограммы, то есть адрес 000A₁₆, по которому расположена команда STOP. На этот адрес и будет указывать регистр SP:

SP-> 00FC 000A

00FE 0012

Теперь займемся подпрограммой: как «достать» переданное значение? Сначала нужно скопировать содержимое указателя стека в какой-то регистр общего назначения, например, в R0:

MOV SP,R0

Теперь в R0 находится адрес вершины стека, но там лежит адрес возврата. Чтобы получить адрес переданного параметра, нужно увеличить R0 на 2:

ADD 2,R0

Теперь можно взять значение по этому адресу и записать его в тот же регистр R0:

MOV (R0),R0

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

SQR:

MOV SP,R0

ADD 2,R0

MOV (R0),R0

MUL R0,R0

RET

Остается один вопрос – кто же будет освобождать стек, удаляя из него параметры подпрограммы? Тут есть два варианта. Этим может заниматься вызывающая программа – после вызова подпрограмму нужно использовать команду POP. Кроме того, это может делать и процедура – для этого нужно применить команду RET с параметром, который обозначает количество байт, которые нужно «сбросить» со стека. Например, в нашем случае можно применить команду

RET 2

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

Таким образом, если параметров мало, их удобно передавать через регистры R0-R3. Кроме того, параметры можно передавать через стек. Если подпрограмма обрабатывает большой массив, лучше передать ей адрес этого массива, вместо того, чтобы записывать его в стек.

Рекурсия

Для процессора рекурсивная подпрограмма ничем не отличается от «обычной». Только внутри рекурсивной подпрограммы есть вызов CALL по адресу той же самой подпрограммы.

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

Факториал числа вычисляется как произведение всех натуральных чисел от 1 до : . Основная идея подпрограммы может быть записана на псевдокоде так:

R1:=R0

R0:=R0-1

вычисляем факториал R0 (вызов процедуры)

R0:=R0*R1

Перевод на язык ассемблера дает:

FACT:

MOV R0,R1

SUB 1,R0

CALL FACT

MUL R1,R0

FINISH:

RET

Однако, выполнение этой подпрограммы никогда не закончится, потому что вызовы никогда не остановятся. Нужно добавить условие выхода: если R0=1, нужно выйти из подпрограммы, то есть перейти на последнюю команду RET (перед ней должна быть метка):

FACT:

CMP 1,R0

JZ FINISH

MOV R0,R1

SUB 1,R0

CALL FACT

MUL R1,R0

FINISH:

RET

Остается еще один недостаток – подпрограмма изменяет значение регистра R1. Нужно при входе в процедуру сохранить его (в стеке), а перед выходом – восстановить. Это вы уже можете сделать самостоятельно.

Задание на практическую работу

1. Запустите тренажёр «ЛамПанель». Напишите и отладьте программу, которая меняет местами значение регистров R2 и R3 с помощью стека (не используя других регистров общего назначения).

Программа:

Опишите, как работает стек при выполнении этой программы:

2. Введите текст программы

MOV 12,R0

CALL SQR

STOP

SQR:

MUL R0,R0

RET

Заполните таблицу, выполнив программу пошагово с помощью клавиши F7 (пошаговое выполнение со входом в подпрограммы):

Адрес	Команда	Регистры после ее выполнения
Адрес	Команда	R0	PC	SP
		?	0000	0100
	MOV 12,R0
	CALL SQR
	STOP
	MUL R0,R0
	RET

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

Программа:

4. Напишите и отладьте программу с подпрограммой, которая и строит RGB-код цвета, 4-битные составляющие которого (R, G и B), записаны соответственно в регистры R0, R1 и R2. Результат должен быть получен в регистре R0.

Программа:

5. Выполните предыдущее задание при условии, что параметры передаются через стек, а значения регистров R1 и R2 не должны измениться.

Программа:

6. Отладьте программу с рекурсивной подпрограммой, которая вычисляет факториал числа, записанного в регистр R0. При выполнении в пошаговом режиме (клавиша F7) наблюдайте, как изменяется регистр SP и содержимое стека.

Программа:

7. Решите задачу предыдущего пункта, используя подпрограмму без рекурсии.

Программа:

Практическая работа № 40.
Перебор элементов массива

Уровень A. Заполните массив случайными числами в интервале [0,100] и найдите среднее арифметическое его значений.

Пример:

Массив:

1 2 3 4 5

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

Уровень B. Заполните массив случайными числами в интервале [0,100] и подсчитайте отдельно среднее значение всех элементов, которые <50, и среднее значение всех элементов, которые ≥50.

Пример:

Массив:

3 2 52 4 60

Среднее арифметическое элементов [0,50): 3.000

Среднее арифметическое элементов [50,100): 56.000

Уровень C. Заполните массив из N элементов случайными числами в интервале [1,N] так, чтобы в массив обязательно вошли все числа от 1 до N (постройте случайную перестановку).

Пример:

Массив:

3 2 1 4 5

Практическая работа № 41.
Линейный поиск

Уровень A. Заполните массив случайными числами в интервале [0,5]. Введите число X и найдите все значения, равные X.

Пример:

Массив:

1 2 3 1 2

Что ищем:

Нашли: A[2]=2, A[5]=2

Пример:

Массив:

1 2 3 1 2

Что ищем:

Ничего не нашли.

Уровень B. Заполните массив случайными числами в интервале [0,5]. Определить, есть ли в нем элементы с одинаковыми значениями, стоящие рядом.

Пример:

Массив:

1 2 3 3 2 1

Есть: 3

Пример:

Массив:

1 2 3 4 2 1

Нет

Уровень C. Заполните массив случайными числами. Определить, есть ли в нем элементы с одинаковыми значениями, не обязательно стоящие рядом.

Пример:

Массив:

3 2 1 3 2 5

Есть: 3, 2

Пример:

Массив:

3 2 1 4 0 5

Нет

Практическая работа № 42.
Поиск максимального элемента массива

Уровень A. Заполните массив случайными числами и найти минимальный и максимальный элементы массива и их номера.

Пример:

Массив:

1 2 3 4 5

Минимальный элемент: A[1]=1

Максимальный элемент: A[5]=5

Уровень B. Заполните массив случайными числами и найти два максимальных элемента массива и их номера.

Пример:

Массив:

5 5 3 4 1

Максимальный элемент: A[1]=5

Второй максимум: A[2]=5

Уровень C. Введите массив с клавиатуры и найдите (за один проход) количество элементов, имеющих максимальное значение.

Пример:

Массив:

3 4 5 5 3 4 5

Максимальное значение 5

Количество элементов 3

Практическая работа № 43.
Алгоритмы обработки массивов

Уровень A. В. Заполнить массив случайными числами и выполнить циклический сдвиг элементов массива вправо на 1 элемент.

Пример:

Массив:

1 2 3 4 5 6

Результат:

6 1 2 3 4 5

Уровень B. Массив имеет четное число элементов. Заполнить массив случайными числами и выполнить реверс отдельно в первой половине и второй половине.

Пример:

Массив:

1 2 3 4 5 6

Результат:

3 2 1 6 5 4

Уровень C. Заполнить массив случайными числами в интервале [-100,100] и переставить элементы так, чтобы все положительные элементы стояли в начала массива, а все отрицательные и нули – в конце. Вычислите количество положительных элементов.

Пример:

Массив:

20 -90 15 -34 10 0

Результат:

20 15 10 -90 -34 0

Количество положительных элементов: 3

Практическая работа № 44.
Отбор элементов массива по условию

Уровень A. Заполнить массив случайными числами в интервале [-10,10] и отобрать в другой массив все чётные отрицательные числа.

Пример:

Массив А:

-5 6 7 -4 -6 8 -8

Массив B:

-4 -6 -8

Уровень B. Заполнить массив случайными числами в интервале [0,100] и отобрать в другой массив все простые числа. Используйте логическую функцию, которая определяет, является ли переданное ей число простым.

Пример:

Массив А:

12 13 85 96 47

Массив B:

13 47

Уровень C. Заполнить массив случайными числами и отобрать в другой массив все числа Фибоначчи. Используйте логическую функцию, которая определяет, является ли переданное ей число числом Фибоначчи.

Пример:

Массив А:

12 13 85 34 47

Массив B:

13 34

Практическая работа № 45.
Сортировка. Метод пузырька

Уровень A. Напишите программу, в которой сортировка выполняется «методом камня» – самый «тяжёлый» элемент опускается в конец массива.

Уровень B. Напишите вариант метода пузырька, который заканчивает работу, если на очередном шаге внешнего цикла не было перестановок.

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

Практическая работа № 46.
Сортировка. Метод выбора

Уровень A. Массив содержит четное количество элементов. Напишите программу, которая сортирует первую половину массива по возрастанию, а вторую – по убыванию. Каждый элемент должен остаться в «своей» половине.

Пример:

Массив:

5 3 4 2 1 6 3 2

После сортировки:

2 3 4 5 6 3 2 1

Уровень B. Напишите программу, которая сортирует массив и находит количество различных чисел в нем.

Пример:

Массив:

5 3 4 2 1 6 3 2 4

После сортировки:

1 2 2 3 3 4 4 5 6

Различных чисел: 6

Уровень C. Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком» и методом выбора. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

Практическая работа № 47.
Быстрая сортировка

Уровень A. Массив содержит четное количество элементов. Напишите программу, которая сортирует по возрастанию отдельно элементы первой и второй половин массива. Каждый элемент должен остаться в «своей» половине. Используйте алгоритм быстрой сортировки.

Пример:

Массив:

5 3 4 2 1 6 3 2

После сортировки:

2 3 4 5 1 2 3 6

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

Пример:

Массив:

5 3 4 2 1 6 3 2 4

После сортировки:

1 2 2 3 3 4 4 5 6

Различных чисел: 5

Уровень C. Напишите программу, которая сравнивает число перестановок элементов при использовании сортировки «пузырьком», методом выбора и алгоритма быстрой сортировки. Проверьте ее на разных массивах, содержащих 1000 случайных элементов, вычислите среднее число перестановок для каждого метода.

Уровень D. Попробуйте построить массив из 10 элементов, на котором алгоритм быстрой сортировки показывает худшую эффективность (наибольшее число перестановок). Сравните это количество перестановок с эффективностью метода пузырька (для того же массива).

Практическая работа № 48.
Двоичный поиск

Уровень A. Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Подсчитать количество сравнений.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

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

Число 2 найдено.

Количество сравнений: 2

Уровень B. Заполнить массив случайными числами и отсортировать его. Ввести число X. Используя двоичный поиск, определить, сколько чисел, равных X, находится в массиве.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

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

Число 4 встречается 2 раз(а).

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 7 9

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

Число 14 не встречается.

Уровень C. Заполнить массив случайными числами и ввести число и отсортировать его. Ввести число X. Используя двоичный поиск, определить, есть ли в массиве число, равное X. Если такого числа нет, вывести число, ближайшее к X.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 12 19

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

Число 12 найдено.

Пример:

Массив:

1 4 7 3 9 2 4 5 2

После сортировки:

1 2 2 3 4 4 5 12 19

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

Число 11 не найдено.

Ближайшее число 12.

Практическая работа № 49.
Посимвольная обработка строк

Уровень A. Ввести с клавиатуры символьную строку и заменить в ней все буквы «а» на «б» и все буквы «б» на «а» (заглавные на заглавные, строчные на строчные).

Пример:

Введите строку:

ааббААББссСС

Результат:

ббааББААссСС

Уровень B. Ввести с клавиатуры символьную строку и определить, сколько в ней слов. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы.

Пример:

Введите строку:

Вася пошел гулять

Найдено слов: 3

Уровень C. Ввести с клавиатуры символьную строку и найдите самое длинное слово и его длину. Словом считается последовательности непробельных символов, отделенная с двух сторон пробелами (или стоящая с краю строки). Слова могут быть разделены несколькими пробелами, в начале и в конце строки тоже могут быть пробелы.

Пример:

Введите строку:

Вася пошел гулять

Самое длинное слово: гулять, длина 6

Практическая работа № 50.
Функции для работы со строками

Уровень A. Ввести с клавиатуры в одну строку фамилию, имя и отчество, разделив их пробелом. Вывести фамилию и инициалы.

Пример:

Введите фамилию, имя и отчество:

Иванов Петр Семёнович

П.С. Иванов

Уровень B. Ввести адрес файла и «разобрать» его на части, разделенные знаком '/'. Каждую часть вывести в отдельной строке.

Пример:

Введите адрес файла:

C:/Фото/2013/Поход/vasya.jpg

Фото

2013

Поход

vasya.jpg

Уровень C. Напишите программу, которая заменяет во всей строке одну последовательность символов на другую.

Пример:

Введите строку:

(X > 0) and (Y < X) and (Z > Y) and (Z <> 5)

Что меняем: and

Чем заменить: &

Результат

(X > 0) & (Y < X) & (Z > Y) & (Z <> 5)

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

Уровень A. Напишите программу, которая вычисляет сумму трех чисел, введенную в форме символьной строки. Все числа целые.

Пример:

Введите выражение:

12+3+45

Ответ: 60

Уровень B. Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются только знаки «+» или «–»). Выражение вводится как символьная строка, все числа целые.

Пример:

Введите выражение:

12-3+45

Ответ: 54

Уровень C. Напишите программу, которая вычисляет выражение, состоящее из трех чисел и двух знаков (допускаются знаки «+», «–», «*» и «/»). Выражение вводится как символьная строка, все числа целые. Операция «/» выполняется как целочисленное деление (div).

Пример:

Введите выражение:

12*3+45

Ответ: 81

Уровень D. Напишите программу, которая вычисляет выражение, состоящее из чисел, знаков (допускаются знаки «+», «–», «*» и «/») и круглых скобок. Выражение вводится как символьная строка, все числа целые. Операция «/» выполняется как целочисленное деление (div).

Пример:

Введите выражение:

2*(3+45)+4

Ответ: 100

Практическая работа № 52.
Строки в процедурах и функциях

Уровень A. Напишите функцию, которая возвращает первое слово переданной ей символьной строки.

Пример:

Введите строку: Однажды в студёную зимнюю пору...

Первое слово: Однажды

Уровень B. Напишите функцию, которая заменяет расширение файла на заданное новое расширение.

Пример:

Введите имя файла: qq

Введите новое расширение: tmp

Результат: qq.tmp

Пример:

Введите имя файла: qq.exe

Введите новое расширение: tmp

Результат: qq.tmp

Пример:

Введите имя файла: qq.work.xml

Введите новое расширение: tmp

Результат: qq.work.tmp

Уровень C. Напишите функцию, которая заменяет во всей строке все римские числа на соответствующие десятичные числа.

Пример:

Введите строку:

В MMXIII году в школе CXXIII состоялся очередной выпуск XI классов.

Результат:

В 2013 году в школе 123 состоялся очередной выпуск 11 классов.

Практическая работа № 53.
Рекурсивный перебор

Уровень A. В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых вторая буква «Ы». Подсчитайте количество таких слов.

Уровень B. В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, стоящие рядом. Подсчитайте количество таких слов.
Программа не должна строить другие слова, не соответствующие условию.

Уровень C. В алфавите языке племени «тумба-юмба» четыре буквы: «Ы», «Ш», «Ч» и «О». Нужно вывести на экран все возможные слова, состоящие из K букв, в которых есть по крайней мере две одинаковые буквы, не обязательно стоящие рядом.
Программа не должна строить другие слова, не соответствующие условию.

Практическая работа № 54.
Сравнение и сортировка строк

Уровень A. Вводится 5 строк, в которых сначала записан порядковый номер строки с точкой, а затем – слово. Вывести слова в алфавитном порядке.

Пример:

Введите 5 строк:

1. тепловоз

2. арбуз

3. бурундук

4. кефир

5. урядник

Список слов в алфавитном порядке:

арбуз, бурундук, кефир, тепловоз, урядник

Уровень B. Вводится несколько строк (не более 20), в которых сначала записан порядковый номер строки с точкой, а затем – слово. Ввод заканчивается пустой строкой. Вывести введённые слова в алфавитном порядке.

Пример:

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

1. тепловоз

2. арбуз

Список слов в алфавитном порядке:

арбуз, тепловоз

Уровень C. Вводится несколько строк (не более 20), в которых сначала записаны инициалы и фамилии работников фирмы. Ввод заканчивается пустой строкой. Отсортировать строки в алфавитном порядке по фамилии.

Пример:

Введите ФИО:

А.Г. Урядников

Б.В. Тепловозов

В.Д. Арбузов

Список в алфавитном порядке:

В.Д. Арбузов

Б.В. Тепловозов

А.Г. Урядников

Практическая работа № 55.
Обработка символьных строк: сложные задачи

Уровень A. На вход программы подаются данные о результатах районной олимпиады. В первой строке – количество участников N, а следующие N строк имеют следующий формат:

<Фамилия> <Имя> <Баллы>

Здесь <Фамилия> – строка, состоящая не более чем из 20 символов; <Имя> – строка, состоящая не более чем из 15 символов; <Баллы> – целое число, обозначающее общее количество баллов, набранное участником. Все данные разделены пробелами. Пример входной строки:

Петечкин Вася 152

На городскую олимпиаду проходят участники, набравшие в сумме более 100 баллов. Требуется вывести количество участников, прошедших на городскую олимпиаду.

Уровень B. На вход программы подаются данные о результатах районной олимпиады. В первой строке – количество участников N, а следующие N строк имеют следующий формат:

<Фамилия> <Имя> <Баллы>

Петечкин Вася 152

На городскую олимпиаду проходят участники, набравшие в сумме более 100 баллов. Требуется вывести список участников, прошедших на городскую олимпиаду (известно, что их не более 25).

Уровень C. На вход программы подаются данные о результатах районной олимпиады. В первой строке – количество участников N (не более 100), а следующие N строк имеют следующий формат:

<Фамилия> <Имя> <Баллы>

Петечкин Вася 152

На городскую олимпиаду проходят лучшие 25 участников (набравшие в сумме наибольшее количество баллов). Если другие участники набрали столько же баллов, что и участник, занявший 25-е место, они тоже приглашаются на городскую олимпиаду. Требуется вывести список участников, прошедших на городскую олимпиаду, отсортировав его по фамилии (в алфавитном порядке).

Практическая работа № 56.
Матрицы

Уровень A. Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], и находит максимальный и минимальный элементы в матрице и их индексы.

Пример:

Матрица А:

12 14 67 45

32 87 45 63

69 45 14 11

40 12 35 15

Максимальный элемент A[2,2]=87

Минимальный элемент A[3,4]=11

Уровень B. Пиксели рисунка закодированы числами от 0 до 255 (обозначающими яркость пикселей) в виде матрицы, содержащей N строк и M столбцов. Нужно преобразовать рисунок в черно-белый по следующему алгоритму:

· вычислить среднюю яркость пикселей по всему рисунку

· все пиксели, яркость которых меньше средней, сделать черными (записать код 0), а остальные – белыми (код 255)

Пример:

Матрица А:

12 14 67 45

32 87 45 63

69 45 14 11

40 12 35 15

Средняя яркость 37.88

Результат:

0 0 255 255

0 255 0 255

255 255 0 0

255 0 0 0

Уровень C. Заполните матрицу, содержащую N строк и M столбцов, натуральными числами по спирали и змейкой, как на рисунках:

Практическая работа № 57.
Обработка блоков матрицы

Уровень A. Напишите программу, которая заполняет квадратную матрицу случайными числами в интервале [10,99], а затем записывает нули во все элементы выше главной диагонали. Алгоритм не должен изменяться при изменении размеров матрицы.

Пример:

Матрица А:

12 14 67 45

32 87 45 63

69 45 14 30

40 12 35 65

Результат:

12 0 0 0

32 87 0 0

69 45 14 0

40 12 35 65

Уровень B. Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните отражение рисунка сверху вниз:

Уровень C. Пиксели рисунка закодированы числами (обозначающими цвет) в виде матрицы, содержащей N строк и M столбцов. Выполните поворот рисунка вправо на 90 градусов:

Практическая работа № 58.
Файловый ввод и вывод

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

Уровень B. Напишите программу, которая находит минимальное и максимальное среди чётных положительных чисел, записанных в файле, и выводит результат в другой файл. Учтите, что таких чисел может вообще не быть.

Уровень C. В файле в столбик записаны целые числа, сколько их – неизвестно. Напишите программу, которая определяет длину самой длинной цепочки идущих подряд одинаковых чисел и выводит результат в другой файл.

Практическая работа № 59.
Обработка массивов из файла

Уровень A. В файле записано не более 100 чисел. Отсортировать их по возрастанию последней цифры и записать в другой файл.

Уровень B. В файле записано не более 100 чисел. Отсортировать их по возрастанию суммы цифр и записать в другой файл. Используйте функцию, которая вычисляет сумму цифр числа.

Уровень C. В двух файлах записаны отсортированные по возрастанию массивы неизвестной длины. Объединить их и записать результат в третий файл. Полученный массив также должен быть отсортирован по возрастанию.

Практическая работа № 60.
Обработка смешанных данных из файла

Уровень A. В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и количество баллов, разделенные пробелами:

<Фамилия> <Имя> <Количество баллов>

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

Уровень B. В предыдущей задаче добавить к полученному списку нумерацию, сократить имя до одной буквы и поставить перед фамилией:

1) П. Иванов

2) И. Петров

3)...

Уровень C. В файле записаны данные о результатах сдачи экзамена. Каждая строка содержит фамилию, имя и количество баллов, разделенные пробелами:

<Фамилия> <Имя> <Количество баллов>

Вывести в другой файл данные учеников, которые получили больше 80 баллов. Список должен быть отсортирован по убыванию балла. Формат выходных данных:

1) П. Иванов 98

2) И. Петров 96

3)...

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:

Основные закономерности психического развития

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

Лексическое и грамматическое значение слова

Расчет нормальной концентрации

Соучастие в преступлении: понятие и признаки. Виды соучастников и формы соучастия

НЭП: ПРИЧИНЫ, СУЩНОСТЬ И ПРОТИВОРЕЧИЯ

Самый сильный аргумент, почему эволюция человека не могла быть