导航:首页 > 源码编译 > java递归算法面试例子

java递归算法面试例子

发布时间:2023-07-25 18:05:01

⑴ 求经典的递归算法以及案例(可用C#、PHP、java其中一种语言来写)!

我用C#来写(注意,更多的请直接到我的个人博客,点击, http://www.cnblogs.com/serviceboy/archive/2009/07/19/1526590.html,收看) 【例1】有甲、乙、丙、丁四人,从甲开始到丁,一个比一个大1岁,已知丁10岁,问甲几岁?【分析】这是递归法的一道非常典型的题目——因为我们可以很显然知道:假设要计算甲的年龄,那么必须直到乙的年龄;同样,算乙的必须直到丙的,算丙的必须知道丁的,因为丁已知,自然可以往前推算了。现在假设有一个数学模型(函数)可以计算出他们各自的年龄(方便期间我们给他们编号——甲=1,乙=2,丙=3,丁=4),那么存在这一个F(X)函数,X表示某人的编号,其规律如下:F(1)=F(2)+1F(2)=F(3)+1F(3)=F(4)+1F(4)=10显然,直到X=4的时候是一个终止值,其余情况下都是返回F(X’),F(X’’)……F(X’’……’),且前者总是比后至大1,这也符合了X’和X总是呈现一定函数关系(设想一下,如果不是等差和等比,又怎么可能在一个递归函数中进行计算?要知道,函数本身就是一个公式表示,既然是公式,那么一定是一种函数关系Y=F(X)),此处显然X和X’的关系是X=X’+1。根据规律式,我们可以写出该递归函数:int AgeCal(int id)
{
if(id==4) return 10;
else
return (AgeCal(id+1)+1);
} 【例2】计算n!【分析】虽然这道题目不像例1一样清晰明了告诉你使用“递归”法反推,但是我们有这样一个常识——n!=(n-1)!*n;(n-1)!=(n-2)!*(n-1)……n=0或1,返回1.显然n与n-1,n-2也是线性的递减数列(等差关系)。其规律如下:F(n)=F(n-1)*nF(n-1)=F(n-2)*(n-1)F(n-2)=F(n-3)*(n-2)……F(1)=1或者F(0)=1(防止别人直接输入0)编写其递归函数,如下:int Fac(int n)
{
if(n==1 || n==0)
{
return 1;
}
else
return Fac(n-1)*n;
} 【例3】求一组整数中的最大(小)值(整数是一个int[]数组,个数未知)。【分析】当数字只有两个的时候,我们可以使用>和<直接比较;但是当数字超过2个的时候(假设3个),那么我们可以使用一个预订的函数(比如Max(1,2)和3进行比较),由于1,2两个数比较的时候已经得到一个最大值,因此在回代到Max中又变成了两个数的比较。这样,我们可以发现一个规律:F(1,2,3,4……n)=F(1,2,3,4……n-1)和n比较F(1,2,3,4……n-1)=F(1,2,3,4……n-2)和n-1比较……F(1,2,3)=F(1,2)和3比较F(1,2)=结果(并回代)相应的递归函数如下(C#):Code
int Max(int[]numbers)
{
if(numbers.Length==2)
{
return (numbers[0]>numbers[1]?numbers[0]:numbers[1]);
}
else
{
int[]tempnumbers=new int[numbers.Length-1];
for(int i=0;i<numbers.Length-1;++i)
{
tempnumbers[i]=numbers[i];
}
return (Max(tempnumbers)>numbers[numbers.Length-1]? Max(tempnumbers): numbers[numbers.Length-1]
}
}

⑵ java 递归问题

(1) 递归就是在过程或函数里调用自身;
(2) 在使用递归策略时,必须有一个明确的递归结束条件,称为递归出口。
递归算法一般用于解决三类问题:
(1)数据的定义是按递归定义的。(Fibonacci函数)
(2)问题解法按递归算法实现。(回溯)
(3)数据的结构形式是按递归定义的。

下面这个例子以递归的方法计算n的阶乘。
public class Test {
public static int factorial(int n){
if(n == 0){
return 1;
}else{
return n * factorial(n-1);
}

}

public static void main(String[] args) {
System.out.println(factorial(3));
}

}

⑶ java递归算法的例子

十进制整数转二进制字符串的递归写法:

public String dtob(int n) {
if (n == 0 || n == 1) {
return Integer.toString(n);
} else {
return dtob(n / 2) + Integer.toString(n % 2);
}
}

⑷ java递归算法的例子。

阶乘:

要求:给定一个数值,计算出它的阶乘值,例如5的阶乘为5*4*3*2*1

实现:

[html] view plain

<span style="font-size:12px;"> // 利用递归实现一个数的阶乘值 private static BigDecimal getNum(BigDecimal inNum) { if (inNum.compareTo(BigDecimal.ONE) == 0) { return inNum; } return inNum.multiply(getNum(inNum.subtract(BigDecimal.ONE))); }</span>

(2)Fibonacci数列:1,1,2,3,5,8,13……

要求:找出数列中指定index位置的数值

实现:

[html] view plain

<span style="font-size:12px;"> // 利用递归实现了Fibonacci数列 private static int fab(int index) { if (index == 1 || index == 2) { return 1; } else { return fab(index - 1) + fab(index - 2); } }</span>

(3)汉诺塔

要求:汉诺塔挪动

实现:

[html] view plain

<span style="font-size:12px;"> <span style="white-space:pre;"> </span>private static final String DISK_B = "diskB"; <span style="white-space:pre;"> </span>private static final String DISK_C = "diskC"; <span style="white-space:pre;"> </span>private static final String DISK_A = "diskA"; <span style="white-space:pre;"> </span>static String from=DISK_A; <span style="white-space:pre;"> </span> static String to=DISK_C; <span style="white-space:pre;"> </span> static String mid=DISK_B; <span style="white-space:pre;"> </span> public static void main(String[] args) { <span style="white-space:pre;"> </span> String input=JOptionPane.showInputDialog("please input the number of the disks you want me move."); <span style="white-space:pre;"> </span> int num=Integer.parseInt(input); <span style="white-space:pre;"> </span> move(num,from,mid,to); <span style="white-space:pre;"> </span> }</span>

[html] view plain

<span style="font-size:12px;"> // 利用递归实现汉诺塔 private static void move(int num, String from2, String mid2, String to2) { if (num == 1) { System.out.println("move disk 1 from " + from2 + " to " + to2); } else { move(num - 1, from2, to2, mid2); System.out.println("move disk " + num + " from " + from2 + " to " + to2); move(num - 1, mid2, from2, to2); } }</span>

(4)排列组合

要求:将输入的一个字符串中的所有元素进行排序并输出,例如:你给出的参数是"abc",

则程序会输出

abc

acb

bac

bca

cab

cba

实现:

[html] view plain

<span style="font-size:12px;"><span style="white-space:pre;"> </span>public static void permute(String str) { <span style="white-space:pre;"> </span> char[] strArray = str.toCharArray(); <span style="white-space:pre;"> </span> permute(strArray, 0, strArray.length - 1); <span style="white-space:pre;"> </span>}</span>

[html] view plain

<span style="font-size:12px;"> // 利用递归实现,将输入的一个字符串中的所有元素进行排序并输出 public static void permute(char[] list, int low, int high) { int i; if (low == high) { String cout = ""; for (i = 0; i <= high; i++) { cout += list[i]; } System.out.println(cout); } else { for (i = low; i <= high; i++) { char temp = list[low]; list[low] = list[i]; list[i] = temp; permute(list, low + 1, high); temp = list[low];

阅读全文

与java递归算法面试例子相关的资料

热点内容
dvd光盘存储汉子算法 浏览:755
苹果邮件无法连接服务器地址 浏览:958
phpffmpeg转码 浏览:669
长沙好玩的解压项目 浏览:140
专属学情分析报告是什么app 浏览:562
php工程部署 浏览:831
android全屏透明 浏览:730
阿里云服务器已开通怎么办 浏览:801
光遇为什么登录时服务器已满 浏览:300
PDF分析 浏览:482
h3c光纤全工半全工设置命令 浏览:139
公司法pdf下载 浏览:379
linuxmarkdown 浏览:349
华为手机怎么多选文件夹 浏览:681
如何取消命令方块指令 浏览:347
风翼app为什么进不去了 浏览:776
im4java压缩图片 浏览:360
数据查询网站源码 浏览:148
伊克塞尔文档怎么进行加密 浏览:888
app转账是什么 浏览:161