Java算法之进制转换的奥义

admin管理员组

文章数量:1794759

Java算法之进制转换的奥义

在计算如此方便的今天，又有多少人知道在一个计算器后面有多少路要走吗？你的手指轻轻一点，后台就有成千上百条代码在帮你工作，今天，就来体验一下计算器中的进制转换功能。

对于进制转换，大家并不陌生，在机器或者程序中常用的进制也就是二进制，八进制，十进制，十六进制...。而对于我们，其实接触的最多其实是十进制，二进制一般用于机器中表示，在数电，数逻，计算机组成，信传输中等等使用频繁。关于其他进制的使用，这里就不再一一阐述了。

今天要完成的功能是对于任何一个数，当然，是在机器所能表示范围之中，完成对于2-16进制中任何一个进制的转换。这里就不讨论1进制了，没有意义。现在我们约定一下功能：

输入：

在第一行输入两个数字，分别是要计算的数字和要转换的进制

输出：

输出转换结果，对于11-16进制。按照16进制的规则，就是10用A表示，11用B表示....

分析：

首先，我们打开电脑自带的计算器功能，在查看中找到程序员专属的这一个...，如图所示，只提供了常见的进制转换功能。

，写程序迫在眉睫啊，因为我们还有 5 6 7 9 11 12 13 14 15进制没实现呢。

首先，关于进制转换的代码，之前学计算机组成原理时已经写过很多次了 ，那时候仅限于二进制，如果要改成其它进制其实基本上也就是换汤不换药了。但是上学期又学了算法。就琢磨着，用个算法来实现，最后决定了，用最粗暴的方法---暴力破解法（也就是枚举）。

开始，其思想是将输入的数值放在数组中，通过按位加权求和操作代码来枚举所有结果，如果遇到正确答案，则给予输出。

既然要暴力破解，那肯定少不了循环的操作了，多少层循环是个关键，这里不得不考虑到极端情况，那就是2进制的情况，需要的表示位是最多的，我在这里假设一个约束，输入的数值最大不超过10000，在此条件下，若转换为2进制，则需要15个二进制位来表示，因此最坏的情况就是15层循环的嵌套，利用CV大法写好循环后，还有一个超级长的按位加权求和操作，最后将正确答案保存至数组进行输出。代码如下。

import Java.util.Scanner; public class radixTransform { // private static String ANSWER=""; private static int RADIX; private static char SYMBOL; private static int DECIMAL; private static int ANSWER[]=new int[15]; public radixTransform(int RADIX,char SYMBOL,int DECIMAL) { radixTransform.RADIX=RADIX; radixTransform.SYMBOL=SYMBOL; radixTransform.DECIMAL=DECIMAL; } public static void RadixTrans(int value[]) { int decimalValue=0; for(int a=0;a<radixTransform.RADIX;a++) { for(int b=0;b<radixTransform.RADIX;b++) { for(int c=0;c<radixTransform.RADIX;c++) { for(int d=0;d<radixTransform.RADIX;d++) { for(int e=0;e<radixTransform.RADIX;e++) { for(int f=0;f<radixTransform.RADIX;f++) { for(int g=0;g<radixTransform.RADIX;g++) { for(int h=0;h<radixTransform.RADIX;h++) { for(int i=0;i<radixTransform.RADIX;i++) { for(int j=0;j<radixTransform.RADIX;j++) { for(int k=0;k<radixTransform.RADIX;k++) { for(int l=0;l<radixTransform.RADIX;l++) { for(int m=0;m<radixTransform.RADIX;m++) { for(int n=0;n<radixTransform.RADIX;n++) { for(int o=0;o<radixTransform.RADIX;o++) { System.out.println("RUNING******"); decimalValue=(int) (a*Math.pow(radixTransform.RADIX,14)+b*Math.pow(radixTransform.RADIX,13)+c*Math.pow(radixTransform.RADIX,12)+d*Math.pow(radixTransform.RADIX,11)+e*Math.pow(radixTransform.RADIX,10)+f*Math.pow(radixTransform.RADIX,9)+g*Math.pow(radixTransform.RADIX,8)+h*Math.pow(radixTransform.RADIX,7)+i*Math.pow(radixTransform.RADIX,6)+j*Math.pow(radixTransform.RADIX,5)+k*Math.pow(radixTransform.RADIX,4)+l*Math.pow(radixTransform.RADIX,3)+m*Math.pow(radixTransform.RADIX,2)+n*Math.pow(radixTransform.RADIX,1)+o*Math.pow(radixTransform.RADIX,0)); if(decimalValue==radixTransform.DECIMAL) { // System.out.println(decimalValue); // System.out.println("来了老弟："+a+" "+b+" "+c+" "+d+" "+e+" "+f+" "+g+" "+h+" "+i+" "+j+" "+k+" "+l+" "+m+" "+n+" "+o); ANSWER[0]=a; ANSWER[1]=b; ANSWER[2]=c; ANSWER[3]=d; ANSWER[4]=e; ANSWER[5]=f; ANSWER[6]=g; ANSWER[7]=h; ANSWER[8]=i; ANSWER[9]=j; ANSWER[10]=k; ANSWER[11]=l; ANSWER[12]=m; ANSWER[13]=n; ANSWER[14]=o; } } } } } } } } } } } } } } } } } public static void show() { int index=0; for(int i=0;i<15;i++) { if(ANSWER[i]!=0) { index=i; break; } } if(radixTransform.SYMBOL=='-') { System.out.print('-'); } else { //DO NOTHING... } for(int i=index;i<ANSWER.length;i++) { if(ANSWER[i]==10) { System.out.print('A'); } else if(ANSWER[i]==11) { System.out.print('B'); } else if(ANSWER[i]==12) { System.out.print('C'); } else if(ANSWER[i]==13) { System.out.print('D'); } else if(ANSWER[i]==14) { System.out.print('E'); } else if(ANSWER[i]==15) { System.out.print('F'); } else { System.out.print(ANSWER[i]); } } } public static void main(String[] args) { char symbol=' '; @SuppressWarnings("resource") Scanner sc=new Scanner(System.in); String value=sc.nextLine(); int decimal=Integer.parseInt(value); int radix=sc.nextInt(); int decimalValue[]= new int[15]; char[] charValue=value.toCharArray(); if(charValue[0]=='-') { symbol='-'; radixTransform.SYMBOL='-'; for(int i=value.length()-1,j=14;i>0;i--,j--) { decimalValue[j]=charValue[i]-48; } } else { symbol=' '; radixTransform.SYMBOL=' '; for(int i=value.length()-1,j=14;i>=0;i--,j--) { decimalValue[j]=charValue[i]-48; } } radixTransform trans = new radixTransform(radix,symbol,decimal) ; trans.RadixTrans(decimalValue); trans.show(); } }

在辛辛苦苦写完这点代码之后，开始Debug了，首先拿二进制做了测试，发现没有任何问题，一下就能得出正确答案。然鹅...，当我使用比二进制更大的转换后，发现程序运行一直结束不了。第一反应是程序本身问题，在反复纠察后，我并没发现任何问题。于是我换了一个比二进制大一点点的计算，那就是3进制。当我输入相应数值之后，程序还是一样没有停下来，经过三分钟漫长的等待，终于出现了想要的结果，没错，三分钟！！！仅仅计算了一个两位数转换成3进制！

emmm..很尴尬，不用说，这就是暴力破解的缺点，时间复杂度和空间复杂度相对较大，粗略的运算了一下，这个代码运行二进制时，其计算量大概是10000多次就能出结果，而对于3进制来说，粗略计算下来，大概需要1400万次才能得到正确结果 ，不敢往下想了....。我的CPU是志强x3470（弱鸡一枚），如果你们无聊可以看看你们的电脑跑这个程序用3进制花多少时间....

因此，又要另寻它路了，这个接近200行的代码报废了。对于接下来的代码，相对于上一个可能相差较大，因为仅有14行，别问为什么。全靠jdk api文档续命...

import java.util.Scanner; public class radixTransform2 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); String value=sc.nextLine(); int radix=sc.nextInt(); String AfterTrans=Integer.toString(Integer.parseInt(value), radix); String Final=AfterTrans.toUpperCase(); System.out.println(Final); } }

运行起来还是嗖嗖带风的啊！

全票通过！！！

 

本文标签： 奥义算法java