Задачи на длинную арифметику

Диапазон представления целых чисел (Integer, Word, LongInt) ограничен, о чем не раз уже говорилось (впрочем, для действительных величин это замечание

Задачи на длинную арифметику

Информация

Компьютеры, программирование

Другие материалы по предмету

Компьютеры, программирование

Сдать работу со 100% гаранией
ли, что можно вычислять факториалы до значения 810! включительно, в записи которого 1999 цифр. Далее вновь возникает переполнение. Расчеты по программе продолжаются около 5 минут (IBM PC с процессором Pentium100).

Ниже будет предложен список задач для самостоятельного выполнения. Из них, по мнению автора, наибольшую сложность представляют реализации алгоритмов деления одного длинного числа на другое и извлечение квадратного корня. Алгоритм извлечения квадратного корня подробно описан в справочнике В.А. Гусева и А.Г. Мордковича [7]. В некоторых случаях составленные программы могут выступать как подпрограммы при разработке алгоритмов решения других, более сложных (как в примере с факториалом), задач. Кроме авторских задач и задач из списка литературы здесь приведены задания из олимпиад школьников по программированию, проводившихся в Пермской области в 1989-99гг.

Задачи для самостоятельного решения

Составить программу сравнения двух многозначных чисел (количество знаков в записи чисел более20).

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

Составить программу вычисления степени an, если a > MaxInt, n>10.

Составить программу вычисления числа 264 1, в результате сохранить все цифры.

Составить программу вычисления 100!.

Составить программу извлечения точного квадратного корня из n-разрядного числа (n>40).

Составить программу вычисления точного значения n!, где n > 12.

Составить программу вычисления точного значения nn, где n > 10.

Составить программу деления числа a на число b, если a, b многозначные числа.

Вычислить 100! + 2100.

Вычислить 100! 2100.

Вычислить 7123.

Встречаются ли среди цифр числа 211213 1 две подряд идущие девятки?

Вычислить 2200.

Составить программу нахождения частного и остатка от деления m-значного числа на nзначное (m, n > 20).

Выяснить, какое из чисел am, bn больше и на сколько (a, b<=40000; m, n<=10).

Найти n знаков в десятичной записи квадратного корня из целого числа m (n >= 50).

Найти количество делителей n-значного натурального числа (n > 20).

Вычислить точное значение (n!)! (n>=3).

Составить программу вычисления точного значения суммы 1! + 2! + 3! + ... + n! при n>10.

Составить программу вычисления точного значения суммы дробей

при n > 10. Ответ должен быть представлен в виде несократимой дроби P / Q, где P, Q натуральные числа.

Вычислить точное значение (nn)! при n>=3.

Составить программу вычисления точного значения суммы первых n членов последовательности 1, k, k2, k3, ..., kn (n > MaxInt). Указание: используйте формулу суммы n членов геометрической прогрессии.

Составить программу вычисления точного значения суммы первых n членов последовательности чисел, кратных данному натуральному числу k (n>MaxInt). Указание: используйте формулу суммы n членов арифметической прогрессии.

Вычислить точное значение суммы 12 + 22 + 32 + … + n2 (n>=20000).

Вычислить точное значение суммы 1n + 2n + 3n + ... + nn (n>=10).

Найти первое простое число, которое больше 1011.

Составить программу вычисления точного значения многочлена anxn + an - 1xn - 1 + ... + a1x + a0, где aiиx целые числа больше 1011.

Найти наибольший общий делитель и наименьшее общее кратное чисел m и n (m, n>=1011).

Проверить, являются ли числа m и n (m, n>=1011) взаимно простыми.

Докажите, что число 219936 * (219937 1) является совершенным, т.е. равно сумме всех своих делителей, кроме самого себя.

"Вращающееся число". Написать программу, которая находит число, обладающее следующими свойствами:

1) число оканчивается на 5;

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

33. Дана последовательность, заданная рекуррентной формулой

an + 1 = 7an mod 2023, a1 = 1,

где x mod y означает остаток от деления x на y. Написать программу, вычисляющую an при 1<=n<=1000000000000000000000.

Дана последовательность

Написать программу, находящую точное значение an при 1<=n<=150.

Пример. При n = 58 получаем an = 10359022039470231387111424.

35. Напишите программу перевода многозначного числа (с количеством знаков больше 20) в системы счисления с основанием два, восемь, шестнадцать.

36. Разложить на простые множители натуральное число с количеством знаков более 11.

37. Умножение периодической дроби. Задана некоторая положительная правильная периодическая дробь Q и натуральное число N. Числа Q и N таковы, что количество цифр, используемых для их описания, не превосходит 100. При изображении дроби Q периодическая часть заключается в круглые скобки.

Требуется написать программу, которая определяет результат умножения Q на N, то есть непериодическую часть и минимальный период числа Q*N.

В случае получения результата умножения в виде конечной дроби скобки опускаются.

Пример работы правильной программы

Введите периодическую дробь: 0.1(6)

Введите натуральное число: 2

Ответ: 0.(3)

Список литературы

Абрамов С.А., Гнездилова Г.Г., Капустина Е.Н., Селюн М.И. Задачи по программированию. М.: Наука, 1988.

Олимпиады по информатике. Задачи и решения. Методические рекомендации для учителей и учащихся школ. Красноярск, 1991.

Пильщиков В.Н. Сборник упражнений по языку Паскаль. М.: Наука, 1989.

Касаткин В.Н. Информация. Алгоритмы. ЭВМ. М.: Просвещение, 1991.

Хонсбергер Р. Математические изюминки. М.: Наука, 1992.

Семакин И.Г., Шестаков А.П. Лекции по программированию. Пермь: изд-во ПГУ, 1998.

Гусев В.А., Мордкович А.Г. Математика. Справочные материалы. М.: Просвещение, 1990.

Гладков В.П. Курс лабораторных работ по программированию. Пермь: изд-во ПГТУ, 1998.

Шестаков А.П. Задачи на длинную арифметику/

Для подготовки данной работы были использованы материалы с сайта http://www.comp-science.narod.ru/

 

 

Похожие работы

< 1 2