Finding the 3 largest numbers of the five entered

This is a discussion on Finding the 3 largest numbers of the five entered within the C Programming forums, part of the General Programming Boards category; So basically i have to enter 5 integers and then find the largest 3 of the 5 that were entered. ...

  1. #1
    Registered User
    Join Date
    Feb 2009
    Posts
    3

    Finding the 3 largest numbers of the five entered

    So basically i have to enter 5 integers and then find the largest 3 of the 5 that were entered. I'm not sure exactly where I went wrong. The program will run but it gives the wrong answers everytime. If someone could help me out it would be greatly appreciated. Thanks

    Code:
    #include<stdio.h>
    
    int main(void)
    
    {
    int n1, n2, n3, n4, n5;
    
    printf("Enter 5 integer numbers\n");
    scanf("%d,%d,%d,%d,%d", &n1, &n2, &n3, &n4, &n5);
    
    printf("The largest 3 numbers of the 5 entered are:");
    
    if ((n1>n2)&&(n1>n3)&&(n1>n4)&&(n1>n5))
    printf("%d",n1);
    else {if(n2>n3 && n2>n4 && n2>n5) 
    printf("%d",n2);
    else if(n3>n4 && n3>n5 && n3>n2)
    printf("%d",n3);
    else if(n4>n5 && n4>n2 && n4>n3)
    printf("%d",n4);} 
    
    if ((n2>n1)&&(n2>n3)&&(n2>n4)&&(n2>n5))
    printf("%d",n2);
    else {if (n1>n3 && n1>n4 && n1>n5) 
    printf("%d",n1);
    else if (n3>n4 && n3>n5 && n3>n1)
    printf("%d",n3);
    else if (n4>n5 && n4>n1 && n4>n3)
    printf("%d",n4);}
    
    if ((n3>n1)&&(n3>n2)&&(n3>n4)&&(n3>n5))
    printf("%d",n3);
    else {if (n1>n2 && n1>n4 && n1>n5) 
    printf("%d",n1);
    else if (n2>n4 && n2>n5 && n2>n1)
    printf("%d",n2);
    else if (n4>n5 && n4>n1 && n4>n2)
    printf("%d",n4);}
    
    if ((n4>n1)&&(n4>n2)&&(n4>n3)&&(n4>n5)) 
      printf("%d",n3);
    else {if (n1>n2 && n1>n3 && n1>n5) 
    printf("%d",n1);
    else if (n2>n3 && n2>n5 && n2>n1)
    printf("%d",n2);
    else if (n3>n5 && n3>n1 && n3>n2)
    printf("%d",n3);}
    
    
    if ((n5>n1)&&(n5>n2)&&(n5>n3)&&(n5>n4))
    printf("%d",n5);
    else {if (n1>n2 && n1>n3 && n1>n4) 
    printf("%d",n1);
    else if (n2>n3 && n2>n4 && n2>n1)
    printf("%d",n2);
    else if (n3>n4 && n3>n1 && n3>n2)
    printf("%d",n3);}
    
    return (0);
    
    }

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Consider what will happen in a few months or so when your projects amount to several hundred or several thousand lines of code. Will you show up here and post the whole thing, explaining "train A and train B, train A coming from a small port in the south carrying agriculture, of which the fruit I place on top so it isn't squished. Then there is a communication system between the trains, which is used for various purposes. Neither of them are on the same track, so I don't know why they collide."

    I could, and probably someone eventually will, come along and extract the relevant as opposed to irrelevant information. However, if it was really important to me to solve the problem (and by me, I think I now mean you), I might decide to do that myself, first, before I post anything.

    But how! you ask. Well, that's a challenge itself -- but it might contain the solution! I will honestly admit that MOST of the questions I set out to ask on cboard get solved before they are posted -- that is, I actually sit there composing a "new thread", in the little "compose new thread" box, and by the time I get the question formulated as specifically as I can, MOST of the time I realize the answer. Honest. I can also honestly say that I have NEVER had to post a piece of code this long and I can tell you FOR A FACT that you do not need to either.

    To work on a problem like this, you need to familiarize yourself with all the steps involved (we call this "problem solving") by breaking them down and dealing with them one at a time. How many times, while working on this, have you written A SHORT, SEPARATE PROGRAM to check your understanding of the commands and concepts involved? If the answer is none, your attitude or methodology MUST change in time. So how about now? This is the natural form of computer programming anyway.

    Most likely no one cares about or is interested in your project. However, there is a chance someone will take an interest in a problem, if you present it properly.

    Best of all, almost certainly someone can answer a specific question ("is this the correct use of ???), but you don't have one yet. If you can write a short (25 lines or less) piece of code that is A COMPLETE, SELF-CONTAINED PROGRAM and explain what you wanted each significant block to accomplish, I promise I will solve your problem. If you don't do it first, that is.

    I know it seems a hassle at first, like you are wasting time. But eventually you will recognize where time really gets wasted, and where it does not. Plus your coding (as opposed to pondering and hand-wringing) skills will naturally improve with every
    Code:
    int main () {
    you start.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  3. #3
    Registered User
    Join Date
    Feb 2009
    Posts
    3
    I wrote a code that can find the largest out of 5 numbers entered but i not exactly sure where to go from here to be able to get the 3 largest numbers of the 5 to print out. I just need a little guidance on where to go from here and I should be able to figure out the rest. Thanks
    Code:
    #include<stdio.h>
    
    int main(void)
    
    {
    int n1, n2, n3, n4, n5;
    
    printf("Enter five integer numbers\n");
    scanf("%d,%d,%d,%d,%d",&n1,&n2,&n3,&n4,&n5);
    
    printf("The largest of the five integers is ");
    
    if (n1>n2 && n1>n3 && n1>n4 && n1>n5) 
    printf("%d",n1);
    else{ if (n2>n1 && n2>n3 && n2>n4 && n2>n5)
    printf("%d", n2);
    else if (n3>n1 && n3>n2 && n3>n4 && n3>n5)
    printf("%d", n3);
    else if (n4>n1 && n4>n2 && n4>n3 && n4>n5)
    printf("%d", n4);
    else if (n5>n1 && n5>n2 && n5>n3 && n5>n4)
    printf("%d", n5);}
    
    return(0);
    
    }

  4. #4
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    The secret purpose of functions is to streamline stuff like this. They also provide all kinds of opportunities of their own. Here's my idea:
    Code:
    #include<stdio.h>
    
    /* use an array so we can apply a loop */
    int n[5];
    
    	/* a function to find the highest number and replace it */
    int sortray () { 
    	int high=n[0],low=n[0],i,t=0,r;    /* "t" is a tag */
    	for (i=1; i<5; i++) {
    		if (n[i]>high) { high=n[i]; t=i; }
    		if (n[i]<low) { low=n[i]; }
    	}
    	r=n[t];	/* store the high value */
    		/* now replace the high value */
    	n[t]=low;
    	return r;
    }
    
    
    int main() {
    	int i; 
    		
    	printf("Enter five integer numbers\n");
    	scanf("%d,%d,%d,%d,%d",&n[0],&n[1],&n[2],&n[3],&n[4]);
    
    	/* use the function 3 times! */
    	for (i=0; i<3; i++) printf("%d\n",sortray());
    
            return(0);
    
    }
    I am pretty sure you cannot "cheat" this, but I am not very good with math. Or perhaps it's more of a logic question, in which case I would say with authority you cannot cheat this
    Code:
    Enter five integer numbers
    5,7,9,131,-99
    131
    9
    7
    
    Notice that n is now a global variable.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  5. #5
    Registered User
    Join Date
    Feb 2009
    Posts
    3
    Thanks for your help with the code.

  6. #6
    Registered User
    Join Date
    Oct 2008
    Posts
    115
    I hope that you do understand what the code is doing.. use that as your reference for learning..

  7. #7
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Another approach, more efficient on larger data sets: sort the array and print the last three elements.

    In C, you already have qsort() for arrays, so there's essentially no additional work left.

    Greets,
    Philip

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,602
    Quote Originally Posted by Snafuist
    Another approach, more efficient on larger data sets: sort the array and print the last three elements.
    Good suggestion, though sorting is not necessary to find the largest n elements as they can be found in linear time on average. Unfortunately, the C standard library has no equivalent of the C++ standard library's std::nth_element().
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Quote Originally Posted by laserlight View Post
    Good suggestion, though sorting is not necessary to find the largest n elements as they can be found in linear time on average.
    For constant n << sizeof(our_array), this holds true. Simply iterate over the array elements and keep track of the largest, second-largest and so on. Let X denote the size of the array, then the asymptotic runtime is O(X + n*log(X)), which is linear for n<<X.

    (Quiz question: proof that O(X + n*log(X)) is indeed the correct asymptotic runtime)


    However, in the general case, i.e. on average, this is wrong.

    Proof by contradiction:

    Fact 1: The lower bound for sorting is O(X*log(X)).
    Fact 2: The algorithm described above finds the first n largest elements in a sorted manner in linear time and this is optimal (I have to look at each of the array elements at least once).

    Now suppose I could find the n largest elements of an array in linear time (on average) in a sorted manner. Then I could especially find all of them in linear time (on average) in a sorted manner.
    => Contradiction to the sorting lower bound.


    Unfortunately, the C standard library has no equivalent of the C++ standard library's std::nth_element().
    But it would be very easy to implement. And again, for n<<X, linearity holds true. But nth_element() has a runtime of O(n), so finding e.g. all X largest elements yields runtime O(X*X).


    In general, as soon as I can express n in terms of X, e.g. n = X/1000, the runtime is not linear. Thus, the runtime is not linear for almost all values of n.


    For practical purposes, reasonably sized arrays and constant n, it is indeed linear sometimes. It's just that I'm generally more interested in complexity theory than in programming. I know I sometimes sound a bit offensive, but this is mostly due to my poor English. My post is not meant to be an offense, I'm just enjoying a free afternoon :-)

    Greets,
    Philip

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,602
    Quote Originally Posted by Snafuist
    Fact 1: The lower bound for sorting is O(X*log(X)).
    As I noted, you do not need to sort, so quoting the lower bound of comparison based sorting is irrelevant.

    Quote Originally Posted by Snafuist
    Now suppose I could find the n largest elements of an array in linear time (on average) in a sorted manner.
    That is not correct. The aim is to find the n largest elements, not to find the n largest elements in sorted order (in which case a partial sort might be more appropriate, but I suppose you could find the n largest elements and then sort that subrange only).

    The idea is to partition the array as in quick sort. If after the partitioning, it turns out that the pivot element is in the nth position, then you know that all the elements in one partition are the n largest elements. If not, you can determine in which partition the n largest elements must be in, and thus pick another pivot in that partition, and repeat the process recursively. This algorithm can perform as bad as quick sort (quadratic time complexity in the worst case), but on average it has linear asymptotic running time.

    Quote Originally Posted by Snafuist
    But nth_element() has a runtime of O(n), so finding e.g. all X largest elements yields runtime O(X*X).
    No, nth_element partitions the range such that all the elements "less than" the nth element are in one partition, and all the elements "not less than" the nth element are in the other partition. It does this partitioning in linear time on average.
    Last edited by laserlight; 02-13-2009 at 10:57 AM.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Complete Beginner
    Join Date
    Feb 2009
    Posts
    312
    Aah, having read the original post once again, I noticed that I implicitly made the assumption that the output should be like:

    Largest element: ...
    2nd-largest: ...
    3rd-largest: ...

    My proof is not wrong, but if order doesn't matter, you are of course right in that there's a faster way to do it.


    The same applies for your second quote about std::nth_element(). Didn't think about partitioning, because I tried to keep the sortedness property.


    I promise that from now on I'll read posts twice. ;-)

    Greets,
    Philip

  12. #12
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,602
    Quote Originally Posted by Snafuist
    My proof is not wrong, but if order doesn't matter, you are of course right in that there's a faster way to do it.
    I suspect that even if order matters, using nth element partitioning followed by a sort on the desired range would be faster than sorting the entire array and then picking the desired range. The reason is that the sort is only performed on the reduced range, and it is the sort's complexity that dominates the overall complexity, so it could be a substantial advantage if you only want say, the top 10% of the array.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Find largest and second largest number (help)
    By Arkon in forum C++ Programming
    Replies: 6
    Last Post: 01-20-2006, 10:21 PM
  2. Finding mode in array of numbers
    By Snowcat in forum C++ Programming
    Replies: 1
    Last Post: 01-16-2006, 08:58 PM
  3. Largest number program
    By rebel in forum C++ Programming
    Replies: 10
    Last Post: 12-01-2005, 03:20 AM
  4. Finding and Printing prime numbers using arrays
    By Sektor in forum C++ Programming
    Replies: 5
    Last Post: 12-11-2003, 07:29 PM
  5. Learning arrays
    By Unregistered in forum C Programming
    Replies: 4
    Last Post: 07-09-2002, 10:27 PM

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