Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 18, средняя оценка - 4.72
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
#1

Классы, Длинная арифметика, LongLong - C++

17.06.2011, 22:25. Просмотров 2232. Ответов 17
Метки нет (Все метки)

Добрый день,

Задание изначально было такое:

Реализовать класс Money , используя для представления рублей класс LongLong.

Класс Money - представлен двумя полями LongLong для рублей и unsigned char для копеек. Дробная часть (копейки) при выводе на экран должна быть отделена от целой части запятой. Реализовать сложение, вычитание, деление сумм, деление суммы на дробное число, умножение на дробное число и операции сравнения.

Класс LongLong для работы с целыми числами из 64 бит. Число должно быть представлено двумя полями: unsigned long — старшая часть, unsigned long — младшая часть. Должны быть реализованы арифметические операции, присутствующие в С++ (без присваивания), и сравнения.

Класс Money реализовал, а проблема в следующем:

Сложение и умножение для LongLong довольно просто реализуется - складываем левые части, складываем правые. Если в левой появился новый разряд, прибавляем в правую. Вычитание тоже ясно, а как быть с умножением?! Как перемножить два longlong если они каждый из двух частей, причём long. Сколько где разрядов получится? Как сделать чтобы не сильно не вылез? А деление я вообще сложно представляю...

В общем, меня как раз и волнуют реализация умножения и деления. Буду рад любым советам. Видел на форуме Валерия Викторовича. Буду очень признателен, если он объяснит какими методами предполагалось решение его задач.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
17.06.2011, 22:25     Классы, Длинная арифметика, LongLong
Посмотрите здесь:

Длинная арифметика - C++
Здравствуйте, есть такая задача.. Препод по алгоритмам задал сделать программу для перевода чисел в разные системы счислений. Это...

Длинная арифметика N+1 - C++
Помогите плиз. Вводится n. Вывести N+1. Ограничений нет. Я понимаю что надо ввести массив и читать каждый символ. Оставшиеся елементы...

Длинная арифметика - C++
http://www.********/index.asp?main=task&id_task=103 Как решить эту задачу? С помощью чего, и в чем смысл решения длянной...

Длинная арифметика - C++
Поодскажите какую-нибудь библиотеку, где реализована работа со знаковыми целыми числами произвольной длины.

Длинная арифметика - C++
Всем привет! Хотелось бы узнать -- есть ли в С++ библиотека, где реализованы операции над длинными числами?

длинная арифметика - C++
решите задачку: пользователь вводит 2 больших числа (числа от -1*2^127 до 1*2^127-1). Написать программу для суммирования таких чисел.

Длинная арифметика - C++
Всем доброго вечера. Нужна помощь в решении задачи. Составить программу для вычисления числа: 2^64-1. В результате сохранить все...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
17.06.2011, 23:01     Классы, Длинная арифметика, LongLong #2
Цитата Сообщение от Yellow2815 Посмотреть сообщение
Сложение и умножение для LongLong довольно просто реализуется - складываем левые части, складываем правые. Если в левой появился новый разряд, прибавляем в правую.
Наверное правильнее оперировать понятиями старшая и младшая, а не левая и правая.
Это на ассемблере просто, там флаг переноса есть. На Си всё-таки посложнее. Ну ладно, будем считать, что просто.

Цитата Сообщение от Yellow2815 Посмотреть сообщение
Вычитание тоже ясно, а как быть с умножением?!
Для умножения могу посоветовать помедитировать над следующей формулой.
Предположим, что у нас есть числа размером 2*n разрядов.
Представим числа A и B половинами по n разрядов
A = (Ah << n) + Al
B = (Bh << n) + Bl
Тогда
A*B = ((Ah << n) + Al) * ((Bh << n) + Bl) = (Ah*Bh << 2*n) + ( (Ah*Bl + Al*Bh) << n ) + Al*Bl

Добавлено через 4 минуты
Цитата Сообщение от Yellow2815 Посмотреть сообщение
А деление я вообще сложно представляю...
А деление сдвигами и вычитаниями, как в школе учили — уголком. Медленно, но зато надёжно
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
17.06.2011, 23:23  [ТС]     Классы, Длинная арифметика, LongLong #3
Цитата Сообщение от grizlik78 Посмотреть сообщение
Наверное правильнее оперировать понятиями старшая и младшая, а не левая и правая.
Это на ассемблере просто, там флаг переноса есть. На Си всё-таки посложнее. Ну ладно, будем считать, что просто.
Когда Money делал, та же задача была с рублями и копейками, копейки сложили - получили рубль - отправили в рубль.

Цитата Сообщение от grizlik78 Посмотреть сообщение
Для умножения могу посоветовать помедитировать над следующей формулой.
Предположим, что у нас есть числа размером 2*n разрядов.
Представим числа A и B половинами по n разрядов
A = (Ah << n) + Al
B = (Bh << n) + Bl
Тогда
A*B = ((Ah << n) + Al) * ((Bh << n) + Bl) = (Ah*Bh << 2*n) + ( (Ah*Bl + Al*Bh) << n ) + Al*Bl
Помедитирую, спасибо за формулу.

Цитата Сообщение от grizlik78 Посмотреть сообщение
А деление сдвигами и вычитаниями, как в школе учили — уголком. Медленно, но зато надёжно
Столбиком? так там же две части? какой алгоритм предполагается?
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
17.06.2011, 23:33     Классы, Длинная арифметика, LongLong #4
Цитата Сообщение от Yellow2815 Посмотреть сообщение
Столбиком? так там же две части? какой алгоритм предполагается?
По-моему это всё-таки называется уголком. В столбик умножают
Предполагается что у нас уже есть реализованные функции сравнения, вычитания и, хотя бы, умножение на 2 (а лучше сдвиг влево).
Участвую делимое, делитель и частное
сначала делитель сдвигаем влево по одному разряду (умножаем на 2) до тех пор, пока делитель меньше делимого. Количество сдвигов определяет число разрядов целой части частного.
Если получим делитель больше делимого, придётся вернуться на разряд назад.
Ну а дальше просто.
Если делимое больше-равно делителя, вычитаем делитель из делимого и прибавляем к частному единицу. Если меньше — ничего не меняется. Дальше сдвигаем делитель на разряд вправо, частное на разряд влево и повторяем столько раз, сколько нужно
Ну, тонкости уже во время реализации продумать можно. Рекомендую поделить разные числа в двоичной форме на листочке вручную
ValeryLaptev
Эксперт С++
1039 / 818 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
18.06.2011, 08:46     Классы, Длинная арифметика, LongLong #5
1. Умножение можно делать многократным сложением - в цикле
2. Деление можно делать многократным вычитанием - в цикле

Сложение младших частей и перенос.
1. Младшая часть LongLong - беззнаковая.
2. Если при сложении получается число, которое меньше обоих слагаемых - значит есть перенос.
Проверьте на числах из одной цифры:
6+7 = 13. В младшей части осталось 3 - меньше 6 и меньше 7.
Поэтому учесть перенос - легко.

Изучайте машинное представление чисел...
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
18.06.2011, 17:28  [ТС]     Классы, Длинная арифметика, LongLong #6
Цитата Сообщение от grizlik78 Посмотреть сообщение
По-моему это всё-таки называется уголком. В столбик умножают
Конечно, уголком... это я утомился и допустил опечатку))

ValeryLaptev,
А цикл вы считаете нормальным решением данной задачи?


Спасибо за советы, выходные частично посвящу этой задаче. Посмотрим, что получится...
ValeryLaptev
Эксперт С++
1039 / 818 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
18.06.2011, 17:38     Классы, Длинная арифметика, LongLong #7
Цитата Сообщение от Yellow2815 Посмотреть сообщение
Конечно, уголком... это я утомился и допустил опечатку))

ValeryLaptev,
А цикл вы считаете нормальным решением данной задачи?

Спасибо за советы, выходные частично посвящу этой задаче. Посмотрим, что получится...
Да. Реализовали базовую операцию вычитания, отладили ее. Теперь в делении можно использовать ГАРАНТИРОВАННО правильную функцию. Если ошибки есть, то только в НОВОМ тексте.
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
18.06.2011, 18:03  [ТС]     Классы, Длинная арифметика, LongLong #8
ValeryLaptev,
Это задание можно без перегрузки операторов делать?
То есть просто методы класса описать и всё? И потом функции только вызывать?

А то я уже задания из второго семинара поделал, там 8-чные числа, 16-чные.. И меня перемкнуло, что здесь тоже нужно перегрузку операторов делать, а это ведь не обязательно да?
ValeryLaptev
Эксперт С++
1039 / 818 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
18.06.2011, 18:48     Классы, Длинная арифметика, LongLong #9
Да, первый раз - без перегрузки. Потом будет и с конструкторами, и с перегрузкой...
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
20.06.2011, 16:12  [ТС]     Классы, Длинная арифметика, LongLong #10
Возник вопрос

Как быть если с числом 10000000000
в старшую часть поместится 10, а в младшую 000000000.
Тогда общее число станет 100, вместо 10000000000.

Такая проблема возникает не только при вводе(что я решил), но и при вычитании...
как быть?
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
20.06.2011, 16:16     Классы, Длинная арифметика, LongLong #11
Непонятно, с чего это общее станет 100? Если старшая часть не равна нулю, то в младшей все нули значащие, и, к примеру, при выводе их нужно будет выводить все.
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
20.06.2011, 16:21  [ТС]     Классы, Длинная арифметика, LongLong #12
Цитата Сообщение от grizlik78 Посмотреть сообщение
Непонятно, с чего это общее станет 100? Если старшая часть не равна нулю, то в младшей все нули значащие, и, к примеру, при выводе их нужно будет выводить все.

так ведь младшая часть у нас unsigned long. а ей что 0, что 0000000. Всё едино.
Простой вывод числа - можно организовать, а вот после вычитания как быть. Сносить разряды из старшей части что ли? Так нам нули надо сохранить... или наоборот в старшую часть нули перекидывать?
silent_1991
Эксперт С++
4961 / 3037 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
21.06.2011, 15:30     Классы, Длинная арифметика, LongLong #13
Yellow2815, если хоть что-то есть в старшей части, а младшая равна нулю, то в ней на самом деле лежит 20 нулей. Просто запоминаем это и действуем по обстоятельствам.
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
21.06.2011, 17:55  [ТС]     Классы, Длинная арифметика, LongLong #14
silent_1991, )) Это хорошо, для вывода сгодится, а вот при таком числе
1000000000000001, делаем разбиение
старшая 1000000 и младшая 000000001.
Что в младшей?
В общем очень не просто. Длинная арифметика лучше реализуется с массивами.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.06.2011, 18:03     Классы, Длинная арифметика, LongLong
Еще ссылки по теме:

Длинная арифметика - C++
Алгоритмы всех операций в принципе уже готовы (длина числа ограничивается только ресурсами ПК). Осталось только подобрать качественный...

Длинная арифметика)) - C++
Программка уже почти готова, единственное неправильно находит остаток при делении По заданию: Надо ввести 2-ва целых числа неогран....

Длинная арифметика - C++
Ребята,объясните как решить задачу , напишите хоть часть кода. Пусть даны числа a , b . Найти a+b, если a и b не больше чем 10 в...

Длинная арифметика - C++
class BigInt { static const int max_size = 100000;//количество десятичных разрядов, которые должно вмещать static...

Длинная арифметика - C++
Как сделать типы длинных чисел, например, знаковое 256-ти битное целое и 256-ти битное вещественное с 224-х битной мантиссой и 32-х битным...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт С++
1908 / 1440 / 110
Регистрация: 29.05.2011
Сообщений: 2,995
21.06.2011, 18:03     Классы, Длинная арифметика, LongLong #15
Цитата Сообщение от Yellow2815 Посмотреть сообщение
Это хорошо, для вывода сгодится, а вот при таком числе
1000000000000001, делаем разбиение
старшая 1000000 и младшая 000000001.
Что в младшей?
Хочется кое что уточнить. Я вот всё не могу понять, что же за представление используется для хранения младшей части, если в примерах там 9 разрядов. Кстати, эти разряды двоичные? Если двоичные, то что это, отдельные биты в некоторой целочисленной переменной?
Ну а непосредственно по вопросу, в младшей части число 1. Но при вычитании двойки в младшей части должно оказаться максимально возможное значение этой младшей части. А старшая должна уменьшиться на 1, то есть да — произойдёт заём из старшей части. Для получения полного числа младшая и старшая части складываются (мысленно) с разными весами. Младшая с весом один, старшая с весом равным максимуму младшей плюс один.

Добавлено через 50 секунд
Если всё не так, то требуется нам подробно объяснить, что понимается под младшей и старшей частями.
Yandex
Объявления
21.06.2011, 18:03     Классы, Длинная арифметика, LongLong
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru