java递归实现十进制数2的幂次表示

1. 题目要求

任何一个正整数都可以用2的幂次方表示。例如：
　　　　137=2^7+2^3+2^0　　　　
同时约定幂次方用括号来表示，即ab 可表示为a（b）。
　　 由此可知，137可表示为：
　　　　 2（7）+2（3）+2（0）
进一步：7= 2^2+2+2^0 （21用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+2^0
所以1315最后可表示为：
　　 2（2（2+2（0））+2）+2（2（2+2（0）））+2（2（2）+2（0））+2+2（0）
　　输入：正整数（n≤20000）
输出：符合约定的n的0，2表示（在表示中不能有空格）
Input Format
一个正整数
Output Format
符合约定的n的0，2表示（在表示中不能有空格）
Sample Input
73
Sample Output
2(2(2)+2)+2(2+2(0))+2(0)

2.递归分析

递归出口：n=1或n=2，分别打印“2（0）”，“2”。之后结束递归。

3.代码实现

import java.util.Scanner;

public class nTobinarypow {
    public static void tpow(int n){

        if(n==1){
            System.out.print("2(0)");
            return;
        }
        if(n==2){
            System.out.print("2");
            return;
        }
        int temp=1;//2的幂次计算结果
        int c=0;//2的幂次
        while(temp<n){
            temp*=2;
            c++;
        }
        c-=1;
        if(n==temp/2){
            System.out.print("2(");
            tpow(c);
            System.out.print(")");
        }
        else 
        {
            if(temp/2==2){
                System.out.print("2");
                System.out.print("+");
                tpow(n-temp/2);

            }
            else {
                System.out.print("2(");
                tpow(c);
                System.out.print(")+");
                tpow(n-temp/2);
            }
        }

    }

    public static void main(String[] args) {
        System.out.println("请输入您想要转化的数值：（正整数哦）");
        Scanner sc= new Scanner(System.in);
        int input = sc.nextInt();
        System.out.println("转化结果为：");
        tpow(input);

    }
}

打赏