我正在尝试解决编程竞赛的初步问题以及我必须计算的两个问题,并打印一些非常大的整数(如100!,2 ^ 100)。
我还需要一种快速的方法来计算这个大整数的幂。
你可以为我建议一些算法或数据结构吗?(顺便说一下,我读过C接口和实现的’任意精度算术’部分,但它对pow()没有帮助)
编辑:我认为通过平方法和位移的取幂对功率起作用,但我还需要一种快速的方法来计算这个因子的阶乘。 谢谢。
EDIT2:对于那些感兴趣的人;
找到包含长度为N的所有位串的最短位串长度(对不起我的英文,我会给出一个例子)。 N <= 10000
例如,包括长度为2(00,01,10,11)的所有位串的最短位串长度是5(11001)。
我对这个问题的解决方案是2 ^ n + n – 1.(所以我应该计算2的幂,我想我会使用位移)
其他问题是,给定2个长度,找到你可以通过多少种方式达到长度N.例如,输入是10,2,3。那么你应该用2和3达到10(例如,2 + 3) 2 + 2 + 2 + 2,2 + 2 + 3 + 3,3 + 2 + 2 + 3,3 + 3 + 2 + 2 ……)。 1 <= N <2 ^ 63。 我们将在mod 1000000007中计算anwser。
我的解决方案是,2x + 3y = N,所以x =(N – 3y)/ 2。 对于从0到2 * N / 3的y,如果x是整数,那么我应该计算此X和Y的广义置换,总计+ =(x + y)! /(x!* y!)。
对于具有整数的幂,通过平方取幂
为了计算功率,使用使用指数的二进制表示的二分法算法并减少所得的乘法数。 数据结构只是一个整数数组
您可能希望了解加密程序的实现(尤其是首先出现在我脑海中的GnuPG)。 原因是加密函数也使用非常大的整数(所谓的MultiPrecision Integers – MPI)。 这些MPI以这样的方式存储,即前2个字节表示整数的大小和后面的字节如何存储该值。
GPG是开源的,只是看看吧:)
使用GMP来处理这些问题。 它内置了阶乘支持和大功率等。它还具有C和C ++接口。 你需要mpz_t
作为一个包含非常大的整数的类型。
对于C这样的东西可以工作,或使用int或char数组滚动自己,数组中的一个点代表一个数字。 [1 | 0 | 1]
[1 | 0 | 1]
或['1'|'0'|'1']
表示101等
您可以按以下格式存储号码:数字位数和此数字的位数。 这是在编程竞赛中处理大数字的常用方法。
这是一个类,而不是提供数字和乘法的存储。 可以添加数字的输入和输出,这是微不足道的。
class huge { public: int size; int data[1000]; friend void mul(const huge &a, int k, huge &c) { c.size = a.size; int r = 0; for (int i = 0; i < a.size; i++) { r += a.data[i] * k; c.data[i] = r % 10; r = r / 10; } if (r > 0) { c.size++; c.data[c.size - 1] = r; } while (c.size > 1 && c.data[c.size - 1] == 0) c.size--; } friend void mul(const huge &a, const huge &b, huge &c) { c.size = a.size + b.size; memset(c.data, 0, c.size * sizeof(c.data[0])); for (int i = 0; i < a.size; i++) { int r = 0; for (int j = 0; j < b.size; j++) { r += a.data[i] * b.data[j] + c.data[i + j]; c.data[i + j] = r % 10; r /= 10; } if (r > 0) c.data[i + b.size] = r; } while (c.size > 1 && c.data[c.size - 1] == 0) c.size--; } };
基础数学可以将任意双倍乘法加倍…
需要了解更多c/c++开发分享如何处理不适合任何语言数据结构的大整数,也可以关注C/ C++技术分享栏目—计算机技术网(www.ctvol.com)!
def biginteger(num1, num2): result = [] lnum1 = len(num1) lnum2 = len(num2) k = x = remainder = 0 while len(result) < lnum1: result.append(0) for i in range(lnum1, 0, -1): multiplier = int(num1[i - 1]) for j in range(lnum2, 0, -1): temp = (int(num2[j - 1]) * multiplier) + remainder + int(result[k]) result[k] = str(temp % 10) remainder = temp / 10 k += 1 result.append(str(remainder)) if remainder != 0: remainder = 0 x += 1 k = x return ''.join([result[i - 1] for i in range(len(result), 0, -1)]) num1 = '37234234234234' num2 = '43234234234232' print biginteger(num1, num2)
以上就是c/c++开发分享如何处理不适合任何语言数据结构的大整数相关内容,想了解更多C/C++开发(异常处理)及C/C++游戏开发关注计算机技术网(www.ctvol.com)!)。
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/979086.html