|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Nickita A Startcev 2:5030/1039.8 09 Oct 2001 08:35:36
To : Denis Petrushenko
Subject : Деление 50-ти значных чисел
--------------------------------------------------------------------------------
18 Sep 01 , 19:49 Denis Petrushenko писал к All:
DP> Даны два 50-ти значных(или менее значных числа).Известно, что одно
DP> является делителем другого. Hеобходимо разделить их не используя
DP> оператора деления. Результат - целое число(максимум
DP> пятидесятизначное). Вычисление любого результата за 15 или менее
DP> секунд(обязательно).
DP> Может у кого-нибудь есть идеи?(желательно поподробнее)
Умножаем делитель на 2, еще раз на 2, и так пока он не станет больше делимого.
Далее берем на одно умножение меньше. Вычитаем результат из делимого.
"использованный множитель" прибавляем к предыдущему использованному множителю.
Пример: 100:4
4,8,16,32,64; 64=4*16;
100-64=36
4,8,16,32; 32=4*8;
36-32=4
4; 4=1*4
Итого: 100=64+32+4=4*(16+8+1)
Искомое число 16+8+1=25
(Другое объяснение: Пусть Д-делимое, д-делитель; среди чисел 2^x*д ищем
наибольшее, при условии 2^x*д <= Д;вычитаем его; Таким образом разлагаем Д в
выражение вида
Д=д*2^а+д*2^b+д*2^c...=д*(2^a+2^b+2^c...)
. С уважением, Hикита.
--- GoldED+/LNX 1.1.4.7
* Origin: Люди Билли не любили... (c) (2:5030/1039.8)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
