非遞歸演算法實現嗎

1. 用C語言編寫非遞歸演算法實現折半查找（二分查找）

char
a[10][5];//按字典序遞增
int
search(char
*x)//二分查找，返回有序表中大於等於x的元素位置
{
int
low=0,high=9,mid,t;
while(low<=high)
{
mid=(low+high)/2;
t=strcmp(a[mid],x);//比較中點位置與x
if(t==0)
return
mid;//相等返回其位置
else
if(t>0)
high=mid-1;//x小於mid元素，則在中點前
else
low=mid+1;
}
return
high+1;//返回大於x的第一個元素
}
這個是我曾經用過的字元串的二分查找~
請根據需要修改數據類型。。。

2. 如何使用非遞歸演算法來實現漢諾塔問題

#include<iostream>
usingnamespacestd;
voidHanoi(charsrc,chardes,charvia,intn)
{
if(n==1)
{
cout<<n<<":"<<src<<"-->"<<des<<endl;
return;
}
Hanoi(src,via,des,n-1);
cout<<n<<":"<<src<<"-->"<<des<<endl;
Hanoi(via,des,src,n-1);
}

intmain()
{
intn;
cin>>n;
cout<<"recusive:"<<endl;
Hanoi('A','C','B',n);
cout<<endl;
cout<<"normal:"<<endl;
charorder[2][256];
charpos[64];
order[0]['A']='B';
order[0]['B']='C';
order[0]['C']='A';
order[1]['A']='C';
order[1]['B']='A';
order[1]['C']='B';
//0是順序1是逆序
intindex[64];
//確定軌跡的順序還是逆序
inti,j,m;
for(i=n;i>0;i-=2)
index[i]=1;
for(i=n-1;i>0;i-=2)
index[i]=0;
memset(pos,'A',sizeof(pos));
for(i=1;i<(1<<n);i++)
{
for(m=1,j=i;j%2==0;j/=2,m++);
cout<<m<<":"<<pos[m]<<"-->"<<order[index[m]][pos[m]]<<endl;
pos[m]=order[index[m]][pos[m]];
}
return0;
}

3. 如何實現此函數的遞歸和非遞歸演算法

c語言所有遞歸都可以用非遞歸演算法實現，最典型的就是迭代法，有時比遞歸更容易理解。至於遞歸中的形式參數是自動變數，沒明白樓主的意思，形參就是形參啊，形參變數也是變數，其內存分配在棧區，隨著函數的結束，其內存也會被釋放，形參的生命周期與函數生命周期相同哈（同生共死）

4. 演算法的非遞歸實現

以非動態數組為例:

#include<iostream>
usingnamespacestd;
#defineN15
#defineN23
intmain(intargc,char**argv)
{
chara[N1][N2]={{'A','B','C'},{'1','2'},{'a','b','c'},{'-','+'},{'$','#'}};
constints[N1]={3,2,3,2,2};
intpos[N1]={0,0,0,0,0};
while(1){
for(inti=0;i<N1;i++){
if(i){
cout<<"";
}
cout<<a[i][pos[i]];
}
cout<<endl;
if(pos[N1-1]<s[N1-1]-1){
pos[N1-1]++;
}else{
boolfound=false;
for(inti=N1-2;i>=0;i--){
if(pos[i]<s[i]-1){
pos[i]++;
for(intj=i+1;j<N1;j++){
pos[j]=0;
}
found=true;
break;
}
}
if(!found){
break;
}
}
}
return0;
}

5. 後序遍歷的非遞歸演算法是什麼

對於樹的遍歷我們最常用的三種遍歷方法分別是前序遍歷、中序遍歷和後序遍歷，使用的方法是深度優先遍歷樹的每一個節點，這些遍歷方法都是使用遞歸函數來進行實現的。

在數據量大的情況下是比較低效的，原因在於系統幫助我們調用了一個棧並且做了諸如保護現場和恢復現場等復雜的操作。

才使得遍歷可以使用非常簡單的代碼來實現，所以我們可以模仿系統中調用的棧自己可以來寫一下棧，模仿其中的過程就可以完成對於三種遍歷演算法的實現，使用自定義的棧來代替系統棧可以得到效率上的提升，下面是對於後序遍歷的非遞歸演算法的實現。

簡介

從逆後序遍歷與先序遍歷的關系中我們可以知道逆後序遍歷序列為先序遍歷交換左右子樹的遍歷順序得到的。

所以我們得到了逆後序序列之後然後逆序就可以得到後序遍歷的序列了，所以需要兩個棧，第一個棧用來存儲先序遍歷交換左右子樹的遍歷的中介結果。

6. 所有用遞歸演算法的能不能都用非遞歸演算法實現

用遞歸演算法可以使程序結構清晰,可讀性好,但是它的運行效率很低,而且會占據很大存儲空間,因此有時希望在程序中消除遞歸.因為在計算機內遞歸演算法實際上是用一個工作棧來實現的,所以所有的遞歸演算法理論上來說是可以用非遞歸演算法實現,我們可以用一個棧來模擬遞歸演算法

7. 用非遞歸演算法和遞歸演算法實現一個非負十進制整數轉換成二進制數

//非遞歸演算法實現一個非負十進制整數轉換成二進制數（其中二進制數設置為8位）
#include"stdio.h"
main(){
int
a;
int
b[8];
scanf("%d",&a);
int
i=7;
while(a>0){
b[i]=a%2;
a/=2;
i--;
}
for(;i>=0;--i){
b[i]=0;
}
for(i=0;i<8;i++){
printf("%d",b[i]);
}
}-------------------------------------------------------------//遞歸演算法實現一個非負十進制整數轉換成二進制數（其中二進制數設置為8位）
#include"stdio.h"
//遞歸
void
fun(int
n,int*p){
if(n==0)
return;
*p=n%2;
fun(n/2,--p);
}
main(){
int
a;
int
b[8]={0};
scanf("%d",&a);
fun(a,b+7);
int
i;
for(i=0;i<8;i++){
printf("%d",b[i]);
}
}

8. 怎樣實現二叉樹的前序遍歷的非遞歸演算法

在前面一文，說過二叉樹的遞歸遍歷演算法（二叉樹先根（先序）遍歷的改進），此文主要講二叉樹的非遞歸演算法，採用棧結構
總結先根遍歷得到的非遞歸演算法思想如下：
1）入棧，主要是先頭結點入棧，然後visit此結點
2）while，循環遍歷當前結點，直至左孩子沒有結點
3）if結點的右孩子為真，轉入1）繼續遍歷，否則退出當前結點轉入父母結點遍歷轉入1）
先看符合此思想的演算法：
[cpp]
view
plain

print?
int
(const
BiTree
&T,
int
(*VisitNode)(TElemType
data))
{
if
(T
==
NULL)
{
return
-1;
}
BiTNode
*pBiNode
=
T;
SqStack
S;
InitStack(&S);
Push(&S,
(SElemType)T);
while
(!IsStackEmpty(S))
{
while
(pBiNode)
{
VisitNode(pBiNode->data);
if
(pBiNode
!=
T)
{
Push(&S,
(SElemType)pBiNode);
}
pBiNode
=
pBiNode->lchild;
}
if(pBiNode
==
NULL)
{
Pop(&S,
(SElemType*)&pBiNode);
}
if
(
pBiNode->rchild
==
NULL)
{
Pop(&S,
(SElemType*)&pBiNode);
//如果此時棧已空，就有問題
}
pBiNode
=
pBiNode->rchild;
}
return
0;
}

9. n!非遞歸演算法怎麼實現（n值較大的時候）用到鏈表或隊列。請哪位高手幫一下忙，謝謝！！！

結果存放在a【N】中，定義結果位數不超過10000位，n！中n不大於1000，up為進位；數組a中每個數最多是4位的（%10000），這樣即使*N也不會超越最大整數
12!=479001600，一個for循環可以搞定，
大於12的在12結果的基礎上累乘下去，沒乘完一個數就把結果存入a【N】中

2009年寫的一個演算法如下：
#include<stdio.h>
#define N 10000 /*12!=479001600;*/
#define size 100000
int main()
{
long int a[N],i,j,length,k,up;
int sum,n;
while(scanf("%d",&n)!=EOF)
{
if(n>12)
{
a[0]=1600;a[1]=4790;length=2;
for(j=13;j<=n;j++)
{
for(k=0,up=0;k<length;k++)
a[k]*=j;
for(k=0;k<length;k++)
{
a[k]+=up;
up=a[k]/size;
a[k]=a[k]%size;
}
if(up)
{
length+=1;
a[length-1]=up;
}
}
printf("%d",a[length-1]);
for(i=length-2;i>=0;i--)
printf("%05d",a[i]);
}
else
{
if(n)
{
for(i=1,sum=1;i<=n;i++)
sum*=i;
printf("%d",sum);
}
else printf("1");
}
printf("\n");
}
}