algorithm - 大きな数の階乗の和

Question

N! の桁数の合計を計算したい。

Nの非常に大きな値、たとえばN（1500）に対してこれを行いたいと思います。.NET 4.0 を使用していません。これを解決するために BigInteger クラスを使用することはできません。

これは、他のアルゴリズムまたは手順で解決できますか? 助けてください。

私はこのようなことをしたい任意に大きな数の階乗を計算し、C#ですべての桁を表示します。しかし、私は解決することができません。

Answer 1

私の知る限り、数字の合計を計算できる特別な魔法はありません。

いずれにせよ、独自の BigInteger クラスを作成するのはそれほど難しいことではありません。3 年生の長い乗算アルゴリズムを実装するだけで済みます。

Answer 2

BigInteger目標が N! の桁数の合計を計算することであり、N が合理的に制限されている場合、型なしで次のことができます。

• 階乗値のリストをオンラインで検索します (テーブル ルックアップはゼロから計算するよりもはるかに効率的であり、必要ありませんBigInteger) 。
• 文字列データ型として保存
• 文字列内の各文字を整数として解析します
• 結果の整数を追加します

Answer 3

どのような実装を選択しても使用できる 2 つのパフォーマンス ショートカットがあります。

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 4

これは、コメントの 1 つで参照している C++ コードの移植です。C++ から C# に移植する際に理解しておくべきことの 1 つは、ブール比較で使用した場合、ゼロの整数は false と評価され、ゼロ以外の整数は true と評価されるということです。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ArbitraryFactorial
{
    class Program
    {
        const int max = 5000;

        static void display(int[] arr)
        {
            int ctr = 0;
            for (int i = 0; i < max; i++)
            {
                if (ctr == 0 && arr[i] != 0) ctr = 1;
                if (ctr != 0)
                    Console.Write(arr[i]);

            }
        }

        static void factorial(int[] arr, int n)
        {
            if (n == 0) return;
            int carry = 0;
            for (int i = max - 1; i >= 0; --i)
            {
                arr[i] = (arr[i] * n) + carry;
                carry = arr[i] / 10;
                arr[i] %= 10;
            }
            factorial(arr, n - 1);
        }

        static void Main(string[] args)
        {
            int[] arr = new int[max];
            arr[max - 1] = 1;
            int num;
            Console.Write("Enter the number: ");
            num = int.Parse(Console.ReadLine());
            Console.Write("Factorial of " + num + " is: ");
            factorial(arr, num);
            display(arr);
        }
    }
}

Answer 5

ソースコードは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 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ように呼び出します。

入力

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

出力

16749

Answer 7

これらの数値は、型がないとまったく使用できませんBigInteger。^{2 64}
より大きい数値を に絞り込むアルゴリズムや手順はありません。long

.Net 3.5 の BigInteger 実装を見つける必要があります。