实验二方法（递归）

递归解决（组合数计算，汉诺塔，回文字符串判断）

组合数计算

1.设计思想

*组合数计算可利用以下方法利用组合数公式计算（注意0！=1！=1,当n=k或k=0时组合数值都为1）

在主类中设计一个方法计算n！，然后再写一个方法返回公式计算的值，即进一步调用n!的计算。

**利用杨辉三角（递推方法）计算

利用二维数组先实现杨辉三角的数的储存，然后利用组合数和杨辉三角的对应关系如当n=6，k=1时即对应杨辉三角(自己定义的如上图)的第七行第二个元素即二维数组中的a[6][1]，利用循环输出该数，即可。

***利用组合数递推公式（递归方法）计算

当k=0或n=k时，返回1，然后利用上面的递推公式返回cucu(n-1,k-1)+cucu(n-1,k)即可算出

的值。

2.程序流程图

Main函数

N！的计算

组合数公式（利用n！）计算

递归（组合式递推公式）

3.源程序代码

package Work_two;

import java.util.Scanner;
public class Second_Test {
     int cu(int  n)//计算n的阶乘
    {
        if(n==0||n==1)
            return 1;
        return n*cu(n-1);
    }
    int cuc(int n,int k)//利用N！计算
    {
        if(k==0||n==k)
            return 1;
        return cu(n)/(cu(k)*cu(n-k));    
    }
    int  cucu(int n,int k)//递归（组合式递推公式）
    {
        if(k==0||n==k)
            return 1;
        return  cucu(n-1,k-1)+cucu(n-1,k);
        
    }
    public static void main(String[] args) {
        Second_Test t=new Second_Test ();
         Scanner in=new Scanner(System.in);
         int n,k,a[][]=new int[100][100];
         boolean flag=true;
         do {
             System.out.println("请输入实现组合数的数目 n k");
             n=in.nextInt();
             k=in.nextInt();
         if(n>=k)
         {
         System.out.println("以下是三种方法实现  ");
         System.out.println("1: 组合数公式计算"); 
         System.out.println("组合数计算结果"+t.cuc(n,k));
         System.out.println("2: 组合数递推公式（递归方法）计算"); 
         System.out.println("组合数计算结果"+t.cucu(n,k));
         System.out.println("3: 杨辉三角（递推方法）计算"); 
         for(int i=0;i<100;i++)//利用杨辉三角计算(递推)生成部分杨辉三角
         {  
             for(int j=0;j<=i;j++)
             { 
                 if(i==j||j==0)
                     a[i][j]=1;
                 else
                     a[i][j]=a[i-1][j-1]+a[i-1][j];
             }
         }
          System.out.println("组合数计算结果"+a[n][k]);//两种输出方式
        /* for(int i=0;i<10;i++)
         {
             for(int j=0;j<=i;j++)
             {
                 if(i==n&&j==k)
                    {
                    System.out.println("组合数计算结果"+a[i][j]);
                    }     
             }
         }*/
          System.out.println("是否还要继续计算 1--继续  2--退出");
          int s=in.nextInt();
           if(s==1)
               flag=false;
           else
           {
               flag=true; 
               System.out.println("已退出运算");
           }
         }
         else
             {
             System.out.println("输入不规范，请重新输入");flag=false;
             }
         
    }while(!flag);
    }
    

}

4.结果截图

二、汉诺塔问题

1.程序设计思想

若只有一个盘子即将其直接从A塔移动到C塔，若有n个盘子，即先将n-1看做整体，即盘子分为二部分，最上面，第n个盘子，先将最上面放在B塔，然后第n个盘子放在C塔，然后将整体放在C塔。A->B ,A->C ,B->C,这样既完成了从A塔到C塔的目的，然后整体重复做以上操作即可。

2.程序流程图

Main 函数

3.源代码

package Work_two;
import java.util.Scanner;
public class Four {
    int m=0;
    void move(int level,String from,String mid,String to)
    {
        if(level==1)
        {
            System.out.println("第"+(++m)+"步 将 1号 盘子"+"从  "+from+"塔 移动到 "+to+" 塔");
        }
        else//++m先加再使用，显示步数
        {
        move(level-1,from,to,mid);//A->B(n-1)整体移动
        System.out.println("第"+(++m)+"步 将 "+level+"号 盘子"+"从  "+from+"塔 移动到 "+to+" 塔");//A->c
        move(level-1,mid,from,to); //B->C
        }            
    }
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        Four f=new Four();
        boolean flag=true;
        while(flag) {
        System.out.print("输入盘子总数：");
        int n=in.nextInt();//读入盘子个数
        if(n>0)
        {
        System.out.println("操作如下：");
        f.move(n, "A", "B", "C");
        flag=false;
        }
        else
            {System.out.println("输入错误，请重新输入");flag=true;}
        }    
    }

}

4.结果截图

三、回文字符串

1.程序设计思想

将读入的字符串中每一个字符通过toCharArray()提取到字符数组a[]中，类中定义一个方法从字符数组的首尾开始判断对应位置的字符是否相等，若不相等，返回0，若判断结束，length为0或1，返回1。在main函数中调用类的该方法，如果返回值是1，即该字符串为回文，否则不是。

2.程序流程图

3.源程序

package Work_two;
import java.util.Scanner;
public class Three {
    int test(int high,int low,String s,int length)
    {
        char a[]=s.toCharArray();
        if(length==0||length==1)
            return 1;
        else if(a[low]!=a[high])
            return 0;
        return test(high-1,low+1,s,length-2); //两个已比较，所以下一次只需比较length（）-2个
        
    }
    public static void main(String[] args) {
        Three t=new Three();
        Scanner in=new Scanner(System.in);
        System.out.println("输入 字符串");
        String s=in.nextLine();//读入一行字符串
        if(t.test(s.length()-1,0,s,s.length())==1)
            System.out.println("该字符串是回文字符串");
        else
            System.out.println("该字符串不是回文字符串");
    }
}

4.结果截图