2015-10-22
848
Задачи по программированию
1 Последовательности
Задача 1 [2] Ежемесячная стипендия студента составляет А рублей, а расходы на проживание превышают ее и составляют B руб. в месяц. Рост цен ежемесячно увеличивает расходы на 3%
Определить, какую нужно иметь сумму денег, чтобы прожить учебный год (10 месяцев), используя только эти деньги и стипендию.
Задача 2 [2] У студента имеются накопления S руб. Ежемесячная стипендия составляет А рублей, а расходы на проживание превышают ее и составляют B руб. в месяц. Рост цен ежемесячно увеличивает расходы на 3%
Определить, сколько месяцев сможет прожить студент, используя только накопления и стипендию.
Задача 3 [1] Остров Манхэттен был приобретен поселенцами за $24 в 1826 г. Каково было бы в настоящее время состояние их счета, если бы эти 24 доллара были помещены тогда в банк под 6% годового дохода?
Задача 4 Последовательность Хейеса1 [6]
Рассмотрим некоторое натуральное число n. Если оно четное, то разделим его на 2, иначе -- умножим на 3 и прибавим 1. Будем повторять такие действия (шаги), пока не получится 1. Полученная последовательность называется последовательностью Хейеса, а наибольшее из чисел этой последовательности -- ее вершиной
Требуется составить программу, вычисляющую для заданного n последовательность Хейеса, подсчитывающую число шагов в ней и находящую ее вершину. 2
2 Геометрические задачи. Координаты
Задача 1 [2] Два прямоугольника, расположенные в первом квадранте, со сторонами, параллельными осям координат, заданы координатами левого верхнего и правого нижнего углов. Для первого прямоугольника это (x1,y1); (x2,0), для второго -- (x3,y3); (x4,0)
Составьте программу, определяющую, пересекаются ли данные прямоугольники и, если пересекаются, какова общая площадь.
Задача 2 [2] Два треугольника заданы координатами своих вершин. Определите, какой из треугольников имеет большую площадь. Используйте формулу Герона
3 Целочисленные операции. Задачи из теории чисел [4]
(Знаком <<*>> помечены задачи, предполагающие использование массивов, а знаком <<!>> -- задачи повышенной сложности |
Понятия теории чисел, встречающиеся в задачах
Простое число
-- натуральное число, большее единицы, имеющее только два делителя: единицу и само это число.
Числа-близнецы
-- два нечетных простых числа, разность которых равна 2, например, 11 и 13.
Совершенное
-- число, равное сумме своих правильных (т. е. меньших самого числа) делителей.
Дружественные
-- два числа, каждое из которых равно сумме правильных делителей другого. Например, 220 и 284.
Число Армстронга
|
|
|
-- число, состоящее из n > 1 цифр, причем сумма его цифр, возведенных в n-ю степень, равна самому этому числу. Например, 153 = 13+53+33.
Цифровой корень
получается, если сложить все цифры числа, потом все цифры полученной суммы и так далее, пока результат не будет одноразрядным числом.
Палиндром
-- число, одинаково читающееся слева направо и справа налево, например, 13531.
Симметричные
-- числа, состоящие из двух одинаковых частей, например, 245245.
Взаимно-простыми
называются числа, наибольший общий делитель которых -- единица.
Ряд Фибоначчи
-- последовательность чисел, каждый член которой, начиная с третьего, равен сумме двух предыдущих.
Тройка Пифагора
-- тройка чисел, соответствующих соотношению <<квадрат гипотенузы равен сумме квадратов катетов>>. Тройки, не имеющие общих делителей, называются основными (например, 3, 4 и 5). Тройки, получаемые умножением всех чисел основной тройки на натуральное число, -- производными3.
Разложение на множители
Задача 1 Подсчитать количество делителей данного простого числа.
Задача 2 Определить, является ли заданное число простым.
Задача 3 Найти в интервале[1, 1000] число, имеющее наибольшее количество делителей.
Задача 4 Найти все простые числа из диапазона от N до M.
Задача 5 Вывести 5 простых чисел, больших (меньших) некоторого заданного числа K.
Задача 6 Дано некоторое натуральное число X. Найти ближайшее к нему простое число.
Задача 7 Определить, являются ли числа, находящиеся рядом с заданным четным числом, близнецами.
Задача 8 Вывести все числа-близнецы из заданного диапазона.
Задача 9 Разложить заданное число на простые множители.
Задача 10 Вычислить сумму делителей заданного числа.
Задача 11 Найти 3 совершенных числа, больших заданного M.
Задача 12 Вывести ближайшее к данному числу N совершенное число.
Задача 13 Найти и распечатать все пары дружественных чисел, меньших 10000.
Задача 14 [*] Найти простые числа из интервала от 1 до 10000 методом <<решета Эратосфена>>.
Разбиение на разряды
Задача 15 Определить число разрядов в заданном натуральном числе.
Задача 16 Вычислить сумму цифр заданного числа.
Задача 17 Записать заданное число в обратном порядке.
Задача 18 Проверить, является ли заданное число палиндромом.
Задача 19 Найти все натуральные числа, меньшие заданного, которые при возведении в квадрат дают палиндром.
Задача 20 Вывести все четные палиндромы из интервала от 10 до миллиона.
Задача 21 Составить программу, определяющую, есть ли среди палиндромов из интервала от 10 до миллиона простые числа. Если таковые есть, вывести их на экран.
Задача 22 Найти все четырехзначные симметричные числа.
Задача 23 Вывести все симметричные простые числа из интервала от 10 до миллиона.
Задача 24 Найти все палиндромы, являющиеся симметричными, из интервала от тысячи до миллиона.
Задача 25 Заданно число X. Вывести на экран число, которое получится в результате исключения из этого числа цифры в разряде N.
Задача 26 [*] Задано число. Получить наибольшее (наименьшее) число, записанное теми же цифрами.
Задача 27 Найти все т-значные числа Армстронга.
Задача 28 Задано 6-значное число. Определить, кратно ли это число 9, используя признак делимости на 9 (число делится на 9, если сумма его цифр делится на 9)
Задача 29 Вывести на печать все натуральные числа, меньшие заданного N, сумма квадратов цифр которых кратна 7.
Задача 30 Найти все натуральные числа от 1 до 2000, равные сумме кубов своих цифр.
Задача 31 Найти все натуральные числа от 1 до 5000, равные кубу суммы своих цифр.
Задача 32 Найти все четырехзначные числа, у которых сумма первых двух цифр равна сумме двух последних.
Задача 33 В десятичной записи числа 42*4* пропущены 2 цифры. Определите эти цифры, если известно, что число кратно 72.
|
|
|
Задача 34 Определите 3 цифры номера автомобиля, если известно, что получившееся число кратно 2, 5 и 7, а сумма цифр равна 12.
Задача 35 Дано натуральное число. Замените в нем все <<единицы>> на <<пятерки>>.
Задача 36 Дано натуральное число. Выбросить из записи все единицы, оставив порядок остальных цифр неизменным.
Задача 37 вывести числа из диапазона [10, 100], в записи которых нет цифр 3 и 7.
Задача 38 Найти все двузначные числа, сумма цифр которых не меняется при умножении числа на 2 (3, 4...9).
Задача 39 Вычислить цифровой корень заданного числа N.
Задача 40 Вывести все числа из интервала [10, 9999], кратные своему цифровому корню.
Задача 41 Вывести все натуральные числа из диапазона [10, 99999], цифровой корень которых: а) кратен 3 или 5; б) является простым числом.
Задача 42 [Постоянная Капрекара[3] Выберите любое четырехзначное число, в котором не все цифры одинаковы. Расположите цифры сначала в порядке возрастания, а потом -- убывания4, а затем вычтите из первого второе. Повторяя тот же процесс с разностями, не более чем за 7 шагов вы достигнете постоянной Капрекара5, которая затем будет воспроизводить саму себя
Требуется составить программу, выполняющую нахождение постоянной Капрекара для любого заданного числа6.
Примечание: постоянная Капрекара равна 6174. Для трехзначных чисел аналогичная постоянная -- 495
Нахождение НОД
Задача 43 Определить наибольший общий делитель двух заданных чисел, используя алгоритм Евклида. (Большее число делится на меньшее, затем меньшее -- на полученный остаток и т. д. Деление повторяется, пока не будет получен остаток, равный нулю. Последний ненулевой остаток и будет наибольшим общим делителем.)
...
while (x<>0) and (y<>0) do
if x>y then x:=x mod y
else y:=y mod x;
nd:=x+y;
..
Задача 44 Определить общий знаменатель по заданным знаменателям трех простых дробей.
Задача 45 Написать программу сложения двух простых дробей.
Задача 46 Написать программу сокращения простой дроби.
Задача 47 Написать программу сокращения неправильной дроби с выделением целой части.
|
|
|
Задача 48 Найти все пары взаимно простых чисел на интервале [1, 1000].
Задача 49 Проверить, являются ли три заданных числа взаимно простыми.
