Реферат: "Длинная" арифметика - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

"Длинная" арифметика

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 24 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

"Длинная" арифметика Известно, что ариф метические действия, выполняемые компьютером в ограниченном числе раз рядов, не всегда позволяют получить точный результат. Более того, мы огра ничены размером (величиной) чисел, с которыми можем работать. А если нам не обходимо выполнить арифметические действия над очень большими числами , например, 30! = 265252859812191058636308480000000? В таких случаях мы сами должны позаботиться о представлен ии чисел в машине и о точном выполнении арифметических операций над ними . Числа, для представления которых в стандартных компьютер ных типах данных не хватает количества двоичных разрядов, называются "дл инными". Реализация арифметических операций над такими "длинными" числам и получила название "длинной арифметики". Организация работы с "длинными" числами во многом зависит от того, как мы представим в компьютере эти числа. "Длинное" число можно за писать, например, с помощью массива десятичных цифр, количество элементо в в таком массиве равно количеству значащих цифр в "длинном" числе. Но если мы будем реализовывать арифметические операции над этим числом, то разм ер массива должен быть достаточным, чтобы разместить в нем и результат, н апример, умножения. Существуют и другие представления "длинных" чисел. Рассмо трим одно из них. Представим наше число 30! = 265252859812191058636308480000000 в виде: 30! = 2 * (104)8 + 6525 * (104)7 + 2859 * (104) + 8121 * (104)5 + 9105 * (104)4 + 8636 * (104)3 + 3084 * (104)2 + 8000 * (104)1 + 0000 * (104)0. Это представление наталкивает на мысль о массиве, предста вленном в табл. 1. Таблица 1 Номер эл емента в массиве А 0 1 2 3 4 5 6 7 8 9 Значение 9 0 8000 3084 8636 9105 8121 2859 6525 2 Мы можем считать, что наше "длинное" число п редставлено в 10000-10 системе счисления (десятитысячно-десятичная система с числения, приведите аналогию с восьмерично-десятичной системой счисле ния), а "цифрами" числа являются четырехзначные числа. Возникают вопросы. Что за 9 в А [0], почему число хранится "задо м наперед"? Ответы очевидны, но подождем с преждевременными объяснениями . Ответы на вопросы будут ясны из текста. Примечание. Мы работаем с положительными числами! Первая задача. Ввести "длинное" число из файла. Решение зада чи начнем с описания данных. Const MaxDig = 1000; Максимальное количество цифр — четырехзна чных! Osn = 10000; Основание нашей системы счисления, в элементах массива храним четырехзначные числа Type Tlong = Array[0..MaxDig] Of Integer; Максимальное количество де сятичных цифр в нашем числе Алгоритм ввода "длинного" числа из файла рассмотрим на кон кретном примере. Пусть в файле записано число 23851674 и основанием (Osn) является 1000 ( храним по три цифры в элементе массива А). Изменение значений элементов м ассива А в процессе ввода (посимвольного в переменную Ch) отражено в табл. 2. Таблица 2 А[0] А[1] А[2] А[3] Ch Примечани е 3 674 851 23 - Конечное состояние 0 0 0 0 2 Начальное состояние 1 2 0 0 3 1-й шаг 1 23 0 0 8 2-й шаг 1 238 0 0 5 3-й шаг 2 385 2 0 1 4-й шаг: старшая цифра элемента А [1] перешла в пока "пустой" эле мент А[2] 2 851 23 0 6 5-й шаг 2 516 238 0 7 6-й шаг 3 167 385 2 4 7-й шаг 3 674 851 23 Проанализируем таблицу (и получим ответы на поставленные выше вопросы). 1. В А[0] храним количество задействованных (ненулевых) элеме нтов массива А — это уже очевидно. 2. При обработке каждой очередной цифры входного числа ста ршая цифра элемента массива с номером i становится младшей цифрой числа в элементе i+1, а вводимая цифра будет младшей цифрой числа из А[1]. В результа те работы нашего алгоритма мы получили число, записанное "задом наперед". Примечание (методическое): Можно ограничиться этим объясн ением и разработку процедуры вынести на самостоятельное задание. Можно продолжить объяснение. Например, выписать фрагмент текста процедуры пе ренос старшей цифры из A[i] в младшую цифру А[i+1], т.е. сдвиг уже введенной части числа на одну позицию вправо: For i := A[0] DownTo 1 Do Begin A[i+l] := A[i+l] + (Longint(A[i]) * 10) Div Osn; A[i] := (LongInt(A[i]) * 10) Mod Osn; End; Пусть мы вводим число 23851674 и первые 6 цифр уже разместили "зад ом наперед" в массиве А. В символьную переменную считали очередную цифру " длинного" числа — это "7". По нашему алгоритму эта цифра "7" должна быть разме щена младшей цифрой в А[1]. Выписанный фрагмент программы "освобождает" мес то для этой цифры. В таблице отражены результаты работы этого фрагмента. i А[1] А[2] А[3] ch 2 516 238 0 7 2 516 380 2 1 160 385 2 После этого остается только добавить теку щую (считанную в ch) цифру "длинного" числа к А[1] и изменить значение А[0]. В конечном итоге процедура должна иметь следующий вид: Procedure ReadLong(Var A : Tlong); Var ch : char; i : Integer; Begin FillChar(A, SizeOf(A), 0) ; Read(ch); While Not(ch In ['0'..'9']) Do Read(ch); пропуск не цифр во вхо дном файле While ch In ['0'..'9'] Do Begin For i := A[0] DownTo 1 Do Begin "протаскивание" старшей цифры в числ е из A[i] в младшую цифру числа из A[i+l] A[i+l] := A[i+l] + (LongInt(A[i]) * 10) Div Osn; A[i] := (LongInt(A[i]) * 10) Mod Osn End; A[1] := A[l] + Ord(ch) - Ord('0'); добавляем мла дшую цифру к числу из А[1] If A[A[0]+1] > 0 Then Inc(A[0]); изменяем длин у, число задействованных элементов массива А Read(ch) End End; Вторая задача . Вывод "длинного" числа в файл и ли на экран. Казалось бы, нет проблем — выводи число за числом. Однако в силу выбранного нами представления "длинного" числа мы должны всегда по мнить, что в каждом элементе массива хранится не последовательность циф р "длинного" числа, а значение числа, записанного этими цифрами. Пусть в эл ементах массива хранятся четырехзначные числа. Тогда "длинное" число 128400583274 будет в массиве А представлено следующим образом: A[0] A[1] A[2] A[3] 3 3274 58 1284 При выводе "длинного" числа из массива нам необходимо вывести 0058, иначе будет потеря цифр. Итак, незначащие нули также необходимо выводить . Процедура вывода имеет вид: Procedure WriteLong(Const A : Tlong); Var ls, s : String; i : Integer; Begin Str(Osn Div 10, Is); Write(A[A[0]]; выводим старшие цифры числа For i := A[0] - l DownTo 1 Do Begin Str(A[i], s); While Length(s) < Length(Is) Do s := '0' + s; дополняем нез начащими нулями Write(s) End; WriteLn End; Третья задача . Предварительная работа по оп исанию способа хранения, вводу и выводу "длинных" чисел выполнена. У нас есть все необходимые "кирпичики", например, для написа ния программы сложения двух "длинных" положительных чисел. Исходные числ а и результат храним в файлах. Назовем процедуру сложения SumLongTwo. Тогда программа ввода двух "длинных" чисел и вывода резуль тата их сложения будет иметь следующий вид: Var A, B, C : Tlong; Begin Assign(Input, 'Input.txt'); Reset(Input); ReadLong(A); ReadLong(B) ; Close(Input); SumLongTwo(A, B, C); Assign(Output, 'Output.txt'); Rewrite(Output); WriteLong(C); Close(Output) End. Алгоритм процедуры сложения можно объяснить на простом п римере. Пусть А=870613029451, В=3475912100517461. i A[i] B[i] C[1] C[2] C[3] C[4] 1 9451 7461 6912 1 0 0 2 1302 51 6912 1354 0 0 3 8706 9121 6912 1354 7827 1 4 0 3475 6912 1354 7827 3476 Алгоритм имитирует привычное сложение столбиком, начиная с мл адших разрядов. И именно для простоты реализации арифметических операц ий над "длинными" числами используется машинное представление "задом нап еред". Результат: С = 3476782713546912. Ниже приведен текст процедуры сложения двух "длинных" чис ел. Procedure SumLongTwo(A, B : Nlong; Var C : Tlong); Var i, k : Integer; Begin FillChar(C, SizeOf (C), 0) ; If A[0] > B[0] Then k := A[0] Else k : =B[0]; For i := l To k Do Begin С [i+1] := (C[i] + A[i] + B[i]) Div Osn; C[i] := (C[i] + A[i] + B[i]) Mod Osn Есть ли в этих о ператорах ошибка? End; If C[k+l] = 0 Then C[0] := k Else C[0] := k + l End; Четвертая задача. Реализация операций сравнения для "длин ных" чисел (А=В, А<В, А>В, А<=В, А>=В). Function Eq(A, B : TLong) : Boolean; Var i : Integer; Begin Eq := False; If A[0] <> B[0] Then Exit Else Begin i := l; While (i <= A[0]) And (A[i] = B[i]) Do Inc(i); Eq := i = A[0] + l End End; Реализация функции А > В также прозрачна. Function More(A, B : Tlong) : Boolean; Var i : Integer; Begin If A[0] < B[0] Then More := False Else If A[0] > B[0] Then More := True Else Begin i := A[0]; While (i > 0) And (A[i] = B[i]) Do Dec(i); If i = 0 Then More := False Else If A[i] > B[i] Then More := True Else More:=False End End; Остальные функции реализуются через функции Eq и More. Function Less(A, B : Tlong) : Boolean; A < B Begin Less := Not(More(A, B) Or Eq(A, B)) End; Function More_Eq(A, B : Tlong) : Boolean; A >= B Begin More_Eq := More(A, B) Or Eq(A, B) End; Function Less_Eq(A, B : Tlong) : Boolean; A <= B Begin Less_Eq := Not More(A, B) End; Для самостоятельного решения может быть предложена след ующая, более сложная, задача. Требуется разработать функцию, которая выд ает 0, если А больше В, 1, если А меньше В, и 2 при равенстве чисел. Но сравнение д олжно быть выполнено с учетом сдвига. О чем идет речь? Поясним на примере. Пусть А равно 56784, а В — 634. При сдвиге числа В на 2 позиции влево функция должн а сказать, что В больше А, без сдвига, что А больше В. Другой пример. При А рав ном 56700, а В — 567 и сдвиге 2 функция должна "сказать", что числа равны. Решение может иметь следующий вид : Function More(Const А , В : Tlong; Const sdvig : Integer) : Byte; Var i : Integer; Begin If A[0] > B[0] + sdvig Then More := 0 Else If A[0] < B[0] + sdvig Then More := l Else Begin i := A[0]; While (i > sdvig) And (A[i] = B[i-sdvig]) Do Dec(i); If i = sdvig Then Begin More:=0; совпадение чисел с учетом сдвига For i := 1 To sdvig Do If A[i] > 0 Then Exit; More := 2; числа равны, "хвост" чис ла А равен нулю End Else More := Byte(A[i] < B[i-sdvig]) End End; Пятая задача. Умножение длинного числа на короткое. Под ко ротким понимается целое число типа LongInt. Процедура очень походит на процедуру сложения двух длинн ых чисел. Procedure Mul(Const A : TLong; Const К : Longlnt; Var С : TLong); Var i : Integer; результат - значение переменной С Begin FillChar (С, SizeOf(С), 0); If K = 0 Then Inc(С[0]) умножение на ноль Else Begin For i:= l To A[0] Do Begin C[i+l] := (LongInt(A[i]) * K + C[i]) Div Osn; C[i] := (LongInt(A[i])* K + C[i]) Mod Osn End; If C[A[0]+1] > 0 Then C[0]:= A[0] + 1 Else C[0]:= A[0] определяем длину результата End End; Шестая задача. Вычитание двух длинных чисел с учетом сдви га Если понятие сдвига пока не понятно, то оставьте его в поко е, на самом деле вычитание с учетом сдвига потребуется при реализации оп ерации деления. В начале выясните логику работы процедуры при нулевом сд виге. Введем ограничение: число, из которого вычитают, больше чи сла, которое вычитается. Работать с "длинными" отрицательными числами мы не умеем. Процедура была бы похожа на процедуры сложения и умножени я, если бы не одно "но" — заимствование единицы из старшего разряда вместо переноса единицы в старший разряд. Например, в обычной системе счислени я мы вычитаем 9 из 11 — идет заимствование 1 из разряда десятков, а если из 10000 в ычитаем 9 — процесс заимствования несколько сложнее. Procedure Sub (Var A : TLong; Const B : TLong; Const sp : Integer); Var i, j : Integer; из А вычитаем В с учетом сдвига sp, результат вычита ния в А Begin For i := l To B[0] Do Begin Dec(A[i+sp], B[i]); j: = i; * реализация сложного заимствования while (A[j+sp] < 0) and (j <= A[0]) Do Begin * Inc(A[j+sp], Osn) ; Dec(A[j+sp+l]); Inc(j); * end; * Реализация простого заимствования. Если операторы, отмеченные *, заменить на нижеприведенные операторы в фигурных с кобках, то, по понятным причинам, логика не будет работ ать при всех исходных данных. Можно сознательн о сделать ошибку и предложить найти ее — принцип "обу чение через ошибку" If A[i+sp]<0 Then Begin Inc(A[i+sp], Osn); Dec (A[i+sp+l]);End; End; i := A[0]; While (i > l) And (A[i] = 0) Do Dec(i); A[0] := i корректировка длины результата операции End; Рекомендуется выполнить трассировку работы данной проц едуры, например, для следующих исходных данных. Число А равно 100000001000000000000, число В — 2000073859998. Седьмая задача. Деление двух длинных чисел, т.е. нахождение целой части частного и остатка. Написать исходную (без уточнений) часть логики не составл яет труда. Это: Procedure Long_Div_Long(Const А, В : TLong; Var Res, Ost : TLong); Begin FillChar(Res, SizeOf(Res), 0); Res[0] := 1; FillChar(Ost, SizeOf(Ost), 0); 0st[0] := 1; Case More(A, B, 0) Of 0: MakeDel(A, B, Res, Ost); А больше В, пока не знаем, как выполнять операцию - "в ыносим" в процедуру 1: Ost:=A; А меньше В 2: Res[l] := l; А равно В End; End; А дальше? Дальше начинаются проблемы. Делить столбиком на с научили в школе. Например, 1000143123567 |73859998 - 73859998 |---------- --------- |13541 (Целая часть частного) 261543143 - 221579994 ---------- 399631495 - 369299990 --------- 303315056 - 295439992 ---------- 78750647 - 73859998 -------- 4890649 (Остаток) Что мы делали? На каждом этапе в уме подбирали цифру (1, 3, 5 и т.д .), такую, что произведение этой цифры на делитель дает число меньшее, но на иболее близкое к числу... Какому? Это трудно сказать словами, но из примера ясно. Зачем нам это делать в уме, пусть делает компьютер. Однако упростим п ример, оставим его для тестирования окончательной логики процедуры, тем более что и числа "длинные". Пусть число А будет меньше В*10, тогда в результа те (целой части деления) будет одна цифра. Например, А равно 564, а В — 63 и прост ая десятичная система счисления. Попробуем подобрать цифру результата, но не методом прямого перебора, а методом деления отрезка пополам. Пусть Down — верхняя граница интервала изменения подбираемой цифры, Up — нижняя г раница интервала, Ost равен делимому. Down Up С = В * ( (Down + Up) Div 2) Ost = 564 0 10 315 = 63 * ( (0 + 10) Div 2) C < Ost 5 10 441 = 63 * ( (5 + 10) Div 2) C < Ost 7 10 504 = 63 * ( (7 + 10) Div 2) C < Ost 8 10 567 = 63 * ( (8 + 10) Div 2) C > Ost 8 9 504 = 63 * ( (8 + 9) Div 2) C < Ost Итак, результат — целая часть частного — равен (Up + Down) Div 2, остаток о т деления — разность между значениями Ost и С. Нижнюю границу (Down) изменяем, е сли результат (С) меньше остатка, верхнюю (Up), — если больше. Усложним пример. Пусть А равно 27856, а В — 354. Основанием систем ы счисления является не 10, а 10000. Down Up С Ost = 27856 0 10000 1770000 C > Ost 0 5000 885000 C > Ost 0 2500 442500 C > Ost 0 1250 221250 C > Ost 0 625 110448 C > Ost 0 312 55224 C > Ost 0 156 27612 C < Ost 78 156 41418 C > Ost 78 117 34338 C > Ost 78 97 30798 C > Ost 78 87 29028 C > Ost 78 82 28320 C > Ost 78 80 27966 C > Ost 78 79 27612 C < Ost Целая часть частного равна 78, остаток от деления — 27856 минус 27612, т.е . 244. Пора приводить процедуру. Используемые "кирпичики": функц ия сравнения чисел (More) с учетом сдвига и функция умножения длинного числа на короткое (Mul) описаны выше. Function FindBin(Var Ost : Tlong; Const В : TLong; Const sp : Integer) : Longint; Var Down, Up : Word; C : TLong; Begin Down := 0;Up := 0sn; основание системы счисления While Up - l > Down Do Begin Есть возможность пре подавателю сделать сознательную ошибку. Изменить условие цикла на Up>Down. Результат - зацикливание программы. Mul(В, (Up + Down) Div 2, С); Case More(Ost, C, sp) Of 0: Down := (Down + Up) Div 2; 1: Up := (Up + Down) Div 2; 2: Begin Up := (Up + Down) Div 2; Down := Up End; End; End; Mul(B, (Up + Down) Div 2, C ); If More (Ost, C, 0) = 0 Then Sub(Ost, C, sp) находим остаток от деления Else begin Sub (C, Ost, sp); Ost := C end; FindBin := (Up + Down) Div 2; целая часть частного End; Осталось разобраться со сдвигом, значением переменной sp в нашем изложении. Опять вернемся к обычной системе счисления и попытаемс я разделить, например, 635 на 15. Что мы делаем? Вначале делим 63 на 15 и формируем, п одбираем в уме первую цифру результата. Подбирать с помощью компьютера м ы научились. Подобрали — это цифра 4, и это старшая цифра результата. Изме ним остаток. Если вначале он был 635, то сейчас стал 35. Вычитать с учетом сдвиг а мы умеем. Опять подбираем цифру. Вторую цифру результата. Это цифра 2 и ос таток 5. Итак, результат (целая часть) 42, остаток от деления 5. А что изменится, если основанием будет не 10, а 10000? Логика совпадает, только в уме считать неск олько труднее, но ведь у нас же есть молоток под названием компьютер — пу сть он вбивает гвозди. Procedure MakeDel(Const А , В : TLong; Var Res, Ost : TLong); Var sp : Integer; Begin Ost := A; первоначальное значение остатка sp := А [0] - В [0]; If More( А , В , sp) = l Then Dec(sp); B * Osn > A, в результате одна цифра Res[0] := sp + l; While sp >= 0 Do Begin находим очередную цифру результата Res[sp + 1] := FindBin(Ost, B, sp); Dec(sp) End End; Методические рекомендации. Представленный материал изл агается на четырех занятиях по известной схеме: 10-15-минутное изложение ид ей, а затем работа учащихся под руководством преподавателя. 1-е занятие. Ввод, вывод и сложение длинных чисел (задачи 1, 2, 3). 2-е занятие. Функции сравнения (задача 4). 3-е занятие. Умножение и вычитание длинных чисел (задачи 5, 6). 4-е занятие. Деление длинных чисел (задача 7). Безусловно, эта схема не догма. В зависимости от уровня подготовки учащихся на самостоят ельное выполнение может быть вынесена значительная часть материала. За мечу только, что в силу сложившейся традиции в ряде случаев допускаются при изложении сознательные ошибки. В результате работы каждый учащийся должен иметь собственный модуль для работы с "длинными" числами. Темы для исследований 1. Решение задач: поиск наибольшего общего делителя двух "дл инных" чисел; поиск наименьшего общего кратного двух "длинных" чисел; извл ечение квадратного корня из "длинного" числа и т.д. 2. "Длинные" числа могут быть отрицательными. Как изменятся описанные выше операции для этого случая? 3. Для хранения "длинных" чисел используется не массив, а сте к, реализованный с помощью списка. Модифицировать модуль работы с "длинн ыми" числами. Список литера туры С.М. Окулов. "Длинна я" арифметика. Для подготовки данной работы были использованы материал ы с сайта http://www.comp-science.ru/
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
- У меня оригами не выходит никак.
- А давно съел?
Anekdot.ru

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

Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru