递归

作者:编程技术

deffib(n):ifn==1:return1ifn==0:return0else:returnint(fib(n-1)) int(fib(n-2))foriinrange(20):print("{:5}".format(fib(i)))这段代码要怎么实现每行输出10个啊,求助求助

c# 递归算法

 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位值,不用递归,我写出了以下这样的代码:

 

图片 1        static void Main(string[] args)
图片 2        {
图片 3
图片 4
图片 5            int[] num=new int[30];
图片 6            num[0]=1;
图片 7            num[1]=1;
图片 8            int first=num[0];
图片 9            int second=num[1];
图片 10            for (int i = 2; i < num.Length; i )
图片 11            {
图片 12                num[i] = first   second;
图片 13                first = second;
图片 14                second = num[i];
图片 15            }
图片 16            Console.WriteLine(num[29]);
图片 17            Console.ReadLine();
图片 18
图片 19         
图片 20
图片 21        }
图片 22

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

 

图片 23        static void Main(string[] args)
图片 24        {
图片 25
图片 26            Console.WriteLine(Process1(30));
图片 27            Console.ReadLine();        
图片 28        }
图片 29        public static int Process1(int i)
图片 30        {
图片 31
图片 32
图片 33
图片 34
图片 35            //计算数组{1,1,2,3,5,8.......} 第30位值
图片 36            if (i == 0) return 0;
图片 37            if (i == 1) return 1;
图片 38            else
图片 39                return Process1(i - 1)   Process1(i - 2);
图片 40        }

做了一些练习:

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

 

图片 41        static void Main(string[] args)
图片 42        {
图片 43            Console.WriteLine(Process2(100));
图片 44            Console.ReadLine();    
图片 45        }
图片 46        public static int Process2(int i)
图片 47        {
图片 48            //计算1 2 3 4 ... 100的值
图片 49            if (i == 0) return 0;
图片 50            return Process2(i - 1)   i;
图片 51
图片 52        }

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

 

图片 53        static void Main(string[] args)
图片 54        {
图片 55
图片 56            Console.WriteLine(Process3(9) - Process3(8));
图片 57            Console.ReadLine();  
图片 58        }
图片 59
图片 60        public static int Process3(int i)
图片 61        {
图片 62            //计算1 -2  3  -4  5- 6   7 - 8   9的值
图片 63            if (i == 0) return 1;
图片 64            if (i == 1) return 2;
图片 65            else return Process3(i - 2)   i;
图片 66        }

3.汉诺塔问题

 

图片 67        static void Main(string[] args)
图片 68        {
图片 69            Hanoi(5, 'A', 'B', 'C');
图片 70            Console.ReadLine();
图片 71        }
图片 72        public static void Hanoi(int n ,char A, char B, char C)
图片 73        {
图片 74            //汉诺塔问题
图片 75            //将n个盘子从A座借助B座,移到C座
图片 76            if (n == 1) Move(A, C);
图片 77            else
图片 78            {
图片 79                Hanoi(n - 1, A, C, B);
图片 80                Move(A, C);
图片 81                Hanoi(n - 1, B, A, C);
图片 82            }
图片 83
图片 84        }
图片 85        public static void Move(char startPlace, char endPlace)
图片 86        {
图片 87            Console.WriteLine("Move {0} To {1}",startPlace,endPlace);
图片 88        }

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

 

图片 89        static void Main(string[] args)
图片 90        {
图片 91            IntToString(483, "");
图片 92            Console.ReadLine();
图片 93        }
图片 94        public static void IntToString(int input,String output)
图片 95        {
图片 96         //用递归法将一个整数n转换成字符串,例如,输入483,就输出字符串"483".n的位数不确定,可以是任意位数的整数。
图片 97         //   String output = "";
图片 98            output = input % 10 output;
图片 99            if (input / 10 != 0)
图片 100            {
图片 101                IntToString(input / 10,output);
图片 102            }
图片 103            else Console.WriteLine(output);
图片 104        }

 

------------------------------------------二分查找算法:

  1. package com.dylan.algorithm;  
  2.   
  3. import javax.sound.sampled.Mixer;  
  4.   
  5. public class BinarySearch {  
  6.   
  7.     public static void main(String[] args) {  
  8.         // TODO Auto-generated method stub  
  9.         
  10.          int arr[] ={10,24,36,47,68,89,130};  
  11.          int index = Search(arr, 89);  
  12.          System.out.println(index);  
  13.     }  
  14.     /*实现二分查找算法(折半算法) 
  15.      *要确定数组是排序好的 
  16.      *最好是里面一定包含该元素 
  17.      */  
  18.     public static int  Search(int[] arr,int key ) {  
  19.            
  20.           int min =0;  
  21.           int max=arr.length-1;  
  22.           int mid = (min max)/2;  
  23.           while(arr[mid]!=key){         
  24.               if (arr[mid]<key) {  
  25.                  min=mid 1;  
  26.                 }else if (arr[mid]>key) {              
  27.                  max=mid-1;  
  28.                }  
  29.              if(max<min){               
  30.                  return -1;//里面不存在值为key的元素  
  31.              }  
  32.              //继续折半  
  33.              mid=(min max)/2;  
  34.           }  
  35.             
  36.         return mid;  
  37.     }  
  38.   

c# 递归算法

本文由美高梅4858官方网站发布,转载请注明来源

关键词: 代码 数列 行输出 ifn