课后作业——递归（组合数、汉诺塔、回文）

课后作业1

使用组合数公式利用n!来计算

一、 程序设计思想

定义n,k,输入并检测输入的值是否是整数，如果n>k，调用计算阶乘的函数，计算并输出结果。阶乘计算函数使用递归的思想，并使用的是BigInteger类；

二、 程序流程图

 

三、 源代码

import java.util.Scanner;
import java.math.BigInteger;
public class CombinatorialNumber1 {
    //信1605-3 20163693 王晓丹
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        System.out.println("请输入组合数的n,k,以便计算n!/k!*(n-k)!");//提示用户输入
        int n=0,k=0;
        if(input.hasNextInt())//检测输入的是否是整数
        {
            n=input.nextInt();
        }
        else
        {
            System.out.println("您输入的数据有误！");
            System.exit(0);
        }
        if(input.hasNextInt())//检测输入的是否是整数
             k=input.nextInt();
        else
        {
            System.out.println("您输入的数据有误！");
            System.exit(0);
        }
        if(n>=k)//检测n是否大于k
            System.out.println(n+"!/"+k+"!*"+(n-k)+"!="+calculate(n).divide(calculate(k)).divide(calculate((n-k))));//调用
        else
        {
            System.out.println("输入错误n<k!");
            System.exit(0);
        }
        
    }
    public static BigInteger calculate(int number)//计算大数据阶乘
    {
        if(number==1||number==0)
            return BigInteger.valueOf(1);
        return BigInteger.valueOf(number).multiply(calculate((number-1)));
        
    }
}

四、 结果截图

五、     实验总结

使用BigInteger类计算大数据，那么加减乘除都要使用BigInteger的类对象进行计算，例如乘使用multiply，除使用divide；题干要求输入整数，那么就要检测输入的数据类型是否正确。

课后作业1

使用递推的方法用杨辉三角形计算

一、程序设计思想

提示用户输入n和k的值，定义n,k,并检测输入的数是否是整数，检测是否n>=k，如果不符合退出，如果都符合要求，定义一个n*n的二维数组，用来杨辉三角的数值，利用for循环嵌套给数组赋值，每一行第一个数都是0，行数和列数相等位置上的数值也为0，其余的根据Ck n+1=Ck-1 n-1+Ck n-1即arry[n][k]=arry[n-1][k-1]+arry[n-1][k]计算，最后输出arry[n][k];

二、程序流程图

三、源代码

　　

import java.util.Scanner;
public class YangHuiTriangle {
       public static void main(String[] args) {
        //信1605-3 20163693 王晓丹
        System.out.println("请输入组合数的n,k,以便计算n!/k!*(n-k)!");//提示用户输入
        Scanner input=new Scanner(System.in);
        int n=0,k=0;
        
        if(input.hasNextInt())//检测输入的是否是整数
        {
            n=input.nextInt();
        }
        else
        {
            System.out.println("您输入的数据有误！");
            System.exit(0);
        }
        if(input.hasNextInt())//检测输入的是否是整数
             k=input.nextInt();
        else
        {
            System.out.println("您输入的数据有误！");
            System.exit(0);
        }
        if(n<k)
        {
            System.out.println("输入错误n<k!");
            System.exit(0);
        }
        int arry[][]=new int [n+1][n+1];
        for(int i=0;i<n+1;i++)
        {
            for(int j=0;j<=i;j++)
            {
                if(j<i&&j!=0&&j!=i)
                    arry[i][j]=arry[i-1][j-1]+arry[i-1][j];
                else
                    arry[i][j]=1;
            }
        }
        System.out.println(n+"!/"+k+"!*"+(n-k)+"!="+arry[n][k]);
    
    }

}

四、结果截图

 

五、实验总结

如果要计算Ck n就需要n+1行，建立一个n+1行n+1列的二维数组，而不是n*n的二维数组，但输出的时候输出的是arry[n][k],因为n代表第n+1行；

课后作业1

使用递归的方法用组合数递推公式计算

一、程序设计思想

    提示用户输入n和k的值，定义n,k,并检测输入的数是否是整数，检测是否n>=k，如果不符合退出，如果都符合要求，就调用组合递归函数，输出结果；组合递归函数，递归结束的条件是n=1或者k=0或者n=k,返回1，如果不是结束条件，返回zuHe(n-1,k)+zeHe(n-1,k-1),依次类推；

二、程序流程图

三、源代码

　　

import java.util.Scanner;
import java.math.BigInteger;
public class ZuHeShu {

    public static void main(String[] args) {
        //信1605-3 20163693 王晓丹
        System.out.println("请输入组合数的n,k,以便计算n!/k!*(n-k)!");//提示用户输入
        Scanner input=new Scanner(System.in);
        int n=0,k=0;
        
        if(input.hasNextInt())//检测输入的是否是整数
        {
            n=input.nextInt();
        }
        else
        {
            System.out.println("您输入的数据有误！");
            System.exit(0);
        }
        if(input.hasNextInt())//检测输入的是否是整数
             k=input.nextInt();
        else
        {
            System.out.println("您输入的数据有误！");
            System.exit(0);
        }
        if(n<k)
        {
            System.out.println("输入错误n<k!");
            System.exit(0);
        }
        System.out.println(n+"!/"+k+"!*"+(n-k)+"!="+zuHe(n,k));

    }
    public static BigInteger zuHe(int n,int k)
    {
        if(n==1||k==0||k==n)
            return BigInteger.valueOf(1);
        else
            return zuHe(n-1,k).add(zuHe(n-1,k-1));//
    }
}

四、结果截图

课后作业2——汉诺塔

一、 程序设计思想

如果有在A座上有n个盘子，将n个盘子借助B盘子移动到C盘子上,就先将A上的n-1个盘子借助C移动到B上, 然后将A上最下面盘子的移动到C上，然后将B上的n-1个盘子借助A，移动到C上;在这个过程中如何将A上n-1个盘子移动到B上就和将A座上的盘子移动到C上是一样的操作，只是移动盘子的顺序改变，所以可以使用递归，递归结束的条件是只剩下一个盘子，然后直接将A座上最后一个盘子移动到C座上。

二、 程序流程图

三、源代码

import java.util.Scanner;
public class Hanoi {

    public static void main(String[] args) {
        // 信1605-3 20163693 王晓丹
        System.out.print("请输入盘子的个数：");
        Scanner input=new Scanner(System.in);
        int n=0;
        if(input.hasNextInt())//检测输入的是否是整数
            n=input.nextInt();
        else
            System.out.println("输入错误！");
        System.out.println("移动盘子的步骤是：");
        hanoi(n,'A','B','C');//调用函数
  
    }
    public static void hanoi(int n,char one,char two ,char three)
    {
        //如果只有一个盘子，那么就直接从A移动到B
        if(n==1)
            move(one,three);
        /*如果不止一个盘子，那么就先将one上的n-1个盘子借助three移动到two上,
         然后将one上最下面的移动到three上,
         然后将two上的n-1个盘子借助one，移动到three上;*/
        else
        {
            hanoi(n-1,one,three,two);
            move(one,three);
            hanoi(n-1,two,one,three);
        }
    }
    public static void move(char x,char y)//移动函数
    {
        System.out.println(x+"->"+y);
    }

}

四、 结果截图

课后作业3——回文

一、 程序设计思想

定义字符串变量并输入字符串，定义两个整数变量存放字符串第一个字符的位置和最后一个字符的位置，调用递归函数判断是否是回文，用if else输出结果。递归函数中，递归结束的条件是第一个字符和最后一个字符相等或者第一个字符等于最后一个字符减一，如果在递归函数中继续调用该函数，返回值是第一个和最后一个字符相等的真假并上第二个字符和倒数第二个字符是否相等；如和判断除去第一个和最后一个字符的字符串是否相等，继续调用回文递归函数，以此类推。

二、 程序流程图

三、 源代码

import java.util.Scanner;
public class palindrome {

      public static void main(String[] args) {
        //信1605-3 20163693 王晓丹
        System.out.print("请输入字符串：");
        Scanner input=new Scanner(System.in);
        String str=input.nextLine();
        int i=0;
        int j=str.length()-1;
        if(huiwen(str,i,j)==true)
            System.out.println("输入的字符串是回文！");
        else
            System.out.println("输入的字符串不是回文！");
    }
    public static boolean huiwen(String str,int i,int j)//判断是否是回文数的函数
    {
        if(i==j||i==j-1)//递归结束的条件
        {
            if(str.charAt(i)==str.charAt(j))
                return true;
            else
                return false;
        }
        else
            return (str.charAt(i)==str.charAt(j))&&huiwen(str,i+1,j-1);
        //charAt()方法返回指定索引位置的字符值
    }

}

 

四、 结果截图

 

 

五、 实验总结

本题递归结束的条件从前向后数到的字符和从后往前数到的字符下标相等或者差1，原来直接判断完，就return true是不正确的，还需要验证他们的值是否相等，相等返回true，不相等返回false。