没有合适的资源?快使用搜索试试~ 我知道了~
Java递归例子.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 182 浏览量
2023-02-28
20:51:18
上传
评论
收藏 442KB PDF 举报
温馨提示
试读
22页
。
资源推荐
资源详情
资源评论
实用文档
Java 中的经典递归
//汉诺塔问题(递归)
(古代有一个梵塔,塔内有三个座 A、B、C,A 座上有 64 个盘子,盘子大小不等,大的在下,
小的在上(如图)。有一个和尚想把这 64 个盘子从 A 座移到 B 座,但每次只能允许移动一
个盘子,并且在移动过程中,3 个座上的盘子始终保持大盘在下,小盘在上。在移动过程中
可以利用 B 座,要求打印移动的步骤。如果只有一个盘子,则不需要利用B 座,直接将盘子
从 A 移动到 C。
如果有 2 个盘子,可以先将盘子 1 上的盘子 2 移动到 B;将盘子 1 移动到 c;将盘子
2 移动到 c。这说明了:可以借助 B 将 2 个盘子从 A 移动到 C,当然,也可以借助 C
将 2 个盘子从 A 移动到 B。
如果有 3 个盘子,那么根据 2 个盘子的结论,可以借助 c 将盘子 1 上的两个盘子从 A
移动到 B;将盘子 1 从 A 移动到 C,A 变成空座;借助 A 座,将 B 上的两个盘子移动
到 C。这说明:可以借助一个空座,将 3 个盘子从一个座移动到另一个。
如果有 4 个盘子,那么首先借助空座 C,将盘子 1 上的三个盘子从 A 移动到 B;将盘
子 1 移动到 C,A 变成空座;借助空座 A,将 B 座上的三个盘子移动到 C。)
package org;
import java.util.Scanner;
public class Tower {
public static void main(String[] args) {
System.out.println("输入盘子的个数:");
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
tower(n,'A','B','C');
}
public static void tower(int n,char a, char b, char c){
if(n!=0){
tower(n-1,a,c,b);
System.out.println("move disk "+n+" "+"from"+a+" "+"to "+c);
c=a;
tower(n-1,b,a,c);
实用文档
}
}
}
//-----------------------------------------------------------------------------
----------------------
//斐波那契级数
(递归,当 n 比较大时,效率比较低)
package org;
import java.util.Scanner;
public class Fib {
public static long fib(int n){
if(n==1 || n==2)
return 1;
else
return fib(n-1)+fib(n-2);
}
/* 测试 */
public static void main(String[] args) {
System.out.println("输入一个整数:");
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.println("结果为:"+fib(n));
}
}
//-----------------------------------------------------------------------------
----------------------
//最大公约数(递归)
package org;
import java.util.Scanner;
public class MaxGcd {
/* 递归实现 */
public static int gcd(int m, int n){
if(n==0)
return m;
实用文档
else if(m<=n)
return gcd(n,m);
else
return gcd(n,m%n);
}
/* 非递归实现 */
public static int gcd2(int m, int n){
if(m>=n){
while(n!=0){
int rem=m % n;
m=n;
n=rem;
}
}
else
gcd2(n,m);
return m;
}
/* 测试 */
public static void main(String[] args) {
System.out.println("请输入两个整数 m 和 n");
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
System.out.println(m+"和"+n+"的最大公约数为:"+gcd(m,n));
}
}
//-----------------------------------------------------------------------------
----------------------
//简单的 0/1 背包问题(递归):
设一背包可容物品的最大质量为 m,现有 n 件物品,质量为 m1,m2,...,mn,mi 均为正
整数,要从 n 件物品中挑选若干件,
//使背包的质量之和正好为 m
package org;
public class Bag01 {
public static boolean knap(int weight, int[] a, int n){
if(n<=0)
return false;
if(weight==a[n-1])
return true;
else{
实用文档
if(weight>=a[n-1]){ //能放
if(knap(weight-a[n-1],a,n-1))
return true;
else
return knap(weight,a,n-1); //不放
}else //不能放
return knap(weight,a,n-1); //不放
}
}
/* 测试 */
public static void main(String[] args) {
int weight=68;
int a[]={16,21,6,31,2,5,7,8,10,15};
boolean flag=knap(weight,a,10);
System.out.println(flag);
}
}
//-----------------------------------------------------------------------------
----------------------
//求 n!
package org;
import java.util.Scanner;
public class Factorial {
/* 递归实现 */
public static long fac(int n){
if(n==0 || n==1)
return 1;
else{
return (n * fac(n-1));
}
}
/* 非递归实现 */
public static long fac2(int n){
int sum=1;
if(n==0 || n==1)
return 1;
for(int i=2;i<=n;i++){
sum*=i;
}
实用文档
return sum;
}
/* 测试 */
public static void main(String[] args) {
System.out.println("输入一个整数:");
Scanner sc=new Scanner(System.in);
int n=sc.nextInt();
System.out.println(n+"!="+fac(n));
}
}
//-----------------------------------------------------------------------------
----------------------
//求 n 个数的排列(递归)
package org;
/* permutation: 排列 */
public class Permutation {
public static void perm(int[] data, int start, int end){
if(start==end-1){
for(int i=0;i<end;i++)
System.out.print(data[i]);
System.out.println();
}else{
for(int i=start;i<end;i++){
int temp;
temp=data[i];
data[i]=data[start];
data[start]=temp;
perm(data,start+1,end);
}
}
}
/* 测试 */
public static void main(String[] args) {
int[] data={1,2,3,4};
int end=4;
perm(data,0,end);
}
}
//-----------------------------------------------------------------------------
----------------------
剩余21页未读,继续阅读
资源评论
不吃鸳鸯锅
- 粉丝: 8344
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功