Anyview数据结构-5

Posted on | Post modified: | In
Words count in article: 804 | Reading time ≈ 4

-广工Anyview题解
-数据结构部分-5
-递归基础

/**
【题目】试编写如下定义的递归函数的递归算法:
g(m,n) = 0 当m=0,n>=0
g(m,n) = g(m-1,2n)+n 当m>0,n>=0
**/

1
2
3
4
5
6
7
8
9
10
int G(int m, int n) 
/* 如果 m<0 或 n<0 则返回 -1 */
{
    if(m<0||n<0)
        return -1;
    else if(m==0&&n>=0)
        return 0;
    else if(m>0&&n>=0)
       return G(m-1,2*n)+n;
}

/**
【题目】试写出求递归函数F(n)的递归算法：
F(n) = n+1 当n=0
F(n) = nF(n/2) 当n>0
**/

1
2
3
4
5
6
7
8
9
10
int F(int n)
/* 如果 n<0 则返回 -1 */
{
    if(n<0) 
        return -1;
    else if(n==0) 
        return n+1;
    else if(n>0) 
        return n*F(n/2);
}

/**
【题目】求解平方根 的迭代函数定义如下：
sqrt(A,p,e) = p 当|pp-A|<e
sqrt(A,p,e) = sqrt(A,(p+A/p)/2,e) 当|pp-A|>=e
其中，p是A的近似平方根，e是结果允许误差。试写出相
应的递归算法。
**/

1
2
3
4
5
6
7
float Sqrt(float A, float p, float e)
{
    if(fabs(p*p-A)<e)
       return p;
    else
       return Sqrt(A,(p+A/p)/2,e); 
}

/**
【题目】已知Ackerman函数的定义如下：
akm(m,n) = n+1 当m=0
akm(m,n) = akm(m-1,1) 当m!=0,n=0
akm(m,n) = akm(m-1,akm(m,n-1)) 当m!=0,n!=0
请写出递归算法。
**/

1
2
3
4
5
6
7
8
9
10
11
12
int Akm(int m, int n)
/* 若 m<0 或 n<0 则返回-1  */
{
   if(m<0||n<0) 
        return -1;
    if(m==0) 
        return n+1;
    else if(m!=0&&n==0)
        return Akm(m-1,1);
    else if(m!=0&&n!=0)
        return Akm(m-1,Akm(m,n-1)) ;
}

/**
【题目】试写出求递归函数F(n)的非递归算法：
F(n) = n+1 当n=0
F(n) = nF(n/2) 当n>0
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
int F(int n)
/* 如果 n<0 则返回 -1 */
{
    int i=n,count=1;
    if(n<0) 
        return -1;
    else if(n==0) 
        return n+1;        
    else
        for(;i>0;i=i/2)
            count=count*i;
    return count;
}

/**
【题目】求解平方根 的迭代函数定义如下：
sqrt(A,p,e) = p 当|pp-A|<e
sqrt(A,p,e) = sqrt(A,(p+A/p)/2,e) 当|pp-A|>=e
其中，p是A的近似平方根，e是结果允许误差。试写出相
应的非递归算法。
**/

1
2
3
4
5
6
7
8
9
10
float Sqrt(float A, float p, float e)
{
    float mp=p;
    if(fabs(p*p-A)<e)
        return p;
    else
        while(fabs(mp*mp-A)>=e)
            mp=(mp+A/mp)/2;
    return mp;
}

/**
【题目】假设以二维数组g[1..m][1..n]表示一个图像
区域，g[i][j]表示该区域中点(i,j)所具颜色，其值
为从0到k的整数。试编写递归算法，将点(i0,j0)所在
区域的颜色置换为颜色c。约定与(i0,j0)同色的上、
下、左、右的邻接点为同色区域的点。

表示图像区域的类型定义如下：
typedef char GTYPE[m+1][n+1];
**/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
void ChangeColor(GTYPE g, int m, int n, 
                 char c, int i0, int j0)
/* 在g[1..m][1..n]中，将元素g[i0][j0] */
/* 所在的同色区域的颜色置换为颜色c    */
{   
     if(i0>m||j0>n)
         return;  
 
     int color;  
     color=g[i0][j0];  
     g[i0][j0]=c; 
      
     if(i0-1>=1)//判断是否越界，下同       
         if(g[i0-1][j0]==color)           
             ChangeColor(g,m,n,c,i0-1,j0);                        
     if(i0+1<=m)       
         if(g[i0+1][j0]==color)         
             ChangeColor(g,m,n,c,i0+1,j0);                    
     if(j0-1>=1)       
         if(g[i0][j0-1]==color)           
             ChangeColor(g,m,n,c,i0,j0-1);                    
     if(j0+1<=n)           
         if(g[i0][j0+1]==color)           
             ChangeColor(g,m,n,c,i0,j0+1);                    
}

Thanks for your reward！