标题：生命游戏 康威生命游戏是英国数学家约翰·何顿·康威在1970年发明的细胞自动机。 这个游戏在一个无限大的2D网格上进行。 初始时，每个小方格中居住着一个活着或死了的细胞。 下一时刻每个细胞的状态都由它周围八个格子的细胞状态决定。 具体来说： 1. 当前细胞为存活状态时，当周围低于2个（不包含2个）存活细胞时， 该细胞变成死亡状态。（模拟生命数量稀少） 2. 当前细胞为存活状态时，当周围有2个或3个存活细胞时， 该细胞保持原样。 3. 当前细胞为存活状态时，当周围有3个以上的存活细胞时，该细胞变成死亡状态。（模拟生命数量过多） 4. 当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。 （模拟繁殖） 当前代所有细胞同时被以上规则处理后, 可以得到下一代细胞图。按规则继续处理这一代的细胞图，可以得到再下一代的细胞图，周而复始。 例如假设初始是:(X代表活细胞，.代表死细胞) ..... ..... .XXX. ..... 下一代会变为: ..... ..X.. ..X.. ..X.. ..... 康威生命游戏中会出现一些有趣的模式。例如稳定不变的模式： .... .XX. .XX. .... 还有会循环的模式： ...... ...... ...... .XX... .XX... .XX... .XX... .X.... .XX... ...XX. -> ....X. -> ...XX. ...XX. ...XX. ...XX. ...... ...... ...... ...... .XX... .XX... ...XX. ...XX. ...... 本题中我们要讨论的是一个非常特殊的模式，被称作"Gosper glider gun"： ...................................... .........................X............ .......................X.X............ .............XX......XX............XX. ............X...X....XX............XX. .XX........X.....X...XX............... .XX........X...X.XX....X.X............ ...........X.....X.......X............ ............X...X..................... .............XX....................... ...................................... 假设以上初始状态是第0代，请问第1000000000(十亿)代一共有多少活着的细胞？ 注意：我们假定细胞机在无限的2D网格上推演，并非只有题目中画出的那点空间。 当然，对于遥远的位置，其初始状态一概为死细胞。 注意：需要提交的是一个整数，不要填写多余内容。
- 初始状态是第0代
- 细胞机在无限的2D网格上推演，并非只有题目中画出的那点空间
枚举十亿次是不现实的，应该相信是有循环规律的，或许到了第N代细胞机细胞数就不会变化，或许细胞数是一直增加的，但是增加得有规律。不管如何，都需要推演出这一代演化到下一代的细胞数目，这样才能探索出规律。判断一个活细胞或者死亡细胞的下一刻是否存活都是很简单的；难点是如何模拟无限的2D网格，用一个很庞大的数组也是不现实的，数组庞大，枚举量也会增大，而且到底用多大的数组仍然需要从原图去探索。数组不行，只能去寻找其他数据结构，Java中除了数组，第二种想到的应该是集合（List、Set、Map），如果通过集合来存取一张细胞机图中的所有X点（用一个类Point对象来代表活细胞，类成员变量x、y代表行、列），然后通过集合中的contains方法可以很轻松的判断一个活细胞周围的八个邻近细胞中有多少个存活细胞，从而判断出当前细胞的下一刻是否可以存活；活细胞判断完了，但是死亡细胞下一刻也有可能存活，茫茫多的死亡细胞如何判定？只要认识到只有在活细胞旁边的死亡细胞才有存活的可能性就知道了应用集合来解题是正确的，在统计一个活细胞旁边八个邻近的活细胞数目时，如果contains返回false，说明这个邻近细胞是死亡细胞，但是也说明了它是有存活的可能性的，所以此刻可以判断它周围的八个活细胞数目来判断其下一刻是否可以存活——每一个在活细胞周围的死亡细胞都应该这样一一去判断（需要注意的是，同一个死亡细胞可能存在不同的活细胞的周围，所以一个在将一个活过来的死亡细胞加入新的细胞机图时需要判断一下，否则可能会重复加入同一细胞）；这样遍历了一张细胞机图中所有的活细胞和有机会存活的死亡细胞后下一张新的细胞机图就会产生了；通过这样迭代，输出第N代前的每一代的细胞数目和代与代之间的细胞数目差来寻找规律。
import java.util.ArrayList; import java.util.List; import java.util.Scanner; class Point{ //代表细胞 public int x; //行 public int y; //列 public Point(int x,int y){ this.x=x; this.y=y; } @Override public boolean equals(Object obj) { Point newPoint=(Point)obj; return this.x==newPoint.x && this.y==newPoint.y; } } public class Main{ static int row=11; static int rank=38; static List<Integer> saveCellNum=new ArrayList<Integer>(); //存放每一代的细胞数 static List<Point> livingCell=new ArrayList<Point>(); //存放活细胞 static List<Point> nextLivingCell; //存放下一代的活细胞 static int dirX[]={-1,-1,-1,0,0,1,1,1}; //八个方向，左上、上、右上、左、右、左下、下、右下 static int dirY[]={-1,0,1,-1,1,-1,0,1}; public static void main(String args[]){ Scanner reader=new Scanner(System.in); char tmp[][]=new char[row][rank]; for(int i=0;i<row;i++){ String str=reader.nextLine(); tmp[i]=str.toCharArray(); } //加入活细胞 for(int i=0;i<row;i++){ for(int j=0;j<rank;j++){ if(tmp[i][j]=='X'){ livingCell.add(new Point(i,j)); } } } saveCellNum.add( new Integer(livingCell.size()) ); //加入第0代活细胞数目 for(int loop=1;loop<=300;loop++){ //循环100次观察规律 nextLivingCell=new ArrayList<Point>(); for(int i=0;i<livingCell.size();i++){ //遍历当前代的所有活细胞 Point curPoint=(Point)livingCell.get(i); int nigorCells=0; //周围八个细胞的存活数目 for(int j=0;j<8;j++){ int dx=curPoint.x+dirX[j]; int dy=curPoint.y+dirY[j]; if(livingCell.contains(new Point(dx,dy))){ nigorCells++; }else{ //只有在活细胞旁边的死亡细胞才存在存活的可能 if(!nextLivingCell.contains(new Point(dx,dy))){ //需要注意，不同的活细胞周围可能存在同一个死亡细胞 int nigorhPoint=0; for(int k=0;k<8;k++){ //同样判断此白细胞 int dxx=dx+dirX[k]; int dyy=dy+dirY[k]; if(livingCell.contains(new Point(dxx,dyy))){ nigorhPoint++; } } if(nigorhPoint==3){ //死亡细胞复活 nextLivingCell.add(new Point(dx,dy)); } } } } if(nigorCells==2 || nigorCells==3){ //活细胞延续 nextLivingCell.add(curPoint); } } //至此上一代的已经更新完毕 saveCellNum.add(new Integer(nextLivingCell.size())); livingCell=nextLivingCell; } for(int i=0;i<saveCellNum.size();i++){ System.out.print(saveCellNum.get(i)+" "); } System.out.println(); for(int i=1;i<saveCellNum.size();i++){ System.out.print(saveCellNum.get(i)-saveCellNum.get(i-1)+" "); } } }
......................................
.........................X............
.......................X.X............
.............XX......XX............XX.
............X...X....XX............XX.
.XX........X.....X...XX...............
.XX........X...X.XX....X.X............
...........X.....X.......X............
............X...X.....................
.............XX.......................
......................................
36 39 43 48 51 44 51 48 61 42 48 50 54 55 56 42 44 47 53 54 54 54 49 60 43 50 47 47 50 48 41 44 48 53 56 49 56 53 66 47 53 55 59 60 61 47 49 52 58 59 59 59 54 65 48 55 52 52 55 53 46 49 53 58 61 54 61 58 71 52 58 60 64 65 66 52 54 57 63 64 64 64 59 70 53 60 57 57 60 58 51 54 58 63 66 59 66 63 76 57 63 65 69 70 71 57 59 62 68 69 69 69 64 75 58 65 62 62 65 63 56 59 63 68 71 64 71 68 81 62 68 70 74 75 76 62 64 67 73 74 74 74 69 80 63 70 67 67 70 68 61 64 68 73 76 69 76 73 86 67 73 75 79 80 81 67 69 72 78 79 79 79 74 85 68 75 72 72 75 73 66 69 73 78 81 74 81 78 91 72 78 80 84 85 86 72 74 77 83 84 84 84 79 90 73 80 77 77 80 78 71 74 78 83 86 79 86 83 96 77 83 85 89 90 91 77 79 82 88 89 89 89 84 95 78 85 82 82 85 83 76 79 83 88 91 84 91 88 101 82 88 90 94 95 96 82 84 87 93 94 94 94 89 100 83 90 87 87 90 88 81 84 88 93 96 89 96 93 106 87 93 95 99 100 101 87 89 92 98 99 99 99 94 105 88 95 92 92 95 93 86
3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7
输出结果的第一行为第0代到第300代的细胞数目，第二行为代与代之间的细胞数目差；通过观察发现，细胞数目是呈现增加的趋势，不存在从第N代开始后细胞数目就稳定不变；但细胞差呈现了循环规律
3 4 5 3 -7 7 -3 13 -19 6 2 4 1 1 -14 2 3 6 1 0 0 -5 11 -17 7 -3 0 3 -2 -7 ，说明每30代细胞数目都会呈现这样一种变化。
public class Test{ public static void main(String args[]){ int a[]={3, 4 ,5 ,3 ,-7, 7, -3 ,13 ,-19, 6, 2 ,4 ,1, 1, -14, 2 ,3 ,6, 1, 0, 0 ,-5 ,11, -17, 7 ,-3 ,0,3 ,-2, -7}; int sum=0; for(int i=0;i<a.length;i++){ sum+=a[i]; } System.out.println(sum); int k=0; k=(1000000000/30)*sum+36; int b[]=new int[1000000000%30]; for(int i=0;i<b.length;i++){ b[i]=a[i]; k+=b[i]; } System.out.println(k); } }
5 166666713
答案：166666713
对于类Point中的Override方法equals(Object obj)，参考：https://blog.csdn.net/chwnpp2/article/details/79657057