Загрузка...
Учебная работа. Реферат: Задачи на длинную арифметику
Спектр представления целых чисел (Integer, Word, LongInt) ограничен, о чем не раз уже говорилось (вообщем, для реальных величин это замечание тоже животрепещуще). Потому при решении задач постоянно приходится действовать с оглядкой, — вроде бы не допустить появления ошибки выхода за спектр либо переполнения. к примеру, вычисляя факториал (n!=1*2*3*…*n), в спектре представления величин типа Integer получится верно получить лишь 7!=5040, а в спектре представления типа LongInt — 12!=479001600. Для огромных значений, естественно, можно употреблять действительные типы данных, но это уже не гарантирует четкого результата. Потому полезно для получения четких значений при действиях с неоднозначными числами создать остальные методы представления таковых чисел, методы выполнения арифметических и остальных операций, процедуры ввода и вывода результатов и т.д.
Покажем реализацию решения такового рода задач на примере умножения 1-го неоднозначного числа на другое. Конкретно эта арифметическая операция более нередко употребляется при решении остальных задач.
Более естественным методом представления неоднозначного числа является запись всякого его разряда в виде отдельного элемента линейного массива (либо перечня, где память под цифру будет отводиться по мере надобности, в то время как в массиве приходится заблаговременно задавать наибольшее количество частей в нем). Пусть (для удобства последующих действий) разряды «длинноватого» числа при записи в массив нумеруются с единицы, начиная с разряда единиц, т.е. цифра из разряда единиц — элемент массива с номером один, цифра из разряда 10-ов — элемент массива с номером два и т.д. Определим для работы с «длинноватыми» неотрицательными числами тип данных:
Const MNax = 2000;
Type Digit = 0..9;
DlChislo = Array[1..Nmax] Of Digit;
Для решения поставленной задачки нужно уметь делать последующие деяния:
1) ввод «длинноватого» числа;
2) фактически умножение 2-ух «длинноватых» чисел;
3) вывод «длинноватого» числа;
4) определение количества цифр в записи числа.
Каждую из подзадач реализуем в виде отдельной подпрограммы. Начнем с ввода. Ввести огромное число целенаправлено в виде строчки, а в предстоящем конвертировать в массив цифр. В процедуре учтен обозначенный выше метод размещения «длинноватого» числа в массиве, т.е. исходя из убеждений юзера число записывается вроде бы в оборотном порядке.
{Процедура преобразования длинноватого числа, записанного
в виде строчки, в массив цифр; переменная OK воспринимает
если в записи числа нет сторонних знаков, хороших от десятичных
цифр, по другому — 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 {Цикл по количеству цифр
во 2-м числе}
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(‘Введите 1-ый множитель: ‘);
ReadLn(S); Translate(S, M, Logic)
Until Logic;
Repeat
Write(‘Введите 2-ой множитель: ‘);
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).
Ниже будет предложен перечень задач для самостоятельного выполнения. Из их, по воззрению создателя, самую большую сложность представляют реализации алгоритмов деления 1-го длинноватого числа на другое и извлечение квадратного корня. метод извлечения квадратного корня тщательно описан в справочнике В.А. Гусева и А.Г. Мордковича [7]. В неких вариантах составленные программки могут выступать как подпрограммы при разработке алгоритмов решения остальных, наиболее сложных (как в примере с факториалом), задач. Не считая авторских задач и задач из перечня литературы тут приведены задания из олимпиад школьников по программированию, проводившихся в Пермской области в 1989-99гг.
Задачки для самостоятельного решения
Составить программку сопоставления 2-ух неоднозначных чисел (количество символов в записи чисел наиболее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 две попорядку идущие девятки?
Вычислить 2–200.
Составить программку нахождения личного и остатка от деления m-значного числа на n–значное (m, n > 20).
Узнать, какое из чисел am, bn больше и на сколько (a, b<=40000; m, n<=10).
Отыскать n символов в десятичной записи квадратного корня из целого числа m (n >= 50).
Отыскать количество делителей n-значного натурального числа (n > 20).
Вычислить четкое
Составить программку вычисления четкого значения суммы 1! + 2! + 3! + … + n! при n>10.
Составить программку вычисления четкого значения суммы дробей
при n > 10. Ответ должен быть представлен в виде несократимой дроби P / Q, где P, Q — натуральные числа.
Вычислить четкое
Составить программку вычисления четкого значения суммы первых n членов последовательности 1, k, k2, k3, …, kn (n > MaxInt). Указание: используйте формулу суммы n членов геометрической прогрессии.
Составить программку вычисления четкого значения суммы первых n членов последовательности чисел, кратных данному натуральному числу k (n>MaxInt). Указание: используйте формулу суммы n членов арифметической прогрессии.
Вычислить четкое
Вычислить четкое
Отыскать 1-ое обычное число, которое больше 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.
Дана последовательность
Написать программку, находящую четкое
Пример. При 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.
Шестаков А.П. задачки на длинноватую математику/
]]>