VPF::Bash.org.ru ест мозг ! - Форум программистов

Nikita27

Дата 13.6.2009, 16:29 (ссылка)

(голосов:1)

Загрузка ...

C++ programmer

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

Цитата

"xxx: 3.49(очень много цифр)*10^5768 - кстати вот он, факториал числа 2010... Просто стало любопытно очень, как бы такое посчитать и сколько нулей там будет. Есесно "в лоб" такое не посчитаешь, тем более с такой огромной точностью (аж 1024 бита! Это очень много), тем более типов данных с такой точностью нет и даже массивы не совсем помогут, ибо тогда ещё и много времени уйдёт на "распиховку" по массиву. В сети способов посчитать сие не нашёл, везде уже на числах порядка 200 комп грузицо на минуты две, а в ответе низкая точность (как правило, около 32 бит). Поэтому пришлось извращаться - расчёт вёлся небольшими интервалами и разбиением всей процедуры на почти одинаковые участки, в случае небольших разниц (из разряда как быстро посчитать 3050, 3100, 3000, 3150 умноженное на 25, не умножая каждое число) они учитывались, а также выносились возможные сомнжители. Суммарное время вычисления - около 2 секунд.
yyy: Вася, покидай свой мехмат, ты долбанулся ещё сильнее!!!

Вот такую цитату я нашел на башорге... И написал программу, которая считает этот факториал с использованием массивов:

Код


#include <iostream>

using namespace std;

int main() {
    int n, carry = 0, tmp = 0, F[10000], last = 0;
    memset(F, 0, sizeof(F));
    cin >> n;
    F[ last++ ] = n;
    for(int i = 1; i < n; i++) {
        carry = 0;
        for(int j = 0; j <= last; j++) {
            tmp = F[j] * i;
            F[j] = tmp % 10000 + carry;
            if(F[j] >= 10000) {
                carry = tmp / 10000 + F[j] / 10000;
                F[j] %= 10000;
            }
            else {
                carry = tmp / 10000;
            }
        }
        if(carry > 0) {
            F[ ++last ] = carry;
            carry = 0;
        }
    }
    cout << F[last];
    for(int i = last - 1; i >= 0; i--) {
        (F[i]<10) ? cout << "000"    << F[i] :
        (F[i]<100) ? cout << "00"    << F[i] :
        (F[i]<1000)?cout << "0"    << F[i] : cout << F[i];
    }
    return 0;
}

Написание этой программы заняло 20 минут... Время, за которое считает эта программка факториал 2010 можете посчитать сами )))

GrayCardinal

Дата 14.6.2009, 19:17 (ссылка)

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

Загрузка ...

Фигасе

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

Цитата

Вася, покидай свой мехмат, ты долбанулся ещё сильнее!!!

--------------------

Go go go !

th1nker

Дата 15.6.2009, 15:56 (ссылка)

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

Загрузка ...

Покоряю вселенную...

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

Клево считает, молодец!

Borland_Delphi_6

Дата 17.6.2009, 16:05 (ссылка)

(голосов:1)

Загрузка ...

LoneLINEss

Профиль
Группа: Участник Клуба
Сообщений: 2509
Регистрация: 5.11.2002
Где: in fortune dreams ...

Вычисление в Wolfram Mathematica - менее секунды. Постановка задачи в той же среде - около 1.5 секунд на набор строки

Код


2010!

Это сообщение отредактировал(а) Borland_Delphi_6 - 17.6.2009, 16:06

--------------------

Blind Guardian Fan :: BMSTU Student :: A polar bear is a rectangular bear after a coordinate transform.

Мои фотографии

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