A better algorithm

This is a discussion on A better algorithm within the C Programming forums, part of the General Programming Boards category; I was given this assignment: There is one integral solution to the equation (a^5)+(b^5)+(c^5)+(d^5)+(e^5)=(f^5) that satisfies 1 <= a <= ...

  1. #1
    Climber spoon_'s Avatar
    Join Date
    Jun 2002
    Location
    ATL
    Posts
    182

    A better algorithm

    I was given this assignment:

    There is one integral solution to the equation (a^5)+(b^5)+(c^5)+(d^5)+(e^5)=(f^5) that satisfies 1 <= a <= b <= c <= d <= e <= f <= 75. Find the solution.

    My algorithm works btw, the answers are a = 19, b = 43, c = 46, d = 47, e = 67, f = 72.

    I have done this assignment in C and Java (it has to be turned in as Java code and I don't know any good Java BBSs. I did it in C so I could find help here), but its a sucky algorithm. Its of O(n^5), maybe O(n^6). I think that its the best it can be. It is just one of those problems that requires brute force. I've looked at this for a few days and can't see a better way.

    The code:
    Code:
    #include<stdio.h>
    #include<math.h>
    
    #define NOT_FOUND -1
    
    int binarySearch(double *n, int n_size, double z)
    {
    	int low = 0;
    	int mid = 0;
    	int high = n_size;
    
    	while(low <= high)
    	{
    		mid = (low + high) / 2;
    
    		if(n[mid] < z)
    		{
    			low = mid + 1;
    		}
    		else if(n[mid] > z)
    		{
    			high = mid - 1;
    		}
    		else
    		{
    			return mid;
    		}
    	}
    
    	return NOT_FOUND;
    }
    
    int main(int argc, char *argv[])
    {
    	int i = 0,
    		a = 0,
    		b = 0,
    		c = 0,
    		d = 0,
    		e = 0;
    
    	int f = 0;
    	double x[75];
    
    	for(i = 0; i < 75; i++)
    	{
    		x[i] = pow((i + 1), 5);
    	}
    
    	for(a = 0; a < 75; a++)
    		for(b = a; b < 75; b++)
    			for(c = b; c < 75; c++)
    				for(d = c; d < 75; d++)
    					for(e = d; e < 75; e++)
    					{
    						if((f = binarySearch(x, 74, (x[a] + x[b] + x[c] + x[d] + x[e]))) != NOT_FOUND)
    						{
    							printf("a = %d, b = %d, c = %d, d = %d, e = %d\nf = %d", (a + 1), (b + 1), (c + 1), (d + 1), (e + 1), (f + 1));
    							return 0;
    						}
    					}
    	return 0;
    }
    Any hints & help would be appreciated.

    spoon_
    Last edited by spoon_; 03-01-2003 at 12:10 AM.

  2. #2
    CS Author and Instructor
    Join Date
    Sep 2002
    Posts
    511

    Cool

    Check the web for answers. Big Oh notation of o^5- not sure about that!
    Mr. C: Author and Instructor

  3. #3
    Registered User
    Join Date
    Feb 2003
    Posts
    595
    In this case, simpler seems to be much faster:

    Code:
    #include<stdio.h>
    
    int main()
    {
            int i,
            a = 0,
            b = 0,
            c = 0,
            d = 0,
            e = 0,
            f = 0;
    
        double asum, bsum, csum, dsum, esum;
        double pow[75];
        for (i = 1; i < 75; i++)
            pow[i] = (double)i*i*i*i*i;
    
        for(f=74;f>1;f--)
        {
    
        for(a = 0, asum = 0; a < f; a++)
            {
                asum = pow[a];
    
                for(b = a, bsum = 0; b < f && bsum < pow[f]; b++)
                {
                    bsum = asum + pow[b];
                    for(c = b, csum = 0; c < f && csum < pow[f]; c++)
                    {
                        csum = bsum + pow[c];
                        for(d = c, dsum = 0; d < f && dsum < pow[f]; d++)
                        {
                            dsum = csum + pow[d];
                            for(e = d, esum = 0; e < f && esum <= pow[f]; e++)
                            {
                                esum = dsum + pow[e];
                                if(esum == pow[f])
                                {
                                    printf("a = %d, b = %d, c = %d, d = "
                                        "%d, e = %d, f = %d\n",a,b,c,d,e,f);
                                    printf("pow[f] = %.0f\n",pow[f]);
    
                                    return 0;
                                }
                            }
                        }
                    }
                }
            }
        }
        printf("Not found.\n");
    
        return 0;
    }
    Last edited by R.Stiltskin; 03-02-2003 at 09:31 AM.

  4. #4
    Climber spoon_'s Avatar
    Join Date
    Jun 2002
    Location
    ATL
    Posts
    182
    Ahh, yes. Thats a different way of doing it and is definately faster than my first post.

    However, I found another way of doing it that is slightly faster than yours (about 1.25-1.50 seconds).

    I just introduced a low variable to the binary search routine and passed the variable e into it. I based this on the fact that e is going to be equal to or less than f, so why not just start searching at index e.

    Code:
    #include<stdio.h>
    #include<math.h>
    
    #define NOT_FOUND -1
    
    int binarySearch(double *list, int list_size, double find_this, int low)
    {
    	int mid;
    	int high = list_size;
    
    	while(low <= high)
    	{
    		mid = (low + high) / 2;
    
    		if(list[mid] < find_this)
    		{
    			low = mid + 1;
    		}
    		else if(list[mid] > find_this)
    		{
    			high = mid - 1;
    		}
    		else
    		{
    			return mid;
    		}
    	}
    
    	return NOT_FOUND;
    }
    
    int main(int argc, char *argv[])
    {
    	int i = 0,
    		a = 0,
    		b = 0,
    		c = 0,
    		d = 0,
    		e = 0;
    
    	int f = 0;
    	double x[75];
    
    	for(i = 0; i < 75; i++)
    	{
    		x[i] = pow((i + 1), 5);
    	}
    
    	for(a = 0; a < 75; a++)
    	{
    		for(b = a; b < 75; b++)
    		{
    			for(c = b; c < 75; c++)
    			{
    				for(d = c; d < 75; d++)
    				{
    					for(e = d; e < 75; e++)
    					{
    						if((f = binarySearch(x, 74, x[a] + x[b] + x[c] + x[d] + x[e], e)) != NOT_FOUND)
    						{
    							printf("a = %d, b = %d, c = %d, d = %d, e = %d\nf = %d", (a + 1), (b + 1), (c + 1), (d + 1), (e + 1), (f + 1));
    							return 0;
    						}
    					}
    				}
    			}
    		}
    	}
    
    	printf("Not Found\n");
    	return 0;
    }
    {RTFM, KISS}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Implement of a Fast Time Series Evaluation Algorithm
    By BiGreat in forum C Programming
    Replies: 7
    Last Post: 12-04-2007, 02:30 AM
  2. Replies: 4
    Last Post: 12-10-2006, 07:08 PM
  3. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21