回溯法解决八人过河问题

一、题目描述

一家六口,一个爸爸,一个妈妈,俩儿子,俩女儿,还有一个警察,一个坏蛋,过一条河,爸爸不在妈妈伤害儿子,妈妈不在爸爸伤害女儿,警察不在坏蛋伤害一家六口,只有妈妈爸爸警察会开船,一次只能过两个人,只有一艘船。 为怎样过河才能使他们安全度过

二、大脑解题思路

我们当然是一个一个试试啦,百度百科解题如下

三、程序解题

其实人解这道题和计算机解答是一样的,就是往过一个一个的试试,只不过是人的思维太活跃的一时半会找不到思考顺序的规律,捋一捋就清楚了,下面是java代码 (复制即可运行)

public class Test {
    //1  1  1   1   1   1   1   1
    //警察犯人爸爸  妈妈    男1 男2   女1  女2
    public static int[] c = new int[]{0,2,3};
    public static void main(String[] args) {
        //a,b两个数组,a代表河这边的人存在为1,不存在为0,本来一组就可以了,但是河对岸的人还要往过来走
        //记录河对岸的测试情况,所以采用两个数组
        int[] a = new int[]{1,1,1,1,1,1,1,1};
        int[] b = new int[]{0,0,0,0,0,0,0,0};
        Boat(a, b,-1,-1);   
    }
    //将题的条件理出来,判断是否方法可行
    public static boolean ifsuccess(int a[],int b[]){
        if(a[0]==0&&a[1]==1){
            for(int i=2;i<8;i++){
                if(a[i]>0){
                    return false;
                }
            }
        }
        if(a[2]==1){
            if(a[3]!=1){
                for(int i=6;i<8;i++){
                    if(a[i]==1){
                        return false;
                    }
                }
            }
        }

        if(a[3]==1){
            if(a[2]!=1){
                for(int i=4;i<6;i++){
                    if(a[i]==1){
                        return false;
                    }
                }
            }
        }


        if(b[0]==0&&b[1]==1){
            for(int i=2;i<8;i++){
                if(b[i]>0){
                    return false;
                }
            }
        }
        if(b[2]==1){
            if(b[3]!=1){
                for(int i=6;i<8;i++){
                    if(b[i]==1){
                        return false;
                    }
                }
            }
        }

        if(b[3]==1){
            if(b[2]!=1){
                for(int i=4;i<6;i++){
                    if(b[i]==1){
                        return false;
                    }
                }
            }
        }

        return true;

    }

    //河这边的往过走
    public static void Boat(int a[],int b[],int a1,int b1){
        System.out.println("--------");
        for(int i = 0;i<3;i++){
            if(a[c[i]]!=0){
                a[c[i]]=0;
                b[c[i]]=1;

                for(int j=0;j<8;j++){
                    if(a[j]!=0&&(c[i]!=a1||j!=b1)&&(c[i]!=b1||j!=a1)){
                        a[j]=0;
                        b[j]=1;
                        //如果满足条件就开始从河对岸往回走
                        if(ifsuccess(a, b)){
                            print(a, b);
                            Boatreturn(a, b,c[i],j);
                        }
                        //不成功继续判断,回溯
                        a[j]=1;
                        b[j]=0;
                    }

                }
                a[c[i]]=1;
                b[c[i]]=0;  
            }
        }
        return;
    }
public static void Boatreturn(int a[],int b[],int a1,int b1){

        for(int i = 0;i<3;i++){
            if(b[c[i]]!=0){
                b[c[i]]=0;
                a[c[i]]=1;
                if(ifsuccess(a, b)){
                    print(a, b);
                    Boat(a, b,c[i],-1);
                }
                for(int j=0;j<8;j++){
                    if(b[j]!=0&&(c[i]!=a1||j!=b1)&&(c[i]!=b1||j!=a1)){
                        b[j]=0;
                        a[j]=1;
                        if(ifsuccess(a, b)){
                            print(a, b);
                            Boat(a, b,c[i],j);
                        }
                        b[j]=1;
                        a[j]=0;
                    }


                }
                b[c[i]]=1;
                a[c[i]]=0;

            }
        }


        return;
    }



   public static void print(int a[],int b[]){
       //判断是否全部过河
       int flag = 0;
       for (int i : a) {
           if(i==0)
           flag++;
       }
       for (int i : b) {
            System.out.print(i);
       }
       if(flag==8){
           System.out.println("成功---------");
           for (int i = 0; i < b.length; i++) {
            b[i]=0;
        }
           for (int i = 0; i < a.length; i++) {
                a[i]=1;
            }
       }
       System.out.println();
   }



}

程序运行只出现一种对的结果,答案是一种以上,如果有什么好的想法或方法可以一起留言讨论

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏web前端教室

JS本身并不难,为什么前端学起来感觉很难?

image.png 这个问题我就不等大家的回答了,相信大家也明白,我并不是闲的无聊这么问。JS本身语法并不难,它困难的地方在哪呢?主要在于以下几点: ? 1,怎...

36490
来自专栏Linyb极客之路

浅谈代码结构的设计

之前无论是作为开发还是测试,习惯性的觉得,别人提供了什么功能,就用什么样的功能,这样做天经地义。然而,在自己的架构设计过程中,如果有了这样额思维,很容易让自己的...

8520
来自专栏企鹅号快讯

谷歌大牛的编程建议和技巧

编译:伯乐在线/PJing 【伯乐在线导读】:Rob Pike 是谷歌公司最著名的软件工程师之一,曾是贝尔实验室 Unix 开发团队成员,Plan 9 操作系统...

26090
来自专栏java学习

每日一练(2017/5/23)

Java基础 | 数据库 | Android | 学习视频 | 学习资料下载 课前导读 ●回复"每日一练"获取以前的题目! ●答案公布时间:为每期发布题目的第二...

27670
来自专栏Java Web

Java 8——行为参数化

前言 《Java8实战》不得不说是一本好书,捧起来看起来就兴奋得不想放下,其中介绍的函数式编程实在是太令人兴奋了,不仅仅大大提高了代码的可读性,而且提高了代码的...

47370
来自专栏AzMark

Python字符串、循环及练习

28140
来自专栏WindCoder

Python学习四周小结-测试题篇

自从发现网易云课堂的计算机课程系列中有Python后就报名听了下,作为新人很快被其模式所吸引了,同时发现自己之前自学时的不足,那时由于没有作业等,自己只是根据《...

36620
来自专栏AI科技大本营的专栏

学Java还是Python?一张图告诉你!

Java 和 Python 一直都是两种很火很强大的编程语言,对于刚开始起步学习编程的同学来说,会迷惑且最经常问的问题是,我该学 Java 还是 Python,...

42370
来自专栏数据结构与算法

主定理与时间复杂度

只好在网上找了一篇看起来不怎么严谨的博客,不过算出来的是对的?那就默认是对的吧qwq

37710
来自专栏web编程技术分享

你可曾见过如此简单粗暴的JavaScript解说 -- js脚本运行机制

32560

扫码关注云+社区

领取腾讯云代金券