Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

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

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

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

Добрый день,

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

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

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

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

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

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

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

Длинная арифметика - C++
Нужно реализовать сложение и умножение больших чисел. Есть идея, необходима помощь в реализации на C++. Собственно, идеи такие... ...

Длинная арифметика - C++
Помогите реализовать длинную арифметику #include <iostream> #include <string> using namespace std; int main(){ int a; string...

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

длинная арифметика - C++
Долгое время бьюсь как составить программу по этой теме в интернете искал нашел это for (int i=(int)s.length(); i>0; i-=9) if (i < 9) ...

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

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

17
grizlik78
Эксперт С++
1966 / 1459 / 120
Регистрация: 29.05.2011
Сообщений: 3,018
17.06.2011, 23:01 #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 Посмотреть сообщение
А деление я вообще сложно представляю...
А деление сдвигами и вычитаниями, как в школе учили — уголком. Медленно, но зато надёжно
0
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
17.06.2011, 23:23  [ТС] #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 Посмотреть сообщение
А деление сдвигами и вычитаниями, как в школе учили — уголком. Медленно, но зато надёжно
Столбиком? так там же две части? какой алгоритм предполагается?
0
grizlik78
Эксперт С++
1966 / 1459 / 120
Регистрация: 29.05.2011
Сообщений: 3,018
17.06.2011, 23:33 #4
Цитата Сообщение от Yellow2815 Посмотреть сообщение
Столбиком? так там же две части? какой алгоритм предполагается?
По-моему это всё-таки называется уголком. В столбик умножают
Предполагается что у нас уже есть реализованные функции сравнения, вычитания и, хотя бы, умножение на 2 (а лучше сдвиг влево).
Участвую делимое, делитель и частное
сначала делитель сдвигаем влево по одному разряду (умножаем на 2) до тех пор, пока делитель меньше делимого. Количество сдвигов определяет число разрядов целой части частного.
Если получим делитель больше делимого, придётся вернуться на разряд назад.
Ну а дальше просто.
Если делимое больше-равно делителя, вычитаем делитель из делимого и прибавляем к частному единицу. Если меньше — ничего не меняется. Дальше сдвигаем делитель на разряд вправо, частное на разряд влево и повторяем столько раз, сколько нужно
Ну, тонкости уже во время реализации продумать можно. Рекомендую поделить разные числа в двоичной форме на листочке вручную
0
ValeryLaptev
Эксперт С++
1042 / 821 / 48
Регистрация: 30.04.2011
Сообщений: 1,659
18.06.2011, 08:46 #5
1. Умножение можно делать многократным сложением - в цикле
2. Деление можно делать многократным вычитанием - в цикле

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

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

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


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

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

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

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

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

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

так ведь младшая часть у нас unsigned long. а ей что 0, что 0000000. Всё едино.
Простой вывод числа - можно организовать, а вот после вычитания как быть. Сносить разряды из старшей части что ли? Так нам нули надо сохранить... или наоборот в старшую часть нули перекидывать?
0
silent_1991
Эксперт С++
4987 / 3044 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
21.06.2011, 15:30 #13
Yellow2815, если хоть что-то есть в старшей части, а младшая равна нулю, то в ней на самом деле лежит 20 нулей. Просто запоминаем это и действуем по обстоятельствам.
0
Yellow2815
0 / 0 / 0
Регистрация: 03.06.2011
Сообщений: 12
21.06.2011, 17:55  [ТС] #14
silent_1991, )) Это хорошо, для вывода сгодится, а вот при таком числе
1000000000000001, делаем разбиение
старшая 1000000 и младшая 000000001.
Что в младшей?
В общем очень не просто. Длинная арифметика лучше реализуется с массивами.
0
grizlik78
Эксперт С++
1966 / 1459 / 120
Регистрация: 29.05.2011
Сообщений: 3,018
21.06.2011, 18:03 #15
Цитата Сообщение от Yellow2815 Посмотреть сообщение
Это хорошо, для вывода сгодится, а вот при таком числе
1000000000000001, делаем разбиение
старшая 1000000 и младшая 000000001.
Что в младшей?
Хочется кое что уточнить. Я вот всё не могу понять, что же за представление используется для хранения младшей части, если в примерах там 9 разрядов. Кстати, эти разряды двоичные? Если двоичные, то что это, отдельные биты в некоторой целочисленной переменной?
Ну а непосредственно по вопросу, в младшей части число 1. Но при вычитании двойки в младшей части должно оказаться максимально возможное значение этой младшей части. А старшая должна уменьшиться на 1, то есть да — произойдёт заём из старшей части. Для получения полного числа младшая и старшая части складываются (мысленно) с разными весами. Младшая с весом один, старшая с весом равным максимуму младшей плюс один.

Добавлено через 50 секунд
Если всё не так, то требуется нам подробно объяснить, что понимается под младшей и старшей частями.
0
21.06.2011, 18:03
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.06.2011, 18:03
Привет! Вот еще темы с ответами:

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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