关于递归求最大值问题（在数组中）

田磊阳

搞了半天。还是不解，求原理？代码怎么写的。

陈圳 · 陈圳

本帖最后由陈圳于 2013-4-15 10:06 编辑

System.out.println(getMax(3,2,6,4,3,10));
System.out.println(getMaxNum(3,4,6,34,10));
}
public static int getMax(int...arr){
int max=arr[0];
for(int i=1;i<arr.length;i++){
if(max<arr[i])
max=arr[i];
}
return max;
}
public static int getMaxNum(int length,int...arr){方法有误,我在修改
int max=arr[length-1];
if(max<arr[length])
return getMaxNum(length--,arr);
else return max;
}

复制代码

这样做没有意义哦,只是实现了.

yinbolove576 · yinbolove576

建议楼主去看看毕老师第20天中IO流的第7小节内容，讲得很详细的，可好好参考参考~~~

通行天下 · 通行天下

本帖最后由通行天下于 2013-4-15 10:42 编辑

class TestMax
{
static int max = 0;
public static int getMax(int[] a,int i)
{
for(;i<a.length-1;)
{
if(a[i] > a[max])
{
max = i;
getMax(a,++i);
}
getMax(a,++i);
}
return a[max];
}
public static void main(String[] args)
{
int[] arr = {1,5,3,4,7,9,8};
System.out.println("Max="+getMax(arr,1));
}
}
希望对你有用！

复制代码

陈圳 · 陈圳

int[] arr={5,46,57,600,340,100};
int length=arr.length-1;
int max=0;
System.out.println(getMaxNum(max,length,arr));
}
public static int getMax(int...arr){
int max=arr[0];
for(int i=1;i<arr.length;i++){
if(max<arr[i])
max=arr[i];
}
return max;
}
public static int getMaxNum(int max,int length,int...arr){
if(length==0)
return max;
if(max<arr[length])
max=arr[length]+(arr[length]=max)*0;
return getMaxNum(max,length-1,arr);
}

复制代码

影响力147753321 · 影响力147753321

陈圳发表于 2013-4-15 10:41

其它的都看懂了。这一句(arr[length]=max)*0;是什么意思？求教？

Alan · Alan

楼主看以下代码就OK了

概述
程序调用自身的编程技巧称为递归（ recursion）。递归做为一种算法在程序设计语言中广泛应用。递归有直接递归和间接递归
•直接递归：函数在执行过程中调用本身。
•间接递归：函数在执行过程中调用其它函数再经过这些函数调用本身。
•表达方式：
•递归算法有四个特性：
（1）必须有可最终达到的终止条件，否则程序将陷入无穷循环；
（2）子问题在规模上比原问题小，或更接近终止条件；
（3）子问题可通过再次递归调用求解或因满足终止条件而直接求解；
（4）子问题的解应能组合为整个问题的解。
下面将从以下几个典型的例子来讲解递归算法：
汉诺塔问题
如图，汉诺塔问题是指有三根杆子A,B,C。C杆上有若干碟子，把所有碟子从C杆上移到B杆上，每次只能移动一个碟子，大的碟子不能叠在小的碟子上面。求最少要移动多少次？
当n=1时：
Move 1 from A to C
当n=1时：
Move 1 from A to B
Move 2 from A to C
Move 1 from B to C
当n=1时：
Move 1 from A to C
Move 2 from A to B
Move 1 from C to B
Move 3 from A to C
Move 1 from B to A
Move 2 from B to C
Move 1 from A to C
源代码
[java]
static StringBuffer str = new StringBuffer();
/**
* //汉诺塔问题
* @param n 盘子的个数
* @param x 将要移动盘子柱子
* @param y 要借用的柱子
* @param z 要移动到的柱子
* @return
*/
public static String hanio(int n, Object x, Object y, Object z) {
//String str ="";
if(1 == n)
str.append(move(x, n, z) + "\n");
else {
hanio(n-1, x, z, y);
str.append(move(x, n, z) + "\n") ;
hanio(n-1, y, x, z);
}
return str.toString();
}
private static String move(Object x, int n, Object y) {
//System.out.println("Move " + n + " from " + x + " to " + y);
return "Move " + n + " from " + x + " to " + y;
}
fibonacci数列
斐波纳契数列，又称黄金分割数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波纳契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=F(n-1)+F(n-2)（n>=2，n∈N*）
源代码
[java]
/**
* fibonacci数列
* @param n
* @return
*/
public static long fibonacci(int n) {
if((0 == n) || (1 == n)) {
return n;
}else {
return fibonacci(n-1) + fibonacci(n-2);
}
}
1加到n累加
用递归实现从1加到n，即1+2+3+4+...+n。
源代码
[java]
/**
* 累加,从1加到n，即1+2+3+4+...+n
* @param n 要累加到的数值
* @return 累加的结果
*/
public static long total(int n) {
if(1 == n) {
return n;
}else {
return total(n-1) + n;
}
}
从1到n累积
用递归实现，从1到n累积，即1*2*3*...*n
源代码
[java]
/**
* 从1到n的累积，即1*2*3*...*n
* @param n 要累乖到的数值
* @return
*/
public static long accumulate(int n) {
if(1 == n) {
return n;
}else {
return accumulate(n-1) * n;
}
}
求数组中的最大值
用递归算法求数组中的最大值。
源代码
[java]
/**
* 用递归算法求数组中的最大值
* @param a 数组
* @param low 数组下标
* @param heigh 数组上标
* @return
*/
public static int Max(int[] a, int low, int heigh) {
int max;
if(low > heigh-2) {
if(a[low] > a[heigh]) max = a[low];
else max = a[heigh];
}else {
int mid = (low + heigh)/2;
int max1 = Max(a, low, mid);
int max2 = Max(a, mid+1, heigh);
max = max1>max2 ? max1 : max2;
}
return max;
}
数字塔问题
用递归算法求解数字塔问题。
n=1时
1
n=2时
1
2 2
n=3时
1
2 2
3 3 3
n=4时
1
2 2
3 3 3
4 4 4 4
源代码
[java]
/**
* 用递归算法求解数字塔问题
* @param n 数字塔的行数
* @return 数字塔的字符串
*/
public static String tourData(int n) {
String str = new String();
if(1 == n) {
str = rowData(n) + "\n";
return str;
}
else {
str = tourData(n-1) + rowData(n) + "\n";
}
return str;
}
private static String rowData(int n) {
String str = new String();
for(int i=0; i<n; i++) {
str = str+ n + " ";
}
return str;
}

复制代码

陈圳 · 陈圳

影响力147753321 发表于 2013-4-15 11:13
其它的都看懂了。这一句(arr[length]=max)*0;是什么意思？求教？

今日总结:关于一步交换两个数值的方法的升华;
int a=5,b=3;
a=b+(b=a)/0;一步交换两个数的值//也是一种最优的算法吧.
异或:异或是位运算,速度应该比较快.
a=a^b;
b=a^b;
a=a^b;
简化:
a=b^(b=a)^a;//现写笔记现总结的.有用!
比较两种方法:a=b^(b=a)^a;
a=b^(b=a)^a;
经过真实测试:所有交换两种数值的方法中:
a=b+(b=a)/0;是最快的.所以建议使用这个
/*以下是n=100000000循环次交换两数取值的使用时间花费:a=b+(b=a)/0速度最快.
而且也证了一步运算,比正确交换值效率要高.
a1=99999994
406毫秒
a2=99999994
281毫秒
a3=99999994
485毫秒
a4=99999994
438毫秒*/
/**反转List集合内的元素
*/
public static <T> List<T> reveriousList(List<T> list){
int length=list.size()-1;
for(int i=0;i<list.size()/2;i++,length--)
list.set(i,list.set(length,list.get(i)));//实现一步交换两个List集合的值.
return list;
}
分析算法:互相list集合中两个元素的位置
4 5
0 1
第一步:list.set(0,list.set(1,list.get(0)));
第二步:list.set(0,list.set(1,4))
第三步:list.set(0,5)
这样,一句话就实现了两个值的互换.我自己想的,哈哈.
/*

复制代码

吴林飞 · 吴林飞

晕，你们写那么多看得我真累，编程追求的是简单化，
以下是我自己的代码实现，不知道还能不能简化，

class DiGui
{
public static void main(String[] args)
{
int[] arr = {4,5,55,7,9,22,32,19};
//从指定角标开始搜索
int max = getMax(arr,7);
System.out.println(max);
}
//从指定角标开始搜索数组，获取最大值
public static int getMax(int[] arr,int index)
{
if(index>arr.length-1)
{
throw new RuntimeException("请不要超出我的能力极限");
}
if(index==arr.length-1)
{
return arr[index];
}
if(index<arr.length-1)
{
if(arr[index]>arr[0])
{
int temp = arr[0];
arr[0] = arr[index];
arr[index] = temp;
index++;
getMax(arr,index);
}
else
{
index++;
getMax(arr,index);
}
}
return arr[0];
}
}

复制代码

吴林飞 · 吴林飞

本帖最后由吴林飞于 2013-4-15 13:58 编辑

刚刚的有点问题修改了下

class DiGui1
{
public static void main(String[] args)
{
int[] arr = {4,5,55,7,9,22,32,59};
int max = getMax(arr,7);
System.out.println(max);
}
//从指定角标开始搜索数组，获取最大值
public static int getMax(int[] arr,int index)
{
if(index>=arr.length)
{
throw new RuntimeException("请不要超出我的能力极限");
}
if(index<arr.length)
{
if(arr[index]>arr[0])
{
int temp = arr[0];
arr[0] = arr[index];
arr[index] = temp;
if(index==arr.length-1)
return arr[0];
index++;
getMax(arr,index);
}
else
{
if(index==arr.length-1)
return arr[index];
index++;
getMax(arr,index);
}
}
return arr[0];
}
}

复制代码

吴林飞 · 吴林飞

陈圳发表于 2013-4-15 10:41

你的代码有问题，如果我给出的数组是int[] arr={1100,46,57,600,340,900}，求出的最大值是900.

陈圳 · 陈圳

吴林飞发表于 2013-4-15 13:53
你的代码有问题，如果我给出的数组是int[] arr={1100,46,57,600,340,900}，求出的最大值是900. ...

那个代码是有问题,我注释了写了...我下面把改正后的代码在楼下又发过...

陈圳 · 陈圳

影响力147753321 发表于 2013-4-15 11:13
其它的都看懂了。这一句(arr[length]=max)*0;是什么意思？求教？

我做题做晕了.这个根本不需要换值.坑爹呀.如果赋值就行了.但是那个还是有点用的.

黄玉昆 · 黄玉昆

如果问题未解决，请继续追问，如果没有问题了，请将帖子分类改为“已解决”，谢谢

帐号		自动登录	找回密码
密码			加入黑马

关于递归求最大值问题（在数组中）

评分

13 个回复

评分

评分

评分

评分

评分

黑马骑士勋章