溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
遞歸算法，總結起來具有以下幾個特點：
特點1 它有一個基本部分，即直接滿足條件，輸出
特點2 它有一個遞歸部分，即 通過改變基數（即n），來逐步使得n滿足基本部分的條件，從而輸出
特點3 在實現的過程中，它采用了分治法的思想：
即將整體分割成部分，并總是從最小的部分（基本部分）開始入手（輸出），其背后的原理在于 當整體遞歸到部分時，會保留整體的信息，部分滿足條件輸出的結果會被回溯給整體使用，從而使得整體輸出結果。
特點4 每一步操作，整體都會將部分當作其必要的一個步驟，從而實現整體步驟的完成
1.Question:
本題是用枚舉的思路來判斷一個規定的邏輯表達式是不是永真式
首先題目意思是最多不會有超過5個邏輯變量，有五種運算
| w x | Kwx | Awx | Nw | Cwx | Ewx |
| 1 1 | 1 | 1 | 0 | 1 | 1 |
| 1 0 | 0 | 1 | 0 | 0 | 0 |
| 0 1 | 0 | 1 | 1 | 1 | 0 |
| 0 0 | 0 | 0 | 1 | 1 | 1 |
其中
K &
A |
N !
C ->
E 同或
其中的C我們可以利用 !A | B 實現
E利用==實現
本題的主要難點并不在于實現我們的語句計算的方式
難點1：
遞歸求解表達式，在這里真的是有深刻的理解了遞歸的強大之處，我們本題的做法真的離不開遞歸，我們的做法是一個一個字符的開始枚舉的遞歸，每個字符分出10種情況，五種變量，五種運算符，這里我們添加一個指示器變量表示我們當前的遞歸的位置和深度，我們不用設置我們的遞歸的終止條件，因為我們的表達式保證了一定是正確的，我們的計算結果一定是會有返回值的，我們的計算結果是一層一層的返回的
難點2：
位運算，我們本題如果不利用位運算的話，至少需要寫5層循環來模擬我們的變量的所有的情況，這樣太低效了，我們將我們的所有的變量封裝到一個一個字節的存儲器中，每次利用位運算提取相關的位置的數字就好了（雖然我們的表達式并不會運算所有的情況，但是至少不會錯）
Code:
#include"iostream"
#include"cstdio"
#include"cstdlib"
#include"cstring"
using namespace std;
int pos=0;
string data;
bool cal(int i)
{
int t=pos++;
switch(data[t])
{
case 'p':
return (i >> 4)&1;
case 'q':
return (i >> 3)&1;
case 'r':
return (i >> 2)&1;
case 's':
return (i >> 1)&1;
case 't':
return i&1;
case 'K':
return cal(i) & cal(i);
case 'A':
return cal(i) | cal(i);
case 'N':
return !cal(i);
case 'C':
return !cal(i) | cal(i);
case 'E':
return cal(i) == cal(i);
}
}
bool isTautology()
{
for(int i=0;i<=31;i++)
{
pos=0;
if(cal(i)) continue;
else return false;
}
return true;
}
int main()
{
while(cin>>data&&data[0]!='0')
{
if(isTautology()) cout<<"tautology"<<endl;
else cout<<"not"<<endl;
}
return 0;
}
總結
以上就是本文關于C++遞歸算法實例代碼的全部內容，希望對大家有所幫助。歡迎參閱：C++中函數指針詳解及代碼分享、C/C++ 編譯器優化介紹等，有什么問題，可以隨時留言，歡迎大家交流討論。感謝朋友們對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
