欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

基于C++的農(nóng)夫過(guò)河問(wèn)題算法設(shè)計(jì)與實(shí)現(xiàn)方法

 更新時(shí)間:2017年09月11日 11:55:43   作者:尼奧普蘭  
這篇文章主要介紹了基于C++的農(nóng)夫過(guò)河問(wèn)題算法設(shè)計(jì)與實(shí)現(xiàn)方法,簡(jiǎn)單描述了農(nóng)夫過(guò)河問(wèn)題,并結(jié)合實(shí)例形式詳細(xì)分析了基于C++實(shí)現(xiàn)農(nóng)夫過(guò)河問(wèn)題的相關(guān)算法實(shí)現(xiàn)步驟與操作技巧,需要的朋友可以參考下

本文實(shí)例講述了基于C++的農(nóng)夫過(guò)河問(wèn)題算法設(shè)計(jì)與實(shí)現(xiàn)方法。分享給大家供大家參考,具體如下:

問(wèn)題描述:

一個(gè)農(nóng)夫帶著—只狼、一只羊和—棵白菜,身處河的南岸。他要把這些東西全部運(yùn)到北岸。他面前只有一條小船,船只能容下他和—件物品,另外只有農(nóng)夫才能撐船。如果農(nóng)夫在場(chǎng),則狼不能吃羊,羊不能吃白菜,否則狼會(huì)吃羊,羊會(huì)吃白菜,所以農(nóng)夫不能留下羊和白菜自己離開(kāi),也不能留下狼和羊自己離開(kāi),而狼不吃白菜。請(qǐng)求出農(nóng)夫?qū)⑺械臇|西運(yùn)過(guò)河的方案。

實(shí)現(xiàn)上述求解的搜索過(guò)程可以采用兩種不同的策略:一種廣度優(yōu)先搜索,另一種深度優(yōu)先搜索。這里介紹在廣度優(yōu)先搜索方法中采用的數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)。

程序源碼:

/***********************************************
 * 農(nóng)夫過(guò)河問(wèn)題(P64 隊(duì)列的應(yīng)用)
 * 約定:用四位二進(jìn)制數(shù)分別順序表示農(nóng)夫、狼、白菜和羊的狀態(tài)
 *   即:{dddd} <=> {Farmer, Wolf, Cabbage, Goat} 其中:d={0,1}
 * 說(shuō)明:0表示在東岸 1表示在西岸,初始狀態(tài)為0000,終止?fàn)顟B(tài)為1111
************************************************/
#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 16
typedef int EntryType;
typedef struct queue
{
  EntryType data[MAXSIZE];
  int front,rear;    //front隊(duì)頭,rear隊(duì)尾
}SeqQueue, * SeqQueuePtr;
// 創(chuàng)建空隊(duì)列
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);
}
// 入隊(duì)
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;
  }
}
// 隊(duì)首元素出隊(duì)(返回0表示出隊(duì)異常,出隊(duì)操作前隊(duì)列為空)
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);
}
// 若狀態(tài)相容(安全)則返回1,否則返回0
int is_safe(int state)
{
  if((is_goat_crossed(state) == is_cabbage_crossed(state)) &&
    (is_goat_crossed(state) != is_farmer_crossed(state))) // 羊菜同岸且農(nóng)夫不在場(chǎng)
    return(0);
  if((is_goat_crossed(state) == is_wolf_crossed(state)) &&
    (is_goat_crossed(state) != is_farmer_crossed(state))) // 狼羊同岸且農(nóng)夫不在場(chǎng)
    return(0);
  return(1);
}
void river_crossing_problem()
{
  int route[16];      // 記錄已經(jīng)考慮過(guò)的狀態(tài)
  int state;        // 記錄當(dāng)前時(shí)刻的狀態(tài)(狀態(tài)編號(hào)的二進(jìn)制形式即狀態(tài)本身)
  int aftercross;     // 記錄漁夫當(dāng)前的選擇(渡河對(duì)象)會(huì)導(dǎo)致的結(jié)果狀態(tài)
  int passenger;      // 臨時(shí)變量,用于表達(dá)農(nóng)夫的選擇(對(duì)應(yīng)二進(jìn)制位為1表示選中該乘客)
  int results[16]={0};   // 輸出結(jié)果
  int counter, i;
  SeqQueuePtr states_que; //
  states_que = create_sequeue(); // 創(chuàng)建“狀態(tài)”隊(duì)列
  enqueue(states_que,0x00);   // 初始狀態(tài)0000入隊(duì)
  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");
    }
    // 依次考慮農(nóng)夫可能的選擇:攜帶羊、白菜和狼,以及農(nóng)夫只身渡河
    for( passenger = 1; passenger<= 8; passenger <<= 1 )
    {
      // 由于農(nóng)夫總是在過(guò)河,隨農(nóng)夫過(guò)河的也只能是與農(nóng)夫同側(cè)的東西
      if(((state & 0x08) != 0) == ((state & passenger) != 0)){
        // 如果農(nóng)夫與當(dāng)前乘客在河岸的同一側(cè)
        aftercross = state^( 0x08|passenger ); // 渡河后的情況
        if(is_safe(aftercross) && (route[aftercross] == -1)){
          // 如果渡河后狀態(tài)安全,則將其狀態(tài)入隊(duì)
          route[aftercross] = state; // 將當(dāng)前狀態(tài)的索引記錄到路徑數(shù)組中(下標(biāo)索引為后續(xù)狀態(tài)值)
          enqueue(states_que, aftercross);
        }
      }
    }//end for()
  }//end while()
  // 輸出過(guò)河策略:0表示在東岸 1表示在西岸,初始狀態(tài)為0000,終止?fàn)顟B(tài)為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("農(nóng)夫從東岸到西岸:");
      }
      else{
        printf("農(nóng)夫從西岸到東岸:");
      }
      switch(state^aftercross ){
      case 12:
        printf("把狼帶過(guò)河\n");
        break;
      case 10:
        printf("把菜帶過(guò)河\n");
        break;
      case 9:
        printf("把羊帶過(guò)河\n");
        break;
      default:
        printf("什么也不帶\n");
        break;
      }
    }
  }
  else{
    printf("No solution for this problem.\n");
  }
}
int main(void)
{
  river_crossing_problem();
  system("pause");
  return 0;
}

運(yùn)行結(jié)果:

希望本文所述對(duì)大家C++程序設(shè)計(jì)有所幫助。

相關(guān)文章

  • C++九種排序具體實(shí)現(xiàn)代碼

    C++九種排序具體實(shí)現(xiàn)代碼

    這篇文章主要介紹了C++九種排序具體實(shí)現(xiàn)代碼,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2020-04-04
  • Visual Studio Code配置C、C++環(huán)境并編寫(xiě)運(yùn)行的方法

    Visual Studio Code配置C、C++環(huán)境并編寫(xiě)運(yùn)行的方法

    這篇文章主要介紹了Visual Studio Code配置C、C++環(huán)境并編寫(xiě)運(yùn)行的方法,小編覺(jué)得挺不錯(cuò)的,現(xiàn)在分享給大家,也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧
    2018-08-08
  • C++11右值引用和轉(zhuǎn)發(fā)型引用教程詳解

    C++11右值引用和轉(zhuǎn)發(fā)型引用教程詳解

    這篇文章主要介紹了C++11右值引用和轉(zhuǎn)發(fā)型引用教程詳解,需要的朋友可以參考下
    2018-03-03
  • 在C++中反射調(diào)用.NET的方法(一)

    在C++中反射調(diào)用.NET的方法(一)

    為什么要在C++中調(diào)用.NET呢?接下來(lái)通過(guò)本文給大家介紹在C++中反射調(diào)用.NET的方法(一),需要的朋友參考下吧
    2017-02-02
  • 淺談C++中對(duì)象的復(fù)制與對(duì)象之間的相互賦值

    淺談C++中對(duì)象的復(fù)制與對(duì)象之間的相互賦值

    這篇文章主要介紹了淺談C++中對(duì)象的復(fù)制與對(duì)象之間的相互賦值,是C語(yǔ)言入門(mén)學(xué)習(xí)中的基礎(chǔ)知識(shí),需要的朋友可以參考下
    2015-09-09
  • C語(yǔ)言字符串轉(zhuǎn)換為Python字符串的方法

    C語(yǔ)言字符串轉(zhuǎn)換為Python字符串的方法

    這篇文章主要介紹了C語(yǔ)言字符串轉(zhuǎn)換為Python字符串的方法,文中講解非常細(xì)致,代碼幫助大家更好的理解和學(xué)習(xí),感興趣的朋友可以了解下
    2020-07-07
  • C++繼承介紹

    C++繼承介紹

    C++繼承可以是單一繼承或多重繼承,每一個(gè)繼承連接可以是public,protected,private也可以是virtual或non-virtual
    2013-01-01
  • 深入淺出分析C++ string底層原理

    深入淺出分析C++ string底層原理

    C ++的string對(duì)象實(shí)質(zhì)上就是一個(gè)容器,其內(nèi)部有一個(gè)c_str方法能夠返回一個(gè)指向的實(shí)質(zhì)存儲(chǔ)字符串副本的數(shù)據(jù)成員。即通過(guò)string::c_str()配合printf函數(shù)可以獲取的字符串副本的內(nèi)存地址
    2021-11-11
  • C語(yǔ)言的堆串操作詳解

    C語(yǔ)言的堆串操作詳解

    大家好,本篇文章主要講的是C語(yǔ)言的堆串操作詳解,感興趣的同學(xué)趕快來(lái)看一看吧,對(duì)你有幫助的話(huà)記得收藏一下
    2022-02-02
  • linux C 打印錯(cuò)誤信息和標(biāo)準(zhǔn)輸入輸出詳細(xì)介紹

    linux C 打印錯(cuò)誤信息和標(biāo)準(zhǔn)輸入輸出詳細(xì)介紹

    這篇文章主要介紹了linux C 打印錯(cuò)誤信息和標(biāo)準(zhǔn)輸入輸出詳細(xì)介紹的相關(guān)資料,需要的朋友可以參考下
    2016-12-12

最新評(píng)論