Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Не работает длинная арифметика

Автор: Innk 20.2.2011, 11:08

http://acm.mipt.ru/judge/problems.pl?problem=009&CGISESSID=748eab5fe68e7817b7b6b2aef495be49
Числа Фибоначчи для n < 1000.

Выдаёт ошибку на 7 тесте, не понимаю почему - вроде всё правильно вычисляет

Код


#include <iostream>
unsigned long int m1[24],m2[24],m3[24];

int main()
{
    int n,j;

    scanf("%d",&n);
    for(j=1;j<24;j++)
    {
        m1[j]=0;
        m2[j]=0;
    }
    m1[0]=0;
    m2[0]=1;
    m3[0]=1;
    for(int i=0;i<n;i++)
    {
        for(j=0;j<24;j++)
            m3[j]=0;
        for(j=0;j<24;j++)
        {        
            m3[j]=m3[j]+(m1[j]+m2[j]) ;

            if(m3[j]>=1000000000)
            {
                m3[j]=m3[j]-1000000000;    
                m3[j+1]=1;
            }
        }
        for(j=0;j<24;j++)
        {
            m1[j]=m2[j];
            m2[j]=m3[j];
        }
    }

    j=23;
    while(m3[j]==0)j--;
    while(j>=0)
    {
        printf("%d",m3[j]);
        j--;
    }
    return 0;
}

Может вывод неправильный

Или как лучше сделать простую длинную арифметику ??

Автор: volatile 20.2.2011, 13:03

В ваш код особо не вникал. Но бросилось в глаза это:

Цитата(Innk @ 20.2.2011, 11:08

)

printf("%d",m3[j]);

Вывод съедает незначащие нули.

Напишите так

Код


        printf("%09d",m3[j]);

Добавлено через 8 минут и 10 секунд
и еще,

Цитата(Innk @ 20.2.2011, 11:08

)

m3[j+1]=1;

при переполнении будет писать за границу массива,

Автор: Innk 20.2.2011, 15:01

volatile, Спасибо !!!!

Точно, все после первого надо выводить с лидирующими нулями - об этом совсем неподумал

Код


    j=23;
    while(m3[j]==0)j--;

    printf("%d",m3[j]);//первый без лидирующих нулей
    j--;
    while(j>=0)
    {
        printf("%09d",m3[j]);//а все остальные выводим с лидирующими нулями!!!
        j--;
    }
    return 0;

При n<1000 моих массивов m[24] в которых числа с 9 знаками = 24*9=216 хватает
Так что переполнения не будет.

Всё прошла сразу за 0.01 )