详细解析蓝桥杯练习系统经典试题：幂方分解

75 阅读 0 评论 50 点赞

我是靠谱客的博主典雅小蘑菇，最近开发中收集的这篇文章主要介绍详细解析蓝桥杯练习系统经典试题：幂方分解，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述
　　任何一个正整数都可以用2的幂次方表示。例如：
　　137=27+23+20
　　同时约定方次用括号来表示，即ab 可表示为a（b）。
　　由此可知，137可表示为：
　　2（7）+2（3）+2（0）
　　进一步：7= 22+2+20 （21用2表示）
　　3=2+20
　　所以最后137可表示为：
　　2（2（2）+2+2（0））+2（2+2（0））+2（0）
　　又如：
　　1315=210 +28 +25 +2+1
　　所以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表示（在表示中不能有空格）

这道题是一道经典的模拟递归问题，在很多oj平台上都有这道题的出现。这道题是可以用二进制算的。但作为一道经典的模拟递归题目我们还是老老实实做吧。
首先，这题的终止条件是0或者2，但也可以把1写作2(1)作为终止条件。一个递归问题除了需要终止条件，还需要状态的变化，就是规模要不断缩小，这样递归才有意义。这里要有两部分要进行递归。一个数可能分成多个数，每个数可能都要递归，另外，每个数它的幂可能大于2，这里也需要进行递归。
算法思路：
1.找到最接近n这个数的2的幂次方
2.对这个幂的进行判断，如果大于2就要把这个幂次方当作一个函数新的n进行递归
3.用n减去这个最接近n的2的幂次方，如果剩下的数不等于0则进行递归，同时要添置＋号
4.如果n小于等于2了，直接用if终止递归

import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
f(n);
}
public static void f(int n) {
if(n==0) {
//这3个if都是终止条件
System.out.print("0");
return;
}
if(n==1) {
System.out.print("2(0)");
return;
}
if(n==2) {
System.out.print("2");
return;
}
System.out.print(2);
//如果在上面if没有被终止，那么肯定n>2的，那么肯定要进行递归，所以这里先写个2
int sum=1,pow=0;//sum最接近n的2的幂次方数，pow代表的幂方
while(sum<=n) {
pow++;
sum*=2;
}
sum/=2;
//这里肯定是多算了一次，因为sum要大于n才停止循环
pow--;
if(pow==0||pow==2) {
//如果这个幂是0或者2可以直接出答案，如果是1则不用处理
System.out.print("("+pow+")");
}
if(pow>=3) {
//如果大于3的话，肯定还要分解
System.out.print("(");
f(pow);
System.out.print(")");
}
n-=sum;
//把n减掉最接近n的2的幂次方这个数
if(n!=0) { //如果剩下的数不为0就要继续递归，并添置＋号
System.out.print("+");
f(n);
}
}
}