Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

Интересная задача о неинтересном делении. У кого какие будут предложения

1.6K
18 сентября 2002 года
professor
2 / / 20.08.2000
А вот собственно и сама задача:
Даны два числа, причем одно их них является делителем другого. Вывести частное, если числа могут включать до 50-ти цифр и стандартные операции деления невозможны.
Решение задачи - в Pascal.
503
20 сентября 2002 года
CD
39 / / 20.12.1999
Т.н. длинная арифметика.
Реализуется делением в столбик. Для этого нужно написать также сложение и умножение больших значений.
543
20 сентября 2002 года
Ampersand
75 / / 20.06.2000
Можно такой вариант предложить - числа представить строками, реализовать вычитание (посимвольно, по правилам "в столбик"), а затем последовательно вычитать, пока нужной точности не достигнем. Результат тоже как строку представить.
Аноним
Цитата:

On 2002-09-20 0754, Ampersand wrote
Можно такой вариант предложить - числа представить строками, реализовать вычитание (посимвольно, по правилам "в столбик"), а затем последовательно вычитать, пока нужной точности не достигнем. Результат тоже как строку представить.


Предположим, делимое имеет 49 цифр, делитель - 25. Тогда при рефльзации этого алгоритма нужно будет осуществить ~10^25 вычитаний столвиком, а это ещ вложенные циклы. Слишком сложно, программа будет работать долго.

1.6K
21 сентября 2002 года
professor
2 / / 20.08.2000
Цитата:

On 2002-09-19 2033, CD wrote
Т.н. длинная арифметика.
Реализуется делением в столбик. Для этого нужно написать также сложение и умножение больших значений.


Можно поподробнее?
[EMAIL]plutin@tut.by[/EMAIL]

543
23 сентября 2002 года
Ampersand
75 / / 20.06.2000
Цитата:

On 2002-09-21 1841, Anonymous wrote
Предположим, делимое имеет 49 цифр, делитель - 25. Тогда при рефльзации этого алгоритма нужно будет осуществить ~10^25 вычитаний столвиком, а это ещ вложенные циклы. Слишком сложно, программа будет работать долго.



Согласен, время обработки будет катастрофическое, но навскидку ничего умнее не придумал

503
24 сентября 2002 года
CD
39 / / 20.12.1999
Цитата:

On 2002-09-21 1849, professor wrote
Можно поподробнее?


Сначала пишется сложение в столбик. Это просто - линейный проход от младших разрядов к старшим порязрядное сложение, перенос. Реализуется с помощью целочисленных массивов.
Аналогично - вычитание.

Далее пишется умножение оно использует сложение. Создается на основе подпрограмм умножения длинного числа на цифру (т.е. поразрядное умножение с переносом на число в пределах 0-9) и поразрядного сдвига (переноса элементов массива - цифр - в соседние разряды с дописыванием нулей в младших разрядах; напр. 123 -> 12300).
Перебираются цифры одного из множителей, умножаются на другой и со сдвигом, увеличивающимся на 1, складываются.
Описано обычное умножение в столбик.

Для начала реализуйте эти функции. Если будут вопросы - задавайте.

[ Это Сообщение было отредактировано CD в 2002-09-23 2051 ]

Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог