Макинтош и образование:Информатика и ИТ:Задачи по программированию

1  Последовательности

Задача 1 [2] Ежемесячная стипендия студента составляет А рублей, а расходы на проживание превышают ее и составляют B руб. в месяц. Рост цен ежемесячно увеличивает расходы на 3%

Определить, какую нужно иметь сумму денег, чтобы прожить учебный год (10 месяцев), используя только эти деньги и стипендию.

Задача 2 [2] У студента имеются накопления S руб. Ежемесячная стипендия составляет А рублей, а расходы на проживание превышают ее и составляют B руб. в месяц. Рост цен ежемесячно увеличивает расходы на 3%

Определить, сколько месяцев сможет прожить студент, используя только накопления и стипендию.

Задача 3 [1] Остров Манхэттен был приобретен поселенцами за $24 в 1826 г. Каково было бы в настоящее время состояние их счета, если бы эти 24 доллара были помещены тогда в банк под 6% годового дохода?

Задача 4 Последовательность Хейеса¹ [6]

Рассмотрим некоторое натуральное число n. Если оно четное, то разделим его на 2, иначе -- умножим на 3 и прибавим 1. Будем повторять такие действия (шаги), пока не получится 1. Полученная последовательность называется последовательностью Хейеса, а наибольшее из чисел этой последовательности -- ее вершиной

Требуется составить программу, вычисляющую для заданного n последовательность Хейеса, подсчитывающую число шагов в ней и находящую ее вершину. ²

2  Геометрические задачи. Координаты

Задача 1 [2] Два прямоугольника, расположенные в первом квадранте, со сторонами, параллельными осям координат, заданы координатами левого верхнего и правого нижнего углов. Для первого прямоугольника это (x₁,y₁);    (x₂,0), для второго -- (x₃,y₃);    (x₄,0)

Составьте программу, определяющую, пересекаются ли данные прямоугольники и, если пересекаются, какова общая площадь.

Задача 2 [2] Два треугольника заданы координатами своих вершин. Определите, какой из треугольников имеет большую площадь. Используйте формулу Герона

3  Целочисленные операции. Задачи из теории чисел [4]

(Знаком <<*>> помечены задачи, предполагающие использование массивов, а знаком <<!>> -- задачи повышенной сложности

3.1  Понятия теории чисел, встречающиеся в задачах

Простое число

-- натуральное число, большее единицы, имеющее только два делителя: единицу и само это число.

Числа-близнецы

-- два нечетных простых числа, разность которых равна 2, например, 11 и 13.

Совершенное

-- число, равное сумме своих правильных (т. е. меньших самого числа) делителей.

Дружественные

-- два числа, каждое из которых равно сумме правильных делителей другого. Например, 220 и 284.

Число Армстронга

-- число, состоящее из n > 1 цифр, причем сумма его цифр, возведенных в n-ю степень, равна самому этому числу. Например, 153 = 1³+5³+3³.

Цифровой корень

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

Палиндром

-- число, одинаково читающееся слева направо и справа налево, например, 13531.

Симметричные

-- числа, состоящие из двух одинаковых частей, например, 245245.

Взаимно-простыми

называются числа, наибольший общий делитель которых -- единица.

Ряд Фибоначчи

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

Тройка Пифагора

-- тройка чисел, соответствующих соотношению <<квадрат гипотенузы равен сумме квадратов катетов>>. Тройки, не имеющие общих делителей, называются основными (например, 3, 4 и 5). Тройки, получаемые умножением всех чисел основной тройки на натуральное число, -- производными³.

3.2  Разложение на множители

Задача 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 методом <<решета Эратосфена>>.

3.3  Разбиение на разряды

Задача 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] Выберите любое четырехзначное число, в котором не все цифры одинаковы. Расположите цифры сначала в порядке возрастания, а потом -- убывания⁴, а затем вычтите из первого второе. Повторяя тот же процесс с разностями, не более чем за 7 шагов вы достигнете постоянной Капрекара⁵, которая затем будет воспроизводить саму себя

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

Примечание: постоянная Капрекара равна 6174. Для трехзначных чисел аналогичная постоянная -- 495

3.4  Нахождение НОД

Задача 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 Проверить, являются ли три заданных числа взаимно простыми.

3.5  Рекуррентные вычисления

Задача 50 Вывести все числа Фибоначчи из заданного интервала.

Задача 51 Подсчитать количество чисел Фибоначчи в заданном интервале.

Задача 52 Определить, какие числа Фибоначчи, не превосходящие 1000, являются простыми.

Задача 53 [!] Вывести на печать делители заданного числа N, являющиеся числами Фибоначчи.

Задача 54 [!!] Вывести на печать все числа, меньшие 100, не являющиеся числами Фибоначчи.

3.6  Перебор

Задача 55 Составить программу печати пифагоровых троек из заданного диапазона.

Задача 56 Найти и вывести на экран число, меньшее 250, которое при делении на 2 дает в остатке 1, при делении на 3 -- 2, при делении на 4 -- 3, при делении на 5 -- 4, при делении на 6 -- 5, а на 7 делится без остатка.

Задача 57 [1] Какие положительные целые числа, меньшие 20, удовлетворяют равенству

4  Строки

Задача 1 [1] Составить процедуру, преобразующую строку цифр в соответствующее целое число. Сделать то же самое для вещественных чисел.

Задача 2 [1] Составить процедуру, преобразующую целое число в соответствующую строку символов с пробелами, разделяющую цифры на группы по три символа, начиная справа.

Задача 3 [1] Разработать программу, выполняющую точное сложение и вычитание 100-разрядных целых чисел.

Задача 4 [1] Разработать программу, выполняющую деление целых чисел с точностью до 30 знаков.

Задача 5 [1] Напишите программу сложения чисел, записанных римскими цифрами. Ограничьтесь числами, не превышающими MMM (3000).

Задача 6 [1] Составить программу, просматривающую строку и выявляющую в ней непарные скобки.

5  Задачи о календаре [1]

Года являются високосными, если обозначающие их числа делятся на 4, за исключением тех, которые кратны 100. Среди последних високосными являются только кратные 400. 1 января 1800 г. (по новому стилю) была среда

Задача 1 Напишите программу, определяющую по дате день недели.

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

Задача 3 Напишите программу, автоматически составляющую календарь текущего (заданного) года.

Задача 4 Напишите программу, определяющую количество дней между двумя заданными датами.

Задача 5 Какова вероятность того, что 13 число заданного месяца окажется пятницей? Определите количество пятниц, пришедшихся на 13-е числа в XX столетии.

6  <<Лабораторные работы>> (точность)

Задача 1 [1] Поверить, будут ли выполняться равенства

• X⁰ = X^0.0 = 1
• sqrt(X) = X^0.5 = X⁽1/2)
• X = X¹ = X^1.0
• X^.X = X² = X^2.0
• X^.X^.X = X³ = X^3.0
• X/Y ^.Y = X
• sin²X+cos²X = 1
• A(B-C) = AB-AC
• (A-B)/C = A/C - B/C

1000^.[1.0/ 5.0] = [1.0/ 5.0]

Задача 2 [1] Запрограммируйте вычисление [1/( n³)] в прямом и обратном порядке. Сравните полученные результаты.

Задача 3 [1] Напишите программу для вычисления каждой из следующих сумм

Сравните полученные результаты. Почему они разные?

7  Модели экосистем

Задача 1 [1] <<Волчий остров>>

Волчий остров размером 20х20 заселен дикими кроликами, волками и волчицами. Имеется по несколько представителей каждого вида. Кролики с равной вероятностью (1/9) могут передвинуться в любой из соседних квадратов либо остаться на месте. Каждый кролик с вероятностью 0,2 может превратиться в двух кроликов. Каждая волчица передвигается случайным образом, пока в одном из соседних 8 квадратов не окажется кролик, за которым она начинае охотиться. Если волчица и кролик оказались в одном квадрате, волчица съедает кролика и повышает свой жизненный уровень на 1 очко. В противном случае -- теряет 0,1 очка. Волк действует подобно волчице, пока в соседних квадратах есть кролики7 Если кроликов нет, но есть волчица -- волк гонится за волчицей. Когда они оказываются в одном квадрате, в котором нет кролика, у них появляется потомство случайного пола. Если у волка или волчицы жизненный уровень уменьшается до нуля, они умирают.

Данная модель является неустойчивой. Постепенно остров становится пустыней. Попробуйте <<установить изгородь>> (сделать часть острова запретной для волков) и посмотреть за результатами

8  Простейшие игры [5]

Задача 1 <<Чет или нечет?>>

Условия игры: Компьютер генерирует случайное целое число, а человек пытается угадать, четное оно или нечетное. Результат сравнения выводится на экран

Задача 2 <<Отгадай число>>

Условия игры: Компьютер генерирует случайное целое число, не превосходящее 100. Играющий пытается угадать это число, делая несколько попыток, после каждой из которых компьютер сообщает, какое из чисел больше

Задача 3 <<Игральные кости>>

Условия игры: компьютер и человек <<бросают>> некоторое число n игральных костей. Победителем считается набравший большую сумму очков

Задача 4 <<Быки и коровы>>

Условия игры: компьютер генерирует целое четырехзначное число, в котором все цифры различны. Играющий пытается угадать это число, делая несколько попыток. После каждой попытки компьютер сообщает о количестве <<коров>> (цифр, совпадающих по разряду с цифрой в загаданном числе) и <<быков>> (цифр, имеющихся в загаданном числе, но не совпадающих по разряду)

9  Комбинированные задачи повышенной сложности

Задача 1 [1] Имеются цифры от 1 до 9 расположенные по возрастанию (убыванию). Требуется расставить между ними произвольное количество знаков <<плюс>> и <<минус>>, чтобы получилось выражение со значением 100. Например

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

Задача 2 [1] Составьте программу, читающую целое положительное число, не превышающее миллиард, и выводящее это же число на естественном языке.

Задача 3 [1] <<Задача о восьми ферзях>> Имеется шахматная доска и восемь ферзей. Требуется расставить их таким образом, чтобы ни один не угрожал другому.

Литература

[1]

Д. Ван Тассел. Стиль, разработка, эффективность, отладка и испытание программ. М.:Мир, 1985.

[2]

Н. А. Сычев. Задания для вступительных экзаменов по информатике в НГУ//Информатика и образование. 1995. 2 с. 66-72.

[3]

О. П. Зеленяк. Задачи как средство обучения программированию//Информатика и образование. 1996. 4 с. 56-68.

[4]

О. В. Покосовская. Решение задач из теории чисел//Информатика и образование. 1996. 6 с. 119-125, 1997 1 с. 83-88, 2 с. 107-110.

[5]

Д. М. Златопольский. Алгоритмизация простейших игр//Ин"-форматика и образование. 1998. 6 с. 77-80.

[6]

О. П. Зеленяк. Графика в Turbo Pascal//Информатика и образование. 1999. 3 с. 87-94.

Примечания:

¹ Впервые задача опубликована Брайаном Хайесом в 1984 г. в американском журнале <<В мире науки>>. Для всех натуральных чисел до 2⁴⁰ экспериментально подтверждена сходимость последовательности, однако строгого доказательства сходимости до сих пор нет.

² Очень эффектно выглядит графическое представление последовательности.

³ Кстати, согласно <<Великой теореме Ферма>>, уравнение вида xⁿ+yⁿ = zⁿ при n > 2 в целых числах неразрешимо.

⁴ нули должны сохраняться.

⁵ Д. Капрекар -- индийский математик, исследователь теории чисел.

⁶ Аналогичная задача возможна и для трехзначных чисел. Для чисел с другим числом знаков постоянной с такими свойствами не существует