Java软件开发A组
1
阶乘位数
9的阶乘等于：362880
它的二进制表示为：1011000100110000000
这个数字共有19位。
请你计算，9999 的阶乘的二进制表示一共有多少位？
注意：需要提交的是一个整数，不要填写任何无关内容（比如说明解释等）
首先想到十进制转二进制的整除2倒取余，然后就很容易推断处下边的结论
public class Main { public static void main(String[] args) { int m = 9999; double temp,r=0; for (int i = m; i > 1; i--) { temp = Math.log(i) / Math.log(2); r += temp; } System.out.println((int)r+1); } }
运行结果：118445
2
凑平方数
把0~9这10个数字，分成多个组，每个组恰好是一个平方数，这是能够办到的。
比如：0, 36, 5948721
再比如：
1098524736
1, 25, 6390784
0, 4, 289, 15376
等等...
注意，0可以作为独立的数字，但不能作为多位数字的开始。
分组时，必须用完所有的数字，不能重复，不能遗漏。
如果不计较小组内数据的先后顺序，请问有多少种不同的分组方案？
注意：需要提交的是一个整数，不要填写多余内容。
import java.util.ArrayList; /** * 思路：先找到不同位数并各位不重复的偶数 * 这里暂时称作Ln比如长度为8的偶数记为L8 * 则所有的组合和分为： * L10 * * L9 L1 * * L8 L2 * L8 L1 L1 * * L7 L3 * L7 L2 L1 * L7 L1 L1 * * L6 L4 * L6 L3 L1 * L6 L2 L2 * L6 L2 L1 L1 * L6 L1 L1 L1 L1 * * .......等 * * 可以发现只要从L10遍历到L1 * 并且在每个内部如（L6 L3 L1这行）要保证前边的数字不小于后边的。这样就能保证不重不漏。 * * @author 王孙悟空 * */ public class 凑平方数 { // 用来存放找到的平方数 static long array[] = new long[10]; //标记数组array的实际长度，或说是关注点 static int ai = 0; // 数组mark[]存放0~9用来判重 static int mark[] = new int[10]; /** * 存放不同长度的平方数 */ static ArrayList<Long> L1 = new ArrayList<Long>(); static ArrayList<Long> L2 = new ArrayList<Long>(); static ArrayList<Long> L3 = new ArrayList<Long>(); static ArrayList<Long> L4 = new ArrayList<Long>(); static ArrayList<Long> L5 = new ArrayList<Long>(); static ArrayList<Long> L6 = new ArrayList<Long>(); static ArrayList<Long> L7 = new ArrayList<Long>(); static ArrayList<Long> L8 = new ArrayList<Long>(); static ArrayList<Long> L9 = new ArrayList<Long>(); static ArrayList<Long> L10 = new ArrayList<Long>(); //统计符合要求的组数 static int result = 0; public static void main(String[] args) { long temp;// 暂时存放平方数 /** * 计算所有的平方数小于11位的平方数并存入对应的数列。 */ for (long i = 0; i <= 100000; i++) { temp = i * i; // 数字进标记; inOutBj(temp, 1); // 判断是否重复 if (!pc()) { switch (String.valueOf(temp).length()) { case 1: L1.add(temp); break; case 2: L2.add(temp); break; case 3: L3.add(temp); break; case 4: L4.add(temp); break; case 5: L5.add(temp); break; case 6: L6.add(temp); break; case 7: L7.add(temp); break; case 8: L8.add(temp); break; case 9: L9.add(temp); break; case 10: L10.add(temp); break; default: break; } } // 标记数组回溯 inOutBj(temp, -1); } /** * 长度为10的一定是符合要求的 */ result = L10.size(); for (int i = 0; i < L10.size(); i++) { System.out.println(L10.get(i)); } /** * 运算最大长度是j的 */ for (int j = 9; j >= 1; j--) { fun(j, 10 - j); } System.out.println(result); } /** * 数字进出标记数组 * @param temp 数字 * @param io 进出标记 */ static void inOutBj(long temp, int io) { //0情况特殊,单独判断 if (temp == 0) { mark[0] += io; } while (temp != 0) { mark[(int) (temp % 10)] += io; temp /= 10; } } /** * 判断是否有一个数字出现两次 * @return */ static boolean pc() { for (int i = 0; i < mark.length; i++) { if (mark[i] > 1) { return true; } } return false; } /** * * @param k 尝试的位数 * @param c 剩余的位数 */ static void fun(int k, int c) { switch (k) { case 1://在长度为1下遍历每种可能的数 for (int i = 0; i < L1.size(); i++) { inOutBj(L1.get(i), 1); array[ai] = L1.get(i); ai++; dg(k, c); //回溯 inOutBj(L1.get(i), -1); ai--; } break; case 2: for (int i = 0; i < L2.size(); i++) { inOutBj(L2.get(i), 1); array[ai] = L2.get(i); ai++; dg(k, c); inOutBj(L2.get(i), -1); ai--; } break; case 3: for (int i = 0; i < L3.size(); i++) { inOutBj(L3.get(i), 1); array[ai] = L3.get(i); ai++; dg(k, c); inOutBj(L3.get(i), -1); ai--; } break; case 4: for (int i = 0; i < L4.size(); i++) { inOutBj(L4.get(i), 1); array[ai] = L4.get(i); ai++; dg(k, c); inOutBj(L4.get(i), -1); ai--; } break; case 5: for (int i = 0; i < L5.size(); i++) { inOutBj(L5.get(i), 1); array[ai] = L5.get(i); ai++; dg(k, c); inOutBj(L5.get(i), -1); ai--; } break; case 6: for (int i = 0; i < L6.size(); i++) { inOutBj(L6.get(i), 1); array[ai] = L6.get(i); ai++; dg(k, c); inOutBj(L6.get(i), -1); ai--; } break; case 7: for (int i = 0; i < L7.size(); i++) { inOutBj(L7.get(i), 1); array[ai] = L7.get(i); ai++; dg(k, c); inOutBj(L7.get(i), -1); ai--; } break; case 8: for (int i = 0; i < L8.size(); i++) { inOutBj(L8.get(i), 1); array[ai] = L8.get(i); ai++; dg(k, c); inOutBj(L8.get(i), -1); ai--; } break; case 9: for (int i = 0; i < L9.size(); i++) { inOutBj(L9.get(i), 1); array[ai] = L9.get(i); ai++; dg(k, c); inOutBj(L9.get(i), -1); ai--; } break; default: break; } } /** * * @param k 尝试的位数 * @param c 剩余的位数 */ static void dg(int k, int c) { //判断不重复,并且后边的数要比前边的数小。 if (!pc() && (ai-2<0||array[ai - 1] <= array[ai - 2])) { //程序出口，说明找到了要找的改组数 if (c == 0) { result++; //输出该组数 for (int i = 0; i < ai; i++) { System.out.print(array[i] + " "); } System.out.println(); } else { /** * 继续找下一个,因为下一个的位数一定不大于前一个的位数并也不大于剩余的位数。 * 所以这里使用Math.min(k,c) */ for (int j = Math.min(k, c); j > 0; j--) { fun(j, c - j); } } } } } 运行结果：1026753849 1042385796 1098524736 1237069584 1248703569 1278563049 1285437609 1382054976 1436789025 1503267984 1532487609 1547320896 1643897025 1827049536 1927385604 1937408256 2076351489 2081549376 2170348569 2386517904 2431870596 2435718609 2571098436 2913408576 3015986724 3074258916 3082914576 3089247561 3094251876 3195867024 3285697041 3412078569 3416987025 3428570916 3528716409 3719048256 3791480625 3827401956 3928657041 3964087521 3975428601 3985270641 4307821956 4308215769 4369871025 4392508176 4580176329 4728350169 4730825961 4832057169 5102673489 5273809641 5739426081 5783146209 5803697124 5982403716 6095237184 6154873209 6457890321 6471398025 6597013284 6714983025 7042398561 7165283904 7285134609 7351862049 7362154809 7408561329 7680594321 7854036129 7935068241 7946831025 7984316025 8014367529 8125940736 8127563409 8135679204 8326197504 8391476025 8503421796 8967143025 9054283716 9351276804 9560732841 9614783025 9761835204 9814072356 102576384 9 105637284 9 139854276 0 152843769 0 157326849 0 158306724 9 176305284 9 180472356 9 183467025 9 187635204 9 208571364 9 215384976 0 218034756 9 245893761 0 254817369 0 284057316 9 307265841 9 316057284 9 326597184 0 361874529 0 375468129 0 382945761 0 385297641 0 412739856 0 430728516 9 472801536 9 475283601 9 523814769 0 529874361 0 537219684 0 549386721 0 560837124 9 570684321 9 576432081 9 587432169 0 589324176 0 597362481 0 615387249 0 627953481 0 653927184 0 672935481 0 697435281 0 714653289 0 734681025 9 735982641 0 743816529 0 783104256 9 825470361 9 842973156 0 847159236 0 853107264 9 923187456 0 13527684 9 0 19847025 36 32970564 81 34257609 81 34857216 9 0 45239076 81 56972304 81 57108249 36 65318724 9 0 68973025 4 1 70459236 81 71520849 36 73256481 9 0 73925604 81 74390625 81 80514729 36 81432576 9 0 85063729 4 1 86397025 4 1 94187025 36 98327056 4 1 1034289 576 1432809 576 2039184 576 2537649 81 0 2893401 576 3048516 729 3297856 4 1 0 3748096 25 1 3798601 25 4 3814209 576 3857296 4 1 0 4730625 81 9 4835601 729 5184729 36 0 5308416 729 5673924 81 0 5827396 4 1 0 5948721 36 0 6385729 4 1 0 6390784 25 1 6517809 324 6734025 81 9 7203856 49 1 7203856 9 4 1 7436529 81 0 7851204 36 9 8567329 4 1 0 8590761 324 8673025 49 1 8673025 9 4 1 9108324 576 9253764 81 0 9572836 4 1 0 139876 25 4 0 173056 289 4 207936 5184 257049 81 36 321489 7056 321489 576 0 349281 7056 349281 576 0 357604 289 1 381924 7056 381924 576 0 385641 729 0 390625 784 1 391876 25 4 0 408321 7569 408321 576 9 423801 7569 423801 576 9 497025 81 36 537289 16 4 0 537289 64 1 0 576081 3249 576081 324 9 603729 5184 635209 784 1 725904 81 36 731025 8649 751689 2304 751689 324 0 760384 529 1 760384 25 9 1 872356 49 1 0 872356 9 4 1 0 893025 1764 893025 4761 15376 2809 4 15376 289 4 0 15876 2304 9 15876 3249 0 15876 324 9 0 17689 3025 4 18769 3025 4 20736 5184 9 23409 15876 23409 576 81 30276 5184 9 30625 784 9 1 30976 841 25 30976 81 25 4 35721 6084 9 35721 8649 0 38025 1764 9 38025 4761 9 39204 15876 39204 576 81 39601 784 25 47089 361 25 47089 36 25 1 47961 38025 51984 20736 51984 30276 63504 729 81 67081 5329 4 71289 63504 71289 4356 0 73984 256 1 0 73984 625 1 0 73984 25 16 0 74529 81 36 0 78961 3025 4 79524 81 36 0 81796 3025 4 87025 1369 4 87025 1936 4 87025 361 49 87025 361 9 4 87025 36 9 4 1 87025 49 36 1 93025 784 16 95481 20736 95481 30276 1089 576 324 1369 784 25 0 1936 784 25 0 2304 576 81 9 3025 784 169 3025 784 196 3025 784 16 9 3025 961 784 3249 576 81 0 4356 729 81 0 5184 729 36 0 5329 784 16 0 7056 3249 81 7056 324 81 9 7396 841 25 0 7396 81 25 4 0 7569 2304 81 7569 324 81 0 9025 784 361 9025 784 36 1 9801 576 324 576 324 81 9 0 784 361 25 9 0 784 529 361 0 784 529 36 1 0 784 36 25 9 1 0 300
3
棋子换位
有n个棋子A，n个棋子B，在棋盘上排成一行。
它们中间隔着一个空位，用“.”表示，比如：
AAA.BBB
现在需要所有的A棋子和B棋子交换位置。
移动棋子的规则是：
1.A棋子只能往右边移动，B棋子只能往左边移动。
2. 每个棋子可以移动到相邻的空位。
3. 每个棋子可以跳过相异的一个棋子落入空位（A跳过B或者B跳过A）。
AAA.BBB可以走法：
移动A==> AA.ABBB
移动B==> AAAB.BB
跳走的例子：
AA.ABBB==> AABA.BB
以下的程序完成了AB换位的功能，请仔细阅读分析源码，填写划线部分缺失的内容。
publicclass Main
{
staticvoid move(char[] data, int from, int to)
{
data[to]= data[from];
data[from]= '.';
}
staticboolean valid(char[] data, int k)
{
if(k<0|| k>=data.length) return false;
returntrue;
}
staticvoid f(char[] data)
{
while(true){
booleantag = false;
for(inti=0; i<data.length; i++){
intdd = 0; // 移动方向
if(data[i]=='.')continue;
if(data[i]=='A')dd = 1;
if(data[i]=='B')dd = -1;
if(valid(data,i+dd) && valid(data,i+dd+dd)
&&data[i+dd]!=data[i] && data[i+dd+dd]=='.'){
// 如果能跳...
move(data,i, i+dd+dd);
System.out.println(newString(data));
tag= true;
break;
}
}
if(tag)continue;
for(inti=0; i<data.length; i++){
intdd = 0; // `移动方向
if(data[i]=='.')continue;
if(data[i]=='A')dd = 1;
if(data[i]=='B')dd = -1;
if(valid(data,i+dd) && data[i+dd]=='.'){
// 如果能移动...
if(valid(data,i+dd+dd)&&valid(data,i+dd*-1)&&data[i+dd*-1]==data[i+dd+dd] ) continue; //填空位置
move(data,i, i+dd);
System.out.println(newString(data));
tag= true;
break;
}
}
if(tag==false)break;
}
}
publicstatic void main(String[] args)
{
char[]data = "AAA.BBB".toCharArray();
f(data);
}
}
注意：只提交划线部分缺少的代码，不要复制已有代码或填写任何多余内容。
