Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 03.10.2010, 22:15
Новичок

Отправить личное сообщение для to_ashes Посмотреть профиль Найти все сообщения от to_ashes
 
Регистрация: 03.10.2010
Сообщений: 3

[C++] Длинная арифметика: деление
Пытаюсь реализовать арифметические операции для длинных чисел. Под тип числа завожу структуру:
#define ACC 30
struct LongNum{
// функция, выцепляющая i-ю цифру
char inline digit(int i) const {
return data[i+ACC];
}
// массив, в котором хранятся цифры
char data[2*ACC];
// знак: +1 или -1
signed char sign;
};

Мне нужно целочисленное деление (чтобы потом считать остатки), а есть только функция для деления чисел с плавающей запятой(алгоритм - вроде деление уголком). Можно ли ее как-то переделать, чтобы она просто делила нацело, и все. А то сейчас по результату деления остаток не восстановишь Вот сама функция:
void LNdivLN (struct LongNum &ln, struct LongNum divider)
{
struct LongNum res, zero;
res.flush(); zero.flush();//обнуляем
int res_sign = ln.sign * divider.sign;
ln.sign = divider.sign = 1;
int p_ln, p_divider;
// если кто-то нуль, то нечего считать
if(LNcmp(ln, zero) == 0) return;

// найдем порядки чисел
int i, j;
for(i=ACC-1;i>=-ACC;i--)
if(ln.digit(i) != 0){//i-я цифра
p_ln = i;
break;
}
for(i=ACC-1;i>=-ACC;i--)
if(divider.digit(i) != 0){
p_divider = i;
break;
}
// вычислим как надо сдвинуть делитель, чтобы его порядок
// совпал с делимым
i = p_ln-p_divider;
if(i>ACC) i = ACC-1-p_divider;
// сдвигаем...
LNshlLN(divider, i);// сдвигает divider на i десятичных разрядов влево(или вправо, если i<0)
struct LongNum tempnum;
// по разрядам вычисляем частное
for(;i>-ACC;i--){
tempnum.flush();//обнуляем tempnum
// подбираем такое j и tempnum == j*divider,
// где divider уже сдвинут на i разрядов
// чтобы j*divider <= ln и (j+1)*divider > ln
// в таком случае j - это цифра i-го разряда частного
j=0;
do{
LNaddLN(tempnum, divider);//сложение: tempnum+divider, результат сохр. в tempnum
j++;
}while(LNabscmp(tempnum, ln) <= 0);//сравнение по модулю
LNsubLN(tempnum, divider);//tempnum - divider, результат сохр. в divider
j--;
// ок, подобрали j, теперь вычитаем из ln tempnum
// (как при делении столбиком)
LNsubLN(ln, tempnum);
res.data[i+ACC]=j;

// сдвигаем вправо на один разряд для вычисления следущей цифры
LNshlLN(divider, -1);
}
res.sign = res_sign;
ln = res;
}
Т. о. она считает: 189/10 = 18,9
А надо чтоб просто 189/10 = 18.
Подскажите пожалуйста, как эту функцию переделать можно, а то я совсем с кодом запутался...
  #2  
Старый 04.10.2010, 13:52
Новичок

Отправить личное сообщение для to_ashes Посмотреть профиль Найти все сообщения от to_ashes
 
Регистрация: 03.10.2010
Сообщений: 3

Все, разобрался =)
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Длинная арифметика гость Математические алгоритмы (другое) 11 23.10.2010 00:06
Арифметика №10 не могу понять гость Задачи 1 02.11.2009 00:28
Длинная арифметика в комбинаторике Pahan Математические алгоритмы (другое) 3 12.01.2009 20:30
деление длинного числа rash Реализация, исходники, языки 4 10.01.2009 18:52
Длинная сума гость Задачи 14 10.07.2008 15:20