歡迎來到 黑吧安全網 聚焦網絡安全前沿資訊,精華內容,交流技術心得!

代碼分析平臺CodeQL學習手記(八)

來源:本站整理 作者:佚名 時間:2020-01-22 TAG: 我要投稿

過河問題是一個經典的邏輯問題,它要求在一定約束下將山羊、卷心菜和狼運到對岸。在本文中,我們將為讀者詳細介紹如何綜合利用類、謂詞和遞歸等知識點來編寫查詢代碼,從而解決這個經典的邏輯問題。
關于過河問題
一位農夫帶著一頭狼,一只山羊和一筐卷心菜過河,河邊有一條小船,農夫劃船每次只能載狼、山羊、卷心菜三者中的一個過河。農夫不在旁邊時,狼會吃掉山羊,山羊會吃卷心菜。問農夫該如何過河?
這個問題的答案,實際上就是關于如何擺渡這些貨物過河的詳細步驟,比如“首先擺渡山羊過河,回來時什么都不帶。然后,把卷心菜運過去,并將某貨物帶回來……”
實際上,解決這個問題的方法有很多,并且,這些方法都可以通過QL語言進行實現。在實現這些解決方法的過程中,需要通過QL語言來定義相應的類、謂詞以及遞歸等概念,對于不熟悉這些概念的讀者,可以先閱讀之前的文章,那里有相關的介紹。當然,這里給出的解決方法,只是各種可行的方法中的一種而已,感興趣的讀者,也可以編寫自己的查詢!
模擬問題中的各種元素
在這個過河問題中,基本的組成元素可以分為兩類:貨物和河岸。其中,貨物包括山羊、卷心菜和狼;而河岸實際上包括河流兩邊的對岸,F在,我們將這些表示為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.650547.live)登載此文出于傳遞更多信息之目的,并不代表本站贊同其觀點和對其真實性負責,僅適于網絡安全技術愛好者學習研究使用,學習中請遵循國家相關法律法規。如有問題請聯系我們,聯系郵箱[email protected],我們會在最短的時間內進行處理。
  • 最新更新
    • 相關閱讀
      • 本類熱門
        • 最近下載
        安徽快3自由的百科 求大神pc蛋蛋幸运28 2019重庆幸运农场走势图 河南彩票泳坛夺金 吉林快三57开奖 云南十一选五走势 辽宁35选7开奖结果i 湖南快乐十分开奖视频走势图 广西11选5购彩平台 期如意期货配资公司 湖南快乐十分总动计划