第二题:纸牌三角形
题目描述
A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形(A按1计算)。要求每个边的和相等。
下图就是一种排法(如有对齐问题,参看p1.png)。
A
9 6
4 8
3 7 5 2
这样的排法可能会有很多。
如果考虑旋转、镜像后相同的算同一种,一共有多少种不同的排法呢?
请你计算并提交该数字。
注意:需要提交的是一个整数,不要提交任何多余内容。
做这道题时遇到的问题:
刚开始是用暴力做的,但是觉得时间有点长。想要用队列优化一下,想的是第一个数是从9个数里面选一个,第二个数是从剩下的8个数中选一个,第三个数从剩下的7个数中选一个....... 。时间复杂度就变成了9 8 7 6 5 4 3 2 1,但是写完之后发现当判断三角形的条件不同时出来的结果也不一样,最下面是代码,请哪位路过的大神帮忙看一下。
![]()
当三角行 三条边分别是a1 a2 a4 a6和a1 a3 a5 a7和a6 a8 a9 a7时,代码执行出来时130
![]()
当三角形的三条边分别是a1 a2 a3 a4和a4 a5 a6 a7和a1 a9 a8 a7时,代码算出来的结果是158
![]()
当三角形的三条边分别是 a1 a2 a4 a6和a1 a3 a5 a9和a6 a7 a8 a9时,代码算出来的结果是126
按照原理应该每种结果都是一样的为什么会不一样呢?大佬们帮忙看一下是怎么回事
下面是代码:
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(1);list.add(2);list.add(3);list.add(4);list.add(5);list.add(6);list.add(7);list.add(8);list.add(9);
int count = 0;
int a1, a2, a3, a4, a5, a6, a7, a8, a9;
for (int i1 = 0; i1 < list.size(); ++i1) {
a1 = list.remove(i1);
for (int i2 = 0; i2 < list.size(); ++i2) {
a2 = list.remove(i2);
for (int i3 = 0; i3 < list.size(); ++i3) {
a3 = list.remove(i3);
for (int i4 = 0; i4 < list.size(); ++i4) {
a4 = list.remove(i4);
for (int i5 = 0; i5 < list.size(); ++i5) {
a5 = list.remove(i5);
for (int i6 = 0; i6 < list.size(); ++i6) {
a6 = list.remove(i6);
for (int i7 = 0; i7 < list.size(); ++i7) {
a7 = list.remove(i7);
for (int i8 = 0; i8 < list.size(); ++i8) {
a8 = list.remove(i8);
a9 = list.get(0);
//这样判断三边相等输出126
if ((a1 + a2 + a4 + a6) == (a6 + a7 + a8 + a9) && (a1 + a2 + a4+ a6) == (a1 + a3 + a5 + a9)) {
count++;
}
//这样判断三边相等输出158
// if ((a1 + a2 + a3 + a4) == (a4 + a5 + a6 + a7) && (a1 + a2 + a3+ a4) == (a1 + a9 + a8 + a7)) {
// count++;
// }
//这样判断3边相等输出130
// if ((a1 + a2 + a4 + a6) == (a1 + a3 + a5 + a7) && (a1 + a2 + a4+ a6) == (a6 + a8 + a9 + a7)) {
// count++;
// }
list.addFirst(a8);
}
list.addFirst(a7);
}
list.addFirst(a6);
}
list.addFirst(a5);
}
list.addFirst(a4);
}
list.addFirst(a3);
}
list.addFirst(a2);
}
list.addFirst(a1);
}
System.out.println(count/3/2);
}
}