蓝桥杯：算法训练 2的次幂表示

Love The Way You Lie 2022-08-05 13:19 179阅读 0赞

问题描述

任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。  
　　将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：137=2^7+2^3+2^0  
　　现在约定幂次用括号来表示，即a^b表示为a（b）  
　　此时，137可表示为：2（7）+2（3）+2（0）  
　　进一步：7=2^2+2+2^0 （2^1用2表示）  
　　3=2+2^0    
　　所以最后137可表示为：2（2（2）+2+2（0））+2（2+2（0））+2（0）  
　　又如：1315=2^10+2^8+2^5+2+1  
　　所以1315最后可表示为：  
　　2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）

输入格式

正整数（1<=n<=20000）

输出格式

符合约定的n的0，2表示（在表示中不能有空格）

样例输入

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)  
  
提示  
用递归实现会比较简单，可以一边递归一边输出

解题思路

用递归来实现。将十进制数转换成二进制，记录转换过程中为1的是第几次循环，然后再判断。递归的边界就是当n==0,n==1n==2的时候。

但是应该注意的是，要判断什么时候输出+号，什么时候不输出。当不是最后一个的时候就输出 +

定义数组的时候要定义为局部变量，因为每一次数组存储的都不同。  
源代码：

#include<stdio.h>
    
    int main()
    {
    	int n;
    	void cimi(int n);//声明函数 
    	while(scanf("%d",&n)!=EOF)//按下Ctrl+Z结束 
    	{
    		cimi(n);//调用函数 
    		printf("\n");
    	}
    	return 0;
    }
    //
    void cimi(int n)
    {
    	int num;
    	int i,j,k;
    	int a[32];//数组定义为局部变量
    	num=0;
    	i=0;
    	while(n)
    	{
    		j=n%2;
    		if(j==1)
    		{
    			a[num]=i;//存储第几次是1 ，如果大于了2次的话将会递归调用重新来一次直到不大于2为止 
    			num++; //数组下标，最终代表多少个1 
    		}
    		i++;
    		n/=2; 
    	} 
    	for(i=num-1;i>=0;i--)
    	{
    		if(a[i]==0)
    		{
    			printf("2(0)");
    		}
    		else if(a[i]==1)
    		{
    			printf("2");
    		}
    		else if(a[i]==2)
    		{
    			printf("2(2)");
    		}
    		else if(a[i]>2)
    		{
    			printf("2(");
    			cimi(a[i]);//递归调用 
    			printf(")");
    		}
    		if(i!=0)
    		{
    			printf("+");//如果不是最后一个就输出 
    		}
    	}
    }

![Center][]

[Center]: /images/20220805/0f9cc798325c45f7ae6814c975d3a7bd.png