Сумма факториалов для больших чисел

Question

Я хочу вычислить сумму цифр N!.

Я хочу сделать это для действительно больших значений N, скажем, N (1500). Я не использую .NET 4.0. Я не могу использовать класс BigInteger для решения этой проблемы.

Может ли это быть решено каким-либо другим алгоритмом или процедурой? Пожалуйста, помогите.

Я хочу сделать что-то вроде этого Рассчитать факториал произвольно большого числа, показывая все цифры , но в C #. Однако я не могу решить.

Answer 1

Существует два ярлыка производительности, которые вы можете использовать для любой выбранной вами реализации.

1. Отрезать любые нули от чисел.
2. Если число делится на 5 ^n, разделите его на 10 ^ n.

таким образом,

16*15*14*13*12*11*10*9*8*7*6*5*4*3*2 = 20,922,789,888,000
//-->
16*1.5*14*13*12*11*1*9*8*7*6*0.5*4*3*2 = 20,922,789,888 //Sum of 63

---

Кроме того, кажется, что должен быть какой-то алгоритм, не возвращаясь к вычислению всего этогоиз.Переходя к 18 !, суммы цифр:

2,6,6,3,9,9,9,27,27,36,27,27,45,45,63,63,63
//the sums of the resulting digits are:
2,6,6,3,9,9,9,9,9,9,9,9,9,9,9,9,9

и, в частности, сумма цифр 1500!равно 16749 (сумма цифр 27)

Answer 2

Если ваша цель - вычислить сумму цифр N !, и если N разумно ограничено, вы можете сделать следующее без BigInteger типа:

• Найти список факторных значений в Интернете (поиск в таблице будет гораздо более эффективным, чем вычисление с нуля, и не требует BigInteger)
• Сохранить как строковый тип данных
• Разбор каждого символа в строке как целого числа
• Добавить получившиеся целые числа

Answer 3

Насколько мне известно, не существует особой магии, которая позволяла бы вам вычислять сумму цифр.

В любом случае создать собственный класс BigInteger не так сложно - вам нужно толькореализовать алгоритм длинного умножения с 3-го класса.

Answer 4

Вы можете найти исходный код по адресу: http://codingloverlavi.blogspot.in/2013/03/here-is-one-more-interesting-program.html

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include<time.h>
#define max 5000
void multiply(long int *,long int);
void factorial(long int *,long int);


int main()
{
clrscr();
cout<<"PROGRAM TO CALCULATE FACTORIAL OF A NUMBER";
cout<<"\nENTER THE NUMBER\n";
long int num;
cin>>num;

long int a[max];
for(long int i=0;i<max;i++)
    a[i]=0;

factorial(a,num);

clrscr();

//PRINTING THE FINAL ARRAY...:):):)
cout<<"THE FACTORIAL OF "<<num<<" is "<<endl<<endl;
long int flag=0;

int ans=0;
for(i=0;i<max;i++)
{
    if(flag||a[i]!=0)
    {
        flag=1;
        cout<<a[i];
        ans=ans+a[i];
    }
}

cout<<endl<<endl<<"the sum of all digits is: "<<ans;


getch();
return 1;
}

void factorial(long int *a,long int n)
{
long int lavish;
long int num=n;
lavish=n;
for(long int i=max-1;i>=0&&n;i--)
{
    a[i]=n%10;
    n=n/10;
}

for(i=2;i<(lavish);i++)
{
    multiply(a,num-1);
    num=num-1;

}
}


void multiply(long int *a,long int n)
{

for(long int i=0;i<max;i++)
    a[i]=a[i]*n;

for(i=max-1;i>0;i--)
{
    a[i-1]=a[i-1]+(a[i]/10);
    a[i]=a[i]%10;
}
}

Answer 5

Вот порт кода C ++ , на который вы ссылаетесь в одном из ваших комментариев.При переносе из C ++ в C # важно понимать, что целые числа, равные нулю, оцениваются как ложные, а целые числа, отличные от нуля, равны истине при использовании в логическом сравнении.

Answer 6

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

Как запоздалая мысль, я думаю, что было бы разумнее представлять большие числа с List<int>() вместо string. Но я оставлю это как упражнение читателю.

Пример кода

static string Mult(string a, string b)
    {
        int shift = 0;
        List<int> result = new List<int>();
        foreach (int aDigit in a.Reverse().Select(c => int.Parse(c.ToString())))
        {
            List<int> subresult = new List<int>();
            int store = 0;
            foreach (int bDigit in b.Reverse().Select(c => int.Parse(c.ToString())))
            {
                int next = aDigit*bDigit + store;
                subresult.Add(next%10);
                store = next/10;
            }

            if (store != 0) subresult.Add(store);

            subresult.Reverse();
            for (int i = 0; i < shift; ++i) subresult.Add(0);
            subresult.Reverse();

            int newResult = new List<int>();
            store = 0;
            for (int i = 0; i < subresult.Count; ++i)
                {
                    if (result.Count >= i + 1)
                    {
                        int next = subresult[i] + result[i] + store;
                        if (next >= 10)
                            newResult.Add(next % 10);
                        else newResult.Add(next);
                        store = next / 10;
                    }
                    else
                    {
                        int next = subresult[i] + store;
                        newResult.Add(next % 10);
                        store = next / 10;
                    }
                }

            if (store != 0) newResult.Add(store);

            result = newResult;
            ++shift;
        }

        result.Reverse();
        return string.Join("", result);
    }

    static int FactorialSum(int n)
    {
        string result = "1";
        for (int i = 2; i <= n; i++)
            result = Mult(i.ToString(), result);
        return result.Sum(r => int.Parse(r.ToString()));
    }

Тестирование кода

Предполагая, что приведенный выше фрагмент кода находится в том же классе, что и ваш метод Main, вызовите его таким образом.

Input

    static void Main(string[] args)
    {
        Console.WriteLine(FactorialSum(1500));
    }

выход

16749

Answer 7

Вы не можете использовать эти числа вообще без BigInteger типа.
Ни один алгоритм или процедура не может сжать числа больше 2 ⁶⁴ в long.

Вам нужно найти реализацию BigInteger для .Net 3.5.