标題：生命遊戲
康威生命遊戲是英國數學家約翰·何頓·康威在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.
...... ...... ......
本題中我們要讨論的是一個非常特殊的模式，被稱作"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網格上推演，并非隻有題目中畫出的那點空間。
當然，對于遙遠的位置，其初始狀态一概為死細胞。
注意：需要送出的是一個整數，不要填寫多餘内容。
這題對我來說挺有難度。需要花些時間琢磨。
想到思路之後就好做了，給了個無邊無際的圖，還讓統計10億次，簡單模拟用表格幾次過程，發現資料毫無規律的增長，而且圖的範圍有限，耗時還麻煩。換條思路：
（1）如果增長毫無規律，還讓模拟10億次，這是不可能的，是以一定存在規律。
（2）無邊無際的圖，表格不适用，而且還分八個方向，連結清單也應該夠嗆，那就不要用結構去模拟了！！
下面代碼采用一個細胞類，類記憶體放自己的坐标。根據題目要求，我們隻需要處理活細胞以及與活細胞周圍死細胞。
是以用一個單獨的清單存放活細胞即可。查找活細胞友善，查找活細胞周圍的死細胞時，可以通過活細胞坐标，計算出周圍細胞坐标，然後判斷目前活細胞清單中是否含有這個細胞，表中沒有的話說明這個細胞是死細胞。
有了這個邏輯，然後就可以按要求處理活細胞以及其周圍的死細胞了。處理之後得到的是新一代活細胞，前一個活細胞清單就沒用了，隻記錄一下每一代數量，将新一代活細胞作為一個新的活細胞表，重複上述過程。
代碼如下：
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
List<Cell> alivelist=new ArrayList<Cell>(); //求存活細胞
List<Integer> numlist=new ArrayList<Integer>(); //存每代結果，用于觀察
List<Cell> templist; //臨時存儲
int[] dx= {-1,0,1,-1,1,-1,0,1};//橫 dy與dx一一對應表示方向
int[] dy= {-1,-1,-1,0,0,1,1,1};//豎
//細胞類
class Cell{
int x,y;//x橫，y縱
public Cell(int x1,int y1) {
this.x=x1;
this.y=y1;
}
//這裡重寫一個equals()，用于List類内部調用
//後面用到list.contains(cell),實質上是用cell自身的equals與list每個元素比較
//是以這裡可以按需要自定義，隻要兩個類的x,y一樣就可以看做相同
@Override
public boolean equals(Object object) {
Cell c=(Cell)object;
return this.x==c.x&&this.y==c.y;
}
}
public Main() {
Scanner sn = new Scanner(System.in);
int x=38,y=11;
//每讀一行，就轉換一行
for (int i = 0; i < y; i++) {
String str=sn.nextLine().trim();
for (int j = 0; j < x; j++) {
//将活細胞存放
if(str.charAt(j)=='X')alivelist.add(new Cell(j, i));
}
}
//記錄初始活細胞總數
numlist.add(alivelist.size());
//開始測試300代進行檢視規律
for(int count=0;count<300;count++) {
//臨時清單，用于存放産生的下一代
templist=new ArrayList<Cell>();
//周遊所有活細胞進行處理
for(Cell c:alivelist) {
deal(c);
}
//收集新一代的細胞數
numlist.add(templist.size());
//将新一代作為基礎，開始下一代
alivelist=templist;
}
//展示每一代資料觀察
for(int i=0;i<numlist.size();i++) {
System.out.print(numlist.get(i)+"\t");
if((i+1)%10==0)System.out.println();
}
System.out.println();
//展示增量檢視資料資訊
for(int i=1;i<numlist.size();i++) {
System.out.print((numlist.get(i)-numlist.get(i-1))+"\t");
if(i%10==0)System.out.println();
}
}
//處理細胞
public void deal(Cell cell) {
int count = 0;
//周遊cell周圍細胞
for(int i=0;i<8;i++) {
Cell cell2=new Cell(cell.x+dx[i], cell.y+dy[i]);
if(alivelist.contains(cell2)) {//統計活的
count++;
}else if(!templist.contains(cell2)) {//檢視死細胞是否滿足複活條件，進行複活加入臨時清單
int count2=0;
for(int j=0;j<8;j++) if(alivelist.contains(new Cell(cell2.x+dx[j], cell2.y+dy[j])))count2++;
if(count2==3)templist.add(cell2);
}
}
//滿足條件加入臨時清單
if (count==2||count==3) {
templist.add(cell);
}
}
public static void main(String[] args) {
new Main();
}
}
輸出結果：
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
我們可以看到：前一段亂七八糟的數字是每一代的活細胞總數，後一段是每兩代之間的增量
顯然後一段是（這裡特意輸出一行10個）每3行一循環，也就是每30個一循環。
那有了這個結果我們就很容易把結果計算出來。
答案：166666713
代碼：
public class Calculate{
//一次循環變化量
int[] num= {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};
public Calculate() {
long a=1000000000;
long re=a/num.length;//求出來倍數，簡化計算
long remainder=a%num.length;//求出來餘數單獨處理
long sum=0;//累計和
//求出一次循環的增量，結果是5
for(int b:num) {
sum+=b;
}
//5乘以re個循環
sum=sum*re;
//餘數重新按一次循環處理
for(int i=0;i<remainder;i++) {
sum+=num[i];
}
//加上初始值
sum+=36;
System.out.println(sum);
}
public static void main(String[] args) {
new Calculate();
}
} 
