遞歸算法，總結(jié)起來(lái)具有以下幾個(gè)特點(diǎn)：

    特點(diǎn)1  它有一個(gè)基本部分，即直接滿足條件，輸出
    特點(diǎn)2  它有一個(gè)遞歸部分，即 通過(guò)改變基數(shù)（即n），來(lái)逐步使得n滿足基本部分的條件，從而輸出
    特點(diǎn)3  在實(shí)現(xiàn)的過(guò)程中，它采用了分治法的思想：
       即將整體分割成部分，并總是從最小的部分（基本部分）開(kāi)始入手（輸出），其背后的原理在于 當(dāng)整體遞歸到部分時(shí)，會(huì)保留整體的信息，部分滿足條件輸出的結(jié)果會(huì)被回溯給整體使用，從而使得整體輸出結(jié)果。
    特點(diǎn)4  每一步操作，整體都會(huì)將部分當(dāng)作其必要的一個(gè)步驟，從而實(shí)現(xiàn)整體步驟的完成

1.Question:

本題是用枚舉的思路來(lái)判斷一個(gè)規(guī)定的邏輯表達(dá)式是不是永真式

首先題目意思是最多不會(huì)有超過(guò)5個(gè)邏輯變量，有五種運(yùn)算

其中

K &
A |
N !
C ->
E 同或

其中的C我們可以利用 !A | B 實(shí)現(xiàn)

E利用==實(shí)現(xiàn)

本題的主要難點(diǎn)并不在于實(shí)現(xiàn)我們的語(yǔ)句計(jì)算的方式

難點(diǎn)1：
遞歸求解表達(dá)式，在這里真的是有深刻的理解了遞歸的強(qiáng)大之處，我們本題的做法真的離不開(kāi)遞歸，我們的做法是一個(gè)一個(gè)字符的開(kāi)始枚舉的遞歸，每個(gè)字符分出10種情況，五種變量，五種運(yùn)算符，這里我們添加一個(gè)指示器變量表示我們當(dāng)前的遞歸的位置和深度，我們不用設(shè)置我們的遞歸的終止條件，因?yàn)槲覀兊谋磉_(dá)式保證了一定是正確的，我們的計(jì)算結(jié)果一定是會(huì)有返回值的，我們的計(jì)算結(jié)果是一層一層的返回的

難點(diǎn)2：

位運(yùn)算，我們本題如果不利用位運(yùn)算的話，至少需要寫5層循環(huán)來(lái)模擬我們的變量的所有的情況，這樣太低效了，我們將我們的所有的變量封裝到一個(gè)一個(gè)字節(jié)的存儲(chǔ)器中，每次利用位運(yùn)算提取相關(guān)的位置的數(shù)字就好了（雖然我們的表達(dá)式并不會(huì)運(yùn)算所有的情況，但是至少不會(huì)錯(cuò)）

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;}

總結(jié)

以上就是本文關(guān)于C++遞歸算法實(shí)例代碼的全部?jī)?nèi)容，希望對(duì)大家有所幫助。有什么問(wèn)題，可以隨時(shí)留言，歡迎大家交流討論。感謝朋友們對(duì)本站的支持！