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