2年前 (2018-06-25)  电子书 |   抢沙发  22 
文章评分 0 次,平均分 0.0

c#递归算法

 

c#递归算法

任何一个方法既可以调用其他方法也可以调用自己,而当这个方法调用自己时,我们就叫它递归函数或递归方法。
通常递归有两个特点:

  1. 递归方法一直会调用自己直到某些条件被满足
  2. 递归方法会有一些参数,而它会把一些新的参数值传递给自己。
    那什么是递归函数?函数和方法没有本质区别,但函数仅在类的内部使用。以前C#中只有方法,从.NET 3.5开始才有了匿名函数。

 

 

 

 

1)1、1、2、3、5、8.......用递归算法求第30位数的值?

首先我们可以发现从第3位数起后一位数等于前两位数值之和,即:x=(x-1)+(x-2),x>2;

这里需要不断的相加,第一时刻就会想到循环处理,我们尝试用数组去装载这些数值,即:

int[] a=new int[30];

a[0]=1;

a[1]=1;

for(int i=2;i<30;i++)

{

a[i]=a[i-1]+a[i-2];

}

求a[29]的值即为第30位数的值。

下面是用递归的方法实现计算阶乘,与之前的代码比起来它更简洁。

递归该如何处理呢?同样定义函数

fun(n)

{

return fun(n-1)+fun(n-2)//n为第几位数,第n位数返回值等于第n-1位数的值与第n-2位数的值之和

}

只有当n>2为这种情况,就可以做个判断

fun(n)

{

if(n==1 || n==2)

return 1;

else

return fun(n-1)+fun(n-2);

}

求fun(30);

网站看到别人的分析也不错:

【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。
斐波那契数列为:0、1、1、2、3、……,即:
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2) (当n>1时)。
写成递归函数有:
int fib(int n)
{ if (n==0) return 0;
if (n==1) return 1;
if (n>1) return fib(n-1)+fib(n-2);
}
递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n-2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。
在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。
在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。
由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。

其他递归解题:

求1+2+3+4+5+....+n的值

Fun(n)=n+Fun(n-1)

n=1时为1

Fun(n)

{

if(n==1)

return 1;

else

return n+Fun(n-1);

}

有两个整数型数组,从小到大排列,编写一个算法将其合并到一个数组中,并从小到大排列

public void Fun()
{
int[] a = { 1, 3, 5, 7, 9, 10 };
int[] b = { 2, 4, 6, 8, 11, 12, 15 };

int[] c = new int[a.Length + b.Length];
ArrayList al=new ArrayList();
int i=0;
int j=0;
while (i <= a.Length - 1 && j <= b.Length - 1)
{  //循环比较把小的放到前面
if (a[i] < b[j])
{
al.Add(a[i++]);
}
else
{
al.Add(b[j++]);
}
}

//两个数组的长度不一样,必有个数组没比较完
while (i <= a.Length - 1)//添加a中剩下的
{
al.Add(a[i++]);
}
while (j <= b.Length - 1)//添加b中剩下的

{
al.Add(b[j++]);
}

for (int ii = 0; ii <= c.Length-1 ; ii++)
{
c[ii] = (int)al[ii];
}
}

----------------------------------------------------

首先碰到的是这样的一首题目:计算数组{1,1,2,3,5,8.......} 第30位值,不用递归,我写出了以下这样的代码:

c#递归算法        static void Main(string[] args)
c#递归算法 {
c#递归算法
c#递归算法
c#递归算法            int[] num=new int[30];
c#递归算法            num[0]=1;
c#递归算法            num[1]=1;
c#递归算法            int first=num[0];
c#递归算法            int second=num[1];
c#递归算法            for (int i = 2; i < num.Length; i++)
c#递归算法 {
c#递归算法                num[i] = first + second;
c#递归算法                first = second;
c#递归算法                second = num[i];
c#递归算法            }
c#递归算法            Console.WriteLine(num[29]);
c#递归算法            Console.ReadLine();
c#递归算法
c#递归算法
c#递归算法
c#递归算法        }
c#递归算法

写出来,十分的累赘,于是改为归递算法来写,一目了然,十分明了。以下是代码:

c#递归算法        static void Main(string[] args)
c#递归算法 {
c#递归算法
c#递归算法            Console.WriteLine(Process1(30));
c#递归算法            Console.ReadLine();
c#递归算法        }
c#递归算法        public static int Process1(int i)
c#递归算法 {
c#递归算法
c#递归算法
c#递归算法
c#递归算法
c#递归算法            //计算数组{1,1,2,3,5,8.......} 第30位值
c#递归算法            if (i == 0) return 0;
c#递归算法            if (i == 1) return 1;
c#递归算法            else
c#递归算法                return Process1(i - 1) + Process1(i - 2);
c#递归算法        }

做了一些练习:

1. 计算1+2+3+4+...+100的值

c#递归算法        static void Main(string[] args)
c#递归算法 {
c#递归算法            Console.WriteLine(Process2(100));
c#递归算法            Console.ReadLine();
c#递归算法        }
c#递归算法        public static int Process2(int i)
c#递归算法 {
c#递归算法            //计算1+2+3+4+...+100的值
c#递归算法            if (i == 0) return 0;
c#递归算法            return Process2(i - 1) + i;
c#递归算法
c#递归算法        }

2. 计算1 -2 +3 +-4+ 5- 6 + 7 - 8 + 9的值

c#递归算法        static void Main(string[] args)
c#递归算法 {
c#递归算法
c#递归算法            Console.WriteLine(Process3(9) - Process3(8));
c#递归算法            Console.ReadLine();
c#递归算法        }
c#递归算法
c#递归算法        public static int Process3(int i)
c#递归算法 {
c#递归算法            //计算1 -2 +3 +-4+ 5- 6 + 7 - 8 + 9的值
c#递归算法            if (i == 0) return 1;
c#递归算法            if (i == 1) return 2;
c#递归算法            else return Process3(i - 2) + i;
c#递归算法        }

3.汉诺塔问题

c#递归算法        static void Main(string[] args)
c#递归算法 {
c#递归算法            Hanoi(5, 'A', 'B', 'C');
c#递归算法            Console.ReadLine();
c#递归算法        }
c#递归算法        public static void Hanoi(int n ,char A, char B, char C)
c#递归算法 {
c#递归算法            //汉诺塔问题
c#递归算法            //将n个盘子从A座借助B座,移到C座
c#递归算法            if (n == 1) Move(A, C);
c#递归算法            else
c#递归算法 {
c#递归算法                Hanoi(n - 1, A, C, B);
c#递归算法                Move(A, C);
c#递归算法                Hanoi(n - 1, B, A, C);
c#递归算法            }
c#递归算法
c#递归算法        }
c#递归算法        public static void Move(char startPlace, char endPlace)
c#递归算法 {
c#递归算法            Console.WriteLine("Move {0} To {1}",startPlace,endPlace);
c#递归算法        }

4.用递归法将一个整数n转换成字符串,例如,输入483,就输出字符串"483".n的位数不确定,可以是任意位数的整数。

c#递归算法        static void Main(string[] args)
c#递归算法 {
c#递归算法            IntToString(483, "");
c#递归算法            Console.ReadLine();
c#递归算法        }
c#递归算法        public static void IntToString(int input,String output)
c#递归算法 {
c#递归算法         //用递归法将一个整数n转换成字符串,例如,输入483,就输出字符串"483".n的位数不确定,可以是任意位数的整数。
c#递归算法         //   String output = "";
c#递归算法            output = input % 10+output;
c#递归算法            if (input / 10 != 0)
c#递归算法 {
c#递归算法                IntToString(input / 10,output);
c#递归算法            }
c#递归算法            else Console.WriteLine(output);
c#递归算法        }

 

除特别注明外,本站所有文章均为HadoopAll原创,转载请注明出处来自http://hadoopall.com/173.html

发表评论

表情 格式

暂无评论

登录

忘记密码 ?

切换登录

注册

扫一扫二维码分享