枚举的应用：熄灯问题&讨厌的青蛙

1.枚举的基本思想 1.枚举应用举例： Q：寻找小于N的最大素数(素数（质数）：除了1和本身，不能被其他数整除的数) N-1？     N-2？     N-3... 2.枚举的定义： 从可能的答案中有规律地一一地去列举猜测（检验）。 3.枚举技巧： 1.减小搜索空间， 及早 排除错误的答案（例如偶数不可能是素数，所以枚举素数要在奇数中找） 2.缩小变量空间，尽量减小规模（原版：素数不能被整数整除-->优化版：素数不能被其他素数整除(不包括1和本身)） 3.合适的搜索顺序，这个顺序的选择要看条件，例如最大数还是最小数。 2.熄灯问题 1.题目 当按下一个按钮后, 该按钮以及周围位置(上边, 下边, 左 边, 右边)的灯都会改变一次（ 如果灯原来是点亮的, 就会被熄灭） 同时按几个按钮效果就会相互抵消 问题： 请你写一个程序, 确定需要按下哪些按钮, 恰好使得所 有的灯都熄灭 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。（所以用%计算）      5.当所有的数组存好之后，取出最后一列的上左右中按钮情况，判断与之前灯亮的关系，如果两者不相等，说明最终灯的状态是亮的，一旦有亮的出现，马上返回错误。 （把核心步骤装到一个方法中） 4.小结思路 A 获取灯亮情况 调用B方法，枚举出不同的第一行 输出所得到的数组 B 二进制的枚举第一行操作情况 调用C方法，把枚举值传过去，根据返回结果，更换第一行 C 通过第一行获取其他行的操作情况 验证最后一行与与灯亮的关系是否为灯灭，返回结果 5.java代码实现 package Test; import java.util.Scanner; /*枚举   熄灯问题  * 当按下一个按钮后, 该按钮以及周围位置(上边, 下边, 左 边, 右边)的灯都会改变一次（ 如果灯原来是点亮的, 就会被熄灭）  * */ public class Test {      //检测排错！！！ static 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 0 1 0 0 1 1 1 0 0 1 0 0 1 1 0 0 1 0 1 0 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.多项干扰：可能会有多只青蛙从稻田穿越 问题： 在各条青蛙行走路径中, 踩踏水稻最多的那一条上, 有多 少颗水稻被踩踏 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，则归为0 B X从小到大，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