在.NET中使用令人难以置信的大数字
-
07-07-2019 - |
题
我正在尝试解决 projecteuler.net 上的问题,但我遇到了一些问题。
第一个是在List<t>
中存储大量元素的问题。在列表中存储大量数据时,我一直收到OutOfMemoryException。
现在我承认我可能没有以最好的方式做这些事情但是,有没有办法定义应用程序可以消耗多少内存?
当我满足100,000,000个元素时,它通常会崩溃:S
其次,一些问题需要增加大量数字。我使用ulong数据类型,我认为这个数字会变得非常大,但我仍然设法绕过最大的受支持的int并进入负数。
你有任何关于使用难以置信的大数字的提示吗?
解决方案
其他提示
您需要使用大量使用一些基本数学原理的类来拆分这些操作。 CodePoject上的 C#BigInteger库的实现似乎是最有希望的。本文对大量数字的操作也有一些很好的解释。
另见: C#中的大整数
就Euler项目而言,如果你遇到OutOfMemory异常,你可能会咆哮错误的树。来自他们的网站:
每个问题都是根据<!>“一分钟规则<!>”设计的,这意味着虽然设计一个成功的算法可能需要几个小时才能解决更多难题,但是有效的实施方案将允许在不到一分钟的时间内在中等功率的计算机上获得的解决方案。
正如用户Jakers所说,如果你使用大数字,可能你做错了。
在我完成的ProjectEuler问题中,到目前为止还没有人需要大数学数学。 它更多的是找到适当的算法来避免大数字。
想要提示吗?发布在这里,我们可能会有一个有趣的Euler线程开始。
我认为这是C#? F#内置了处理这两个问题的方法(BigInt类型和延迟序列)。
如果您愿意,可以使用C#中的两种F#技术。如果添加对核心F#程序集的引用,则BigInt类型可以从其他语言中合理使用。
懒惰序列基本上只是语法友好的枚举器。将100,000,000个元素放入列表中并不是一个好计划,因此您应该重新考虑解决方案以解决这个问题。如果您不需要保留信息,请将其扔掉!如果重新计算它比存储它便宜,扔掉它!
请参阅此螺纹。您可能需要使用可用的第三方大整数库/类之一,或者等待包含本机BigInteger数据类型的C#4.0。
至于定义应用程序将使用多少内存,您可以在执行操作之前使用 MemoryFailPoint 类。
这允许您在执行操作之前预先分配内存,因此您可以在运行之前检查操作是否会失败。
您不需要使用BigInteger您可以使用字符串数组来执行此事件。
class Solution
{
static void Main(String[] args)
{
int n = 5;
string[] unsorted = new string[6] { "3141592653589793238","1", "3", "5737362592653589793238", "3", "5" };
string[] result = SortStrings(n, unsorted);
foreach (string s in result)
Console.WriteLine(s);
Console.ReadLine();
}
static string[] SortStrings(int size, string[] arr)
{
Array.Sort(arr, (left, right) =>
{
if (left.Length != right.Length)
return left.Length - right.Length;
return left.CompareTo(right);
});
return arr;
}
}
string Add(string s1, string s2)
{
bool carry = false;
string result = string.Empty;
if (s1.Length < s2.Length)
s1 = s1.PadLeft(s2.Length, '0');
if(s2.Length < s1.Length)
s2 = s2.PadLeft(s1.Length, '0');
for(int i = s1.Length-1; i >= 0; i--)
{
var augend = Convert.ToInt64(s1.Substring(i,1));
var addend = Convert.ToInt64(s2.Substring(i,1));
var sum = augend + addend;
sum += (carry ? 1 : 0);
carry = false;
if(sum > 9)
{
carry = true;
sum -= 10;
}
result = sum.ToString() + result;
}
if(carry)
{
result = "1" + result;
}
return result;
}
我不确定它是否是处理它的好方法,但我在我的项目中使用以下内容。
我有一个<!> quot; double theRelevantNumber <!> quot;变量和<!> quot; int PowerOfTen <!> quot;对于每个项目,在我的相关课程中,我有一个<!> quot; int relatedDecimals <!> quot;变量。
所以...当遇到大数字时,它们会像这样处理:
首先它们被改为x,yyy形式。因此,如果输入了数字123456,789并且<!> quot; powerOfTen <!>是10,它会这样开始:
theRelevantNumber = 123456,789 PowerOfTen = 10 那时的数字是:123456,789 * 10 ^ 10
然后改为: 1,23456789 * 10 ^ 15
然后将相关小数的数量(例如5)四舍五入到1,23456,然后与<!>一起保存“; PowerOfTen = 15 <!>”
在一起添加或减少数字时,将忽略相关小数之外的任何数字。这意味着:
1 * 10 ^ 15 + 1 * 10 ^ 10如果<!>“relatedDecimals <!>”,它将变为1,00001;是5,但如果<!> quot; relatedDecimals <!>,则不会改变;是4。
这种方法使你能够毫无问题地处理doubleLimit * 10 ^ intLimit上的数字,至少对于OOP来说,跟踪它并不困难。