Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
HomeAnnouncementsWhite Papers
Discussion GroupsFirst AidDatabasesJavaBeansGUIJava 3DVirtual MachineCORBASecurityToolsGeneral
Java DirectoryOpen Source ProjectsSample Book ChaptersUser GroupsWeb Resources
Related Topics
Databases.NETMore Topics ...

Java Forum / General / September 2006

Tip: Looking for answers? Try searching our database.

A simple question about opreator.

Thread view: 
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 Magazines

Get 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 ...

Oracle MagazineNetwork ComputingComputer WorldBio-IT WorldeWeekInformation WeekInfosecurity
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.