非递归算法实现吗

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