在2行5列的格子中填入1到10的数字。 要求： 相邻的格子中的数，右边的大于左边的，下边的大于上边的。
如【图1.png】所示的2种，就是合格的填法。
请你计算一共有多少种可能的方案。
请提交该整数，不要填写任何多余的内容（例如：说明性文字）。（答案：42）
请你计算一共有多少种可能的方案。
请提交该整数，不要填写任何多余的内容（例如：说明性文字）。（答案：42）
public class Main{
static int sum = 0;
public static void main(String[] args){
int[] num = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
sort(num, 1);
System.out.println(sum);
}
// 全排列10个数字
public static void sort(int[] str, int start){
for(int i = start; i < str.length-1; i++){
if(i>start){
jiaohuan(str, start, i);
}
if(start == str.length-2){
// 输出初始状态
bianli(str); // abc
// 交换后两位，并输出
jiaohuan(str, str.length-1, str.length-2);
bianli(str); // acb
// 复位第16行
jiaohuan(str, str.length-1, str.length-2);//恢复到abc
return;
}else{
sort(str, start+1);
}
if(i>start){
jiaohuan(str, start, i);
}
}
}
public static void bianli(int[] arr){
if(arr[0]<arr[1] && arr[1]<arr[2] && arr[2]<arr[3] && arr[3]<arr[4]
&& arr[5]<arr[6] && arr[6]<arr[7] && arr[7]<arr[8] && arr[8]<arr[9]
&& arr[0]<arr[5]&& arr[1]<arr[6] && arr[2]<arr[7] && arr[3]<arr[8] && arr[4]<arr[9]){
sum++;
}
}
public static void jiaohuan(int[] arr, int a, int b){
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
这道题使用了全排列来解题！关于全排列，我使用如下的方式来总结：
public class Demo01{
static int num = 0;
public static void main(String[] args){
String[] str = {"a", "b", "c"};
// PaiLie(str);
// PaiLie000000(str, 0);
String[] str1 = {"a", "b", "c", "d"};
// PaiLie11(str1, 0);
// PaiLie000000(str1, 0);
String[] str2 = {"a", "b", "c", "d", "e"};
// PaiLie22(str2);
PaiLie000000(str2, 0);
}
//a b
public static void PaiLie00(String[] arr,int start){
for(int i= start; i<arr.length; i++){
if(i>start){
JiaoHuan(arr, start, i);
}
// ÏÔʾbac
BianLi(arr);
if(i>start){
JiaoHuan(arr, start, i);
}
}
}
// a b c
public static void PaiLie(String[] arr, int start){
for(int i= start; i<arr.length; i++){
if(i>start){
JiaoHuan(arr, start, i);
}
PaiLie00(arr, start+1);
if(i>start){
JiaoHuan(arr, start, i);
}
}
}
// a b c d
public static void PaiLie11(String[] arr, int start){
for(int i= start; i<arr.length; i++){
if(i>start){
JiaoHuan(arr, start, i);
}
PaiLie(arr, start+1);
if(i>start){
JiaoHuan(arr, start, i);
}
}
}
// a b c d e
public static void PaiLie22(String[] arr){
for(int i= 0; i<arr.length; i++){
if(i>0){
JiaoHuan(arr, 0, i);
}
PaiLie11(arr, 1);
if(i>0){
JiaoHuan(arr, 0, i);
}
}
}
public static void PaiLie000000(String[] arr, int start){
for(int i= start; i<arr.length; i++){
if(i>start){
JiaoHuan(arr, start, i);
}
if(start==arr.length-1){
BianLi(arr);
return;
}
PaiLie000000(arr, start+1);
if(i>start){
JiaoHuan(arr, start, i);
}
}
}
public static void BianLi(String[] arr){
num++;
System.out.print(num+": ");
for(int i = 0; i< arr.length; i++){
System.out.print(arr[i]+"\t");
}
System.out.println();
}
public static void JiaoHuan(String[] arr, int a, int b){
String temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
搞懂了全排列，这道题就很简单了，下边的题目也是类似的：
看这个算式： ☆☆☆ + ☆☆☆ = ☆☆☆
如果每个五角星代表 1 ~ 9 的不同的数字。
这个算式有多少种可能的正确填写方法？
295 + 173 = 468
173 + 295 = 468
183 + 492 = 675
以上都是正确的填写法！
注意：
111 + 222 = 333 是错误的填写法！
因为每个数字必须是不同的！
也就是说：1~9中的所有数字，每个必须出现且仅出现一次！