.png)
同時按幾個按鈕效果就會相互抵消
.png)
問題： 請你寫一個程序, 確定需要按下哪些按鈕, 恰好使得所 有的燈都熄滅2.解題1.輸入 要解決的案例數 0 1 0 1...燈情況（1亮起，0不亮）2.輸出 0 1 0 1...操作情況（1按下，0不按）3.分析 不同行的燈可以相互影響， 對第1行中每盞點亮的燈, 按下第2行對應的按鈕, 就 可以熄滅第1行的全部燈 如此重復下去, 可以熄滅第1, 2, 3, 4行的全部燈 第一想法：將所有按鈕狀態一一枚舉，判斷最后是否全滅 （但是可能性有2^30可能，會超時） 燈最后的是亮是按取決于兩個因素：1.當前行的按鈕情況 2.下一行的按鈕情況其他行根本就不會影響當前行的燈，所以第一行的按鈕是沒法預測的（隨機的），當第一行的按鈕情況確定之后，下一行就是唯一的了，依次類推下下行也是唯一的。所以我們要遍歷的就是第一行的隨機情況。 而判斷是否全滅，就是當最后一行熄滅了前一行的所有燈之后，最后一行如果剛好全滅，說明所有的燈都熄滅了。否則第一行就得換狀態。 第二想法：將第一行可能性枚舉，下一行將固定，判斷最后一行是否剛好全滅。（第一行的可能性：2^6=64） 優化想法：按列來枚舉（第一行的可能性：2^5=32）4.具體實現 1.做兩個數組，數組A用來表示燈亮顯示，數組B用來表示按鈕操作。 2.用六重循環，遍歷第一行的每個數的兩種可能。（想要簡介的話，把第一行看做6位的二進制來算：用while來形成二級制的規律,嘗試一下） 3.優化過程：解決0坐標開始和最后一個結束的問題，設立不用0坐標和最后一個的數組 4.判斷這個燈亮不亮：取決于上面的燈處理之后的狀態，而上面的燈的處理需要左右上的按鈕和本身狀態決定（除了第一行是隨機的），所以用上面的四個影響因素（左右上的按鈕和本身狀態）加起來，如果是偶數，效果抵消，值為0。（所以用%計算）
.png)
5.當所有的數組存好之后，取出最后一列的上左右中按鈕情況，判斷與之前燈亮的關系，如果兩者不相等，說明最終燈的狀態是亮的，一旦有亮的出現，馬上返回錯誤。（把核心步驟裝到一個方法中）4.小結思路A獲取燈亮情況調用B方法，枚舉出不同的第一行輸出所得到的數組B二進制的枚舉第一行操作情況調用C方法，把枚舉值傳過去，根據返回結果，更換第一行C通過第一行獲取其他行的操作情況驗證最后一行與與燈亮的關系是否為燈滅，返回結果5.java代碼實現package Test;import java.util.Scanner;/*枚舉 熄燈問題 * 當按下一個按鈕后, 該按鈕以及周圍位置(上邊, 下邊, 左 邊, 右邊)的燈都會改變一次（ 如果燈原來是點亮的, 就會被熄滅） * */public class Test { //檢測排錯?。。tatic int light[][]=new int[6][8]; //燈亮情況數組5行6列去外圍(左右頭尾);static int PRess[][]=new int[6][8]; //燈亮情況數組5行6列去外圍(左右頭尾);public static void main(String[] args) {// A/* * 測試數據： *0 1 1 0 1 01 0 0 1 1 10 0 1 0 0 11 0 0 1 0 10 1 1 1 0 0*/ System.out.println("請輸入燈亮情況"); Scanner input=new Scanner(System.in); //獲取輸入數組：燈亮情況 for(int i=1;i<light.length;i++){ //行 for(int j=1;j<light[i].length-1;j++){ //列 light[i][j]=input.nextInt(); } } System.out.println("輸入完畢"); //調用B方法，枚舉出不同的第一行 if(FirstRow()){ // 輸出所得到的數組 for(int i=1;i<press.length;i++){ //行 for(int j=1;j<press[i].length-1;j++){ //列 System.out.print(press[i][j]+" "); } System.out.println(); //換行 } }else{ System.out.println("找不到解法"); }}//首行隨機數方法static boolean FirstRow(){//B//二進制轉換器 for(int i=0;i<light.length;i++){ //行 for(int j=0;j<light[i].length;j++){ //列 press[i][j]=0; //初始化所有按鈕為0，包括外圍 } }//調用C方法，把枚舉值傳過去，根據返回結果，更換第一行 while(!guess(press)){ //執行結果不正確時 press[1][1]++; int c=1; //指向的數 while(press[1][c]>1){ //檢驗進位器:從第一位開始檢查，一大于1就進一位 press[1][c]=0; c++; press[1][c]++; if(press[1][press[1].length-2]>1){ //說明都超位了還找不到 return false; //找不到了 } } } return true; //找到了按鈕}static boolean guess(int press[][]) { //C //通過第一行獲取其他行的操作情況 for(int i=2;i<press.length;i++){ //從第二列到最后一列 for(int j=1;j<press[i].length-1;j++){ //該列的每一項 press[i][j]=(light[i-1][j]+press[i-1][j]+press[i-1][j-1]+press[i-1][j+1]+press[i-2][j])%2; //該項的按鈕操作情況取決于上個按鈕操作后的情況 } } //驗證最后一行與與燈亮的關系是否為燈滅，返回結果 for(int i=1;i<press[press.length-1].length-1;i++){ if((press[press.length-1][i]+press[press.length-1][i-1]+press[press.length-1][i+1]+press[press.length-2][i])%2!=light[press.length-1][i]){ //不相等說明最后亮 return false; } } return true;}}3.討厭的青蛙1.題目1.直線路徑：每只青蛙總是沿著一條直線跳躍稻田2.相同間距：且每次跳躍的距離都相同3.有進有出：而青蛙總是從稻田的一側跳進稻田, 然后沿著某條直線穿 越稻田, 從另一側跳出去4.多項干擾：可能會有多只青蛙從稻田穿越
.png)
問題： 在各條青蛙行走路徑中, 踩踏水稻最多的那一條上, 有多 少顆水稻被踩踏2.解題1.輸入 6 7 //6行7列 14 //被踩的數量14棵 2 1 //稻子的坐標 3 4 5 3... （總共14個）2.輸出 7 （單只青蛙踩最多的步數，沒有輸出為0）3.分析 第一想法：枚舉每一條路徑的情況， 起點可能性*方向可能性*步長可能性=非常多（不可?。┊斘覀兇_定的想法為前兩個的時候，我們就可以確定步長，步長有兩個，dX是X方向上，dY是Y方向上。確定了步長就可以減少：1.前面需要超過稻田 2.后面沒有超過稻田 第二想法：枚舉兩個點的組合，判斷這兩個點能不能成立。成立的話計算最多步數。首先獲取行列，稻子坐標，然后排序稻子大小，排序方式我本來是想用ArrayList來存坐標對象，但是這樣做得手動進行位置交換，所以我就想到用TreeSet的方式，這樣就可以自動排序。接下來就對稻子進行一一組合，組合后有一些組合根本就不能存在，像第一步前一步如果在稻田里的話（需要判斷XY，continue掉），還有就是設立最大步數（初始化為2），如果（最大步數-1）步的時候到了稻田外（需要判斷兩個，X判斷break，Y判斷continue，因為包含的關系），那也不行。調用步長方法：從這點觸發，傳dX，dY，能夠走幾步，將返回的步數賦給最多步最后判斷最多步如果為2，則歸為0步長方法添加步長，添加步數做while循環，做判斷坐標沒有越界，就不斷添加步數4.小結思路A獲取行列數，被踩數量，稻子坐標（坐標用對象的方式實現，新建一個類）調用B方法，排序稻子坐標循環x，y坐標，一個個組合，判斷組合如果符合條件 當第一步減去步長大于1 大于1與小于稻田長寬，跳過這次循環 當第一步X+最大步數（-1）*步長如果越界，跳過整個循環 當第一步Y+最大步數（-1）*步長如果越界，跳過這次循環（因為屬于子類）調用C方法，獲取最大步數判斷最大步數為2，則歸為0BX從小到大，Y從小到大C初始化步數為2，第一步變為第二步（XY）做while循環，當變化后的xy沒有超過稻田，就不斷把步數加上去最終返回最大步數5.代碼實現package Test;import java.util.ArrayList;import java.util.Iterator;import java.util.Scanner;import java.util.TreeSet;public class Test { static int c; static int r; static ArrayList<Sign> al; public static void main(String[] args) { int max=2; //定義最大步數為2// A// 獲取行列數，被踩數量，稻子坐標（坐標用對象的方式實現，新建一個類） System.out.println("請輸入行，列，被踩稻子數："); @SuppressWarnings("resource") Scanner input=new Scanner(System.in); r=input.nextInt(); c=input.nextInt(); int desNum=input.nextInt(); //被踩稻子數 System.out.println("請輸入被踩稻子的坐標："); //記錄稻子坐標 TreeSet<Sign> ts=new TreeSet<Sign>(); //用TreeSet的自動排序 for(int i=0;i<desNum;i++){ ts.add(new Sign(input.nextInt(), input.nextInt())); //y&x } al=new ArrayList<Sign>(); //將TreeSet轉存到ArrayList Iterator<Sign> it=ts.iterator(); while(it.hasNext()){ al.add(it.next()); }// 循環坐標，一個個組合，判斷組合如果符合條件 for(int i=0;i<al.size();i++){ for(int j=i+1;j<al.size();j++){ //組合跟順序無關，所以用i+1 int dX=al.get(j).x-al.get(i).x; //xd:x的跨距，后面的減前面的 int dY=al.get(j).y-al.get(i).y; int pX=al.get(i).x-dX; //得到第一步的前一步，用于驗證 int pY=al.get(i).y-dY;// 當第一步減去步長大于1 大于1與小于稻田長寬，跳過這次循環 if(pX>=1&&pY>=1){ //前一步在田里面 continue; //跳過這一次循環 }// 當第一步X+最大步數（-1）*步長如果越界，跳過整個循環 if(al.get(i).x+(max-1)*dX>r){ //判斷如果加上最大步就超過田，跳過循環i break; }// 當第一步Y+最大步數（-1）*步長如果越界，跳過這次循環（因為屬于子類） if(al.get(i).y+(max-1)*dY>c){ continue; }// 調用B方法，獲取最大步數 int step=Step(al.get(i),dX,dY); if(step>max){ //步數超過的記錄起來 max=step; } } }// 判斷最大步數為2，則歸為0 if(max==2){ max=0; } System.out.println(max); }//獲取最大步數 private static int Step(Sign step,int dX,int dY){// B// 做while循環，當變化后的xy沒有超過稻田，就不斷把步數加上去 int max=0; int x=step.x; //不能用對象，對象只是地址符，重量級 int y=step.y; while(x<=c&&y<=r){ //判斷沒有超出田地時,可以等于田地。注意邊緣數據 //判斷是不是踩倒的稻草 if(!isDao(y,x)){ //新產生的對象不能和舊的比較 max=0; break; } x+=dX; y+=dY; max++; //加1次就多一步，但是最后一次是在田外的，所以抵消第一步 }// 最終返回最大步數 return max; }//判斷是不是踩倒 private static boolean isDao(int y,int x){ boolean flag=false; for(int i=0;i<al.size();i++){ if(al.get(i).y==y){ if(al.get(i).x==x){ flag=true; } } } return flag; }}//新建坐標類class Sign implements Comparable<Sign>{ //繼承Comparable對數據進行比較 int x; int y; Sign(int y,int x) { //構造方法賦值 this.x=x; this.y=y; } @Override //定義排序規則 public int compareTo(Sign o) { if(this.x>o.x){ return 1; }else if(this.x<o.x){ return -1; }else{ if(this.y>o.y){ return 1; }else if(this.y<o.y){ return -1; }else{ return 0; } } }}資料來自：https://www.coursera.org/learn/suanfa-jichu/lecture/rfoj5/mei-ju-de-ji-ben-si-xiang新聞熱點
疑難解答
