首页 > 代码库 > 每日一小练——数值自乘非递归解

每日一小练——数值自乘非递归解

上得厅堂,下得厨房,写得代码,翻得围墙,欢迎来到睿不可挡的每日一小练!


题目:数值自乘非递归解


内容:

连续求m^n问题(m与n是正整数)。前面的提示会得到一个递归程序,请编写一个运算效率同样高的非递归的程序。

 

我的解法:上来没多想,打开vs2013就敲了起来,问题果然很简单,分分钟就超神。。奥,不对就解决了!如果是非递归其实一种简单的方法就是把,

递归的几种分类做好if分支,用一个循环处理就好了,不过如果我们认真思考m^n这个式子,我们会发现n如果用二进制表示的话如:2^7可改写为

2^0111即为2^(2^0) x 2^(2^1) x 2^(2^2) ,所以其实所用的数都能用这样的方式表示的:i1*m^(2^0)+i2*m^(2^1)+.... 

而m^(2^(i+1))=m^(2^i*2)=(m^(2^i))^2=m^(2^i)*m^(2^i)所以我们就可以利用这些原理进行循环了。

 

#include <iostream>
using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	unsigned long int recursion(unsigned long int base, unsigned long int index);
	unsigned long int base, index;
	cout << "请输入底数:" << endl;
	cin >> base;
	cout << "请输入指数:" << endl;
	cin >> index;
	cout << base << "的" << index << "次方为:" << recursion(base, index) << endl;
	getchar();
	getchar();
	return 0;
}

unsigned long int recursion(unsigned long int base, unsigned long int index)
{
	unsigned long int temp = 1;
	while (index > 0)
	{
		if (index & 0x01 == 1)
			temp *= base;
		base *= base;
		index >>= 1;
	}
	return temp;
}

实验结果:



欢迎大家加入每日一小练,嘿嘿!

每天练一练,日久见功夫,加油!


            -End-

参考文献:《c语言名题精选百则》