Интересная задача о неинтересном делении. У кого какие будут предложения
Даны два числа, причем одно их них является делителем другого. Вывести частное, если числа могут включать до 50-ти цифр и стандартные операции деления невозможны.
Решение задачи - в Pascal.
Реализуется делением в столбик. Для этого нужно написать также сложение и умножение больших значений.
On 2002-09-20 0754, Ampersand wrote
Можно такой вариант предложить - числа представить строками, реализовать вычитание (посимвольно, по правилам "в столбик"), а затем последовательно вычитать, пока нужной точности не достигнем. Результат тоже как строку представить.
Предположим, делимое имеет 49 цифр, делитель - 25. Тогда при рефльзации этого алгоритма нужно будет осуществить ~10^25 вычитаний столвиком, а это ещ вложенные циклы. Слишком сложно, программа будет работать долго.
On 2002-09-19 2033, CD wrote
Т.н. длинная арифметика.
Реализуется делением в столбик. Для этого нужно написать также сложение и умножение больших значений.
Можно поподробнее?
[EMAIL]plutin@tut.by[/EMAIL]
On 2002-09-21 1841, Anonymous wrote
Предположим, делимое имеет 49 цифр, делитель - 25. Тогда при рефльзации этого алгоритма нужно будет осуществить ~10^25 вычитаний столвиком, а это ещ вложенные циклы. Слишком сложно, программа будет работать долго.
Согласен, время обработки будет катастрофическое, но навскидку ничего умнее не придумал
On 2002-09-21 1849, professor wrote
Можно поподробнее?
Сначала пишется сложение в столбик. Это просто - линейный проход от младших разрядов к старшим порязрядное сложение, перенос. Реализуется с помощью целочисленных массивов.
Аналогично - вычитание.
Далее пишется умножение оно использует сложение. Создается на основе подпрограмм умножения длинного числа на цифру (т.е. поразрядное умножение с переносом на число в пределах 0-9) и поразрядного сдвига (переноса элементов массива - цифр - в соседние разряды с дописыванием нулей в младших разрядах; напр. 123 -> 12300).
Перебираются цифры одного из множителей, умножаются на другой и со сдвигом, увеличивающимся на 1, складываются.
Описано обычное умножение в столбик.
Для начала реализуйте эти функции. Если будут вопросы - задавайте.
[ Это Сообщение было отредактировано CD в 2002-09-23 2051 ]