Пупышев В.В 50 задач по началам программирования
/~pvv/packst/
Введение
Эта книжка – очень сжатый вариант задачника для желающих научиться программировать. Конечно, она не самоучитель, скорее нужна для закрепления, углубления и контроля знаний и умений, полученных от учителя, из учебников или еще каким-нибудь путем.
Задачи не требуют знания какого-то конкретного языка программирования. Их можно решать на том языке, который Вы решили изучить. Задачи также требуют только общих знаний, может, чуть более глубоких по математике.
Задачи, для большей пользы, надо решать подряд. Пропускать можно только задачи повышенной трудности (помеченные звездочкой) лишь в том случае, если решить их Вы не можете.
В каждой задаче приведен пример. Входные и выходные данные примера всегда правильные. Если формулировка задания не ясна до конца. Проанализируйте пример. Во всех примерах показаны входные и выходные данные, но это не значит, что нужно вводить и выводить именно так, как показано. Если способ ввода и вывода не указан, то выбирайте его сами.
Поясним некоторые обозначения. В задачнике встречаются названия задач, начинающиеся латинскими заглавными буквами и цифрами. Эти условные обозначения показывают, когда и на каком соревновании по программированию давалась данная задача. Число после букв указывает год, а буквы обозначают само соревнование. DOI –районные олимпиады школьников Удмуртии. MFOI – олимпиада про программированию Удмуртского государственного университета для поступающих на математический факультет. MARK – студенческая олимпиада, спонсируемая ассоциацией предприятий МАРК. Некоторые части примеров записаны разными шрифтами. Если текст написан таким шрифтом, то этот текст выводится на экран, если таким шрифтом, тот этот текст надо набирать с клавиатуры.
Проверка правильности решения
После того, как для решения задачи придуман алгоритм и готова программа, надо проверить, правильно ли она работает. Для этого очень часто применяется метод тестов. Этот метод используется следующим образом: придумывают входные данные и вычисляют, какие должны быть выходные значения.
Входные данные, правильный ответ и время, через которое программа должна дать ответ, называют тестом. Потом входные данные задаются программе и проверяют, совпадают ли вычисленные ранее выходные значения и результат работы программы. Если программа выдала ответ, такой как было вычислено ранее, не позже заданного времени, то тест считается пройденным. Для большей уверенности нужно придумать несколько тестов и выполнить для них программу. Придумывать тесты для программы надо так, как будто Вы желаете, чтобы программа не смогла их пойти.
Этот способ не даёт полной гарантии того, что программа работает правильно. Не существует способа проверить любую программу лучше, чем хорошо подобранным набором тестов.
В этом задачнике для каждой задачи уже есть набор тестов. Но не спешите проверять программу сразу, как только её написали, на этих тестах.
Проверять решение нужно так:
0. Придумайте несколько (не меньше трёх) тестов для Вашей программы.
1. В каждой задаче есть пример. Проверьте, правильно ли работает Ваша программа на этом примере. Если пример не пройден то, нужно исправить ошибки в программе или алгоритме[1]. И вернуться к пункту 1. Только после того, как программа пройдет пример, можно идти дальше.
2. Проверьте программу на тестах из пункта 0. Если программа прошла не все тесты, исправьте программу или алгоритм и вернитесь к пункту 1. Если удалось пройти все тесты, то переходите к пункту 3.
3. Теперь нужно открыть тесты в конце книги. Проверять программу тестами нужно обязательно подряд, начиная с первого. Проверять нужно до тех пор, пока программа проходит тесты. Но как только программа тест не прошла, необходимо вернуться к пункту 1. Если программа прошла все тесты, то эту задачу Вы сделали полностью и можно переходить к следующей.
Задачи
5.Вежливое приветствие с восклицательным знаком
В предыдущей задаче (N4) необходимо, чтобы в конце приветствия программа ставила восклицательный знак. Написать программу.
ПРИМЕР 1.
Имя: Слава
Здравствуй, Слава!
6.Сумма
Написать программу, которая запрашивает два целых числа и печатает их сумму.
ПРИМЕР 2.
Первое число: 15
Второе число: 12
Ответ: 27
7. Сумма чисел
Написать программу, которая запрашивает два целых числа и печатает их сумму. Ответ должен быть развёрнутым.
ПРИМЕР 3.
Первое число: 15
Второе число: 12
15+12=27
8. Длина строки
Написать программу, подсчитывающую количество символов в заданной строке. Ответ должен быть развернутым.
ПРИМЕР 4.
Строка: Мама мыла раму
В строке: Мама мыла раму символов: 14
9.Инициалы
Написать программу, которая запрашивает фамилию, имя и отчество, а выводит фамилию и инициалы.
ПРИМЕР 5.
Фамилия: Пупышев
Имя: Вячеслав
Отчество: Викторович
Пупышев В.В.
10.Максимум из двух
Написать программу, которая запрашивает два числа и сообщает, которое из них не больше другого. Эта задача должна быть решена без использования ветвления.
ПРИМЕР 6.
Первое число:15
Второе число:6
Число 6 не больше числа 15.
ДЛЯ РЕШЕНИЯ СЛЕДУЮЩИХ ЗАДАЧ НЕОБХОДИМО ЗНАТЬ, КАК ПРОГРАММИРОВАТЬ ВЕТВЛЕНИЯ АЛГОРИТМА.
11. Частное
Написать программу, которая запрашивает два целых числа и выводит их частное.
ПРИМЕР 7.
Первое число: 6
Второе число: 2
6 : 2 = 3
12. Частное любых чисел
Известно, что на 0 делить нельзя. В задаче N11 при вводе 2 и 0 возникает аварийная ситуация. Избавьтесь от нее.
ПРИМЕР 8.
Первое число: 2
Второе число: 0
На ноль делить НЕЛЬЗЯ !!!
13. Фамильярность
Написать программу, которая читает строку и, если это Ваше имя, пишет: "Привет ", а если нет, пишет: "Здравствуйте! ".
Заметим, у каждого автора программы своё имя.
ПРИМЕР 9 (для автора):
Имя: Слава
Привет!
14. Чётность числа
Написать программу, которая определяет, чётное[2] ли число.
ПРИМЕР 10.
Число: 10
Чётное
15. ФИО
Написать программу, которая читает строку и определяет, что это, Ваше имя, фамилия или отчество. Если ни то, ни другое и не третье, то пишет: "НЕ ЗНАЮ". Заметим, у каждого автора программы свои имя, фамилия и отчество.
ПРИМЕР 11 (для автора задачника):
Строка: Викторович
Викторович - Ваше отчество.
16. Название оценки
Сделать программу, которая читает число от 1 до 5 и печатает название оценки.
ПРИМЕР 12.
Оценка: 1
Очень плохо.
17. Оценка ли?
Решить предыдущую задачу (N16), но можно вводить любое целое число. Если число не является оценкой, печатать: Не оценка.
ПРИМЕР 13:
Оценка: -3
Не оценка.
18. Счастливое четырёхзначное
Четырёхзначное число называется счастливым, если сумма первых двух его цифр равна сумме двух последних. Ваша программа должна читать число четырёхзначное и определять счастливое ли оно.
ПРИМЕР 14:
Число: 9889
Счастливое.
19. Сортировка четырёх
Написать программу, которая запрашивает четыре числа и выводит их в порядке возрастания.
ПРИМЕР :
Введите четыре числа:
3 8 19 11
3 8 11 19
ДЛЯ СЛЕДУЮЩИХ ЗАДАЧ ПОНАДОБИТСЯ ЗНАТЬ , КАК ЗАПИСЫВАТЬ АЛГОРИТМЫ С ПОВТОРЕНИЯМИ.
20. Числа от 10 до 100
Написать программу, печатающую все целые числа от 10 до 100 включительно.
21. Чётные от 2 до 100
Написать программу, печатающую все целые числа от 2 до 100 включительно.
22. От N до 0, кратные 3
Написать программу, печатающую все целые числа, большие N и меньшие 0. Эти числа должны делиться на 3.Число N запрашивает программа.
ПРИМЕР.
N= -9
-6 -3
23. 10 целых AR
Написать программу, которая печатает 10 разных целых чисел, не меньших А и делящихся на R нацело. Целые A и R запрашивает программа.
ПРИМЕР :
А= 11
R=2
12 14 16 18 20 22 24 26 28 30
24. Сколько ы ?
Написать программу для подсчета количества букв ы в заданной строке. Ответ должен быть развернутым.
ПРИМЕР:
Мама мыла раму !
В строке Мама мыла раму! букв ы - 1.
25. Лишние пробелы
Минимизировать количество пробелов в заданной строке.
В этой задаче требуется написать программу, которая убирает лишние пробелы. Лишние - это начальные и конечные пробелы строки а также те которые идут подряд. Нужно оставить из группы пробелов только один.
ПРИМЕР.
Строка: _ _ _ _ааа _ _ёёё _ _ _ВВВ _
ааа _ёёё _ВВВ
ЧТОБЫ РЕШАТЬ СЛЕДУЮЩИЕ ЗАДАЧИ , НУЖНО ЗНАТЬ , КАК ХРАНИТЬ СЛОЖНЫЕ ДАННЫЕ , СВЯЗАННЫЕ ДРУГ С ДРУГОМ. НАПРИМЕР , КАК ХРАНИТЬ ТАБЛИЦУ.
26. Обращение чисел
Прочитать N чисел ( N < 100) и напечатать их в обратном порядке . Можно запрашивать N , читать очередное число или поступать как больше нравится.
ПРИМЕР:
3, 2, -1, 8, 4
Результат: 4, 8, -1, 2, 3
27. Среднее число
Прочитать N чисел и сообщить , есть ли среди них их среднее арифметическое.
ПРИМЕР:
3 2 4 -1 8 4 1
Результат: ДА.
28. Поиск строки
Прочитать несколько строк и сказать, есть ли среди них заданная строка.
ПРИМЕР:
abc
xyz
мама
программа
Строка: xyz
Результат: ДА.
29. Поиск одинаковых строк
Прочитать несколько строк и сказать, есть ли среди них одинаковые.
ПРИМЕР:
xyz
программирование
информатика
xyz
Результат: ДА.
30. Самый высокий
Запросить имя и рост каждого человека и напечатать имя самого высокого. Если таких несколько, напечатать любого.
ПРИМЕР:
Маша
120
Коля
50
Саша
150
Валя
130
Результат: Саша.
31. Сокращение числа
Задано натуральное число, длина которого не больше 100 знаков. Верно ли, что убирая по две подряд рядом стоящие цифры сумма которых равна 10, можно сократить все число?
ПРИМЕР: 123456789123456789
Результат: Да
32. Удаление символов
Можно ли из одной строчки получить другую, убрав некоторые символы?
ПРИМЕР:
программа
гамма
Результат: Да
ДАЛЬШЕ ПРИГОДИТСЯ УМЕНИЕ ИСПОЛЬЗОВАТЬ ЧАСТЬ ПРОГРАММЫ НЕСКОЛЬКО РАЗ В РАЗНЫХ МЕСТАХ.
ОБЫЧНО ТАКУЮ ЧАСТЬ НАЗЫВАЮТ подпрограммой.
33. Последовательность чисел
Вводится последовательность целых чисел, заканчивающаяся нулем. Преобразовывать последовательность следующим образом:
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
34. Двадцатизначное число
Ввести 20-значное натуральное число. Вывести результат добавления к нему 1, вывести результат умножения его на 1, 10 и 2.
ПРИМЕР.
Число: 12345678901234567890
12345678901234567890 + 1 = 12345678901234567891
12345678901234567890 * 1 = 12345678901234567890
12345678901234567890 * 10 = 123456789012345678900
12345678901234567890 * 2 = 24691357802469135780
35. Уравнение в шестнадцатеричных
Решить уравнение 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
______________________
36. Значение f( a )
Пусть f(a) -- сумма цифр целого числа a. Для заданного х
вычислить: f( f ( x+2 ) + f ( 2 •x)) •f (x • x )
ПРИМЕР.
x = 12
Выход: 18
37. Значение f ( x , y )
Вычислить значение функции 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
38* . MFOI1997. Системы счисления
Запись ( X )Y обозначает, что X есть запись числа в системе счисления по основанию Y . Написать программу, которая решает уравнения вида: (A)X = B, где A и B ( целые положительные числа не большие 2000000000 ) заданы, а X - переменная. A и B - заданы десятичными цифрами.
ПРИМЕР.
A = 160 B = 112
X = 8
ДАЛЬШЕ НЕОБХОДИМО УМЕТЬ РАБОТАТЬ С БОЛЬШИМИ[4] ОБЪЕМАМИ ДАННЫХ, КОТОРЫЕ НЕ ПРОПАДАЮТ ПРИ ВЫКЛЮЧЕНИИ КОМПЬЮТЕРА. ОБЫЧНО ТАКИЕ ДАННЫЕ ХРАНЯТ В файле.
_____________________
39. ы в файле
Есть ли в заданном файле буква ы ?
ТЕХНИЧЕСКОЕ ЗАДАНИЕ.
Программа должна спросить имя файла и напечатать:
ДА - если в этом файле есть буква ы , и НЕТ - в про тивном случае.
ПРИМЕР.
Для текста задачи ответ: ДА .
40. Самое часто встречающееся число
Написать программу, которая запрашивает имя файла и пе чатает число, которое встречается в заданном файле чаще дру гих. Файл может содержать не только числа.
Длина чисел не имеет значения.
ПРИМЕР:
в последовательности 2 3 4 5 67 6 5 64 это число 6.
41. Максимальная последовательность символов
Написать программу, которая запрашивает имя файла и пе чатает длину самой большой последовательности из одного и
того же символа.
ПРИМЕР:
в тексте задачи самая длинная последовательность мм и длина ее 2.
42. Переворот 10 символов
В файле записано 10 символов. Записать их в другой файл в обратном порядке.
ПРИМЕР.
В файле: ротялипмоК
В файле с результатом: Компилятор
43. Переворот файла
Задан текстовый файл из строк символов.
Написать программу, которая записывает исходный
файл в новый так, чтобы строки расположились в
обратном порядке.
ПРИМЕР.
для текста задачи получается:
обратном порядке.
файл в новый так, чтобы строки расположились в
Написать программу, которая записывает исходный
Задан текстовый файл из строк символов.
CЛЕДУЮЩИЕ НЕСКОЛЬКО ЗАДАЧ МОЖНО РЕШИТЬ, ЕСЛИ ПЕРЕБИРАТЬ ВОЗМОЖНЫЕ ВАРИАНТЫ РЕШЕНИЯ И ПРОВЕРЯТЬ, ДЕЙСТВИТЕЛЬНО ЛИ ОНИ ПОДХОДЯТ. ТАКОЙ СПОСОБ НАЗЫВАЮТ перебором вариантов.
44. Уравнение x + 2•x + 3 • x + ... + x • x = n
Решить уравнение: x + 2 • x + 3 • x + ...+ x • x = n . Вводится n, найти x. Какими могут быть n и x, догадайтесь сами.
ПРИМЕР.
n= 18
x=3
45. Уравнение x!. N = y!
Решить уравнение: x!. N = y!. N - целое число. K! [5] - определяется только для натуральных K. K! = 1 . 2 . 3 . ... . K,
0! = 1.
__________________________________
ТЕХНИЧЕСКОЕ ЗАДАНИЕ.
Получить для заданного N все различные пары (x,y).
ПРИМЕР.
N= 12
Ответ : (2,4)(11,12)
46. DOI1996. Числовое кольцо
В кольце записаны N цифр, составляющих по часовой стрелке три числа: два слагаемых и сумму.
ТЕХНИЧЕСКОЕ ЗАДАНИЕ.
Написать программу, которая запрашивает строку цифр и, считая её кольцом, печатает какое-нибудь решение в виде A+B=C. Все цифры должны входить в числа в порядке следования в кольце. Цифр в кольце не более 100.
ПРИМЕР.
Ввод: 01902021
Вывод:190+20=210
СЛЕДУЮЩИЕ ЗАДАЧИ ТРЕБУЮТ УМЕНИЯ ЗАПИСЫВАТЬ ПОДПРОГРАММЫ, КОТОРЫЕ ИСПОЛЬЗУЮТ САМИ СЕБЯ. ТАКОЙ ПРИЁМ НАЗЫВАЕТСЯ рекурсией.
47. Максимальное R(x,y)
Вычислить максимальное значение R(x,y) для заданных целых x,y ( y<50 ).
Внимание, «функция» R -неоднозначная (может давать разные значения на одинаковых аргументах).
ПРИМЕР.
X=3
Y=4
Максимальное значение R(3, 4)=16
48. DOI1995. Сравнение с образцом.
Образец имеет вид:
образец ::= <PT>
<PT> ::= <A><PT> | <A>
<A> ::= '['<PT>']' | <ST>
<ST> ::= <символы>
Часть образца, заключенная в квадратные скобки показывает, что эту часть можно исключать. Таким образом, образец описывает множество строк. Образец всегда правильный. Например:
образец: [a[b]]c
описывает строки: a, ab, abc
Слово подходит под образец, если оно совпадает с одним из слов, описываемых образцом. Задача написать программу, которая по заданному образцу и слову печатает «НЕТ », если слово подходит под образец, и «ДА », если не подходит.
ПРИМЕР:
образец: [a[b]]c
слово: ab
ответ: ДА
49*. MARK1997. Уравнение f(X) = A
Решить уравнение вида 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
В СЛЕДУЮЩЕЙ ЗАДАЧЕ ПРИМЕНЯЕТСЯ ПРИЁМ, КОТОРЫЙ НАЗЫВАЕТСЯ динамическим программированием ПРИЁМ ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО ЗАПОМИНАЮТ ТЕ ПРОМЕЖУТОЧНЫЕ РЕЗУЛЬТАТЫ, КОТОРЫЕ УЖЕ ВЫЧИСЛЕНЫ, А ПОТОМ ИСПОЛЬЗУЮТ ИХ.
50*. MARK1997. Квадрат чисел
Задана квадратная таблица чисел. Размер таблицы нечётный. Движение начинается из центра. Двигаться можно вправо, влево, вверх и вниз. По ходу движения суммируются числа, записанные в клетках пути следования. Движение заканчивается на стороне квадрата.
Написать программу, которая сообщит минимальную сумму.
ТЕХНИЧЕСКОЕ ЗАДАНИЕ.
Заданный квадрат хранится в файле. Файл устроен следующим образом:
<Размер квадрата>
<Число> <Число> . . . <Число>
<Число> <Число> . . . <Число>
. . .
<Число> <Число> . . . <Число>
Все числа натуральные, не больше 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. Сумма
N
Вход
Выход
Ценность в процентах
0
15
12
27
1%
1
2
3
5
33%
2
1
-1
0
33%
3
-10
-20
-30
33%
Время работы программы 0 секунд.
7.Сумма чисел.
N
Вход
Выход
Ценность в процентах
0
15 12
15 + 12 = 27
1%
1
3 2
3 + 2 = 5
33%
2
-1 1
-1 + 1 = 0
33%
3
-100 -32
-100 + -32 = -132
33%
Время работы программы 0 секунд
8. Длинна строки
N
Вход
Выход
Ценность
в процентах
0
Мама мыла раму
В строке:
"Мама мыла раму" символов: 14
1%
1
Тест
В строке:
Тест символов: 4
25%
2
Test only
В строке:
Test only сим волов: 9
25%
3
В строке:
символов: 0
24%
4
1
В строке:
1 символов: 1
25%
Время работы программы 0 секунд
Пупышев Вячеслав Викторович
50 задач по началам программирования
в авторской редакции
корректор Е. Ф. Осипова
/~pvv/packst/
ЛР № 020411 от 16.02.97. Сдано в производство 01.03.99.
Формат 60 х 84 1/18. Печать офсетная.
Уч. изд. л. 3,9. Усл. печ. л. Заказ № 34. Тираж 300.
Издательский дом Удмуртский университет.
426011, г. Ижевск, ул. Майская 23.
Примечания
1
Если программа выдаёт правильный результат, но не укладывается в отведённое время, то, скорее всего, ошибка в алгоритме.
(обратно)2
Число называется чётным, если делится на 2 без остатка.
(обратно)3
Шестнадцатеричные числа записываются с использованием обычных десятичных цифр 0, 1, ..., 9 и ещё букв A, B, C, D, E, F, обозначающих 10, 11, 12, 13, 14, 15, соответственно.
(обратно)4
Большие -- могут не поместиться в оперативной памяти.
(обратно)5
читается <ка факториал>
(обратно)6
Т.е. сцепление строк, приписывание одной строки к другой.
(обратно)
Комментарии к книге «50 задач по началам программирования», Вячеслав Викторович Пупышев
Всего 0 комментариев