Algorithm: largest of the four

[jackson6612]

Write an algorithm to find the largest of the four numbers A, B, C, D.

1: See if A is greater than the three of the rest, if YES, then go to Step 5
2: See if B is greater than the two of the rest, if YES, then go to Step 5
3: See if C is greater than the last one, if YES, then go to Step 5
4: The last one is the largest, proceed to Step 5 to end the algorithm
5: END

Do you find the above algorithm correct? Please let me know.

 

[Mark44]

That's much more complicated than it needs to be. I would pick the larger of A and B, and then the larger of C and D. Finally, I would compare the two winners. That would be the largest of all four numbers.

 

[rcgldr]

I assume this takes 3 compares no matter how you do it.

lntext = "A"
ln = A
if (B > ln){
    lntext = "B"
    ln = B}
if (C > ln){
    lntext = "C"
    ln = C}
if (D > ln){
    lntext = "D"
    ln = D}
ouput "largest number is ", lntext

 

[Borek]

max(max(a,b),max(c,d));

 

[AlephZero]

max(max(max(a,b),c),d)

Borek's is neater for 4 variables, but this is easier to generalize to N variables.

I assume this takes 3 compares no matter how you do it.

The minimum number of compares is 3, for the same reason that in a knockout tennis tournament between n players, the number of matches played must be n-1 however you organize the competition. with "seeded players" or whatever.

Of course you can use more than the minimum number of compares - see the OP for an example!

 

[jackson6612]

I assume this takes 3 compares no matter how you do it.

lntext = "A"
ln = A
if (B > ln){
    lntext = "B"
    ln = B}
if (C > ln){
    lntext = "C"
    ln = C}
if (D > ln){
    lntext = "D"
    ln = D}
ouput "largest number is ", lntext

Thanks a lot, everyone, Mark, RCG, Borek, Aleph. Things would have been a lot difficult without your help.

I think the algorithms, which are precise and to the point, are more suited to programming-related problems. I wanted an algorithm which could also be written in the form of a simple flowchart. The simple example would be: http://upload.wikimedia.org/wikipedia/commons/9/91/LampFlowchart.svg

RCG: Could you please explain your algorithm? I don't get what these "intext", "In", etc., are. Please guide me. Thanks.

 

[rcgldr]

RCG: Could you please explain your algorithm? I don't get what these "intext", "In", etc., are. Please guide me. Thanks.

ln = largest number (the value)
lntext = largest number text, to display which number was largest (A, B, C, or D)

 

[jackson6612]

I assume this takes 3 compares no matter how you do it.

[B][COLOR="Red"]lntext = "A"
ln = A
if (B > ln){
    lntext = "B"
    ln = B}[/COLOR][/B]
if (C > ln){
    lntext = "C"
    ln = C}
if (D > ln){
    lntext = "D"
    ln = D}
ouput "largest number is ", lntext

Thank you for the explanation.

This is how I interpret your first step (is it first?):
largest number text is "A" and "A" is the largest number if: B is greater than the largest number which is "A"? Obviously as you can see this is misinterpretation. So, please help.

 

[rcgldr]

This is how I interpret your first step (is it first?):
largest number text is "A" and "A" is the largest number

Correct.

if B is greater than the largest number which is "A"?

if B is greater than largest number (which is currently A), then set the largest number to the value of B and set lntext to the letter "B".

 

[jackson6612]

I assume this takes 3 compares no matter how you do it.

lntext = "A"
ln = A
if (B > ln){
    lntext = "B"
    ln = B}

Thanks. I get it now. Perhaps, there is a reason the way you have written the algorithm. I would have written it somewhat like this:
lntext = "A"
ln = A
if (B > ln){lntext = "B", ln = B}.

Is my way also correct?

Is it okay to use the shortened form "algo" for the full form "algorithm"?

Please guide me. And thanks a lot for being there to help me most of the time.

 

[jtbell]

lntext = "A"
ln = A
if (B > ln){
    lntext = "B"
    ln = B}
if (C > ln){
    lntext = "C"
    ln = C}
if (D > ln){
    lntext = "D"
    ln = D}
ouput "largest number is ", lntext

Why use both text and number variables, when the original problem mentions only numbers?

input A, B, C, D;
largest = A;
if (B > largest)
{
    largest = B;
}
if (C > largest)
{
    largest = C;
}
if (D > largest)
{
    largest = D;
}
print largest;

 

[jtbell]

Perhaps, there is a reason the way you have written the algorithm. I would have written it somewhat like this:
lntext = "A"
ln = A
if (B > ln){lntext = "B", ln = B}.

When writing an algorithm, either version is OK. It's not intended to be compiled directly into an actual executable program, so the rules for writing out an algorithm aren't as strict as when writing it in an actual programming language. We often call this "pseudocode."

Most people probably write pseudocode that looks somewhat like whichever programming language they usually use, but doesn't have all the details that would be necessary to make a complete program in C or C++ or Java or whatever.

Is it okay to use the shortened form "algo" for the full form "algorithm"?

It's a matter of taste. I prefer to use the complete word, but you often see the short version in slangy colloquial writing. I'm old-fashioned.

 

[jackson6612]

When writing an algorithm, either version is OK. It's not intended to be compiled directly into an actual executable program, so the rules for writing out an algorithm aren't as strict as when writing it in an actual programming language. We often call this "pseudocode."

Most people probably write pseudocode that looks somewhat like whichever programming language they usually use, but doesn't have all the details that would be necessary to make a complete program in C or C++ or Java or whatever.



It's a matter of taste. I prefer to use the complete word, but you often see the short version in slangy colloquial writing. I'm old-fashioned.

Thanks a lot, JT. You have also helped me a lot in the past. Thanks for all the help and I hope you would continue to help me as much as you can.

Please remember that I'm neither a student of science or computer science.

"compiled" - Don't they write "0's" and "1's" when writing a program?

"...pseudocode..." - You mean that they use a kind of generic format which could easily be converted to some specific format for some particular programming language?

Thanks.

 

[jtbell]

"compiled" - Don't they write "0's" and "1's" when writing a program?

A program called a compiler does that for you. It translates the C or C++ or Fortran (or whatever) code that you write, into strings of 0s and 1s that are the actual "machine language" that you find in a .exe file.

"...pseudocode..." - You mean that they use a kind of generic format which could easily be converted to some specific format for some particular programming language?

Yes. To take your example, if I were starting from scratch with pseudocode, I might write this:

Get A, B, C, D from user;
largest = A;
if B > largest then
    Largest = B;
if C > largest then
    Largest = C;
if D > largest then
    largest = D;
Print largest.

This is something that I could almost read out loud and it would be understandable. It just describes the logical sequence of what I want to do. Here's a complete C++ program for it, with all the extra details and "scaffolding" that C++ requires, and in the style that I usually use for formatting the code:

#include <iostream>

using namespace std;

int main ()
{
    cout << "Enter four integers: ";
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    int largest = A;

    if (B > largest)
    {
        largest = B;
    }

    if (C > largest)
    {
        largest = C;
    }

    if (D > largest)
    {
        largest = D;
    }
    
    cout << "The largest one is: " << largest << "." << endl;

    return 0;
}

I put this in a file named largest.cpp. Here's what I see when I compile and run it, using the Unix command line in a Terminal window on my Mac:

Jons-Mac-Pro:c++ jtbell$ g++ largest.cpp -o largest
Jons-Mac-Pro:c++ jtbell$ ./largest
Enter four integers: 4 25 12 20
The largest one is: 25.
Jons-Mac-Pro:c++ jtbell$

On each line, the stuff up to and including the $ is my system's command prompt. "g++" is the name of my C++ compiler.

 

[jackson6612]

Why use both text and number variables, when the original problem mentions only numbers?

input A, B, C, D;
largest = A;
if (B > largest)
{
    largest = B;
}
if (C > largest)
{
    largest = C;
}
if (D > largest)
{
    largest = D;
}
[B][COLOR="Red"]print largest[/COLOR][/B];

Does the "print largest" steps means to print the result on a printer? Please let me know.

 

[jtbell]

It means "print" to your monitor or computer terminal. "Display" or "show" would probably be a better word, but in many computer languages, the output statement/command is named something like "print" regardless of where the output actually goes, so even in pseudocode some people always say "print."

 

[jackson6612]

Thanks a lot, JT.

Best wishes
Jackson

 

[rcgldr]

Why use both text and number variables, when the original problem mentions only numbers?

The original post also mentions a set of numbers by name {A, B, C, D}, and it wasn't clear if the goal was to determine the largest number value or which number in the set {A, B, C, D} was largest.

 

[Edgardo]

Imagine you write the following numbers on the blackboard: [13 2 8 25 36]
How would you determine the largest number?

Probably, you would put your finger on the very left number and move your finger
from left to right. In your right hand you have a small calculator to save a number,
namely the current maximum.

Example:
The left hand side shows the five numbers with the red number
being the position of your left finger.
On the right hand side is the number that you type into the calculator.

Step 1:
At the beginning the calculator displays 0.
[13 2 8 25 36] [0]

Finger on 13. This number is our current maximum. Type 13 into the calculator.
[13 2 8 25 36] [13]


Step 2:
Finger is moved one step to the right.
[13 2 8 25 36] [13]

Compare with calculator => 2 is smaller than 13.
We leave the calculator as it is (current maximum is still 13).
[13 2 8 25 36] [13]


Step 3:
Finger is moved one step to the right.
[13 2 8 25 36] [13]

Compare with calculator => 8 is smaller than 13.
We leave the calculator as it is (current maximum is still 13).
[13 2 8 25 36] [13]


Step 4:
Finger is moved one step to the right.
[13 2 8 25 36] [13]

Compare with calculator => 25 is greater than 13.
Delete the number on the calculator display and type 25 (current maximum is now 25).
[13 2 8 25 36] [25]


Step 5:
Finger is moved one step to the right.
[13 2 8 25 36] [25]

Compare with calculator => 36 is greater than 25.
Delete the number on the calculator display and type 36 (current maximum is now 36).
[13 2 8 25 36] [36]

Since you can't move your finger further to the right you look at your calculator
with the current maximum being 36. This is also the largest number in the row.

In programming the art is to translate this "human" algorithm into something the
computer understands. For example, the calculator here is translated to the
variable "ln" in your code.

 

[Grep]

Not saying previous replies are incorrect in any way. I just wanted to point out that I would almost never write something as specific as what I've seen suggested, at least in practice.

The most general form of the algorithm to find the largest number I come up with off the top of my head is:
1. Set current largest number to first number in list (at index 0).
2. Set current index to 1.
3. If number at current index is larger than current largest number, make it the new current largest number.
4. If at last number in list, current largest number is the largest. Otherwise, increment current index and go to step 3.

There's other ways to do more or less the same thing, of course, and I have no clue what's expected of you in your question. But it seems to me the greatest understanding and practical use comes from a similar general approach.

In straight C, something like this with hard coded values:

#include <stdio.h>

#define NUM_OF_NUMBERS 4
static int numbers[NUM_OF_NUMBERS] = {24, 10, 42, 18};

int main()
{
   int i;
   int largest = numbers[0];

   for (i = 1; i < NUM_OF_NUMBERS; i++)
   {
      if (numbers[i] > largest)
      {
         largest = numbers[i];
      }
   }

   printf("Largest is %d\n", largest);
}

Don't see any mistakes, but feel free to correct me if I made any.

EDIT: Just wanted to add that Edgardo has the right idea when breaking down the steps. Learning to generalize things and break them down into steps is at the core of learning programming and algorithms. So if I was a teacher, I'd consider the general answer to be the better answer. But then, I wouldn't have specified the exact number of elements, either, because I would want them to reason out the answer that I know will teach them more.

 

[TylerH]

You could generalize to say that, given the limitation of two-element equalities, n-1 comparisons is the best case for finding the largest/smallest of n numbers.

Now, think of this: Can the best case be improved if more-than-two-element equalities. For example, if you were able to do three-element equalities(ie x >= y >= z) what would be the generalization of that?

 

[Borek]

Not saying previous replies are incorrect in any way. I just wanted to point out that I would almost never write something as specific as what I've seen suggested, at least in practice.

There are situations when what you really need is just to deal with a list of three or four numbers. Using general method in such a case is an overkill.

 

[jtbell]

In this case, you don't even have a list (array or vector) to begin with, just four individual variables.

 

[Borek]

Yes, although it may happen they are stored in an array

 

[jackson6612]

A program called a compiler does that for you. It translates the C or C++ or Fortran (or whatever) code that you write, into strings of 0s and 1s that are the actual "machine language" that you find in a .exe file.



Yes. To take your example, if I were starting from scratch with pseudocode, I might write this:

Get A, B, C, D from user;
largest = A;
if B > largest then
    Largest = B;
if C > largest then
    Largest = C;
if D > largest then
    largest = D;
Print largest.

This is something that I could almost read out loud and it would be understandable. It just describes the logical sequence of what I want to do. Here's a complete C++ program for it, with all the extra details and "scaffolding" that C++ requires, and in the style that I usually use for formatting the code:

[B][COLOR="Red"]#include <iostream>

using namespace std;

int main ()
{
    cout << "Enter four integers: ";
    int A, B, C, D;
    cin >> A >> B >> C >> D;

    int largest = A;

    if (B > largest)
    {
        largest = B;
    }

    if (C > largest)
    {
        largest = C;
    }

    if (D > largest)
    {
        largest = D;
    }
    
    cout << "The largest one is: " << largest << "." << endl;

    return 0;
}[/COLOR][/B]

I put this in a file named largest.cpp. Here's what I see when I compile and run it, using the Unix command line in a Terminal window on my Mac:

Jons-Mac-Pro:c++ jtbell$ g++ largest.cpp -o largest
Jons-Mac-Pro:c++ jtbell$ ./largest
Enter four integers: 4 25 12 20
The largest one is: 25.
Jons-Mac-Pro:c++ jtbell$

On each line, the stuff up to and including the $ is my system's command prompt. "g++" is the name of my C++ compiler.

Hi

Please remember that I have no knowledge of computer programming and not a student of science or math.

1: I was wondering how in the first place a computer would determine which number is the largest because it has no intelligence of its own. So, there should be some second algorithm or some procedure which helps computer to know the number '9' is smaller than '10'.

2: Where do I get this C++ compiler? Doesn't C++ let you create a software with GUI where you can enter your four numbers and clicking some button tells you the largest one? How do I learn some VERY basic "scaffolding" and 'extra details' of C++ to do simple software such as the one to find the largest number?

Please guide me.

 

[Mark44]

Hi

Please remember that I have no knowledge of computer programming and not a student of science or math.

1: I was wondering how in the first place a computer would determine which number is the largest because it has no intelligence of its own. So, there should be some second algorithm or some procedure which helps computer to know the number '9' is smaller than '10'.

A compiler translates human readable code in some high-level language to machine code that can run on a specific processor (CPU). Processors generally have a comparison instruction that enables them to determine whether one number is larger than another, smaller than another, or equal to another. The comparison of two values a and b is usually done by subtraction; if the result of a - b is positive, a is larger than b; if a - b is negative, a is less than b; if a - b is zero, a is equal to b.

2: Where do I get this C++ compiler? Doesn't C++ let you create a software with GUI where you can enter your four numbers and clicking some button tells you the largest one? How do I learn some VERY basic "scaffolding" and 'extra details' of C++ to do simple software such as the one to find the largest number?

There are lots of C++ compilers out there. Some are free and some you have to pay for. When you choose one you will need to get one that runs on whatever operating system you're using - Windows, or some variant of Linux, or one of the Apple OSes.

You can use C++ or C# or Java or other high-level languages to create a GUI that displays a form with four text boxes and a button that the user can click to make the form display the largest of the four numbers. This sort of program is typically implemented using events - i.e., when the button is clicked, an event is raised, and a method/function in your program responds by finding the largest number and displaying it in your form.

For GUI-type programs, I would recommend C# or Java over C++, as they would be simpler to write, IMO.

 

[Grep]

There are situations when what you really need is just to deal with a list of three or four numbers. Using general method in such a case is an overkill.

Like I said, nothing wrong in any way with the specific case. I just think more is learned by looking at the general case. Even the specific case is just the general case with an unrolled loop, in a manner of speaking. I figure it's good for the OP to at least be aware of it.

In this case, you don't even have a list (array or vector) to begin with, just four individual variables.

Fair point, but I don't think it matters much. A teacher who would take marks away for using an array type of construct in this case would be a very poor one, IMO (and I really hope OP doesn't have one like that). Anyways, not much difference between assigning them letters or numbers. We could consider them stored in an array such as number[A], number, etc and use the letter as the index, as far as the logic is concerned.

1: I was wondering how in the first place a computer would determine which number is the largest because it has no intelligence of its own. So, there should be some second algorithm or some procedure which helps computer to know the number '9' is smaller than '10'.

You can assume there are certain basic operations available to you. Comparing numbers like that is a basic operation in any computer. I doubt you're expected to work out an algorithm for that. It's implemented in the hardware of the computer, not the software.

So the logic is simply something like:
If (9 < 10) Then DO SOMETHING

Without getting into too many details, the 'If ... Then ...' is a very important statement, and the (9 < 10) stuff is called an expression (you'll want to learn about expressions for sure). This one evaluates to true or false (well, in this case always true, but you get my meaning I hope). If it's true, it does the 'Then' stuff. Otherwise, it goes on to whatever is next.

In a flowchart, it would be the diamond shape for a decision point.

2: Where do I get this C++ compiler? Doesn't C++ let you create a software with GUI where you can enter your four numbers and clicking some button tells you the largest one? How do I learn some VERY basic "scaffolding" and 'extra details' of C++ to do simple software such as the one to find the largest number?

There's a lot of possibilities there. I use g++ on a Linux system. Assuming you're on a Windows system, you could get Visual Studio. That's one possibility.

Another that I like, if you want to make GUIs, is QtCreator, which is an text editor and a form editor, that allows you to write GUI programs in the QT GUI Toolkit. But it depends on what GUI you wish to write for. And I wouldn't worry about GUIs until you get farther along in your development as a programmer. Simple text programs are the place to start.

 

[TylerH]

Codeblocks is a nice IDE(integrated development environment) for Windows and Linux. The cool part about using IDEs like Visual Studio or Codeblocks is the nearly instant feedback. You write a simple program, click the "run" button to run your program. This can expedite the learning process.

I would seriously caution a beginner considering starting in GUI. Learning to implement simple algorithms in a new language is a lot easier when you can concentrate on learning the language alone, rather than the GUI library you're using and the language. IMHO, you should stick to console programming, at least for a while.

 

[rcgldr]

Where do I get this C++ compiler?

If you're running windows, you can download and run Microsoft Visual C++ Express for free.

gui

At this point, I would recommend starting with dos console window programs first.

 

[jtbell]

How do I learn some VERY basic "scaffolding" and 'extra details' of C++ to do simple software such as the one to find the largest number?

There are many introductory textbooks for C++ programming, aimed at people who have not programmed before. I haven't taught a C++ course in several years, so I'm not familiar with what is currently available. It would be best to ask about these in the "Science Books" forum here (sub-forum of "Academic Guidance".

These books generally teach only console-mode programs that you run from a Unix or DOS command line, like my example. As others have noted, programming a GUI with windows and data-entry boxes is much more complicated and not for raw beginners to attempt.

Also keep in mind that C++ is not the only possible choice for a language to learn. In the USA, most introductory programming courses nowadays use Java, and there are now probably more introductory Java books than C++ books. (I don't know Java myself, so I can't help along those lines.)

 

[TylerH]

Not to go completely off track, but if all you want is to study algorithms, there's no reason you would have to start with one of the C based languages(C, C++, Java, ...). Basic was my first language, and the first of many other programmers I know. You can learn standard Basic, which as many implementations by many different organisations, or Visual Basic(VB), a M$ invention, that allows for making click and drag GUIs. If you want GUI from the beginning, VB is the way to go. Making a text box in VB is as easy as selecting from a list and dragging it to where, on the form, you want it, then double clicking to edit what happens when the text changes.

 

[jackson6612]

Thank you very much, everyone, RCG, JT, Edgardo, Grep, Tyler, Borek, Mark. I'm much obliged to all of you.

A compiler translates human readable code in some high-level language to machine code that can run on a specific processor (CPU).

Yes, it could be said it is readable but I don't think it's understandable unless you know what those extra detail and parameters would mean when pseudo-code (pseudo-code is readable and understandable by a non-programmer) is converted into language code (language code is only understandable by the programmer) which in turn is translated into machine code by the compiler. Am I right?

Even the specific case is just the general case with an unrolled loop, in a manner of speaking.

What is an "unrolled loop"?

In this case, you don't even have a list (array or vector) to begin with, just four individual variables.

Fair point, but I don't think it matters much. A teacher who would take marks away for using an array type of construct in this case would be a very poor one, IMO (and I really hope OP doesn't have one like that). Anyways, not much difference between assigning them letters or numbers. We could consider them stored in an array such as number[A], number, etc and use the letter as the index, as far as the logic is concerned.

What are you guys saying? Please let me know.

You can assume there are certain basic operations available to you. Comparing numbers like that is a basic operation in any computer. I doubt you're expected to work out an algorithm for that. It's implemented in the hardware of the computer, not the software.

As is BIOS software is part of the hardware? Does a processor have a fixed permanent memory chip which holds BIOS-like software in it for simple operations such as the difference between two numbers to be done by the processor?

Are there C++ compilers which could automatically convert pseudo-code into language code?

Okay, I don't want GUI feature. What simple C++ compilers would you recommend me then? I use Win XP Pro. It could be freeware or shareware but should be flexible and easy.

Any simple and straightforward book on C++ for a layman?

Thank you very much for all the help. I understand that it takes a lot of time and energy to help others, especially in such a kind way.

 

[jtbell]

What is an "unrolled loop"?

What are you guys saying? Please let me know.

This is what happens when programmers start talking in programmer-speak around non-programmers. :uhh: Don't worry too much about it yet. This sort of thing happens in physics threads too... people come into a thread and start talking to each other without regard for the original questioner's level of expertise.

 

[TylerH]

1: High level languages, such as C++, as said to be human readable. To some they are not readable, but in contrast to machine language, they are to most programmers.

2: An unrolled loop is a complex compiler technique. It's nothing to worry about unless you learn assembly or write a compiler.

3: Arrays, lists, and vectors are just ways to store multiple variables in a list. Google "C++ array."

4: The BIOS is wholly unrelated. It prepares the mobo, cpu, and other components, gets them into normal operating modes, and other things. Then loads the OS.

4.5: The logic to test the relation of two numbers is literally built into the processor. It does it with circuitry.

5: Wouldn't that not be a C++ compiler anymore? A compiler that compiles pseudo-code would be a psuedo-code compiler. A pseudo-code compiler cannot exist. Pseudo-code, by definition, is meant for humans only, and if it is compilable it is no longer pseudo-code.

6: If you have 2+ GiB of RAM, get M$ Visual Studio Express Edition, if not, get CodeBlocks. Both are free.

7: I've never read any C++ books, so I don't know. I learned what I know from numerous sources throughout the internet. cprogramming.com has a set of tutorials that range in skill level from nonprogrammer-beginner to intermediate.

 

[jackson6612]

What are you guys saying? Please let me know.[/quote]

This is what happens when programmers start talking in programmer-speak around non-programmers. :uhh: Don't worry too much about it yet. This sort of thing happens in physics threads too... people come into a thread and start talking to each other without regard for the original questioner's level of expertise.[/QUOTE]

Ya, you are quite right. That's the reason I keep on reminding you guys that I'm neither a student of science nor of... But it seems you forget it soon!