Сумма факториалов для больших чисел
Я хочу вычислить сумму цифр N!.
Я хочу сделать это для действительно больших значений N, скажем, N(1500). Я не использую.NET 4.0. Я не могу использовать класс BigInteger для решения этой проблемы.
Может ли это быть решено каким-то другим алгоритмом или процедурой? Пожалуйста помоги.
Я хочу сделать что-то вроде этого Рассчитать факториал произвольно большого числа, показывая все цифры, кроме C#. Однако я не могу решить.
7 ответов
Есть два ярлыка производительности, которые вы можете использовать для любой выбранной вами реализации.
- Отрежьте любые нули от чисел.
- Если число делится поровну на 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)
Если ваша цель - вычислить сумму цифр N!, и если N разумно ограничен, вы можете сделать следующее без BigInteger тип:
- Найти список факторных значений в Интернете (поиск в таблице будет гораздо более эффективным, чем вычисление с нуля, и не требует
BigInteger) - Хранить как строковый тип данных
- Разобрать каждый символ в строке как целое число
- Добавьте полученные целые числа
Для меня нет особой магии, которая позволяла бы вам вычислять сумму цифр.
В любом случае не должно быть так сложно создать собственный класс BigInteger - вам нужно только реализовать алгоритм длинного умножения с 3-го класса.
Вы можете найти исходный код по адресу: 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;
}
}
Вот некоторый рабочий код. Некоторые компоненты могут быть улучшены для повышения эффективности. Идея состоит в том, чтобы использовать любой алгоритм умножения, который мне говорили в школе, и хранить длинные целые числа в виде строк.
Как запоздалая мысль, я думаю, что было бы разумнее представлять большие числа с 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
Вот порт кода C++, на который вы ссылаетесь в одном из ваших комментариев. При переносе из C++ в C# нужно понимать одну вещь: целые числа, равные нулю, оцениваются как ложные, а целые числа, отличные от нуля, равны истине при использовании в логическом сравнении.
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);
}
}
}
Вы не можете использовать эти цифры вообще без BigInteger тип.
Ни один алгоритм или процедура не может сжать числа больше чем 264 в long,
Вам нужно найти реализацию BigInteger для.Net 3.5.