50 задач по началам программирования

Введение

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

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

Задачи, для большей пользы, надо решать подряд. Пропускать можно только задачи повышенной трудности (помеченные звездочкой) лишь в том случае, если решить их Вы не можете.

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

Поясним некоторые обозначения. В задачнике встречаются названия задач, начинающиеся латинскими заглавными буквами и цифрами. Эти условные обозначения показывают, когда и на каком соревновании по программированию давалась данная задача. Число после букв указывает год, а буквы обозначают само соревнование. DOI –районные олимпиады школьников Удмуртии. MFOI – олимпиада про программированию Удмуртского государственного университета для поступающих на математический факультет. MARK – студенческая олимпиада, спонсируемая ассоциацией предприятий МАРК. Некоторые части примеров записаны разными шрифтами. Если текст написан таким шрифтом, то этот текст выводится на экран, если таким шрифтом, тот этот текст надо набирать с клавиатуры.

После того, как для решения задачи придуман алгоритм и готова программа, надо проверить, правильно ли она работает. Для этого очень часто применяется метод тестов. Этот метод используется следующим образом: придумывают входные данные и вычисляют, какие должны быть выходные значения.

Входные данные, правильный ответ и время, через которое программа должна дать ответ, называют тестом. Потом входные данные задаются программе и проверяют, совпадают ли вычисленные ранее выходные значения и результат работы программы. Если программа выдала ответ, такой как было вычислено ранее, не позже заданного времени, то тест считается пройденным. Для большей уверенности нужно придумать несколько тестов и выполнить для них программу. Придумывать тесты для программы надо так, как будто Вы желаете, чтобы программа не смогла их пойти.

Этот способ не даёт полной гарантии того, что программа работает правильно. Не существует способа проверить любую программу лучше, чем хорошо подобранным набором тестов.

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

Проверять решение нужно так:

0. Придумайте несколько (не меньше трёх) тестов для Вашей программы.

1. В каждой задаче есть пример. Проверьте, правильно ли работает Ваша программа на этом примере. Если пример не пройден то, нужно исправить ошибки в программе или алгоритме[1]. И вернуться к пункту 1. Только после того, как программа пройдет пример, можно идти дальше.

2. Проверьте программу на тестах из пункта 0. Если программа прошла не все тесты, исправьте программу или алгоритм и вернитесь к пункту 1. Если удалось пройти все тесты, то переходите к пункту 3.

3. Теперь нужно открыть тесты в конце книги. Проверять программу тестами нужно обязательно подряд, начиная с первого. Проверять нужно до тех пор, пока программа проходит тесты. Но как только программа тест не прошла, необходимо вернуться к пункту 1. Если программа прошла все тесты, то эту задачу Вы сделали полностью и можно переходить к следующей.

Задачи

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

ПРИМЕР 1.

Имя: Слава

Здравствуй, Слава!

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

ПРИМЕР 2.

Первое число: 15

Второе число: 12

Ответ: 27

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

ПРИМЕР 3.

Первое число: 15

Второе число: 12

15+12=27

Написать программу, подсчитывающую количество символов в заданной строке. Ответ должен быть развернутым.

ПРИМЕР 4.

Строка: Мама мыла раму

В строке: Мама мыла раму символов: 14

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

ПРИМЕР 5.

Фамилия: Пупышев

Имя: Вячеслав

Отчество: Викторович

Пупышев В.В.

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

ПРИМЕР 6.

Первое число:15

Второе число:6

Число 6 не больше числа 15.

ДЛЯ РЕШЕНИЯ СЛЕДУЮЩИХ ЗАДАЧ НЕОБХОДИМО ЗНАТЬ, КАК ПРОГРАММИРОВАТЬ ВЕТВЛЕНИЯ АЛГОРИТМА.

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

ПРИМЕР 7.

Первое число: 6

Второе число: 2

6 : 2 = 3

Известно, что на 0 делить нельзя. В задаче N11 при вводе 2 и 0 возникает аварийная ситуация. Избавьтесь от нее.

ПРИМЕР 8.

Первое число: 2

Второе число: 0

На ноль делить НЕЛЬЗЯ !!!

Написать программу, которая читает строку и, если это Ваше имя, пишет: "Привет ", а если нет, пишет: "Здравствуйте! ".

Заметим, у каждого автора программы своё имя.

ПРИМЕР 9 (для автора):

Имя: Слава

Привет!

Написать программу, которая определяет, чётное[2] ли число.

ПРИМЕР 10.

Число: 10

Чётное

Написать программу, которая читает строку и определяет, что это, Ваше имя, фамилия или отчество. Если ни то, ни другое и не третье, то пишет: "НЕ ЗНАЮ". Заметим, у каждого автора программы свои имя, фамилия и отчество.

ПРИМЕР 11 (для автора задачника):

Строка: Викторович

Викторович - Ваше отчество.

Сделать программу, которая читает число от 1 до 5 и печатает название оценки.

ПРИМЕР 12.

Оценка: 1

Очень плохо.

Решить предыдущую задачу (N16), но можно вводить любое целое число. Если число не является оценкой, печатать: Не оценка.

ПРИМЕР 13:

Оценка: -3

Не оценка.

Четырёхзначное число называется счастливым, если сумма первых двух его цифр равна сумме двух последних. Ваша программа должна читать число четырёхзначное и определять счастливое ли оно.

ПРИМЕР 14:

Число: 9889

Счастливое.

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

ПРИМЕР :

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

3 8 19 11

3 8 11 19

Написать программу, печатающую все целые числа от 10 до 100 включительно.

Написать программу, печатающую все целые числа от 2 до 100 включительно.

Написать программу, печатающую все целые числа, большие N и меньшие 0. Эти числа должны делиться на 3.Число N запрашивает программа.

ПРИМЕР.

N= -9

-6 -3

Написать программу, которая печатает 10 разных целых чисел, не меньших А и делящихся на R нацело. Целые A и R запрашивает программа.

ПРИМЕР :

А= 11

R=2

12 14 16 18 20 22 24 26 28 30

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

ПРИМЕР:

Мама мыла раму !

В строке Мама мыла раму! букв ы - 1.

Минимизировать количество пробелов в заданной строке.

В этой задаче требуется написать программу, которая убирает лишние пробелы. Лишние - это начальные и конечные пробелы строки а также те которые идут подряд. Нужно оставить из группы пробелов только один.

ПРИМЕР.

Строка: _ _ _ _ааа _ _ёёё _ _ _ВВВ _

ааа _ёёё _ВВВ

Прочитать N чисел ( N < 100) и напечатать их в обратном порядке . Можно запрашивать N , читать очередное число или поступать как больше нравится.

ПРИМЕР:

3, 2, -1, 8, 4

Результат: 4, 8, -1, 2, 3

Прочитать N чисел и сообщить , есть ли среди них их среднее арифметическое.

ПРИМЕР:

3 2 4 -1 8 4 1

Результат: ДА.

Прочитать несколько строк и сказать, есть ли среди них заданная строка.

ПРИМЕР:

abc

xyz

мама

программа

Строка: xyz

Результат: ДА.

Прочитать несколько строк и сказать, есть ли среди них одинаковые.

ПРИМЕР:

xyz

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

информатика

xyz

Результат: ДА.

Запросить имя и рост каждого человека и напечатать имя самого высокого. Если таких несколько, напечатать любого.

ПРИМЕР:

Маша

120

Коля

50

Саша

150

Валя

130

Результат: Саша.

Задано натуральное число, длина которого не больше 100 знаков. Верно ли, что убирая по две подряд рядом стоящие цифры сумма которых равна 10, можно сократить все число?

ПРИМЕР: 123456789123456789

Результат: Да

Можно ли из одной строчки получить другую, убрав некоторые символы?

ПРИМЕР:

программа

гамма

Результат: Да

ОБЫЧНО ТАКУЮ ЧАСТЬ НАЗЫВАЮТ подпрограммой.

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

1) заменить отрицательные числа в последовательности на их модули и вывести получившуюся последовательность;

2) в полученной последовательности заменить четные чис ла на максимальное число последовательности, вывести результат;

3) в полученной последовательности вычесть из каждого члена последовательности 2, вывести результат;

4) в полученной последовательности заменить отрицатель ные на 0, вывести результат.

ПРИМЕР.

Последовательность: 1 2 3 0

1) 1 2 3

2) 1 3 3

3) -1 1 1

4) 0 1 1

Ввести 20-значное натуральное число. Вывести результат добавления к нему 1, вывести результат умножения его на 1, 10 и 2.

ПРИМЕР.

Число: 12345678901234567890

12345678901234567890 + 1 = 12345678901234567891

12345678901234567890 * 1 = 12345678901234567890

12345678901234567890 * 10 = 123456789012345678900

12345678901234567890 * 2 = 24691357802469135780

Решить уравнение ax + b = cx - d. a, b, c, d и x -- целые

шестнадцатеричные числа[3]. a, b, c, d -- вводятся, x -- выводится.

ПРИМЕР.

a = A b = B c = C d = D

x = C

______________________

Пусть f(a) -- сумма цифр целого числа a. Для заданного х

вычислить: f( f ( x+2 ) + f ( 2 •x)) •f (x • x )

ПРИМЕР.

x = 12

Выход: 18

Вычислить значение функции f( x, y ) при заданных x, y, если:

для любых целых x и y

f ( 0, y ) = y '

f ( x, 0 ) = x '

f ( x, x ) = f ( x - 1, x - 1 ) + 1, при x > 0,

f ( y, y ) = f ( y + 1, y + 1) -1, при y < у,

f ( x, y ) = f ( x, x) + f ( y, y ), при x ¹ y .

ПРИМЕР.

f ( - 2, 3 ) = 1

Запись ( X )_Y обозначает, что X есть запись числа в системе счисления по основанию Y . Написать программу, которая решает уравнения вида: (A)_X = B, где A и B ( целые положительные числа не большие 2000000000 ) заданы, а X - переменная. A и B - заданы десятичными цифрами.

ПРИМЕР.

A = 160 B = 112

X = 8

_____________________

Есть ли в заданном файле буква ы ?

ТЕХНИЧЕСКОЕ ЗАДАНИЕ.

Программа должна спросить имя файла и напечатать:

ДА - если в этом файле есть буква ы , и НЕТ - в про тивном случае.

ПРИМЕР.

Для текста задачи ответ: ДА .

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

Длина чисел не имеет значения.

ПРИМЕР:

в последовательности 2 3 4 5 67 6 5 64 это число 6.

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

того же символа.

ПРИМЕР:

в тексте задачи самая длинная последовательность мм и длина ее 2.

В файле записано 10 символов. Записать их в другой файл в обратном порядке.

ПРИМЕР.

В файле: ротялипмоК

В файле с результатом: Компилятор

Задан текстовый файл из строк символов.

Написать программу, которая записывает исходный

файл в новый так, чтобы строки расположились в

обратном порядке.

ПРИМЕР.

для текста задачи получается:

обратном порядке.

файл в новый так, чтобы строки расположились в

Написать программу, которая записывает исходный

Задан текстовый файл из строк символов.

Решить уравнение: x + 2 • x + 3 • x + ...+ x • x = n . Вводится n, найти x. Какими могут быть n и x, догадайтесь сами.

ПРИМЕР.

n= 18

x=3

Решить уравнение: x!. N = y!. N - целое число. K! [5] - определяется только для натуральных K. K! = 1 . 2 . 3 . ... . K,

0! = 1.

__________________________________

ТЕХНИЧЕСКОЕ ЗАДАНИЕ.

Получить для заданного N все различные пары (x,y).

ПРИМЕР.

N= 12

Ответ : (2,4)(11,12)

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

ТЕХНИЧЕСКОЕ ЗАДАНИЕ.

Написать программу, которая запрашивает строку цифр и, считая её кольцом, печатает какое-нибудь решение в виде A+B=C. Все цифры должны входить в числа в порядке следования в кольце. Цифр в кольце не более 100.

ПРИМЕР.

Ввод: 01902021

Вывод:190+20=210

Вычислить максимальное значение R(x,y) для заданных целых x,y ( y<50 ).

Внимание, «функция» R -неоднозначная (может давать разные значения на одинаковых аргументах).

ПРИМЕР.

X=3

Y=4

Максимальное значение R(3, 4)=16

Образец имеет вид:

образец ::=

::= |

::= '['']' |

Решить уравнение вида f(X) = A, где A -строка из маленьких латинских букв, X -переменная строка, f -функция на строках, построенная с помощью операций * и + над строками. Операция + обозначает конкатенацию[6] строк. Например, adbc + 123 = abcd123. Результатом операции A * B будет стро ка, где после каждого символа A записана B; если A или B - пустые строки, то результат будет также пустой строкой. На пример, ab * cd = acdbcd. Операции выполняются в порядке их следования.

ТЕХНИЧЕСКОЕ ЗАДАНИЕ.

Программа должна запросить уравнение и напечатать одно из решений.

ПРИМЕР.

Уравнение: X * ab + c * X = aabcabcac

X = ac

Задана квадратная таблица чисел. Размер таблицы нечётный. Движение начинается из центра. Двигаться можно вправо, влево, вверх и вниз. По ходу движения суммируются числа, записанные в клетках пути следования. Движение заканчивается на стороне квадрата.

Написать программу, которая сообщит минимальную сумму.

ТЕХНИЧЕСКОЕ ЗАДАНИЕ.

Заданный квадрат хранится в файле. Файл устроен следующим образом:

<Размер квадрата>

<Число> <Число> . . . <Число>

<Число> <Число> . . . <Число>

. . .

<Число> <Число> . . . <Число>

Все числа натуральные, не больше 200. Разделителями являются пробелы. Количество чисел в строке и количество строк совпадает с размером квадрата. Размер таблицы не больше 100.

Программа должна запросить имя файла с описанием квадрата и напечатать длину кратчайшего пути.

ПРИМЕР.

В файле:

5

20 13 23 12 18

6 14 3 17 11

21 2 1 4 25

7 15 5 16 10

22 8 19 9 24

Ответ: 23

Тесты

Метод использования тестов

Тесты надо проверять с первого до поседнего, подряд. Программа на каждом тесте должна работать не более указанного времени. Если время тестирования ограничено 0 секунд, это значит, что программа должна работать мгновенно.

Для каждого теста приведена его стоимость в процентах.

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

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

Первая группа. К первой группе можно отнести тесты, в которых сложность оценивается после тестирования программы (чаще нескольких программ). Тест считается более сложным, если программа (лучше несколько) проходит его с большими трудностями. Разновидности отличаются оценкой сложных и простых тестов.

Вторая группа. Тесты, ценность которых определяется до тестирования. Разновидности отличаются так же, как и в первой группе, но не по сложности, а по общности.

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

1.Привет

ответ очевиден.

2.здравствуй

ответ очевиден.

3. Арифметика

а)14; б)5202;

в)12254; г)-19961;

д)4293; е)-3878;

ж)19812; з)-1031.

4. Вежливое приветствие

ответ очевиден.

5. Вежливое приветствие с восклицательным знаком

ответ очевиден.

6. Сумма

Время работы программы 0 секунд.

7.Сумма чисел.

Время работы программы 0 секунд

8. Длинна строки

Время работы программы 0 секунд

50 задач по началам программирования

в авторской редакции

корректор Е. Ф. Осипова

http://ulm.uni.udm.ru/~pvv/packst/

ЛР № 020411 от 16.02.97. Сдано в производство 01.03.99.

Формат 60 х 84 1/18. Печать офсетная.

Уч. изд. л. 3,9. Усл. печ. л. Заказ № 34. Тираж 300.

Издательский дом Удмуртский университет.

426011, г. Ижевск, ул. Майская 23.