程序员的算法趣题Q56: 鬼脚图中的横线

2021/11/5 9:40:02

本文主要是介绍程序员的算法趣题Q56: 鬼脚图中的横线,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录

1. 问题描述

2. 初步分析

3. 代码及测试

4. 后记


1. 问题描述

 

 

2. 初步分析

        感觉非常没有头绪。先做一些实例计算分析。

        考虑图1的{1234--3421}的例子。为了说明方便,以U*表示上边的数字,D*表示下边的数字。以“纵1”表示第一根纵线,余类推。以”横*”表示所添加的横线,横线上的数字(图中8边形中的数字)表示横线添加的序号。

        假定按照类似于贪心算法的方式来绘制鬼脚图。

        比如说U1要到达D1,必须横跨中间两根纵线,因此可以画出对应的横线如下图所示:

         接下来考虑U2àD2. U2往下走时先碰到横1横跨到纵1,然后肯定必须再加一根横线回到纵2。但是这根横线添加的(相对于其它已经添加的横2、3的)纵向相对位置是与后续动作相关的,所以必须分情况考虑。显然这里有三种可能的情况,如下所示:

         上图中的(2.1)由于横4的加入导致原来的U1到D1的路径发生了变化,所以予以排除(注1:暂时按照这种规则进行)。

        图(2.2)中U2经过横1、横4后回到纵2,然后需要再添加一条横线到达D2,同样有相对于横3的上下相对位置的两种选择。但是如果添加到横3上面(横4与横3之间)的话,会导致原U1到D1的路径发生变化所以排除(2.2.1)。因此只有一种选择,如下图所示(2.2.2):

 

        接下来继续考虑(2.2.2),我们会发现在(2.2.2)中U3和U4已经可以借助既有横线到达目的点了:U3-横2-横4;U4-横3-横5。因此我们得到{1234--3421}的一个鬼脚图解。

       接下来再回头考虑(2.3)的继续。U2要到到达D2还要追加一条线,由于横4已经比横3低了,所以追加横5只有一种可能。如下图所示:

 

         然后我们同样发现,在(2.3.1)中U3和U4已经可以借助既有横线到达目的点了:U3-横2-横4;U4-横3-横5。因此我们得到{1234--3421}的第二个鬼脚图解。

        以上我们基于类似于贪心算法的思路得到了{1234--3421}的两个鬼脚图解。但是这里存在几个问题:

  1. 如何确保,或者说如何证明,以上贪心算法总能得到最优解?
  2. 以上鬼脚图绘制规则由人手动来做的话似乎是一目了然的,但是如何让计算机按照这个规则来搜索呢,或者说如何编程呢?

 

3. 代码及测试

4. 后记

        [2021-11-05] 非常惭愧,这道题目从最开始看到过去了两个星期。但是一直没有找到明确的头绪,所以暂时先把到目前为止的思路列上。欢迎小伙伴们讨论指点。不过我还没有放弃(还没有想去偷看原书答案),还是希望自己能够找到一个属于自己的(哪怕笨拙)解决方案^-^毕竟现实生活中的问题并不总是有答案可以参考的。

        上一篇:Q55: 平分蛋糕

        下一篇:Q57: 最快的联络网

        本系列总目录参见:程序员的算法趣题:详细分析和Python全解



这篇关于程序员的算法趣题Q56: 鬼脚图中的横线的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程