Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Центр помощи > [C++] Умножение и деление больших чисел


Автор: pharrell 3.12.2006, 23:21
Всем доброго времени суток.Прошу помочь мне в умножении больших чисел,каждое из которых находится в массиве,каждый разряд в отдельном элементе.Со сложением и делением справился,а умножение и деление никак не получается.Пишу на Visual C++.Заранее спасибо

Автор: Alexeis 3.12.2006, 23:53
pharrell, советую воспользоваться поиском, тема с делением больших чисел уже рассматривалась недавно (не более месяца назад).

Автор: Dude03 4.12.2006, 00:08
Цитата(pharrell @  3.12.2006,  23:21 Найти цитируемый пост)
Всем доброго времени суток.Прошу помочь мне в умножении больших чисел,каждое из которых находится в массиве,каждый разряд в отдельном элементе.Со сложением и делением справился,а умножение и деление никак не получается.Пишу на Visual C++.Заранее спасибо 

 smile Парень, ты жжешь - деление сложнее чем умножение smile. Причем на порядок...
А вообще в чем проблема с умножение? В столбик, например, число можешь умножить? НУ так действуй аналогично. Кстати, если тебя это заинтересовало - попробуй написать функцию для выделения корня тз больших чисел(хотя бы методом дихотомии, когда посмотришь в словаре, что значит это слово - поймешь в чем заключается метод smile ).

Автор: pharrell 4.12.2006, 23:04
проблема собственно в том,что не получается промежуточные результаты умножения правильно сложить!Я имел ввиду,что со сложением и вычитанием,а деление и умножение не получается.Простите за опечатку.

Автор: Mercator 5.12.2006, 16:08
pharrell, что значит, не получается сложить? Если ты умножаешь по типу столбика, то я так себе представляю, что сначала множимое умножаешь на последнюю цифру множителя, получаешь некоторое длинное число (массив), потом умножаешь множимое на предпоследнюю цифру множителя, получаешь новое длинное (массив, последняя цифра которого 0, так как умножаем на десятки, про эти нули надо не забывать) и т.д. Ты либо для умножения на каждую цифру множителя сохраняешь свое длинное, либо как только получаешь 2, складываешь и с каждым разом его пополняешь. А складывать длинные ты уже умеешь.

Автор: pharrell 6.12.2006, 00:02
Вот сам накидал,знаю что не все правильно.Помогите разобраться с алгоритмом.Заранее большое спасибо!
Код

void write_res(int ar[], int size)
{
    int i;
    for(i = size; i >= 0; i--)
        printf("%d", ar[i]);    
}
//----------------------------------------------------------
int carry=0;
int res[result]  ={0};
for(j=b-1;j>=0;j--)
        {

                for(i=a-1;i>=0;i--)
                {
                    tmp=num_1[i]*num_2[j]+carry+res[i+j];
                    if(tmp<10)
                    {
                        res[i]=tmp;
                        carry=0;
                                                
                    }
                    else
                    {
                        res[i]=tmp%10;
                        carry=tmp/10;
                    }
            
                }h++;
            
        }
        write_res(res,h-1);
    }


M
alexeis1
Модератор: не забывайте выбирать подсветку.

Автор: pharrell 8.12.2006, 01:12
Всем Здравствуйте.Не хочется создавать новую тему,ведь опять о своем умножении и делении.Вот код-сложение и деление работает,а вот умножение плохо некоторые числа умножает,добавляя при этом лишние нули ,другие неправильно.Помогите пожалуйста добить умножение и начать наконец деление.Заранее всам БОЛЬШОЕ СПАСИБО.
Код

[color=blue][/color]
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<string.h>

#define maxlen 400
#define result 500

#define base 10


int read_num(int ar[])
{
    char  ch;
    int   i = 0;

    while((ch=getchar()) >= '0' && ch <= '9')
        ar[i++]=(ch - '0');        
    
    printf("%d\n", i);

    return i;
}

void write_num(int ar[], int size)
{
    int i;
    for(i = 0; i < size; i++)
        printf("%d", ar[i]);    
}


void write_res(int ar[], int size)
{
    int i;
    for(i = size; i >= 0; i--)
        printf("%d", ar[i]);    
}


void main(void)
{
    int a,b,h=0;
    int i=0,j=0,k=0;
    int num_1[maxlen]={0};
    int num_2[maxlen]={0};
    int res[result]  ={0};
    int flag;
    int tmp=0;
    char sig;

    int carry=0;
  int div[maxlen]={0};
    int l=0;

    
      a=read_num(num_1);
    write_num(num_1,a);
    printf("\n");
    b=read_num(num_2);
    write_num(num_2,b);
    
    
    //_______________________________________
    printf("\nEnter mathematical action:");
    scanf("%c",&sig);
    switch(sig)
    {

        //----------------------------------------------------
        case '+':

        flag=0;
        for(i=a-1,j=b-1;(i >= j ? i : j) >= 0 ;i--,j--)
        {
            tmp=num_1[i]+num_2[j]+flag;
            if(tmp<10)
            {
                res[k++]=tmp;
                flag=0;
            }
            else
            {
                res[k++]=tmp-10;
                flag=1;
                if((i >= j ? i : j) == 0)
                {
                    res[k]=flag;
                    h++;
                }
            }
            h++;            
        }
        printf("\n\n\nresultat:");
        write_res(res,h-1);
        break;
        //----------------------------------------------------
        case '-':

        flag=0;
        for(i=a-1,j=b-1;(i >= j ? i : j) >= 0 ;i--,j--)
        {
            tmp=num_1[i]-num_2[j]-flag;
            if(tmp>=0)
            {
                res[k++]=tmp;
                flag=0;
            }
            else
            {
                res[k++]=10+tmp;
                flag=1;
            }
            h++;            
        }
        write_res(res,h-1);
        break;
        //----------------------------------------------------
        case '*':
            for(j=b-1;j>=0;j--)
                {
                       for(i=a-1;i>=0;i--)
                            {
                                tmp=num_1[i]*num_2[j]+carry+div[i+j];                    
                                div[i+j]=tmp%base;
                                carry=tmp/base;
                                h++;
                            }
                            carry=0;
                }
             write_num(div,h-1);      
    }
printf("\n");
}
[/color]

Автор: Mercator 8.12.2006, 09:02
pharrell, а вы пробовали по шагам программку гнать? Очень помогает. Отловите то место, где получаются лишние нули и смотрите, откуда они получаются. И вообще-то в коде должны быть комментарии.

Автор: pharrell 19.12.2006, 01:18
здравствуйте еще раз.Наконец-то справился с умножением.Но вот что-то с делением как-то трудновато.У меня все теже два числа,представляющие собой массивы.Почитал книги и в интернете посмотрел темы посвященные этому вопросу,но все равно не пойму как делать.Если кто может помогите пожалуйста хотя бы начать.Деление только целых,беззнаковых чисел,остаток оставщийся от деления не учитывать.Заранее большое спасибо..

Автор: Pete 19.12.2006, 08:43
http://www.cs.sunysb.edu/~skiena/392/lectures/week5/

Добавлено @ 08:45 
http://www.cs.sunysb.edu/~skiena/392/programs/bignum.c, готовая программа.

Добавлено @ 08:47 
Если нужно пояснение на русском, могу скинуть книгу, из которой это взято.  smile 

Автор: pharrell 19.12.2006, 17:14
Да это было бы отлично.Спасибо большое!!! smile 

Автор: Pete 20.12.2006, 00:06
http://slil.ru/23605838

Автор: pharrell 29.12.2006, 14:40
Все ничего не получается.С этим делением я просто никак не могу разобраться.Кто может помогите доделать программу,а именно деление больших чисел.Очень прошу ,помогите пожалуйста,надо сдавать,а я никак не могу доделать.Всем Огромное спасибо за помощь заранее!!И с Наступающим новым годом!!!

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)