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

ПОДГОТОВКА К ОЛИМПИАДАМ ПО ПРОГРАММИРОВАНИЮ

В настоящее время олимпиады школьников по программированию, с одной стороны, продолжают пользоваться неизменной популярностью, с другой — число их участников с каждым годом уменьшается, что связано с уменьшением доли подготовки по содержательной линии "Алгоритмизация и программирование" в школе. Таким образом, в числе участников чаще всего оказываются спортсмены-профессионалы — учащиеся специализированнных физико-математических школ либо учащиеся, подготовленные тренерами.

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

К участию в подготовке к олимпиадам по программированию приглашаются учащиеся любых классов школ любых профилей Российской Федерации и ближнего зарубежья. Направлять решения, а также получать консультации можно по адресу [email protected].

ЗАНЯТИЕ № 1. ДЛИННАЯ АРИФМЕТИКА

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

В предлагаемой статье излагаются основные идеи работы с "длинными" числами, присутствует достаточно большой набор задач. Предлагаю внимательно ее прочесть и выполнить на компьютере рассмотренные примеры программ (статья "Задачи на длинную арифметику").

Возможны и другие подходы к представлению длинных чисел, отличные от изложенного в приведенной статье. Например, в публикации С.М. Окулова ""Длинная" арифметика" ("Информатика", № 4, 2000, с. 19-23) предлагается представление длинного числа не в десятичной, а в 10000-ичной системе счисления.

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

Некоторые рекомендации по программированию отдельных алгоритмов

1) Вычисление степени

2) Вычисление квадратного корня

Задания для самостоятельного выполнения

1) Набор арифметических и логических операций для неотрицательных целых длинных чисел.

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

3) Написать программу извлечения квадратного корня из целого числа.

4) Решить одну из задач, приведенных в статье по длинной арифметике, используя набор разработанных в предыдущих заданиях подпрограмм.

5)^* Набор арифметических и логических операций для действительных длинных чисел.

Шестаков А.П.

ЗАДАЧИ НА ДЛИННУЮ АРИФМЕТИКУ

Рассмотрим достаточно популярную в программировании задачу на работу с "длинными" числами. Реально с "астрономическими" или "микроскопическими" числами приходится сталкиваться не так уж и часто. Тем не менее, упражнения, рассматриваемые в этой публикации, могут послужить хорошей тренировкой в области программирования и занять достойное место в классах с углубленным изучением информатики или на кружках по программированию. Алгоритмы, представленные ниже, записаны на Turbo Pascal, версия 7.0. При желании или необходимости они могут легко быть адаптированы к любой другой программной среде.

Диапазон представления целых чисел (Integer, Word, LongInt) ограничен, о чем не раз уже говорилось (впрочем, для действительных величин это замечание тоже актуально). Поэтому при решении задач всегда приходится действовать с оглядкой, — как бы не допустить возникновения ошибки выхода за диапазон или переполнения. Например, вычисляя факториал (n! = 1 * 2 * 3 * … * n), в диапазоне представления величин типа Integer удастся правильно получить только 7! = 5040, а в диапазоне представления типа LongInt — 12! = 479001600. Для больших значений, конечно, можно использовать действительные типы данных, но это уже не гарантирует точного результата. Поэтому полезно для получения точных значений при действиях с многозначными числами разработать другие способы представления таких чисел, алгоритмы выполнения арифметических и других операций, процедуры ввода и вывода результатов и т.д.

Покажем реализацию решения такого рода задач на примере умножения одного многозначного числа на другое. Именно эта арифметическая операция наиболее часто используется при решении других задач.

Наиболее естественным способом представления многозначного числа является запись каждого его разряда в виде отдельного элемента линейного массива (или списка, где память под цифру будет отводиться по мере надобности, в то время как в массиве приходится заранее задавать максимальное количество элементов в нем). Пусть (для удобства дальнейших действий) разряды "длинного" числа при записи в массив нумеруются с единицы, начиная с разряда единиц, т.е. цифра из разряда единиц — элемент массива с номером один, цифра из разряда десятков — элемент массива с номером два и т.д. Определим для работы с "длинными" неотрицательными числами тип данных:

Const MNax = 2000; Type Digit = 0..9; DlChislo = Array[1..Nmax] Of Digit;

Для решения поставленной задачи необходимо уметь выполнять следующие действия:

1) ввод "длинного" числа;

2) собственно умножение двух "длинных" чисел;

3) вывод "длинного" числа;

4) определение количества цифр в записи числа.

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

{Процедура преобразования длинного числа, записанного в виде строки, в массив цифр; переменная OK принимает значение True, если в записи числа нет посторонних символов, отличных от десятичных цифр, иначе — false} Procedure Translate(S : String; Var A : DlChislo; Var OK : Boolean); Var I : Word; Begin Zero(A); I := Length(S); OK := True; While (I >= 1) And OK Do Begin If S[I] In ['0'..'9'] Then A[Length(S)- I + 1]:= Ord(S[I]) - 48 Else OK := False; I := I - 1 End End;

В процедуре вызывается подпрограмма Zero(A), назначение которой — запись нуля в каждый разряд длинного числа. Вот текст этой процедуры:

{Процедура обнуления длинного числа} Procedure Zero(Var A : DlChislo); Var I : Integer; Begin For I := 1 To NMax Do A[I] := 0; End;

Таким образом, длинное число записано в массив, где впереди (в качестве элементов с большими номерами) стоят незначащие нули. При выполнении действий и выводе ответа они не учитываются.

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

{Функция определения количества цифр в записи длинного числа} Function Dlina(C : DlChislo) : Integer; Var I : Integer; Begin I := NMax; While (I > 1) And (C[I] = 0) Do I := I - 1; Dlina := I End;

При ее разработке было использовано следующее соображение: если число не равно нулю, то количество цифр в его записи равно номеру первой цифры, отличной от нуля, если просмотр числа осуществляется от старшего разряда к младшему. Если же длинное число равно нулю, то получается, что количество цифр в его записи равно одной, что и требовалось.

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

{Процедура умножения длинных чисел. A, B — множители, C — произведение} Procedure Multiplication(A, B : DlChislo; Var C : DlChislo); Var I, J : Integer; P : Digit; VspRez : 0..99; Begin Zero(C); For I := 1 To Dlina(A) Do {Цикл по количеству цифр в первом числе} Begin P := 0; {Первоначально перенос равен нулю} For J := 1 To Dlina(B) Do {Цикл по количеству цифр во втором числе} Begin VspRez := A[I] * B[J] + P + C[I + J - 1]; C[I + J - 1] := VspRez Mod 10; {Очередное значение цифры в разряде I + J - 1} P := VspRez Div 10 {Перенос в следующий разряд} End; C[I + J] := P {последний перенос может быть отличен от нуля, запишем его в пока ещё свободный разряд} End End;

Сейчас приведем листинг программы целиком.

Program DlUmn;Const NMax = 2000;Type Digit = 0..9; DlChislo = Array[1..Nmax] Of Digit;Var S : String; M, N, R, F : DlChislo; I, MaxF : Word; Logic : Boolean;{Процедура обнуления длинного числа}Procedure Zero(Var A : DlChislo);Var I : Integer; Begin For I := 1 To NMax Do A[I] := 0; End;{Функция определения количества цифр в записи длинного числа}Function Dlina(C : DlChislo) : Integer;Var I : Integer; Begin I := NMax; While (I > 1) And (C[I] = 0) Do I := I - 1; Dlina := I End;{Процедура печати длинного числа}Procedure Print(A : DlChislo);Var I : Integer; Begin For I := Dlina(A) DownTo 1 Do Write(A[I] : 1); WriteLn End;{Процедура преобразования длинного числа в массив цифр}Procedure Translate(S : String; Var A : DlChislo; Var OK : Boolean);Var I : Word; Begin Zero(A); I := Length(S); OK := True; While (I >= 1) And OK Do Begin If S[I] In ['0'..'9'] Then A[Length(S) - I+ 1] := Ord(S[I]) - 48 Else OK := False; I := I - 1 End End;Procedure Multiplication(A, B : DlChislo; Var C : DlChislo);Var I, J : Integer; P : Digit; VspRez : 0..99; Begin Zero(C); For I := 1 To Dlina(A) Do Begin P := 0; For J := 1 To Dlina(B) Do Begin VspRez := A[I] * B[J] + P + C[I + J - 1]; C[I + J - 1] := VspRez Mod 10; P := VspRez Div 10 End; C[I + J] := P End End;{Основная программа}Begin Repeat {повторяем ввод, пока число не будет введено правильно} Write('Введите первый множитель: '); ReadLn(S); Translate(S, M, Logic) Until Logic; Repeat Write('Введите второй множитель: '); ReadLn(S); Translate(S, N, Logic) Until Logic; Multiplication(M, N, R); Print(R)End.

В приведенном листинге Print — процедура вывода длинного числа. Предоставим читателю самостоятельно разобраться в алгоритме ее работы.

Вернемся к вычислению факториала. Используя разработанные подпрограммы, определим, значение факториала какого максимального числа можно разместить в памяти при таком представлении длинных чисел.

Вот измененный фрагмент основной программы, решающий поставленную задачу.

Begin MaxF := 810; Zero(F); F[1] := 1; For I := 1 To MaxF Do Begin Str(I, S); {преобразование числа I к строковому типу S} Translate(S, M, Logic); Multiplication(F, M, F); Print(F); WriteLn('Факториал числа ', I : 4, ' содержит ', Dlina(F), ' цифр.') End End.

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

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

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

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

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

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

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

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

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

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

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

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

10. Вычислить 100! + 2¹⁰⁰.

11. Вычислить 100! – 2¹⁰⁰.

12. Вычислить 7¹²³.

13. Встречаются ли среди цифр числа 2¹¹²¹³ – 1 две подряд идущие девятки?

14. Вычислить 2^–200.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

28. Составить программу вычисления точного значения многочлена a_nxⁿ + a_{n - 1}x^{n - 1} + ... + a₁x + a₀, где a_i и x — целые числа больше 10¹¹.

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

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

31. Докажите, что число 2¹⁹⁹³⁶ * (2¹⁹⁹³⁷ – 1) является совершенным, т.е. равно сумме всех своих делителей, кроме самого себя.

32. "Вращающееся число". Написать программу, которая находит число, обладающее следующими свойствами:
1) число оканчивается на 5;
2) при умножении его на 5 образуется новое число, которое может быть получено из исходного вычеркиванием цифры 5 на конце и переписыванием ее в начало числа.

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

a_{n + 1} = 7a_n mod 2023, a₁ = 1,

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

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

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

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

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

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

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

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

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

Пример работы правильной программы
Введите периодическую дробь: 0.1(6)
Введите натуральное число: 2
Ответ: 0.(3)

Список использованной литературы

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

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

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

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

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

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

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

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