VPF::Не работает длинная арифметика

Innk

Дата 20.2.2011, 11:08 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 7.8.2010

Репутация: нет
Всего: нет

http://acm.mipt.ru/judge/problems.pl?probl...7b6b2aef495be49
Числа Фибоначчи для 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 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

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

Цитата(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 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 7.8.2010

Репутация: нет
Всего: нет

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 )

Это сообщение отредактировал(а) Innk - 20.2.2011, 15:02

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »