取幂的前n位数
如何确定取幂的前n位数(a b )。
eg: for a = 12, b = 13 & n = 4, the first 4 digits are 1069.
通过以下迭代计算b :
a 1 = a 1 ,
a 2 = a 2 ,
…
a i = a i ,
…
a b = a b
你有一个i + 1 = a i ×a 。 不完全地对每个人进行计算 。 问题是a的相对误差小于a的相对误差的n倍。
您希望最终相对误差小于10 -n 。 因此,每个步骤的相对误差可能是 。 删除每一步的最后一位数字。
例如, a = 2 , b = 16 , n = 1 。 最终相对误差为10 -n = 0.1 。 每个步骤的相对误差为0.1 / 16> 0.001 。 因此,每个步骤的3个数字很重要。 如果n = 2,则必须保存4位数。 通用规则:每步保存[ n + log 10 b ]个数字。
2(1),4(2),8(3),16(4),32(5),64(6),128(7),256(8),512(9),1024(10)→ 102,
204(11),408(12),816(13),1632(14)→163,326(15),652(16)。
答案:6。
该算法具有O(b)的复杂性。 但很容易将其更改为O(log b)
另一种解决方案,使用log10:
#include #include #include int main(int argc, char **argv) { int a = 12; int b = 13; int n = 4; double x, y; x = b * log10(a); y = floor(pow(10, x - floor(x) + n - 1)); printf("Result: %d\n", (int)y); return EXIT_SUCCESS; }
n = 9 k = 3 n ^ n = 387420489,答案应为387
这是同样的事情,@ RC在他的代码中做了什么。 谢谢@RC我只是展示了代码的数学表示。
以编程方式执行此操作的最简单方法是使用字符串流将指数的结果转换为字符串,然后使用n个最重要(即左)字符。
如果你想要一种没有字符串的方法,那么这将有效:
#include #include #include using namespace std; double nDigExp( double a, double b, int n ) { stringstream ss; ss.setf( ios::fixed, ios::floatfield ); ss << pow(a,b); double ret; for ( int i = 0; i < n; ++i) ret = (10 * ret) + (ss.get() - '0'); // Yeuch!! return ret; } int main( ) { double result = nDigExp( 12, 13, 4 ); cout << result << endl; return 0; }
但它不是最优雅的代码。 我相信你可以改进它。
对于这种情况 – 使用魔法数字12,13,4:
#include #include #include double a = 12; int b = 13; double result = std::pow(a,b); std::stringstream strVal; strVal.setf( ios::fixed, ios::floatfield ); strVal << result; std::string output(strVal.str().substr(0,4));
输出=“1069”
std::stringstream intStr(output); int intVal; intStr >> intVal;
intVal = 1069
编辑:这应该适用于结果不会溢出double
任何组合。