close

Вход

Забыли?

вход по аккаунту

?

lab3(длинная арифм)

код для вставкиСкачать
Лабораторная работа № 3
Арифметика многоразрядных целых чисел
Известно, что переменные целого типа в языке программирования не могут принимать сколь угодно большие значения. Более того, для представления целого числа используется ограниченная память, значит, количество значений целого типа конечно, что противоречит нашим математическим представлениям. Например, в языке программирования Паскаль для хранения целых чисел обычно отводится два (тип Integer) или четыре байта (тип Longint), то есть 16 или 32 бита. В первом случае можно представить 216 = 65536 различных чисел, во втором - 232 = 4294967296 . Иногда нужно обрабатывать числа, которые не входят в этот диапазон. Например, пусть необходимо вычислить
2100 = 1267650600228229401496703205376.
Такие числа мы будем называть ѕдлиннымиї, а средства работы с ними - "длинной арифметикой". Рассмотрим способ хранения "длинного" числа в памяти компьютера. Возьмем массив обычных "коротких" целых и будем считать его позиционной записью "длинного" числа в системе счисления с некоторым основанием В. Тогда каждый элемент этого массива будет принимать значения от 0 до B - 1 , а N таких элементов позволят представить неотрицательные числа от 0 до BN-1 . Для упрощения будем хранить в каждом элементе массива по одной десятичной цифре (то есть B примем равным 10). В языке программирования Паскаль количество элементов массива задается при его описании, поэтому нужно научиться оценивать количество цифр в "длинном" числе. Часто удается использовать формулу для количества цифр в числе N : K = [lg N + 1].
Например, количество цифр в числе 2100 равно K = [lg 2100 + 1] = [100 * lg 2 + 1] = 31
Иногда удается оценить количество цифр в числе, сравнивая его с большим числом. Например,
3200 = 9100 < 10100
Таким образом, в числе 3200 не более 100 десятичных цифр.
Далее будем предполагать, что количество цифр N задано в программе как константа. Определим специальный тип для представления "длинных" целых
Type item = longint;
Long = array [1..N] of item;
Тип item будут иметь элементы, составляющие "длинное" число. Собственно "длинные" числа будут иметь тип Long. Выделить место для записи "длинного" числа - это еще не все. Надо договориться, как мы будем записывать "длинное" число в массив: с начала или с конца массива, с начала или с конца числа. Чтобы было понятнее, что имеется в виду, все варианты показаны на рисунке для случая N = 6 , размещаемое число - 1234 , пустые ячейки обозначены *:
1. 1234***
2. ***1234
3. 4321***
4. ***4321
Чтобы не хранить реальную длину числа, будем хранить в пустых ячейках незначащие нули и обрабатывать их наравне с заполненными. В этом случае выберем второй вариант заполнения массива: будем хранить цифры в обычном порядке в конце массива.
Напишем основные операции с ѕдлиннымиї числами.
1. Преобразование строки в "длинное" число. Идея процедуры: исходя из длины строки рассчитываем позицию цифр в массиве. Сначала заполняем "длинное" число нулями, затем проходим по строке и помещаем каждую цифру в массив на рассчитанное место.
procedure StringToLong(s:String; var x:Long);
Var l,i,k:integer;
begin
l:=length(s);
for i:=1 to N do x[i]:=0;
for i:=1 to l do Val(s[i],x[i+N-l],k);
end;
Эту процедуру можно использовать при вводе "длинных" чисел и при преобразовании обычного числа в "длинное".
2. Вывод "длинного" числа.
"Длинное" число выводится по одной цифре с начала массива. Обязательно нужно пропустить ведущие нули. Реализуйте процедуру вывода самостоятельно.
3. Сложение "длинных" чисел.
Для сложения используется алгоритм сложения "столбиком". Процесс начинается от конца числа. Выделим специальную переменную с для хранения переноса. Сначала с равна нулю. На каждом шаге вычисляется сумма соответствующих цифр двух чисел и переноса. Последняя цифра результата помещается в выходной массив z, остальные - переносятся в следующий разряд.
procedure AddLong(x,y:Long; var z:Long);
Var i,c:integer;
begin
c:=0;
for i:=N downto 1 do
begin
z[i]:=(x[i]+y[i]+c) mod 10;
c:=(x[i]+y[i]+c) div 10;
end;
end;
4. Сравнение "длинных" чисел.
Перебираем цифры с начала массива, пока не найдем две различные цифры. Больше то число, которому принадлежит большая из этих цифр. Реализуйте процедуру самостоятельно.
5. Умножение "длинного" целого на обычное целое.
Эта процедура очень похожа на сложение: точно так же моделируется вычисление столбиком, точно так же на каждом шаге определяется перенос в следующий разряд. Реализуйте процедуру самостоятельно.
6. Умножение "длинного" целого на степень 10.
Эта операция заключается в дописывании к числу нескольких нулей. При этом все значащие цифры сдвигаются влево.
7. Умножение "длинных" целых.
Реализуйте алгоритм умножения "столбиком" с использованием процедур сложения, умножения на обычное целое число и умножения на степень 10.
8. Вычитание "длинных" целых.
Также похоже на сложение. На каждом шаге из цифры одного числа вычитается цифра другого и перенос. Если результат отрицательный, то к нему прибавляется 10 и перенос становится равным 1, иначе перенос обнуляется. Не стоит пытаться моделировать школьную процедуру заема единицы из старшей цифры, поскольку при наличии нулей алгоритм сильно усложняется.
9. Деление "длинных" чисел c остатком.
Сводится к вычитанию. Сначала обнулим остаток, далее будем добавлять к остатку по одной цифре делимого, взяв их слева. Каждый раз выполняем цикл: пока остаток не меньше делителя, вычитаем делитель из остатка и увеличиваем очередную цифру частного.
Задание к лабораторной работе:
Задание 1. Написать функции сложения длинных чисел; умножения длинного числа на целое обычное; умножения длинного числа на степень десятки; умножения двух "длинных" натуральных чисел.
Задание 2. Написать процедуру деления с остатком "длинного" числа на "длинное", используя сравнение и вычитание длинных чисел.
Задание 3.Решить задачу по вариантам, используя "длинную" арифметику:
1) По вводимому с клавиатуры числу n (0 <= n <= 1000), необходимо вычислить значение 2n. 2) Даны два натуральных числа, не превышающие 1000. Вывести точное значение A/B без лишних точек, нулей и пробелов. В случае присутствия бесконечной записи числа следует вывести период в скобках. Например, 10/7=1.(428571), 1/3=0.(3), 100/25=4. 3) Даны три натуральных числа, каждое из которых не превышает 10100. Определить и вывести максимальное из этих трех чисел. ()
4) По заданному натуральному числу А (A <= 103000) требуется найти наибольшее число В такое, что B2 <= A. (другими словами извлечь квадратный корень из числа A). 5) Вычислить факториал целого числа N (N < 1000). Факториал обозначают как N! и вычисляют по формуле: N! = 1 * 2 * 3 * ... * (N-1) * N, причем 0! = 1.
6) В двух строках записаны два неотрицательных целых числа A и B, не превышающие 101000. Выведите значение A-B, учитывая знак.
7) Для натуральных чисел A и B (1 <= A <= 9, 1 <= B <= 104) требуется вычислить значение AB.
8) Факториалом натурального числа K называется произведение K!=1×2×3×...×K. Требуется написать программу, которая по заданному числу N (N ≤ 200) вычислит сумму 1!+2!+...+N!.
Алгоритмы и анализ сложностиИТ(б)II курс, 3 семестр
Документ
Категория
Рефераты
Просмотров
320
Размер файла
51 Кб
Теги
lab3, длинная, арифм
1/--страниц
Пожаловаться на содержимое документа