備戰藍橋杯------遞歸算法及經典例子

遞歸算法在程式中不斷反複調用自身的方法調用方式。此處的重點是調用自身

遞歸滿足兩個條件

1.有反複執行的過程（調用自身）

2.有跳出反複執行過程的條件（遞歸出口）

遞歸算法在軟體競賽中，考察的非常多

我的qq：1527624144   希望和大家交流，一起努力進入總決賽

經典例子：1.求10的階乘

public class A13 {

	public static void main(String[] args) {
            int s=f(10);
            System.out.println(s);
	}
   public static int f(int n)
   {
	   if(n<=1)  return 1;
	   return f(n-1)*n;
   }
}
           

經典例子：2.斐波那契數組

斐波那契數列，又稱黃金分割數列，指的是這樣一個數列

1、1、2、3、5、8、13、21、34........

這個數列從第三項開始，每一項等于兩項之和

public class A15 {

	public static void main(String[] args) {
           int  s= f(8);
System.out.println(s);
	}
	//1、1、2、3、5、8、13、21、34
	public static int f(int n)  //n表示第幾項
	{
		if(n==0)  return 0;
		if(n==1) return 1;
		
		return f(n-1)+f(n-2);       //表示n的前一項，加上n的前前一項
	}

}

           

經典例子：3.排列問題

//排列問題
//  計算3個A，2個B可以組成多少排列？
//如：AAABB  ABAAB

public class A10 {

	public static void main(String[] args) {
      int s=f(3,2);	
      System.out.println(s);
      

	}
   //有m個a，n個b。組成排列
	public static int f(int m,int n)
	{
		if(m==0||n==0) return 1;
		return f(m-1,n)+f(m,n-1);   //核心思想
		//平地起風雷    思路：有兩種情況：一種是有A的排列組合，一種是沒有A的排列組合
       //f(m-1,n)   當組合為第一個A，那麼剩下（m-1）個A元素，n個B元素
           //f(m,n-1)   當組合第一個為B，那麼剩下（n-1）個B元素，m個A元素
          //然後把他們相加，就是組成了多少排列
	}	
	
		

	
	
}
           

經典例子：4.取球問題

在n個球中，任意取m個（不放回），求有多少種取法？

思路：在n個球中，假設有一個特殊的球X，用劃分：一種是包含X的取法，一種是不包含X的取法    
           

public class A {

	public static void main(String[] args) {
	     int k=f(10,3);   //在10個球中，取3個
	     System.out.println(k);
	}
	 public static int f(int n,int m)
	 {
		 if(n<m){   return 0;  }//10個球中，總球數 小于  取的球 ，那麼隻有傳回0}
	     if(n==m){ return 1;  }  //取的球等去總球數，那麼隻有一種取法
	     if(m==0){ return 1;}  //如果取0個球 ，那麼也隻有一種取法
	 
	     return f(n-1,m-1)+f(n-1,m);
	     
	 
	 }
	
	
	
}
           

以上是關于遞歸算法的經典應用。遞歸算法在藍橋杯中考察的很多

樓主我也報名參加了藍橋杯。看過藍橋直播經驗交流會。

老師說過：1.主要是暴力破解，多層循環的解題模式

2.深入暴力破解，熟練遞歸技巧    

有機會沖擊進總決賽。

我是一名大二的學生，非常想能進入總決賽。下面我來說一下真題，希望看到的朋友能和一起交流，一起努力，進入總決賽

————————————————————————————————————————

真題1  （代碼填空）

代碼填空：

楊輝三角形

                  1                           第一行

                 1  1                        第二行

                1  2  1                     第三行

            1   3   3    1                 第四行

           1  4  6   4     1              第五行

        1   5  10  10   5   1          第六行

請填寫下面代碼

   //遞歸

       //第m行，第n個元素

     if(n==0)  return n=1

      if(m==n)   return n=1

        return f(m-1,n)+f(m-1,n-1)   //填空