处理长号以构建巨大的数组 [英] handle long number to build a huge array

问题描述

你好，
在我的项目中，我尝试获取2个数字之间的所有组合，例如，如果我有2个数组，则第一个存储最小界限，第二个存储最大界限，所以arr1 [3] = {1,1,2}和arr2 = {2,2,3}，所以我应该建立一个二维数组，存储所有组合，
112、212、122、222、113，...，223.
首先，我计算2d数组的行数，由于min和max的元素数在10到20之间变化，所以有时我会产生大量需要构建一个巨大数组的数，我的代码是:

Hello,
In my project I am trying to get all combination between 2 numbers, for example if I have 2 array the first one store the min bound and the second one store the max bound,so arr1[3] = {1,1,2} and the arr2 = {2,2,3} so I should build a 2d array store all combination which are
112, 212, 122, 222, 113, ..., 223.
first I calculate the number of row of the 2d array and since the number of element of min and max are vary between 10 and 20, it sometime give me a large number which need to build a huge array, my code is:

unsigned long long row =0;  // to count the number of row
unsigned long long rh1 = 1;

for(int i=0; i<col;++i)    {
rh1 *= t_end[i] - t_s[i] + 1;// t_end is max bound array, t_s is the min bound arr
row += rh1;

 cout << "Row= "<< row <<endl;
  }

所以一段时间(行)变得如此之大而无法处理该值，例如，如果我具有以下最小和最大界限:
t_s = {3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2}
t_end = {2 2 3 4 6 10 3 11 11 13 4 15 8 9 19 19 20 23 27 10}

那么该行将如下所示:

so some time the number (row) become so large and can''t handle this value, for example if I have the following min and max bound:
t_s = {3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 }
t_end = {2 2 3 4 6 10 3 11 11 13 4 15 8 9 19 19 20 23 27 10 }

then the row will be as follow:

Row= 4
  Row= 32
  Row= 144
  Row= 1152
  Row= 11232
  Row= 112032
  Row= 1120032
  Row= 14224032
  Row= 92848032
  Row= 1193584032
  Row= 16603888032
  Row= 309399664032
  Row= 2944561648032
  Row= 53012639344032
  Row= 1104442270960032
  Row= 24235894166512032
  Row= 278681865017584032
  Row= 6894277107145456032
  Row= 12879056739084163488
  Row= 5417061573465168288     --- this value is smaller than previous and this is wrong

有时行"值变为负值，所以如何解决此问题，当然我不能用如此大量的行构建数组，我想将其除以，但我无法获得行数可以让我计算出我应该拥有的子数组的数量.
另一个问题是，我可以拥有的最大数组大小是多少，以及如何知道.

and sometime the Row value become negative, so how to solve this issue, and for of course I cant build an array with this huge number of row, and I was thinking to divide it, but I can''t get the number of row that allow me to calculate the number of sub-array I should have.
Other question, what is the max size of array that I could have and how to know that.

推荐答案

12879056739084163488是一个很大的数字，您的下一个迭代包含无符号long long的大小限制，导致数字较小.

[更新]
您可以尝试 Matt McCutchens的C ++大整数库 [ ^ ]

最好的问候
Espen Harlinn

12879056739084163488 is a very big number, your next iteration wraps around the size limit of an unsigned long long, causing the smaller number.

[Update]
You can try Matt McCutchens'' C++ Big Integer Library[^]

Best regards
Espen Harlinn

使用任意精度数学 [ ^ ]类，例如 ^ ].

Use an arbitrary-precision math[^] class, for example GMP[^].

我认为您的算法存在本质上的错误，具体取决于您的实际问题是:您正在谈论值的数组，或者您谈论的是数字位数.导致问题的示例表明您实际上根本不是在谈论数字(可能很长)，因为某些最大值根本不是数字！

那么，为什么要将这些数字数组转换为一个大整数?只需坚持使用数字数组，就像定义最小和最大数组一样！问题解决了.

PS:我什至注意到您甚至说您都需要定义一个 2D 数组来存储所有中间组合，所以您的要求毕竟是，以产生数字数组的列表，而不是非常长的数字的列表！

I think there''s something intrinsically wrong in your algorithm, depending on what your actual problem is: either you are talking about arrays of values, or you''re talking about digits of numbers. The example that causes your problem indicates that you are not, actually talking about digits of (potentially very long) numbers at all, since some of the max values are not digits at all!

So why are you converting these arrays of numbers into a big integer number? Just stick with arrays of numbers, just like you defined your min and max array! Problem solved.

P.S.: I just noticed you even said that you need to define a 2D array to store all intermediate combinations, so your requirement is, after all, to produce a list of arrays of numbers, not a list of very long numbers!

这篇关于处理长号以构建巨大的数组的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！