Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Java: Общие вопросы > Деление болших чисел не пребегая к BigInteger?

Автор: unkis 25.11.2004, 17:12

Ребята нужен алгоритм деления лубих больших не отрецателних целих чисел, которий возвращяет резултат и остаток.
При етом исползоват ммогно только елиментарние типи данних(БигИнтежер исползоват нелзя).

пример.
1000000000000000000000000000000000000000:20000000000000000000000000000000=........

Кто знает подскагите пожалуйста .

Зарания благодарен!
smile

Автор: AntonSaburov 25.11.2004, 17:29

Берем книгу Кнута, там находим алгоритм и пишем, пишем, пишем smile

В принципе тут без шуток - они напоминают умножение, деление, вычитание и сложение столбиком. В принципе реализовать не очень сложно.

Автор: Domestic Cat 25.11.2004, 17:35

Деление двух целых неотрицательных чисел - это просто вычитание одного из другого до тех пор, пока второе не станет меньше чем первое:

Код


// a/b
int result = 0;
while (a > b)
{
      a -= b;
      result++;
}
остаток = a;
результат = result;

То есть, нужно знать, кak вычитать целыe числа произвольной длины и как их сравнивать.
Хранить эи чслa можнo в массивах :

Код


int[] a = {1, 0, 0, 0, 0, 0, 0, ......};

Тогдa сравниват' их очень простo :

Код


int lengthA = a.length;
int lengthB = b.length;
if (lengthA > lengthB) System.out.println( " A > B");
else if (lengthA < lengthB) System.out.println( " A < B");
else
for (int  i= 0; i < lengthB; i++)
{
     if (a[i] > b[i]) { System.out.println( " A > B"); break; }
     if (a[i] < b[i]) { System.out.println( " A < B"); break; };
}

- предполагается, что числа не начнаются с 0.

Вычитать тоже просто, вспомни кak это делается столбиком и делай то жe самое с массивамi.

Автор: unkis 25.11.2004, 17:47

Domestic Cat я тут прикинул и вот что получается если мне надо к примеру разделит числа

Код


а[]={4,2,5,4,5,7,8,4,6,7,6,8,4,1,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} на 
b[]={9,8,7,6,5,4,3,2,1,9,8,7,6,3,2,5,4,6,5,4,5,8,7,9}

то по вашему методу из 4 я не могу вичесть 9 так как 4<9

?????

AntonSaburov у меня ест книги кнута, правда в електронном виде, и там нет оглавления, ви не подскагете в каком томе на какой странице я могу наити ети олгаритми, зарания благодарен.

Автор: AntonSaburov 25.11.2004, 17:52

Скорее всего в первом, но я не помню точно. Давно смотрел. Книга мне давалась тяжело.
Если найду, то скажу.

Автор: Domestic Cat 25.11.2004, 17:59

Цитата

то по вашему методу из 4 я не могу вичесть 9 так как 4<9

ну а столбиком как вычiтается?

Код


 21
-13
-----
 1(-2)
 // прибавляем к отрицательному чисслу 10, вычитаем 1 из следующей за -2 единицей:
08

алгоритм тут несложный

Автор: Sleepy_PIP 25.11.2004, 21:45

Цитата(unkis @ 25.11.2004, 17:47)

Domestic Cat я тут прикинул и вот что получается если мне надо к примеру разделит числа

Код


а[]={4,2,5,4,5,7,8,4,6,7,6,8,4,1,3,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} на 
b[]={9,8,7,6,5,4,3,2,1,9,8,7,6,3,2,5,4,6,5,4,5,8,7,9}

если я правильно понимаю - том 2, параграф 4.3, стр. 304 - это начало.

Автор: unkis 26.11.2004, 12:26

Ребята щсем болшое спасибо.
Попробуемс