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

= 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. Для хранения "длинных" чисел используется не массив, а стек, реализованный с помощью списка. Модифицировать модуль работы с "длинными" числами.

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

С.М. Окулов/ "Длинная" арифметика/

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: