基于C++如何解決農夫過河問題

這篇文章給大家分享的是有關基于C++如何解決農夫過河問題的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。

問題描述：

一個農夫帶著—只狼、一只羊和—棵白菜，身處河的南岸。他要把這些東西全部運到北岸。他面前只有一條小船，船只能容下他和—件物品，另外只有農夫才能撐船。如果農夫在場，則狼不能吃羊，羊不能吃白菜，否則狼會吃羊，羊會吃白菜，所以農夫不能留下羊和白菜自己離開，也不能留下狼和羊自己離開，而狼不吃白菜。請求出農夫將所有的東西運過河的方案。

實現上述求解的搜索過程可以采用兩種不同的策略：一種廣度優先搜索，另一種深度優先搜索。這里介紹在廣度優先搜索方法中采用的數據結構設計。

程序源碼：

/***********************************************
 * 農夫過河問題（P64 隊列的應用）
 * 約定：用四位二進制數分別順序表示農夫、狼、白菜和羊的狀態
 *   即：{dddd} <=> {Farmer, Wolf, Cabbage, Goat} 其中：d={0,1}
 * 說明：0表示在東岸 1表示在西岸，初始狀態為0000，終止狀態為1111
************************************************/
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 16
typedef int EntryType;
typedef struct queue
{
  EntryType data[MAXSIZE];
  int front,rear;    //front隊頭，rear隊尾
}SeqQueue, * SeqQueuePtr;
// 創建空隊列
SeqQueuePtr create_sequeue(void)
{
  SeqQueuePtr pque;
  pque = (SeqQueuePtr)malloc(sizeof(SeqQueue));
  if(pque){
    pque->front = 0;
    pque->rear = 0;
  }
  else{
    printf("Error: malloc() failed, out of memory!\n");
  }
  return(pque);
}
int is_queEmpty(SeqQueuePtr pque)
{
  return( pque->front == pque->rear );
}
int is_queFull(SeqQueuePtr pque)
{
  return( (pque->rear+1)%MAXSIZE == pque->front);
}
// 入隊
int enqueue(SeqQueuePtr pque, EntryType x)
{
  if(is_queFull(pque)){
    printf("Queue Overflow Error: trying to add an element onto a full queue\n");
    return 1;
  }
  else{
    pque->data[pque->rear] = x;
    pque->rear = (pque->rear + 1) % MAXSIZE;
    return 0;
  }
}
// 隊首元素出隊（返回0表示出隊異常，出隊操作前隊列為空）
int dequeue(SeqQueuePtr pque, EntryType * e)
{
  if(is_queEmpty(pque)){
    printf("Empty Queue.\n");
    return 0;
  }
  else{
    *e = pque->data[pque->front];
    pque->front = (pque->front + 1) % MAXSIZE;
    return 1;
  }
}
int is_farmer_crossed(int state)
{
  return ((state & 0x08) != 0);
}
int is_wolf_crossed(int state)
{
  return ((state & 0x04) != 0);
}
int is_cabbage_crossed(int state)
{
  return ((state & 0x02) != 0);
}
int is_goat_crossed(int state)
{
  return ((state & 0x01) != 0);
}
// 若狀態相容（安全）則返回1，否則返回0
int is_safe(int state)
{
  if((is_goat_crossed(state) == is_cabbage_crossed(state)) &&
    (is_goat_crossed(state) != is_farmer_crossed(state))) // 羊菜同岸且農夫不在場
    return(0);
  if((is_goat_crossed(state) == is_wolf_crossed(state)) &&
    (is_goat_crossed(state) != is_farmer_crossed(state))) // 狼羊同岸且農夫不在場
    return(0);
  return(1);
}
void river_crossing_problem()
{
  int route[16];      // 記錄已經考慮過的狀態
  int state;        // 記錄當前時刻的狀態（狀態編號的二進制形式即狀態本身）
  int aftercross;     // 記錄漁夫當前的選擇（渡河對象）會導致的結果狀態
  int passenger;      // 臨時變量，用于表達農夫的選擇（對應二進制位為1表示選中該乘客）
  int results[16]={0};   // 輸出結果
  int counter, i;
  SeqQueuePtr states_que; //
  states_que = create_sequeue(); // 創建“狀態”隊列
  enqueue(states_que,0x00);   // 初始狀態0000入隊
  for(int i = 0; i < 16; i++){
    route[i] = -1;
  }
  //route[0] = 0;
  while(!is_queEmpty(states_que) && (route[15] == -1))
  {
    if( !dequeue(states_que, &state) ){
      printf("Error: dequeue() - the queue is empty\n");
    }
    // 依次考慮農夫可能的選擇：攜帶羊、白菜和狼，以及農夫只身渡河
    for( passenger = 1; passenger<= 8; passenger <<= 1 )
    {
      // 由于農夫總是在過河，隨農夫過河的也只能是與農夫同側的東西
      if(((state & 0x08) != 0) == ((state & passenger) != 0)){
        // 如果農夫與當前乘客在河岸的同一側
        aftercross = state^( 0x08|passenger ); // 渡河后的情況
        if(is_safe(aftercross) && (route[aftercross] == -1)){
          // 如果渡河后狀態安全，則將其狀態入隊
          route[aftercross] = state; // 將當前狀態的索引記錄到路徑數組中（下標索引為后續狀態值）
          enqueue(states_que, aftercross);
        }
      }
    }//end for()
  }//end while()
  // 輸出過河策略：0表示在東岸 1表示在西岸，初始狀態為0000，終止狀態為1111
  if(route[15] != -1)
  {
    //printf("The reverse path is:\n");
    counter = 0;
    for(state = 15; state != 0; state = route[state]){
      //printf("The state is: %d \n",state);
      results[counter] = state;
      counter++;
      //if(state == 0) return;
    }
    for(i = 0; i< counter; i++){
      state= results[i];
      aftercross = results[i+1];
      if(state & 0x08){
        printf("農夫從東岸到西岸:");
      }
      else{
        printf("農夫從西岸到東岸:");
      }
      switch(state^aftercross ){
      case 12:
        printf("把狼帶過河\n");
        break;
      case 10:
        printf("把菜帶過河\n");
        break;
      case 9:
        printf("把羊帶過河\n");
        break;
      default:
        printf("什么也不帶\n");
        break;
      }
    }
  }
  else{
    printf("No solution for this problem.\n");
  }
}
int main(void)
{
  river_crossing_problem();
  system("pause");
  return 0;
}

運行結果：

感謝各位的閱讀！關于“基于C++如何解決農夫過河問題”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！