进制转换和2的幂次方表示

大家好，欢迎来到IT知识分享网。

进制转换和2的幂次方表示

一、题目要求
题目1：将非负十进制整数n转换成b进制。（其中b=2~16）
题目2：任何一个正整数都可以用2的幂次方表示。例如：
　　　　137=2⁷⁺²3+2^0　　　　
同时约定幂次方用括号来表示，即ab 可表示为a（b）。
　　 由此可知，137可表示为：
　　　　 2（7）+2（3）+2（0）
进一步：7= 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)

二、算法设计
1.题目分析
进制转化（2~16）：
首先设置函数为两参数number和i，number表示输入所要求解的数，i表示所要转化成的进制。
递归出口：number < i
递归函数：test(number/i, i)
每次将number % i的值j输出，即可得到所要的进制数，但是输出的顺序会是所想要答案的倒序，因此在输出j之前再次调用递归函数，这样就构造了一个栈模型，所输出的值既是所求。
以 将6转化为二进制为例：
进栈过程：



当number < i时进栈结束。
出栈过程：



得到6的二进制数110

非递归函数：用while对number>i进行判断，在循环体中计算number % i的余数j的值，并设置number = number / i；将余数j使用push（从头部）添加到LinkedList中，当number < i时将number同样添加到列表中。此时列表中的元素的排列顺序既是所需的进制数，使用循环读出即可。
题目2：
参考借鉴：[https://blog.csdn.net/sonovain/article/details/50575348]（c代码）

对其c代码进行理解，重置为java代码，并绘制多叉树模型（以73为例）如下：

将多叉树模型转化为二叉树模型：

三、主要代码

题目一：

package Recuision;

import java.util.LinkedList;
import java.util.Scanner;

public class TestChange { 
   
	public static void main(String[] args) { 
   
		Scanner scanner = new Scanner(System.in);
		System.out.println("请输入您要转化的数字：");
		int number = scanner.nextInt();
		System.out.println("请输入您要转换的进制（2~16）:");
		int i = scanner.nextInt();
		
		System.out.println("递归结果：");
		Change.test(number,i);
		System.out.println();
		System.out.println("非递归结果：");
		Change.test1(number, i);
		scanner.close();
	}

}

class Change{ 
   
	public static void test(int number, int i) { 
   
		if(number < i) { 
   
			if(number < 10) { 
   
				System.out.print(number);
			}else if(number == 10) { 
   
				System.out.print('A');
			}else if(number == 11) { 
   
				System.out.print('B');
			}else if(number == 12) { 
   
				System.out.print('C');
			}else if(number == 13) { 
   
				System.out.print('D');
			}else if(number == 14) { 
   
				System.out.print('E');
			}else if(number == 15) { 
   
				System.out.print('F');
			}

		}else { 
   
			int j = number % i;
			number = number / i;
			test(number, i);
			if(j < 10) { 
   
				System.out.print(j);
			}else if(j == 10) { 
   
				System.out.print('A');
			}else if(j == 11) { 
   
				System.out.print('B');
			}else if(j == 12) { 
   
				System.out.print('C');
			}else if(j == 13) { 
   
				System.out.print('D');
			}else if(j == 14) { 
   
				System.out.print('E');
			}else if(j == 15) { 
   
				System.out.print('F');
			}
			
		}
	}
	
	public static void test1(int number, int i) { 
   
		LinkedList<String> list = new LinkedList<>();
		while(number > i) { 
   
			int j = number % i;
			number = number / i;
			if(j < 10) { 
   
				list.push(String.valueOf(j));
			}else if(j == 10) { 
   
				list.push("A");
			}else if(j == 11) { 
   
				list.push("B");
			}else if(j == 12) { 
   
				list.push("C");
			}else if(j == 13) { 
   
				list.push("D");
			}else if(j == 14) { 
   
				list.push("E");
			}else if(j == 15) { 
   
				list.push("F");
			}
		}
		
		if(number < 10) { 
   
			list.push(String.valueOf(number));
		}else if(number == 10) { 
   
			list.push("A");
		}else if(number == 11) { 
   
			list.push("B");
		}else if(number == 12) { 
   
			list.push("C");
		}else if(number == 13) { 
   
			list.push("D");
		}else if(number == 14) { 
   
			list.push("E");
		}else if(number == 15) { 
   
			list.push("F");
		}
		
		for(String n:list) { 
   
			System.out.print(n);
		}
	}

}

题目二：（参考借鉴：[https://blog.csdn.net/sonovain/article/details/50575348]（c代码），重置为java代码） 侵权，删

package Recuision;

import java.util.Scanner;

public class TestSecondPower { 
   
	public static void main(String[] args) { 
   
		Scanner scanner = new Scanner(System.in);
		System.out.println("请输入一个正整数");
		int number = scanner.nextInt();
		SecondPower.test(number);
		scanner.close();
	}
	
}
class SecondPower{ 
   
	public static void test(int number) { 
   
		if(number == 1) { 
   
			System.out.print("2(0)");
			return;
		}
		if(number == 2) { 
   
			System.out.print("2");
			return;
		}
		int p = 1;
		int s = 0;
		
		while(p <= number) { 
   
			p = p*2;
			s++;
		}
		s = s - 1;
		if(number == p/2) { 
   
			System.out.print("2(");
			test(s);
			System.out.print(")");
		}else { 
   
			if(p/2 == 2 ) { 
   
				System.out.print("2 + ");
				test(number-p/2);
			}else { 
   
				System.out.print("2(");
				test(s);
				System.out.print(")+");
				test(number-p/2);
			}
		}
		
	}
}

四、调试和测试
将18转换为5进制，结果如下：

在将3242转化为16进制时，出现了不一致的情况如下：

经过计算，递归结果正确，非递归的出错，出错原因：当跳出循环后，即number<I 后，未对number进行判断，而是直接添加到列表中（没有考虑number>=10的情况），加入判断语句后，结果正确：

题目二：
经过测试均正确：


五、总结
在本次作业中，首先对递归和非递归有了更深的认识，学会了针对问题设计出递归模型，找到递归的出口和递归体，能够将递归转化为非递归，但对于题目二，有自己的思路，但是并未设计出合理的结构解决问题，在借鉴其他人的代码的过程了，学习到了其他人解题思路和解决问题的方法，受益匪浅。