2015年9月15号360笔试算法2
程序员文章站
2024-01-23 09:22:28
...
Problem Description
当你学一些可视化程序设计语言时,老师经常让你设计并编程做出一个计算机,这时也许你会仿照windows系统自带的计算器外观和功能区设计,但是现在考试要你多做出一个有新功能的计算器,实现当输入一个数是,能够将这个数分解成一个或多个素因子乘积的形式,并按素因子的大小排列显示出来。大家对计算器中数的表示应该是很清楚的,下面显示出了0-9这是个数组的表示形式,每个数字占据5*3大小的字符区域。
你能实现这个心能能吗?试试看吧!
输入
能输入多组测试数据,每组包括一个正整数n(n<=1000000)
输出
对于每个数,将它分解成若干个素数乘积的形式,应按从小到大的顺序输出,素因子之间用“*”的形式链接
样例输入
10 2
样例输出
- - | | - * - | | - - - | - | -
解析:
此题主要有两个难点,第一是将一个整数分解为素数的乘积,第二是将各个数显示出来,
代码
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class WindowsNumber { public static void main(String[] args) { // TODO Auto-generated method stub Scanner scanner = new Scanner(System.in); while(scanner.hasNextInt()) { compute(scanner.nextInt()); } scanner.close(); } public static void compute(int number) { String[] number0 = new String[]{" - ", "| |", " ", "| |", " - "}; String[] number1 = new String[]{" ", " |", " ", " |", " "}; String[] number2 = new String[]{" - ", " |", " - ", "| ", " - "}; String[] number3 = new String[]{" - ", " |", " - ", " |", " - "}; String[] number4 = new String[]{" ", "| |", " - ", " |", " "}; String[] number5 = new String[]{" - ", "| ", " - ", " |", " - "}; String[] number6 = new String[]{" - ", "| ", " - ", "| |", " - "}; String[] number7 = new String[]{" - ", " |", " ", " |", " "}; String[] number8 = new String[]{" - ", "| |", " - ", "| |", " - "}; String[] number9 = new String[]{" - ", "| |", " - ", " |", " - "}; List<List<String[]>> resultNumbers = new ArrayList<List<String[]>>(); //保存被分解的数 int[] result = new int[10000]; int resultLength = 0; resultLength = decodeInt(number, result); for(int i=0; i<resultLength; i++) { List<String[]> resultNumber = new ArrayList<String[]>(); int temp = result[i]; while((temp%10 != 0) || (temp/10>0)) { int mod = temp % 10; temp = temp / 10; switch (mod) { case 0: resultNumber.add(0, number0); break; case 1: resultNumber.add(0, number1); break; case 2: resultNumber.add(0, number2); break; case 3: resultNumber.add(0, number3); break; case 4: resultNumber.add(0, number4); break; case 5: resultNumber.add(0, number5); break; case 6: resultNumber.add(0, number6); break; case 7: resultNumber.add(0, number7); break; case 8: resultNumber.add(0, number8); break; case 9: resultNumber.add(0, number9); break; } } resultNumbers.add(resultNumber); } //将最终结果输出 for(int i=0; i<5; i++) { for(int j=0; j<resultLength; j++) { List<String[]> resultNumber = resultNumbers.get(j); for(int k=0; k<resultNumber.size(); k++) { System.out.print(resultNumber.get(k)[i]); } if((i==2) && (j!=resultLength-1)) System.out.print(" * "); else System.out.print(" "); } System.out.println(); } } //此处代码借用别人的 public static int decodeInt(int n, int[] facArr) { int fac; int count; if (n < 4) { facArr[0] = n; return 1; } count = 0; // 下面的while循环为2试出n,直到2不是n的因子为止 while ((n & 1) == 0) // 这里判断偶数用 (n &1)==0,这比(n % 2)==0更快 { facArr[count++] = 2; n /= 2; } fac = 3; // 用3到sqrt(n)之间的奇数试除 while (fac * fac <= n) // fac*fac <= n { while (n % fac == 0) { facArr[count++] = fac; n /= fac; } fac += 2; } if (n == 1) return count; facArr[count++] = n; return count; } }