Книга "Алгоритмы и программы"

Задачи из главы 4 "Нестандартная обработка чисел"

содержание задачника

1. Реализуйте сравнение длинных чисел. Решение
2. Реализуйте сложение и вычитание длинных чисел.
3. Реализуйте умножение длинных чисел.
4. Реализуйте деление длинных чисел.
5. По длинному числу $L$ найдите целую часть квадратного корня $\sqrt{L}$.
6. Вычислите значение $e=lim (1+\frac{1}{n})^n$ с заданным количеством $M$ десятичных знаков после запятой.
7. Вычислите значение $\pi$ с заданным количеством $M$ десятичных знаков после запятой.
8. Великая Треугольная Область (ВТО) представляет собой прямоугольный треугольник. Его катеты имеют целые длины $m$ и $n$ и лежат на осях координат. Нужно покрыть как можно большую часть территории ВТО квадратными плитами размером 1 x 1. Плиты должны плотно прилегать одна к другой и к катетам ВТО, не выходя за пределы области. Резать плиты нельзя.Плиты поставляются только контейнерами по $p$ штук, используется необходимый минимум количества контейнеров. Вычислите, сколько плит из последнего контейнера останется после покрытия ВТО.
   Вход. Три целых числа: $2\le m, n\le 2000000000, 100\le p\le 10000$
   Выход. Количество оставшихся плит.
   Пример. Вход: 4 3 100. Выход: 97.
9. Найдите наименьшее число с одинаковыми цифрами, кратное заданному натуральному числу $K$. Выведите цифру и количество цифр в найденном числе. Если решение не существует, выведите $0 0$. Например, при $K=37$ нужно вывести $1 3$, а при $K=10$ - $0 0$.
10. Натуральные $k$ и $m$, где $1\le k<m$, задают правильную дробь $\displaystyle\frac{k}{m}$. Выведите кратчайшую последовательность цифр $AA...A$, предшествующих периоду и период $BB...B$ десятичного представления дроби в виде $0,AA...A(BB...B)$. Если длина периода больше 100, то выведите его первые 100 цифр и многоточие, а после его периода - его длину в скобках. Пример. Вход: 3 4 Выход: 0,75(0)
11. В рекуррентной последовательности, называемой числами Фибоначчи, каждый элемент (кроме двух начальных) является суммой двух предыдущих: $F_0=0, F_1=1$, $F_n=F_{n-1}+F_{n-2}$ при $n\ge 2$. Найдите остаток от деления $n$-го числа Фибоначчи на натуральное число $p$. Пример. При $n=12$, $p=10$ остаток равен 4.
12. Заданы натуральные числа $N$ и $p$ (оба в диапазоне от 2 до $10^9$). Найдите количество нулей в конце числа $N$!, записанного в системе счисления с основанием $p$. Пример. При $N=7$ и $p=10$ количество нулей равно 1, так как $7!=5040$.

содержание задачника