Java Forum / General / September 2006
A simple question about opreator.
Flamingo - 12 Sep 2006 16:13 GMT Hi guys,
I want to write a recursion function that returns the maximum among the first n elemetns of an array, using at most "lgn" recursive calls.
here is my function:
public class Prob0405 {
/** * @param args */ public static double max(double[] a, int n) { if(n==1) return a[0]; int n1 = n/2; int n2 = n-n1;
double m1 = max(a, n1); double m2 = max(a+n1,n2); return (m1>m2 ? m1:m2); } }
but when I try to compile , some syntex error reported, error happend at "double m2 = max(a+n1,n2)",
it is said "The operator + is undefined for the argument type(s) double[], int",
how could modify that? Any help would be appreciated! thanks.
Manish Pandit - 12 Sep 2006 16:21 GMT The error is self-explainatory.
Why are you adding a number to an array? Recheck your logic/alogorithm - you need to be operating on array *element*, not the array *object* on that line.
-cheers, Manish
Patricia Shanahan - 12 Sep 2006 16:24 GMT > Hi guys, > [quoted text clipped - 22 lines] > but when I try to compile , some syntex error reported, error happend > at "double m2 = max(a+n1,n2)", Why are you adding to an array reference? Java has no pointer arithmetic, and even if it did, a non-null array reference points to the array object, not necessarily the first cell of the array.
This looks like an attempt to run C code in Java.
To do what you want, you need to pass around enough information to identify a consecutive slice of the array, such as start index and length, or start and end index, as well as the array reference.
Patricia
Flamingo - 12 Sep 2006 16:30 GMT sorry , I'm not very familiar with the syntax of Java, can you give me an example how to "pass around enough information "
> > Hi guys, > > [quoted text clipped - 34 lines] > > Patricia Oliver Wong - 12 Sep 2006 17:24 GMT [post re-ordered]
>> > Hi guys, >> > >> > I want to write a recursion function that returns the maximum among the >> > first n elemetns of an array, using at most "lgn" recursive calls. [Patricia wrote:]
>> To do what you want, you need to pass around enough information to >> identify a consecutive slice of the array, such as start index and >> length, or start and end index, as well as the array reference. > > sorry , I'm not very familiar with the syntax of Java, can you give me > an example how to "pass around enough information " "Add a parameter to the method which is getting called recursively" is an example of a way to pass around information.
- Oliver
Shawn - 12 Sep 2006 18:21 GMT > "Add a parameter to the method which is getting called recursively" > is an example of a way to pass around information. > > - Oliver I am very interested in this statement or strategy. Could you elaborate it a little more?
Thank you very much.
Oliver Wong - 12 Sep 2006 18:48 GMT >> "Add a parameter to the method which is getting called recursively" is >> an example of a way to pass around information. [quoted text clipped - 5 lines] > > Thank you very much. <oldCode> public void someMethod() { //Does something } </oldCode>
<newCode> public void someMethod(int aNewParameter) { //Does something } </newCode>
Seriously, this seems like such a basic concept to me that I'm not sure what more can be said on it. Previously, someMethod had no information being passed into it. Now it has an integer passed into it.
- Oliver
Shawn - 12 Sep 2006 20:45 GMT > Hi guys, > [quoted text clipped - 27 lines] > > how could modify that? Any help would be appreciated! thanks. I like your original program, even though it doesn't run. It is good thinking. I just changed it so that it runs. Following is the file Tool.java. It runs correctly.
public class Tool { public static double max(double[] aArray, int iTotal, int iStart) { if (iTotal == 1) { return aArray[iStart]; } else { int iEnd = iStart + iTotal - 1; int iFirstHalfCount = iTotal/2; int iLastHalfCount = iTotal - iFirstHalfCount;
double dMaxFirstHalf = max(aArray, iFirstHalfCount, iStart); double dMaxLastHalf = max(aArray, iLastHalfCount, iStart+iFirstHalfCount);
if (dMaxFirstHalf >= dMaxLastHalf) { return dMaxFirstHalf; } else { return dMaxLastHalf; } }
}
public static void main(String[] args) { double[] myArray = {3.3, 15.8, 9.7, 4.3, 16.6, 1.4, 3.6, 8.0, 5.2}; double max = max(myArray, 6, 0);
System.out.println("max = " + max); }
}
Oliver Wong - 12 Sep 2006 21:20 GMT > Hi guys, > [quoted text clipped - 27 lines] > > how could modify that? Any help would be appreciated! thanks. Incidentally, I don't think "what you're trying to do" (assuming I correctly guessed what you're trying to do) will work. Imagine the array is of length 4. log2(4) = 2, so you could make at most 2 recursive calls, but you actually make 4 recursive calls.
Here's the simplest solution I can think of (in pseudocode) which satisfy the (arbitrary?) requirement that the method must be recursive:
<pseudocode> public double max(double[] a, int n) { double max = MINIMAL_DOUBLE_VALUE; if (length of a == 1) { return a[0]; } if (n == SOME_MAGIC_VALUE) { return AN_IRRELEVANT_VALUE; } max(a[], SOME_MAGIC_VALUE); /*obligatory recursive call*/ for (double d : a) { if (d > max) { max = d; } } return max; } </pseudocode>
There's two cases of interest: Either the the length of the array is 1, or it is greater than 1.
If the array is length 1, then we may only make lg2(1) == 0 recursive calls. Luckily, the algorithm above makes 0 recursive calls if the array length is 1.
If the array length is > 1, then we may make l2(array length) >= 1 recurisve calls. Luckiyl, the algorithm above makes 1 recursive call if the array length is > 1.
Assumptions made are that an empty array won't be passed in (in which case the max is undefined), and that SOME_MAGIC_VALUE will not be a value passed in for n. For example, if we assume the user will never provide a negative n, SOME_MAGIC_VALUE can be -1.
- Oliver
Shawn - 12 Sep 2006 21:36 GMT > Incidentally, I don't think "what you're trying to do" (assuming I > correctly guessed what you're trying to do) will work. Imagine the array [quoted text clipped - 40 lines] > > - Oliver I never thought I would disagree anything from you. But this time is really exceptional:
I believe OP means in the oder of theta of log(n), which means double the number n, the required time (memory space? details ignored...) is only doubled, instead of linear increase, for example.
Lasse Reichstein Nielsen - 12 Sep 2006 23:21 GMT > I believe OP means in the oder of theta of log(n), which means double > the number n, the required time (memory space? details ignored...) is > only doubled, actually, only increased by 1
> instead of linear increase, for example. However, the OP's requirement about using recursion is arbitrary, since the simplest and fastest algorithm is just a linear iteration through the data.
A requirement of at most O(log2(n)) recursive calls (or log2(n)) sounds even more arbitrary, since the simplest recusive function takes a approx. n/2 recursive calls (this is the one the OP has actually implemented), and an algorithm using log2(n) calls would be needlessly complicated.
And my guess about the cause of the problem is that the OP has tried to implement a C (or C++) algorithm using pointer arithmetic in Java.
/L
 Signature Lasse Reichstein Nielsen - lrn@hotpop.com DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html> 'Faith without judgement merely degrades the spirit divine.'
Patricia Shanahan - 13 Sep 2006 00:13 GMT >> Incidentally, I don't think "what you're trying to do" (assuming I >> correctly guessed what you're trying to do) will work. Imagine the [quoted text clipped - 47 lines] > the number n, the required time (memory space? details ignored...) is > only doubled, instead of linear increase, for example. To find the maximum of an array every element must participate in at least one comparison, implying Omega(N) comparisons.
In the recursive code above, there will be N calls with length 1, sup(N/2) calls with length 2, ... , 1 call with length N, a total of about 2N calls, Theta(N).
Finding the maximum is very different from the classic O(log N) problem, binary search, because binary search, at each level, can use a single comparison to halve the data that must be examined.
The recursion depth is O(log N), which may be what is meant.
Of course, one can do the problem, very efficiently, with a single call which is O(lg N) calls.
Patricia
Free MagazinesGet these publications absolutely FREE for up to 12 months. There are no hidden fees and no obligation. Simply choose a title, complete the application form and submit it. Read more ...
|
|
|