本文共 1284 字，大约阅读时间需要 4 分钟。

                                                   2的幂次方表示（递归）

 

采用二进制数，从最高位到最低位依次转换。

一、问题描述

任何一个正整数都可以用2的幂次方表示。同时约定方次用括号来表示，即ab可表示为a(b)。例如：

137可表示为：

     2(2(2)+2+2(0))+2(2+2(0))+2(0)

1315可表示为：

     2(2(2+2(0))+2)+2(2(2+2(0)))+2(2(2)+2(0))+2+2(0)

输入

     一个正整数n（n≤20000）。 输出      一行，符合约定的n的0，2表示（在表示中不能有空格）。   二、问题分析   第二次做这个题目了，可解题时还是不流畅。最开始纠结的地方是用二进制数来求解好，还是除2取余法好。良久，最后选择了二进制数，从最高位开始，依次对每一位进行转换，直到最低位转换完毕。

于是，首先需要一个函数确定二进制数的位数，以便从最高位开始转换。这里规定最低位为第1位

int getlen(int i){
   	//计算二进制数n的位长度	int len = 0;	while (i)	{
   		i >>= 1;		++len;	}	return len;}

在转换过程中，如果第k位为0，则跳过，进行第k-1位的转换。否则先将该位转换完毕，再进行第k-1位的转换。第k位的转换具体如下：

如果 k=1，则打印2⁰；

        k=2,则打印2；

其他情况，将k作为要转换的数。要注意第k位是2^k-1，而不是2^k。今天我就在这里犯了错误，最后才幡然悔悟啊，当心。

  三、源代码

// 2的幂次方表示#include 
   
    using namespace std;int getlen(int i){
   	//计算二进制数n的位长度	int len = 0;	while (i)	{
   		i >>= 1;		++len;	}	return len;}void convert(int num,int k)//转换二进制数的第k位，从最高位开始转换{
   	if (k == 0) return;    //第0位，不存在，数已经转换完毕	int num_k = (num >> (k-1)) & 1;		if (!num_k)            //第k位为0，则开始转换下一位		convert(num, k - 1);	else           	{
   		if (k != getlen(num)) cout << "+";//转换数的最高位时不用打印 +				if (k == 1) cout << "2(0)";		else if (k == 2) cout << "2";		else 		{
   			cout << "2(";			convert(k-1, getlen(k-1));//对幂指数进行转换			cout << ")";		}		convert(num, k - 1);	}}int main(){
   	int n;	cin >> n;	convert(n, getlen(n));	return 0;}
   

转载地址：http://nhirf.baihongyu.com/