|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 29 Nov 2001 21:54:00
To : Ilia Kantor
Subject : Re: Деление 50-ти значных чисел
--------------------------------------------------------------------------------
DP>> Есть интересный вопрос (возможно кому-то покажется простым - не судите
DP>> строго).
DP>> даны два 50-ти значных(или менее значных числа).Известно, что одно
DP>> является делителем другого. Hеобходимо разделить их не используя
DP>> оператора деления. Результат - oeелое число(максимум пятидесятизначное).
DP>> Вычисление любого результата за 15 или менее секунд(обязательно).
DP>> Может у кого-нибудь есть идеи?(желательно поподробнее)
IK> Способ 1(бpед) Известно, что деление можно заменить многоpазовым
IK> вычитанием. :))) Пpи этом скоpость дико упадет, а пpи делении на пеpвые
IK> 10, скажем, чисел вычитаний будет слишком много - для них можно написать
IK> отдельные пpоoeедуpы деления, учитывающие инфу об используемых числах
А может это даже и не бред. Только вычитать надо делать по умному. Т.е. делить
столбиком,
а не в лоб. Сложность получается O(mn), где m,n - длины чисел. А делаеться это
так:
пусть n - длина делимого, m - делителя. Выделяем в делимом первые m знаков,
вычитаем
из этого делитель, пока число меньше делителя не получиться. Вот мы и получили
первую
цыфру часного(кол-во вычитаний). Далее берем остаток(то что у нас осталось в
результате вычитания), и дописывдм справа следующую циферь делимого, и т.д.
Таким способом можно
получить даже остаток. далее о сложности, сложность вычитания - m, всего
вычитаний
<= (n-m)*9(только перед каждым вычитанием идет сравнение) отсюда получдм всего
9m(n-m)
действий, или O(mn)
У меня стозначное на пятидесятизначное за мгновение делиться.
С наиbestевейшими regardsами, Sergey.
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: WinPoint 95 (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
