2的N次幂表示

比眉伴天荒 2022-08-05 02:52 212阅读 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)

提示

用递归实现会比较简单，可以一边递归一边输出

参考代码：

#include<stdio.h>
    	#include<math.h>
    	void power(int n){
    		int i;
    		if(n>=4){
    			printf("2(");
    			for(i=0;i<n;i++){
    				if(pow(2,i)<=n&&pow(2,i+1)>n)
    					break;
    			}
    			power(i);
    			n-=pow(2,i);
    			putchar(')');
    			if(n>0){
    				printf("+");
    				power(n);
    			}
    		}else{
    			if(n==3){
    				printf("2+2(0)");			
    			}
    			if(n==2)
    				putchar('2');
    			else{
    				if(n==1){
    					printf("2(");
    					putchar('0');
    					putchar(')');
    				}
    			}
    				
    		}
    		
    	}
    	int main(){
    		int n;
    		scanf("%d",&n);
    		power(n);
    		return 0;
    
    }

测试结果：

![SouthEast][]![SouthEast 1][]

[SouthEast]: https://img-blog.csdn.net/20150603184946629?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveHVrdW41MTM3/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: /images/20220805/9dbe94a3259049b6b8709e2208cd75d5.png