用递归求数组最大值的位置

很奇葩的一道题，初看很简单，结果想了很久才写出来:

1. int max(const int a[], int n)
   
2. {
   
3.         if (n == 1)
   
4.                 return a[0];
   
5.         int i = a[0];
   
6.         int j = max(a+1, n-1);
   
7.         if (i > j)
   
8.                 return i;
   
9.         else
   
10.                 return j;
    
11. }

复制代码

结果发现上面的代码是求最大值而不是他的位置……
又想了很久始终无解(感觉思路被求最大值绕进去了)，求高人解答

ps:要求不用global variable,不用static，不可改变max函数的argument

这个的确是求最大值...
每次递归的时候a[0]和a[1...n-1]中的最大值作比较.

rogerdai 发表于 2013-2-10 17:46
这个的确是求最大值...
每次递归的时候a[0]和a[1...n-1]中的最大值作比较.

我写了半天终于run出结果了，结果回头一看requirement又囧了……

edussx 发表于 2013-2-10 18:08
我写了半天终于run出结果了，结果回头一看requirement又囧了……

是“不可改变max函数的输入参数”吗？

rogerdai 发表于 2013-2-10 18:10
是“不可改变max函数的输入参数”吗？

是，其实就是不能改变max函数的声明:

1. //max function declaration
   
2. int max(const int a[], int n);

复制代码

edussx 发表于 2013-2-10 18:23
是，其实就是不能改变max函数的声明:

噢，这样啊。那这个解答就是对的呀。

rogerdai 发表于 2013-2-10 19:12
噢，这样啊。那这个解答就是对的呀。

如果一个数组

1. int a[5] = {1,3,5,7,9};

复制代码

那么按照要求

1. std::cout << max(a,5);

复制代码

的结果是4(因为a[4] == 9)而不是9

edussx 发表于 2013-2-10 19:20
如果一个数组那么按照要求的结果是4(因为a[4] == 9)而不是9

我测试的结果是9呀，你再试一下吧...

rogerdai 发表于 2013-2-10 19:31
我测试的结果是9呀，你再试一下吧...

要求输出结果是4，不是9

1. int max(const int a[], int n) {
   
2.         if (n == 1) return 0;
   
3.         int p = max(a + 1, n - 1);
   
4.         return a[0] > a[p + 1] ? 0 : p + 1;
   
5. }

复制代码

目测样例是有