.png)
同時按幾個按鈕效果就會相互抵消
.png)
問題： 請你寫一個程序, 確定需要按下哪些按鈕, 恰好使得所 有的燈都熄滅2.解題1.輸入 要解決的案例數(shù) 0 1 0 1...燈情況（1亮起，0不亮）2.輸出 0 1 0 1...操作情況（1按下，0不按）3.分析 不同行的燈可以相互影響， 對第1行中每盞點亮的燈, 按下第2行對應的按鈕, 就 可以熄滅第1行的全部燈 如此重復下去, 可以熄滅第1, 2, 3, 4行的全部燈 第一想法：將所有按鈕狀態(tài)一一枚舉，判斷最后是否全滅 （但是可能性有2^30可能，會超時） 燈最后的是亮是按取決于兩個因素：1.當前行的按鈕情況 2.下一行的按鈕情況其他行根本就不會影響當前行的燈，所以第一行的按鈕是沒法預測的（隨機的），當?shù)谝恍械陌粹o情況確定之后，下一行就是唯一的了，依次類推下下行也是唯一的。所以我們要遍歷的就是第一行的隨機情況。 而判斷是否全滅，就是當最后一行熄滅了前一行的所有燈之后，最后一行如果剛好全滅，說明所有的燈都熄滅了。否則第一行就得換狀態(tài)。 第二想法：將第一行可能性枚舉，下一行將固定，判斷最后一行是否剛好全滅。（第一行的可能性：2^6=64） 優(yōu)化想法：按列來枚舉（第一行的可能性：2^5=32）4.具體實現(xiàn) 1.做兩個數(shù)組，數(shù)組A用來表示燈亮顯示，數(shù)組B用來表示按鈕操作。 2.用六重循環(huán)，遍歷第一行的每個數(shù)的兩種可能。（想要簡介的話，把第一行看做6位的二進制來算：用while來形成二級制的規(guī)律,嘗試一下） 3.優(yōu)化過程：解決0坐標開始和最后一個結束的問題，設立不用0坐標和最后一個的數(shù)組 4.判斷這個燈亮不亮：取決于上面的燈處理之后的狀態(tài)，而上面的燈的處理需要左右上的按鈕和本身狀態(tài)決定（除了第一行是隨機的），所以用上面的四個影響因素（左右上的按鈕和本身狀態(tài)）加起來，如果是偶數(shù)，效果抵消，值為0。（所以用%計算）
.png)
5.當所有的數(shù)組存好之后，取出最后一列的上左右中按鈕情況，判斷與之前燈亮的關系，如果兩者不相等，說明最終燈的狀態(tài)是亮的，一旦有亮的出現(xiàn)，馬上返回錯誤。（把核心步驟裝到一個方法中）4.小結思路A獲取燈亮情況調用B方法，枚舉出不同的第一行輸出所得到的數(shù)組B二進制的枚舉第一行操作情況調用C方法，把枚舉值傳過去，根據(jù)返回結果，更換第一行C通過第一行獲取其他行的操作情況驗證最后一行與與燈亮的關系是否為燈滅，返回結果5.java代碼實現(xiàn)package Test;import java.util.Scanner;/*枚舉 熄燈問題 * 當按下一個按鈕后, 該按鈕以及周圍位置(上邊, 下邊, 左 邊, 右邊)的燈都會改變一次（ 如果燈原來是點亮的, 就會被熄滅） * */public class Test { //檢測排錯！！！static int light[][]=new int[6][8]; //燈亮情況數(shù)組5行6列去外圍(左右頭尾);static int PRess[][]=new int[6][8]; //燈亮情況數(shù)組5行6列去外圍(左右頭尾);public static void main(String[] args) {// A/* * 測試數(shù)據(jù)： *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); //獲取輸入數(shù)組：燈亮情況 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()){ // 輸出所得到的數(shù)組 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("找不到解法"); }}//首行隨機數(shù)方法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方法，把枚舉值傳過去，根據(jù)返回結果，更換第一行 while(!guess(press)){ //執(zhí)行結果不正確時 press[1][1]++; int c=1; //指向的數(shù) 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 //被踩的數(shù)量14棵 2 1 //稻子的坐標 3 4 5 3... （總共14個）2.輸出 7 （單只青蛙踩最多的步數(shù)，沒有輸出為0）3.分析 第一想法：枚舉每一條路徑的情況， 起點可能性*方向可能性*步長可能性=非常多（不可取）當我們確定的想法為前兩個的時候，我們就可以確定步長，步長有兩個，dX是X方向上，dY是Y方向上。確定了步長就可以減少：1.前面需要超過稻田 2.后面沒有超過稻田 第二想法：枚舉兩個點的組合，判斷這兩個點能不能成立。成立的話計算最多步數(shù)。首先獲取行列，稻子坐標，然后排序稻子大小，排序方式我本來是想用ArrayList來存坐標對象，但是這樣做得手動進行位置交換，所以我就想到用TreeSet的方式，這樣就可以自動排序。接下來就對稻子進行一一組合，組合后有一些組合根本就不能存在，像第一步前一步如果在稻田里的話（需要判斷XY，continue掉），還有就是設立最大步數(shù)（初始化為2），如果（最大步數(shù)-1）步的時候到了稻田外（需要判斷兩個，X判斷break，Y判斷continue，因為包含的關系），那也不行。調用步長方法：從這點觸發(fā)，傳dX，dY，能夠走幾步，將返回的步數(shù)賦給最多步最后判斷最多步如果為2，則歸為0步長方法添加步長，添加步數(shù)做while循環(huán)，做判斷坐標沒有越界，就不斷添加步數(shù)4.小結思路A獲取行列數(shù)，被踩數(shù)量，稻子坐標（坐標用對象的方式實現(xiàn)，新建一個類）調用B方法，排序稻子坐標循環(huán)x，y坐標，一個個組合，判斷組合如果符合條件 當?shù)谝徊綔p去步長大于1 大于1與小于稻田長寬，跳過這次循環(huán) 當?shù)谝徊絏+最大步數(shù)（-1）*步長如果越界，跳過整個循環(huán) 當?shù)谝徊結+最大步數(shù)（-1）*步長如果越界，跳過這次循環(huán)（因為屬于子類）調用C方法，獲取最大步數(shù)判斷最大步數(shù)為2，則歸為0BX從小到大，Y從小到大C初始化步數(shù)為2，第一步變?yōu)榈诙剑╔Y）做while循環(huán)，當變化后的xy沒有超過稻田，就不斷把步數(shù)加上去最終返回最大步數(shù)5.代碼實現(xiàn)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; //定義最大步數(shù)為2// A// 獲取行列數(shù)，被踩數(shù)量，稻子坐標（坐標用對象的方式實現(xiàn)，新建一個類） System.out.println("請輸入行，列，被踩稻子數(shù)："); @SuppressWarnings("resource") Scanner input=new Scanner(System.in); r=input.nextInt(); c=input.nextInt(); int desNum=input.nextInt(); //被踩稻子數(shù) 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()); }// 循環(huán)坐標，一個個組合，判斷組合如果符合條件 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;// 當?shù)谝徊綔p去步長大于1 大于1與小于稻田長寬，跳過這次循環(huán) if(pX>=1&&pY>=1){ //前一步在田里面 continue; //跳過這一次循環(huán) }// 當?shù)谝徊絏+最大步數(shù)（-1）*步長如果越界，跳過整個循環(huán) if(al.get(i).x+(max-1)*dX>r){ //判斷如果加上最大步就超過田，跳過循環(huán)i break; }// 當?shù)谝徊結+最大步數(shù)（-1）*步長如果越界，跳過這次循環(huán)（因為屬于子類） if(al.get(i).y+(max-1)*dY>c){ continue; }// 調用B方法，獲取最大步數(shù) int step=Step(al.get(i),dX,dY); if(step>max){ //步數(shù)超過的記錄起來 max=step; } } }// 判斷最大步數(shù)為2，則歸為0 if(max==2){ max=0; } System.out.println(max); }//獲取最大步數(shù) private static int Step(Sign step,int dX,int dY){// B// 做while循環(huán)，當變化后的xy沒有超過稻田，就不斷把步數(shù)加上去 int max=0; int x=step.x; //不能用對象，對象只是地址符，重量級 int y=step.y; while(x<=c&&y<=r){ //判斷沒有超出田地時,可以等于田地。注意邊緣數(shù)據(jù) //判斷是不是踩倒的稻草 if(!isDao(y,x)){ //新產(chǎn)生的對象不能和舊的比較 max=0; break; } x+=dX; y+=dY; max++; //加1次就多一步，但是最后一次是在田外的，所以抵消第一步 }// 最終返回最大步數(shù) 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對數(shù)據(jù)進行比較 int x; int y; Sign(int y,int x) { //構造方法賦值 this.x=x; this.y=y; } @Override //定義排序規(guī)則 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新聞熱點
疑難解答
