【算法编程】过河问题

    今天偶尔想到了过河问题。记得读小学六年级的时候第一次接触到这个问题--六个老虎过河问题(百度上有详细介绍，本文解决的是一个简单的问题，下一篇文章中将讨论该问题)，当时都是从逻辑思维的方法得到正确的解决方法。本文介绍了普遍适用该类问题的方法以及该方法的改进方法，下一篇文章将介绍问题的变型及解法。

向量法（人、狗、鸡、米过河问题）

    问题描述：某人带狗、鸡、米用船来过河，只有人会划船(好像是废话，后面问题我们还会假设动物也会划船),另外至多还能载一物，当人不在时，狗要吃鸡(有人可能会质疑：狗吃鸡？，但是我看到的是狗和猫都吃小鸡)，鸡吃米。问人、狗、鸡、米怎么过河？

    我们用一个向量来表示人、狗、鸡、米所处的状态，例如：(1 1
1 1)表示人、狗、鸡、米都在左岸，则对应的(0 0 0 0)表示人、狗、鸡、米都在右岸。这些向量我们称为状态向量，但是由于问题的条件限制，有些状态是允许的，而有些状态是不允许的，例如(0
1 1 1)表示人不在左岸，显然是不允许的。我们可以穷举出所有允许的状态：

        (1 1 1 1)     
  (0 0 0 0)    

        (1 1 1 0)     
  (0 0 0 1)

        (1 1 0 1)     
  (0 0 1 0)

        (1 0 1 1)     
  (0 1 0 0)

        (1 0 1 0)     
  (0 1 0 1)

从上面的允许状态中，我们可以发现规律如下：

    当人在时（也就是第一位为1时），不能有相邻的0，例如(1 1 0 0)是不允许的

    当人不在时(也就是第一个为0时)，不能有相邻的1 ，例如(0 1 1 0)是不允许的

    我们将船的一次运载也用向量表示，例如(1 1 0 0)表示人和狗在船上。由于只有人会划船，则允许的运算向量为：

        (1 1 0 0)     
  (1 0 1 0)        (1 0 0 1) 
      (1 0 0 0)

因此我们可以将一次过河过程看成是一个状态向量与一个运算向量的异或运算（模2加运算：1+1=0 1+0=1 0+0=0）。根据上述的向量法的描述，我们可以将问题简化成：将状态(1 1 1 1)经过奇数次与运算向量运算，变成状态为(0 0 0 0)的状态转移过程。下面是过河的图解过程：

          开始状态     
          船上状态     
           结果状态

 1       (1
1 1 1)    ------>   
(1 0 1 0)     ------>  
  (0 1 0 1)

 2       (0 1 0 1)    ------> 
  (1 0 0 0)     ------> 
   (1 1 0 1)

 3       (1 1 0 1)    ------> 
  (1 0 0 1)     ------>    
(0 1 0 0)

 4       (0 1 0 0) 
  ------>    (1
0 1 0)     ------>     (1 1 1 0)

 5       (1 1 1 0) 
  ------>    (1
1 0 0)     ------>     (0
0 1 0)

 6       (0 0 1 0) 
  ------>    (1
0 0 0)     ------>     (1 0 1 0)

 7       (1 0 1 0) 
  ------>    (1
0 1 0)     ------>   
 (0 0 0 0)  

奇数次：去河对岸

偶数次：回河这边

注意事项：

    在第3次过河时，开始状态为(1 1 0 1)，如果船上状态为(1 1 0 0),则结果状态为(0 0 0 1)，然后经过船上状态(1 0 0 1),结果状态为(1 0 0 0),然后经过船上状态(1 0 0 0)，就可以完成任务(总共5次过河)。但是这里存在问题：当开始状态为(0
0 0 1)，船上状态不可能为(1 0 0 1)。因为开始状态(0 0 0 1)表示只有米在左岸，船上状态(1 0 0 1)表示人和米在船上，这是不可能的！因此船上状态的选择是有限制的。奇数时，开始状态为1的位置，船上对应位置才可以为1；偶数时，开始状态为0的位置，船上对应的位置才可以为0.通俗的说：奇数时，是将有的东西运到河对岸，偶数时，是将河对岸的东西(河这边没有)运到河这边。这些数学的表述可能太麻烦，我举例说明：奇数时，当河这边只有人、狗、米，我们可以从选择人、狗上船或则人、米上船，而不能选择人、鸡上船（鸡在对岸）;当偶数次数时，河这边是狗、河对岸则是人、鸡、米，我们可以人、鸡或则人、米回到河这边，而不能选择人、狗过河。

算法实现：

    上面的实现可用matlab或则c来实现。若用matlab来实现，则那些状态向量以及状态间的异或运算比较容易表示；若用c来实现，则用时较短。两者的难点在于注意事项中的船上变量的选取问题。因此这种方法不适合用计算机实现，在状态变量较少的情况下，我们可以直接用手工进行运算的方法来得到结果(大家可以试试)。

改进型算法---图论法

    算法思路：将10个状态向量用10个点表示，将这10个状态向量分别与可行的运算向量进行运算，如果结果向量仍为允许的状态向量，则两者间连一条线，从而构成了一个图的问题。我们的目标是找到一条可以从状态(1 1 1 1)到状态(0 0 0 0)的通路。下面是我运算得到的图:



注意：图中的标号用于表示对应的状态


具体算法实现如下：

1、Dijkstra算法

#include<stdio.h>
#define M 20//边数
#define N 10//顶点数
#define MAX 10000
void Dijkstra(int v, int dist[][N],int D[N],int p[N],int s[N]) ;
int flag[N]={0};
int flag1=0;
int flag2=0;
typedef struct
{
    int startvex;
    int endvex;
    int length;
}edge;//边的结构体
edge T[M];
void main()
{
    int dist[N][N]={{0,MAX,MAX,MAX,MAX,1,MAX,MAX,MAX,MAX},//图的邻接矩阵
                    {MAX,0,MAX,MAX,MAX,MAX,1,1,MAX,MAX},
                    {MAX,MAX,0,MAX,MAX,1,1,MAX,1,MAX},
                    {MAX,MAX,MAX,0,MAX,MAX,MAX,1,1,MAX},
                    {MAX,MAX,MAX,MAX,0,MAX,MAX,1,MAX,1},
                    {1,MAX,1,MAX,MAX,0,MAX,MAX,MAX,MAX},
                    {MAX,1,1,MAX,MAX,MAX,0,MAX,MAX,MAX},
                    {MAX,1,MAX,1,1,MAX,MAX,0,MAX,MAX},
                    {MAX,MAX,1,1,MAX,MAX,MAX,MAX,0,MAX},
                    {MAX,MAX,MAX,MAX,1,MAX,MAX,MAX,MAX,0}
    };
    int D[N]={0};
    int p[N]={0};
    int s[N]={0};
    int num=0;
    Dijkstra(0,dist,D, p,s) ;//0表示从状态(1111)开始
}
 void Dijkstra(int v, int dist[][N],int D[N],int p[N],int s[N])
 {     int i, j, k, v1, min, max=10000, pre;     /* Max中的值用以表示dist矩阵中的值*/
    v1=v;
    for( i=0; i<N; i++)              /* 各数组进行初始化*/
    {    D[i]=dist[v1][i];
        if( D[i] != MAX )  p[i]= v1+1;
        else p[i]=0;
        s[i]=0;
    }
    s[v1]=1;                          /* 将源点送U */
      for( i=0; i<N-1; i++)      /* 求源点到其余顶点的最短距离*/
    {    min=10001;    /* min>max, 以保证值为的的的的顶顶顶顶点点点点也也也也能能能能加加加加入入入入U */
        for( j=0; j<N-1; j++)
              if ( ( !s[j] )&&(D[j]<min) )          /* 找出到源点具有最短距离的边*/
                  {min=D[j];
                        k=j;
                     }
                s[k]=1;  /* 将找到的顶点k送入U */
    for(j=0; j<N; j++)
     if ( (!s[j])&&(D[j]>D[k]+dist[k][j]) ) /* 调整V－U中各顶点的距离值*/
        {D[j]=D[k]+dist[k][j];
        p[j]=k+1;                      /* k是j的前趋*/
                }
            }                               /*  所有顶点已扩充到U中*/
            for( i=0; i<N; i++)
            {
                printf(" %d : %d ", D[i], i);
                pre=p[i];
            while ((pre!=0)&&(pre!=v+1))
            {    printf ("<- %d ", pre-1);
                pre=p[pre-1];
            }
            printf("<-%d \n", v);
        }
}

结果显示如下：

从上图的第七行可知，从标号为1的状态到标号为10的状态所要经过的过程为(数组下标是从0开始的)：

    1---6---3---7---2---8---5---10

    

2、通过每对顶点之间的最短路径算法实现：

#include<stdio.h>
#define N 10 //顶点个数
#define MAX 10000
void Floyd(int dist[N][N],int A[N][N],int path[N][N])
{
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
            for(int k=0;k<N;k++)
            {
                /*if(A[i][j]>(A[i][k]+dist[k][j]))//方法一：计算每一次矩阵
                {
                    A[i][j]=(A[i][k]+dist[k][j]);
                    path[i][j]=path[k][j];
                }*/
                if(A[i][j]>(A[i][k]+A[k][j]))//方法二:计算的幂次矩阵
                {
                    A[i][j]=(A[i][k]+A[k][j]);
                    path[i][j]=path[k][j];
                }
            }
}
void main()
{
    int dist[N][N]={{0,MAX,MAX,MAX,MAX,1,MAX,MAX,MAX,MAX},//图的邻接矩阵
                    {MAX,0,MAX,MAX,MAX,MAX,1,1,MAX,MAX},
                    {MAX,MAX,0,MAX,MAX,1,1,MAX,1,MAX},
                    {MAX,MAX,MAX,0,MAX,MAX,MAX,1,1,MAX},
                    {MAX,MAX,MAX,MAX,0,MAX,MAX,1,MAX,1},
                    {1,MAX,1,MAX,MAX,0,MAX,MAX,MAX,MAX},
                    {MAX,1,1,MAX,MAX,MAX,0,MAX,MAX,MAX},
                    {MAX,1,MAX,1,1,MAX,MAX,0,MAX,MAX},
                    {MAX,MAX,1,1,MAX,MAX,MAX,MAX,0,MAX},
                    {MAX,MAX,MAX,MAX,1,MAX,MAX,MAX,MAX,0}
    };
    int A[N][N];
    int path[N][N]={0};//给出两顶点间的路径
    int pre=0;
    for(int i=0;i<N;i++)
        for(int j=0;j<N;j++)
        {
            A[i][j]=dist[i][j];
            if(dist[i][j]!=MAX)
                path[i][j]=i+1;
            else
                path[i][j]=0;
        }

    for(int k=0;k<7;k++)//若用方法一，需循环N-3次，若用方法二，需要循环lg(N-1)次
        Floyd(dist,A,path);
    printf("每对顶点间的最短路径矩阵为：\n");
    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
            printf("%d ",A[i][j]);
        printf("\n");
    }
    printf("\n每对顶点的具体最短路径为：\n");

    for(int i=0;i<N;i++)
    {
        for(int j=0;j<N;j++)
        {
            printf("%d: %d ",A[i][j],j+1);
        pre=path[i][j];
        while((pre!=0)&&(pre!=i+1))
        {
            printf("<- %d ",pre);
            pre=path[i][pre-1];
        }
        printf(" <- %d\n",i+1);
        }
    }
}

结果显示如下：





从上图的最短路径矩阵的第一行第10列可知，从状态1到状态10需要7步，从具体最短路径的第10行可知，所要经过的过程为：

    1---6---3---7---2---8---5---10


两种方法求得的结果相同，我们可以用图形象的表示如下：





通过对比可以发现，图论法实质是在向量法的基础上进行改进的算法，无论是在手动计算还是计算机实现上都比向量法更好。


原文：http://blog.csdn.net/tengweitw/article/details/25296257

作者：nineheadedbird

时间： 2024-12-30 23:31:18

【算法编程】过河问题的相关文章

推荐一个算法编程学习中文社区-51NOD【算法分级，支持多语言，可在线编译】

    最近偶尔发现一个算法编程学习的论坛,刚开始有点好奇,也只是注册了一下.最近有时间好好研究了一下,的确非常赞,所以推荐给大家.功能和介绍看下面介绍吧.首页的标题很给劲,很纯粹的Coding社区....虽然目前人气可能一般,但这里面题目和资源还是比较丰富的,希望给初学者一个帮助. 本文原文地址:[推荐]一个算法编程学习中文社区-51NOD[算法分级,支持多语言,可在线编译] 1.51NOD论坛介绍     该论坛网址:http://www.51nod.com/index.html     论

c++算法编程，急求，谢谢

问题描述 c++算法编程,急求,谢谢 正方形网格中,每个格点有一定数量的宝石.小明从网格左上(0,0)出发, 采集宝石.小明每次横向或竖向移动不超过 ．．．k．个方格后,停下来采集宝石.强迫 症的小明要求每次采集宝石数量不低于上一次,否则宁愿停止采集. 注: 停下来采集宝石后,才能转向: 一次移动不超过 k 步即,可以是 1,2.-k 经过的格点的宝石数量没有要求: 例如 : 对如下网格,网格中的整数为宝石数: 1 2 5 10 11 6 12 12 7 当 k 为 1 时,优值为 37 : k

c语言-请教一个C编程 打印输出图像的算法编程

问题描述 请教一个C编程 打印输出图像的算法编程 解决方案 大概就是这样,建立笛卡尔坐标系. 用point()函数里的嵌套for循环来输出每一个字符,然后把代表坐标的i和j传递给getChar()函数通过坐标来决定输出的是什么字符. 解决方案二: char getChar(int x,int y,int n) { if(x<0) x=-x; if(y<0) y=-y; if(x>y) { if(n-x<=2) return 'x'+n-x; else return '0'+n-x-

CCF CCSP2016：算法编程是最基本、最重要的能力

"湖南卫视超级女声的名气那么大,我也想把这个比赛做成计算机领域里有名气的比赛."这是CCF前理事长.CCF CCSP竞赛委员会主席.清华大学教授郑纬民对CCF CCSP比赛的期盼. 11月26日,首届CCF大学生计算机系统与程序设计竞赛(The Collegiate Computer System & Programming Contest, CCSP)在北京理工大学良乡校区举行.大赛由中国计算机学会(CCF)主办,清华大学等13所著名高校共同发起的.旨在提高高校计算机教育水平

算法-[编程题] 无平方数因数的数

问题描述 [编程题] 无平方数因数的数 如果一个正整数不能被大于1的完全平方数所整除,那么我们就将该数称为无平方数因数的数.例如,靠前的一些无平方数因数的数是{12356710111314151719-}.创建一个class SquareFree,其中包括一个函数getNumber在给定一个int n后,该函数能够返回第n个最小无平方因数的数.请注意这里是从1开始的,那么如果n=1该算法将会返回最小的无平方数因数的数. n 的取值范围为1到1000000000(其中包括1和1000000000)

数据结构算法-农夫过河问题用深度优先遍历和广度优先遍历？

问题描述 农夫过河问题用深度优先遍历和广度优先遍历? 农夫过河问题用深度优先遍历和广度优先遍历的区别?用哪个更好? 解决方案 求解这个问题的最简单的方法是一步一步进行试探,每一步都搜索所有可能的选择,对前一步合适的选择再考虑下一步的各种方案. 用计算机实现上述求解的搜索过程可以采用两种不同的策略:一种是广度优先(breadth_first) 搜索,另一种是深度优先(depth_first) . 广度优先: u 广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态,然后再进一步考虑更后

【算法编程】小学数学题难倒博士

昨天在科学网上得知这样一个新闻<越南小学数学题难倒博士>,据悉题目来自越南保禄小学三年班,不过报道称该题难倒了上至博士下至家长,未免也太言过其实了. 题目描述 学生需要在下图表格中按由上至下.从左到右的顺序,填入1~9的数字,可重复填写,并按先乘除后加减(图中冒号代表除法)的运算法则,完成整条算式. 解题方法 显然,这题对于我们这种程序员来说完全不是问题,只要在大一上过C语言的学生(我们学校全校都学过C,即使是文科专业)基本上都可以用九重for循环来穷举解出此题,下面我分别用C和Matlab实

【算法编程】随机数的不重复选择

       前一篇文章中,我们在Java中用实现两种不同接口的类,解决了不重复选择随机数的问题.现在我们在C++中,通过几种不同的算法来解决上述问题.在下面的四种算法实现中,用的随机函数都是C的库函数,这个函数产生的随机数的范围是限定的,[0, 32767].当然我们可以通过四则运算来改变取值范围.具体的算法实现如下: #include<iostream> #include<ctime> #include<algorithm> #include <set>

【算法编程】基于Miller-Rabin的大素数测试

基本原理: 费尔马小定理:如果p是一个素数,且0<a<p,则a^(p-1)%p=1.       利用费尔马小定理,对于给定的整数n,可以设计素数判定算法,通过计算d=a^(n-1)%n来判断n的素性,当d!=1时,n肯定不是素数,当d=1时,n  很可能是素数. 二次探测定理:如果p是一个素数,且0<x<p,则方程x^2%p=1的解为:x=1或x=p-1.       利用二次探测定理,可以再利用费尔马小定理计算a^(n-1)%n的过程中增加对整数n的二次探测,一旦发现违背二次探