试题 算法训练 2的次幂表示

题目描述

资源限制
时间限制：1.0s 内存限制：512.0MB
问题描述
　　任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。
　　将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：137=2⁷⁺²3+2^0
　　现在约定幂次用括号来表示，即a^b表示为a（b）
　　此时，137可表示为：2（7）+2（3）+2（0）
　　进一步：7=2²⁺²⁺²0 （2^1用2表示）
　　3=2+2^0
　　所以最后137可表示为：2（2（2）+2+2（0））+2（2+2（0））+2（0）
　　又如：1315=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、将输入的数字转化为二进制，而转换进制的经典方法就是通过取模来获取其二进制中每一位对应的数字，
   并且用数组来储存（注意：第一次取模得出的是其二进制的最后一位，所以输出的时候要倒序输出）
   2、题目规定输出的形式只能由2以内的数字表示，而且在数组中，每个数对应的下标(n)就是其二进制表达的
   2的次幂即 (2^n),当n>2时要通过递归对n进行进制转换
   3，就是考虑什么时候该递归，什么时候打印，什么时候要打印' +' 、' ( '、' ) '符号，这些就在下面的
   代码中说明

#include <stdio.h>

void my_function(int n)
{
	int i = 0;
	int arr[100] = { 0 };
	while (n)//当n取模完后，n也变成0
	{
		arr[i++] = n % 2;
		n /= 2;
	}
	int k = 0;
	int flag = 1;
	for (k = i - 1; k >= 0; k--){//因为n的二进制储存进数组时，是从最后一位开始储存
		if (arr[k])//判断不为0的元素
			flag = k;
	}
	for (int j = i - 1; j >= 0; j--)
	{
		if (arr[j] == 1)
		{
			if (j > 2)//当n大于二时，在2^j中，要对j进行转化
			{
				printf("2(");
				my_function(j);
				printf(")");//对其次幂转化后，要封好‘)’
			}
			else if (j == 1)//当j==1时，其所表示的是2^1,即2
			{
				printf("2");
			}
			else
			{
				printf("2(%d)", j);
			}
			if (flag != j)//如果flag!=j，就说明在上面判断中因arr[j]==0，没有进入if语句
			{             //而arr[j]==0,就说明此时要打印下一位数，而两位数之间要打印'+'
				printf("+");
			}
		}
	}
}

int main()
{
	int n = 0;
	scanf("%d", &n);
	my_function(n);
	return 0;
}