我正在解决一个简单的组合问题,其解决方案是 2^(n-1)。
唯一的问题是 1 <= n <= 2^31 -1(有符号 32 位整数的最大值)
我尝试使用 Java 的 BigInteger 类,但它对于 2^31/10^4 及更大的数字会超时,所以这显然行不通。
此外,我仅限于使用 Java 或 C++ 的内置类。
知道我需要速度,我选择用 C++ 构建一个对字符串进行算术运算的类。
现在,当我进行乘法运算时,我的程序的乘法类似于我们在纸上进行乘法以提高效率(而不是重复添加字符串)。
但即使这样,我也不能将 2 自身乘以 2^31 - 1 次,它只是不够有效。
因此,我开始阅读有关该问题的文本,并得出了...的解决方案
2^n = 2^(n/2) * 2^(n/2) * 2^(n%2)
(其中 / 表示整数除法,% 表示模数)
这意味着我可以求解对数乘法的幂运算。但对我来说,我无法绕过如何将此方法应用于我的代码?如何选择下限以及跟踪最终乘法所需的各种数字的最有效方法是什么?
如果有人对如何解决此问题有任何了解,请详细说明(示例代码表示赞赏)。
更新
感谢大家的帮助!显然,这个问题应该以一种现实的方式来解决,但我确实设法java.math.BigInteger
用只执行 ceil(log2(n)) 迭代的幂函数来超越。
如果有人对我生成的代码感兴趣,这里是......
using namespace std;
bool m_greater_or_equal (string & a, string & b){ //is a greater than or equal to b?
if (a.length()!=b.length()){
return a.length()>b.length();
}
for (int i = 0;i<a.length();i++){
if (a[i]!=b[i]){
return a[i]>b[i];
}
}
return true;
}
string add (string& a, string& b){
if (!m_greater_or_equal(a,b)) return add(b,a);
string x = string(a.rbegin(),a.rend());
string y = string(b.rbegin(),b.rend());
string result = "";
for (int i = 0;i<x.length()-y.length()+1;i++){
y.push_back('0');
}
int carry = 0;
for (int i =0;i<x.length();i++){
char c = x[i]+y[i]+carry-'0'-'0';
carry = c/10;
c%=10;
result.push_back(c+'0');
}
if (carry==1) result.push_back('1');
return string(result.rbegin(),result.rend());
}
string multiply (string&a, string&b){
string row = b, tmp;
string result = "0";
for (int i = a.length()-1;i>=0;i--){
for (int j= 0;j<(a[i]-'0');j++){
tmp = add(result,row);
result = tmp;
}
row.push_back('0');
}
return result;
}
int counter = 0;
string m_pow (string&a, int exp){
counter++;
if(exp==1){
return a;
}
if (exp==0){
return "1";
}
string p = m_pow(a,exp/2);
string res;
if (exp%2==0){
res = "1"; //a^exp%2 is a^0 = 1
} else {
res = a; //a^exp%2 is a^1 = a
}
string x = multiply(p,p);
return multiply(x,res);
//return multiply(multiply(p,p),res); Doesn't work because multiply(p,p) is not const
}
int main(){
string x ="2";
cout<<m_pow(x,5000)<<endl<<endl;
cout<<counter<<endl;
return 0;
}