欢迎来到 黑吧安全网 聚焦网络安全前沿资讯,精华内容,交流技术心得!

代码分析平台CodeQL学习手记(八)

来源:本站整理 作者:佚名 时间:2020-01-22 TAG: 我要投稿

过河问题是一个经典的逻辑问题,它要求在一定约束下将山羊、卷心菜和狼运到对岸。在本文中,我们将为读者详细介绍如何综合利用类、谓词和递归等知识点来编写查询代码,从而解决这个经典的逻辑问题。
关于过河问题
一位农夫带着一头狼,一只山羊和一筐卷心菜过河,河边有一条小船,农夫划船每次只能载狼、山羊、卷心菜三者中的一个过河。农夫不在旁边时,狼会吃掉山羊,山羊会吃卷心菜。问农夫该如何过河?
这个问题的答案,实际上就是关于如何摆渡这些货物过河的详细步骤,比如“首先摆渡山羊过河,回来时什么都不带。然后,把卷心菜运过去,并将某货物带回来……”
实际上,解决这个问题的方法有很多,并且,这些方法都可以通过QL语言进行实现。在实现这些解决方法的过程中,需要通过QL语言来定义相应的类、谓词以及递归等概念,对于不熟悉这些概念的读者,可以先阅读之前的文章,那里有相关的介绍。当然,这里给出的解决方法,只是各种可行的方法中的一种而已,感兴趣的读者,也可以编写自己的查询!
模拟问题中的各种元素
在这个过河问题中,基本的组成元素可以分为两类:货物和河岸。其中,货物包括山羊、卷心菜和狼;而河岸实际上包括河流两边的对岸。现在,我们将这些表示为QL语言中的类。
首先,定义一个包含不同货物的Cargo类。需要注意的是,由于这个农夫也可以自己渡河,啥也不带,所以,直接将“Nothing”明确定义为一件货物是很有帮助的。
/** A possible cargo item. */
class Cargo extends string {
  Cargo() {
    this = "Nothing" or
    this = "Goat" or
    this = "Cabbage" or
    this = "Wolf"
  }
}
其次,任何货物都可以位于两个河岸中的一个上面。为了便于区分,这里将河岸分别命名为“左岸”和“右岸”。为此,我们可以定义一个Shore类来表示河岸,其中包含“Left”和“Right”,本别表示“左岸"和"右岸"。
此外,农夫可能需要在两岸之间多次摆渡,这就涉及到“对岸”的概念,所以,我们可以在Shore类中定义一个成员谓词,专门求对岸,例如,给出左岸,该谓词将返回右岸,反之亦然。
/** One of two shores. */
class Shore extends string {
  Shore() {
    this = "Left" or
    this = "Right"
  }
 
  /** Returns the other shore. */
  Shore other() {
    this = "Left" and result = "Right"
    or
    this = "Right" and result = "Left"
  }
}
此外,我们还需要设法跟踪农夫、山羊、卷心菜和狼的位置。在这里,我们把这些组合在一起的位置信息称为“状态”。为此,我们可以定义一个类State,来表示每件货物的位置。例如,如果农夫在左岸,山羊在右岸,卷心菜和狼在左岸,那么,当前的状态应该是左、右、左、左。
大家可能已经发现,如果我们引入一些变量来表示农夫和货物所在河岸的话,将是非常有帮助的。在类的定义中,这些临时变量被称为字段。
/** A record of where everything is. */
class State extends string {
  Shore manShore;
  Shore goatShore;
  Shore cabbageShore;
  Shore wolfShore;
 
  State() { this = manShore + "," + goatShore + "," + cabbageShore + "," + wolfShore }
}
为了解决这个过河问题,我们对其中的两种特定的状态非常关注,即初始状态和目标状态。假设刚开始的时候,所有货物都在左岸,成功渡河后,所有货物都在右岸,那么,我们可以通过State类派生两个子类,一个是表示初始状态的InitialState类,另一个是表示目标状态的GoalState类。
/** The initial state, where everything is on the left shore. */
class InitialState extends State {
  InitialState() { this = "Left" + "," + "Left" + "," + "Left" + "," + "Left" }
}
 
/** The goal state, where everything is on the right shore. */
class GoalState extends State {
  GoalState() { this = "Right" + "," + "Right" + "," + "Right" + "," + "Right" }
}
需要注意的是,我们可以引入一个助手谓词renderState,来帮我们以适当的形式呈现状态数据。
好了,到目前为止,我们的QL代码如下所示:
/** A possible cargo item. */
class Cargo extends string {
  Cargo() {
    this = "Nothing" or
    this = "Goat" or
    this = "Cabbage" or
    this = "Wolf"
  }
}
 
/** One of two shores. */
class Shore extends string {
  Shore() {
    this = "Left" or
    this = "Right"
  }
 
  /** Returns the other shore. */
  Shore other() {
    this = "Left" and result = "Right"
    or
    this = "Right" and result = "Left"
  }
}
 
/** Renders the state as a string. */
string renderState(Shore manShore, Shore goatShore, Shore cabbageShore, Shore wolfShore) {

[1] [2] [3] [4]  下一页

【声明】:黑吧安全网(http://www.myhack58.com)登载此文出于传递更多信息之目的,并不代表本站赞同其观点和对其真实性负责,仅适于网络安全技术爱好者学习研究使用,学习中请遵循国家相关法律法规。如有问题请联系我们,联系邮箱admin@myhack58.com,我们会在最短的时间内进行处理。
  • 最新更新
    • 相关阅读
      • 本类热门
        • 最近下载