Книга “Алгоритмы и программы”
Задачи из главы 1 “Разминка”
- Стрелки часов движутся с постоянными угловыми скоростями и показывают \(h\) часов \(m\) минут. Найдите число полных минут до ближайшего момента, в который стрелки совпадут. Решение
Вход. Два целых числа \(h\) и \(m\) (на клавиатуре). Выход. Целое число минут (на экране).
Пример. Вход: 0 0; выход: 0. Вход: 1 1; выход: 4. - Разбить последовательность чисел от 1 до \(N^2\) на \(N\) подпоследовательностей так, чтобы все они состояли из \(N\) чисел и имели равные суммы. Если решений несколько, то вывести любое из них. Решение
Вход. Целое число от 1 до 200 (на клавиатуре).
Выход. \(N\) строк, содержащих по \(N\) возрастающих чисел, разделенных пробелами (на экране). Порядок, в котором выводятся подпоследовательности, роли не играет.
Примеры.
Вход: 1; выход: 1.
Вход: 3; выход:
1 5 9
2 6 7
3 4 8 - Составить программу поиска всех решений ребуса VOLVO + FIAT = MOTOR. Разным буквам соответствуют разные цифры, одинаковым – одинаковые. Старшая цифра каждого числа отличается от нуля. Решение
- Определите, является ли натуральное число простым. Таблица простых чисел Что такое простое число Решение
- Как известно, каждое натуральное число \(n, n>1\), однозначно раскладывается в произведение простых сомножителей, например, \(13=13\), \(105=3\cdot 5\cdot 7\), \(72=2\cdot 2\cdot 2\cdot 3\cdot 3\). Разложите натуральное число на простые множители (факторизация числа). Решение
- По целому \(n\) и \(n\) положительным целым числам определите, можно ли из них образовать подмножество, сумма элементов которого делится на \(n\) без остатка. Если можно, то найти любое из таких подмножеств. Решение
- Найти все делители данного натурального числа. Решение
- Дан действительный радиус \(r\) круга на плоскости. Известно, что центр круга – точка с целочисленными координатами. Найдите количество узлов целочисленной координатной сетки внутри круга. Предложите одно решение с оценкой сложности \(\Theta(r^2)\), другое – \(\Theta(r)\).
- Числа от 1 до \(n\), (\(2\le n\le 10^6)\) нужно разбить на максимально возможное количество пар так, чтобы суммы чисел в парах были простыми числами. Найдите количество пар. Например, при \(n=3\) получается одна пара (1;2), при \(n=7\) получается три пары (1;2), (3;4), (6;7).
- От прямоугольника с целочисленными размерами \(n x m\) отрезают квадраты максимального размера, пока не останется квадрат. Найдите количество отсечений.
- По двум натуральным числам \(a\) и \(b\) найдите наименьшее положительное число \(d\) и какие-нибудь целые \(u\) и \(v\), при которых \(a\cdot u+b\cdot v=d\).
- По заданным натуральным числам \(a_1, a_2, …, a_n\), где \(n\le 2\cdot 10^9\), найдите наибольшее натуральное число \(d\), при котором остатки от деления заданных чисел на \(d\) равны.
- В одном ящике находится \(a\) морковок, в другом – \(b\) морковок, всего не больше \(2\cdot 10^9\). Каждый ящик может вместить всю морковь. За один раз из одного ящика можно переложить в другой столько морковок, сколько лежит в другом ящике. Определите, можно ли в результате таких перекладываний освободить один из ящиков. Например, при \(a=9, b=3\) это возможно, при \(a=6, b=3\) – нет.
- Концы отрезка на плоскости имеют целочисленные координаты. Вычислите, сколько всего точек с целочисленными координатами принадлежат отрезку.
- У Аси есть неограниченный запас монеток достоинством \(a\) копеек, у Васи – \(b\) копеек. Нужно найти максимальную сумму, которую Ася и Вася не смогут набрать своими монетками. Если такие суммы не ограничены, выдать ответ 0. Например, при \(a=2, b=5\) ответ 3, а при \(a=2, b=4\) нельзя набрать ни одной нечетной суммы, поэтому ответ 0.
- Прямоугольник состоит из \(X\)x\(Y\) клеток единичного размера. Из него вырезан прямоугольник размером \((X-2)\)x\((Y-2)\) так, что осталась рамка шириной в одну клетку. Определите, можно ли покрыть всю рамку плитками размером \(A\)x\(1\). Запас плиток не ограничен, плитки не накладываются одна на другую и за предел рамки не выходят.
Вход. В первой строке теста записаны \(X\) и \(Y\), во второй – последовательность размеров \(A\), для которых нужно проверить возможность покрытия (через пробел).
Выход. Последовательность строк. Каждая строка состоит из 0 и 1, соответствующих проверяемым размерам плиток (1 – покрыть можно, 0 – покрыть нельзя). Например, при \(X=5\) и \(Y=3\) размерам 2, 3, 4 соответствует строка 110. - Найти минимальное натуральное число, которого нет в данной последовательности.
- Напечатать в порядке возрастания первые \(N\) чисел (\(1\le N\le 10^4\)), имеющие из простых делителей только числа 2, 3 и 5 (последовательность Хэмминга). Например, первые 10 чисел таковы: 2, 3, 4, 5, 6, 8, 9, 10, 12, 15.