Use of nested loops.

Discussion in 'C Programming' started by Neptune, Nov 3, 2003.

  1. Neptune

    Neptune Guest

    Hello.

    I am working my way through Zhang's "Teach yourself C in 24 hrs (2e)"
    (Sam's series), and for nested loops, he writes (p116) "It's often
    necessary to create a loop even when you are already in a loop." Then he
    goes on to portray a contrived example that doesn't tell me under what
    conditions a nested loop might be favoured as a solution? i.e. what are
    nested loops useful for? What kinds of algorithms are served by nested
    loops? etc. Is any of this making sense? :)

    Anyway - thoughts welcomed.

    - Andy
     
    Neptune, Nov 3, 2003
    #1
    1. Advertising

  2. Neptune

    Ben Pfaff Guest

    Neptune <neptune@no_spam_here> writes:

    > I am working my way through Zhang's "Teach yourself C in 24 hrs (2e)"
    > (Sam's series), and for nested loops, he writes (p116) "It's often
    > necessary to create a loop even when you are already in a loop." Then
    > he goes on to portray a contrived example that doesn't tell me under
    > what conditions a nested loop might be favoured as a solution?
    > i.e. what are nested loops useful for? What kinds of algorithms are
    > served by nested loops? etc. Is any of this making sense? :)


    A typical beginner's example is printing a bar graph,
    e.g. (warning: poorly proofread):

    #include <stdio.h>

    int main (void)
    {
    int bars[] = {1, 6, 2, 4, 9};
    int i;

    for (i = 0; i < sizeof bars / sizeof *bars; i++) {
    int j;

    printf ("%3d ", bars);
    for (j = 0; j < bars; j++)
    putchar ('*');
    putchar ('\n');
    }
    return 0;
    }
    --
    Peter Seebach on C99:
    "[F]or the most part, features were added, not removed. This sounds
    great until you try to carry a full-sized printout of the standard
    around for a day."
     
    Ben Pfaff, Nov 3, 2003
    #2
    1. Advertising

  3. Neptune

    Neptune Guest

    osmium wrote:
    > Neptune writes:
    >
    >
    >>I am working my way through Zhang's "Teach yourself C in 24 hrs (2e)"
    >>(Sam's series), and for nested loops, he writes (p116) "It's often
    >>necessary to create a loop even when you are already in a loop." Then he
    >>goes on to portray a contrived example that doesn't tell me under what
    >>conditions a nested loop might be favoured as a solution? i.e. what are
    >>nested loops useful for? What kinds of algorithms are served by nested
    >>loops? etc. Is any of this making sense? :)

    >
    >
    > One case that might have some natural appeal is to compute the sum of all
    > the elements of a two-dimensional array. C only simulates (emulates?
    > whatever) a two-dimensional array, but the simulation is pretty effective.
    >
    > Something like:
    >
    > double sum = 0.0;
    > for(i=0; i<10; i++)
    > for(j=0; j<25; j++)
    > sum = sum + a[j];
    >
    > It is often helpful to hide the nesting. This can be accomplished very
    > effectively by calling a function. It lets one focus on the thing of most
    > immediate interest. EG: sum_array() calls sum_columns().
    >
    >


    Thanks for replying:
    1. I get the idea in terms of the structure of a nested for loop and its
    output (e.g. 2 lists of integers from 0 to 10 and 0 to 25) ... but
    what does the 'a' stand-for in "sum = sum + a[j];"?
    2. This is due to my ignorance, but under what conditions would one use
    it? In this instance, why would I want a two-dimensional array, anyway?
    What would I use it for? That was more to my question.



    --
    "Today a young man on acid realised that all matter was really energy
    condensed to a slow vibration, that we are all one consciousness
    experiencing itself subjectively, there's no such thing as death,
    life is only a dream, and we're the imaginations of ourselves.
    Here's Tom with the weather ..." - Bill Hicks.
     
    Neptune, Nov 3, 2003
    #3
  4. Neptune

    Neptune Guest

    Ben Pfaff wrote:
    > Neptune <neptune@no_spam_here> writes:
    >
    >
    >>I am working my way through Zhang's "Teach yourself C in 24 hrs (2e)"
    >>(Sam's series), and for nested loops, he writes (p116) "It's often
    >>necessary to create a loop even when you are already in a loop." Then
    >>he goes on to portray a contrived example that doesn't tell me under
    >>what conditions a nested loop might be favoured as a solution?
    >>i.e. what are nested loops useful for? What kinds of algorithms are
    >>served by nested loops? etc. Is any of this making sense? :)

    >
    >
    > A typical beginner's example is printing a bar graph,
    > e.g. (warning: poorly proofread):
    >
    > #include <stdio.h>
    >
    > int main (void)
    > {
    > int bars[] = {1, 6, 2, 4, 9};
    > int i;
    >
    > for (i = 0; i < sizeof bars / sizeof *bars; i++) {
    > int j;
    >
    > printf ("%3d ", bars);
    > for (j = 0; j < bars; j++)
    > putchar ('*');
    > putchar ('\n');
    > }
    > return 0;
    > }

    Cheers Ben
    That was helpful. Gives me an idea of its usage outside of text book
    example. I haven't come across "sizeof" before. I presume that it is
    some standard way of referencing the length of the array?
    Thanks


    --
    "Today a young man on acid realised that all matter was really energy
    condensed to a slow vibration, that we are all one consciousness
    experiencing itself subjectively, there's no such thing as death,
    life is only a dream, and we're the imaginations of ourselves.
    Here's Tom with the weather ..." - Bill Hicks.
     
    Neptune, Nov 3, 2003
    #4
  5. Neptune <neptune@no_spam_here> wrote in news:3fa6ba48@212.67.96.135:

    > That was helpful. Gives me an idea of its usage outside of text book
    > example. I haven't come across "sizeof" before. I presume that it is
    > some standard way of referencing the length of the array?
    > Thanks


    Sizeof is a nice operator (it's not a function) that tells you the size of
    any "object".

    E.g.

    sizeof (int);
    - tells you the size of an int on your platform (in bytes). For types you
    must use the parenthesis.


    struct foo
    {
    int a;
    double d;
    long *p;
    } fooVar;

    sizeof fooVar
    - tells you the size of the variable fooVar (a struct) in bytes. You don't
    need parenthesis for a variable when uses with the sizeof operator.


    int var[64];

    sizeof var;
    - tells you the size of the var in bytes.

    The sizeof operator is calculated at compile time so it has no run-time
    performance overhead.

    --
    - Mark ->
    --
     
    Mark A. Odell, Nov 3, 2003
    #5
  6. Neptune <neptune@no_spam_here> writes:
    [...]
    > That was helpful. Gives me an idea of its usage outside of text book
    > example. I haven't come across "sizeof" before. I presume that it is
    > some standard way of referencing the length of the array?
    > Thanks


    "sizeof" should be explained in that text book of yours. If it isn't,
    you need a better text book.

    BTW, another example of a nested loop might be reading lines from a
    file, and processing each character in each line. You might use a
    triple-nested loop to open each of the files named on the command
    line, reading each line from each file, and processing each character
    on each line.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
    Schroedinger does Shakespeare: "To be *and* not to be"
     
    Keith Thompson, Nov 3, 2003
    #6
  7. Neptune

    Ben Pfaff Guest

    Neptune <neptune@no_spam_here> writes:

    > osmium wrote:
    > > double sum = 0.0;
    > > for(i=0; i<10; i++)
    > > for(j=0; j<25; j++)
    > > sum = sum + a[j];

    >
    > Thanks for replying:
    > 1. I get the idea in terms of the structure of a nested for loop and
    > its output (e.g. 2 lists of integers from 0 to 10 and 0 to 25) ... but
    > what does the 'a' stand-for in "sum = sum + a[j];"?


    It's just the name of an array, perhaps declared as
    double a[10][25];

    > 2. This is due to my ignorance, but under what conditions would one
    > use it? In this instance, why would I want a two-dimensional array,
    > anyway? What would I use it for? That was more to my question.


    Suppose you're calculating a statistical crosstabulation;
    e.g. you have a bunch of survey responses from several people,
    and the survey includes two questions, one of which has 10
    possible answers and another of which has 25 possible answers.
    Then it may be interesting to figure out how often each possible
    combination of responses (25 * 10 = 250 possibilities) was given
    by respondents. A two-dimensional array with cell values
    corresponding to a count of people is a natural way to do this.
    The sum of all of the cell values is then the total number of
    survey respondents.

    There are of course many other possibilities, too.
    --
    int main(void){char p[]="ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz.\
    \n",*q="kl BIcNBFr.NKEzjwCIxNJC";int i=sizeof p/2;char *strchr();int putchar(\
    );while(*q){i+=strchr(p,*q++)-p;if(i>=(int)sizeof p)i-=sizeof p-1;putchar(p\
    );}return 0;}
     
    Ben Pfaff, Nov 3, 2003
    #7
  8. Neptune

    Ben Pfaff Guest

    Neptune <neptune@no_spam_here> writes:

    > Ben Pfaff wrote:
    > > int bars[] = {1, 6, 2, 4, 9};
    > > int i;
    > > for (i = 0; i < sizeof bars / sizeof *bars; i++) {


    > That was helpful. Gives me an idea of its usage outside of text book
    > example. I haven't come across "sizeof" before. I presume that it is
    > some standard way of referencing the length of the array?


    sizeof yields the number of bytes in its operand. `sizeof bars'
    is the number of bytes in array bars[]; `sizeof *bars' is the
    number of bytes in a single element of bars[]. Thus, the
    quotient of those two expressions is the number of elements in
    bars[]; in this case, 5.
    --
    "It wouldn't be a new C standard if it didn't give a
    new meaning to the word `static'."
    --Peter Seebach on C99
     
    Ben Pfaff, Nov 3, 2003
    #8
  9. Neptune

    osmium Guest

    Neptune writes:

    > I am working my way through Zhang's "Teach yourself C in 24 hrs (2e)"
    > (Sam's series), and for nested loops, he writes (p116) "It's often
    > necessary to create a loop even when you are already in a loop." Then he
    > goes on to portray a contrived example that doesn't tell me under what
    > conditions a nested loop might be favoured as a solution? i.e. what are
    > nested loops useful for? What kinds of algorithms are served by nested
    > loops? etc. Is any of this making sense? :)


    One case that might have some natural appeal is to compute the sum of all
    the elements of a two-dimensional array. C only simulates (emulates?
    whatever) a two-dimensional array, but the simulation is pretty effective.

    Something like:

    double sum = 0.0;
    for(i=0; i<10; i++)
    for(j=0; j<25; j++)
    sum = sum + a[j];

    It is often helpful to hide the nesting. This can be accomplished very
    effectively by calling a function. It lets one focus on the thing of most
    immediate interest. EG: sum_array() calls sum_columns().
     
    osmium, Nov 3, 2003
    #9
  10. Neptune

    David Rubin Guest

    Neptune wrote:

    > > double sum = 0.0;
    > > for(i=0; i<10; i++)
    > > for(j=0; j<25; j++)
    > > sum = sum + a[j];

    [snip]
    > Thanks for replying:
    > 1. I get the idea in terms of the structure of a nested for loop and its
    > output (e.g. 2 lists of integers from 0 to 10 and 0 to 25) ... but


    In this example, a is a (two-dimensional) array, likely defined as

    double a[10][25];

    > what does the 'a' stand-for in "sum = sum + a[j];"?
    > 2. This is due to my ignorance, but under what conditions would one use
    > it? In this instance, why would I want a two-dimensional array, anyway?
    > What would I use it for? That was more to my question.


    Two-dimensional arrays are useful in many circumstances; numerical
    programming is an obvious one. For example, this is how you would do
    matrix addition, transposition, multiplication by a scalar, etc.

    /david

    --
    Andre, a simple peasant, had only one thing on his mind as he crept
    along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
    -- unknown
     
    David Rubin, Nov 3, 2003
    #10
  11. Neptune

    Neptune Guest

    Ben Pfaff wrote:
    > It's just the name of an array, perhaps declared as
    > double a[10][25];


    OK - thought as much, but wanted to confirm.

    >
    > Suppose you're calculating a statistical crosstabulation;
    > e.g. you have a bunch of survey responses from several people,
    > and the survey includes two questions, one of which has 10
    > possible answers and another of which has 25 possible answers.
    > Then it may be interesting to figure out how often each possible
    > combination of responses (25 * 10 = 250 possibilities) was given
    > by respondents. A two-dimensional array with cell values
    > corresponding to a count of people is a natural way to do this.
    > The sum of all of the cell values is then the total number of
    > survey respondents.
    >
    > There are of course many other possibilities, too.


    This gels it for me. Thanks Ben. Very useful.

    --
    "Today a young man on acid realised that all matter was really energy
    condensed to a slow vibration, that we are all one consciousness
    experiencing itself subjectively, there's no such thing as death,
    life is only a dream, and we're the imaginations of ourselves.
    Here's Tom with the weather ..." - Bill Hicks.
     
    Neptune, Nov 3, 2003
    #11
  12. Neptune

    Neptune Guest

    David Rubin wrote:
    >
    > Two-dimensional arrays are useful in many circumstances; numerical
    > programming is an obvious one. For example, this is how you would do
    > matrix addition, transposition, multiplication by a scalar, etc.


    Thanks David. I wouldn't know where to start with the examples you list,
    but I get the basic idea. Cheers.

    --
    "Today a young man on acid realised that all matter was really energy
    condensed to a slow vibration, that we are all one consciousness
    experiencing itself subjectively, there's no such thing as death,
    life is only a dream, and we're the imaginations of ourselves.
    Here's Tom with the weather ..." - Bill Hicks.
     
    Neptune, Nov 3, 2003
    #12
  13. Neptune

    Neptune Guest

    Keith Thompson wrote:
    > "sizeof" should be explained in that text book of yours. If it isn't,
    > you need a better text book.


    ooops - it is. Right in the next section under "Using conditional
    operators".

    >
    > BTW, another example of a nested loop might be reading lines from a
    > file, and processing each character in each line. You might use a
    > triple-nested loop to open each of the files named on the command
    > line, reading each line from each file, and processing each character
    > on each line.
    >

    Thanks :)

    --
    "Today a young man on acid realised that all matter was really energy
    condensed to a slow vibration, that we are all one consciousness
    experiencing itself subjectively, there's no such thing as death,
    life is only a dream, and we're the imaginations of ourselves.
    Here's Tom with the weather ..." - Bill Hicks.
     
    Neptune, Nov 3, 2003
    #13
  14. Neptune

    Neptune Guest

    Mark A. Odell wrote:
    > Sizeof is a nice operator (it's not a function) that tells you the size of
    > any "object".
    >
    > E.g.
    >
    > sizeof (int);
    > - tells you the size of an int on your platform (in bytes). For types you
    > must use the parenthesis.
    >
    >
    > struct foo
    > {
    > int a;
    > double d;
    > long *p;
    > } fooVar;
    >
    > sizeof fooVar
    > - tells you the size of the variable fooVar (a struct) in bytes. You don't
    > need parenthesis for a variable when uses with the sizeof operator.
    >
    >
    > int var[64];
    >
    > sizeof var;
    > - tells you the size of the var in bytes.
    >
    > The sizeof operator is calculated at compile time so it has no run-time
    > performance overhead.
    >


    That was a useful summary - thanks. As it so happens it looks like that
    is the next section in this book, so I'll keep your precise in mind when
    reading.

    --
    "Today a young man on acid realised that all matter was really energy
    condensed to a slow vibration, that we are all one consciousness
    experiencing itself subjectively, there's no such thing as death,
    life is only a dream, and we're the imaginations of ourselves.
    Here's Tom with the weather ..." - Bill Hicks.
     
    Neptune, Nov 3, 2003
    #14
  15. Neptune

    Neptune Guest

    Ben Pfaff wrote:

    >
    > sizeof yields the number of bytes in its operand. `sizeof bars'
    > is the number of bytes in array bars[]; `sizeof *bars' is the
    > number of bytes in a single element of bars[]. Thus, the
    > quotient of those two expressions is the number of elements in
    > bars[]; in this case, 5.


    Cheers Ben. Your explanation coupled with that given by Mark will be
    very useful when I tackle the next section in my book. Much obliged.

    --
    "Today a young man on acid realised that all matter was really energy
    condensed to a slow vibration, that we are all one consciousness
    experiencing itself subjectively, there's no such thing as death,
    life is only a dream, and we're the imaginations of ourselves.
    Here's Tom with the weather ..." - Bill Hicks.
     
    Neptune, Nov 3, 2003
    #15
  16. "Keith Thompson" <> wrote in message
    news:...
    > BTW, another example of a nested loop might be reading lines from a
    > file, and processing each character in each line. You might use a
    > triple-nested loop to open each of the files named on the command
    > line, reading each line from each file, and processing each character
    > on each line.


    Neptune, in many cases you use multiple nested loops without even knowing
    it.

    Let's look at Keith's a modified example. Open a text file and read and
    print
    each line. You need a loop in which to read a line, test you have
    successfully
    read it and then print it. Inside that loop, you would probably use fgets
    for
    reading and puts or printf for printing. Each of these functions contains at
    least one loop, possibly more than one. So, you may get nested loops simply
    by
    calling a function in a loop. Isn't programming fun :)

    To answer your original question, nested loops are used whenever an
    algorithm
    asks for it. Processing more than one-dimensional entities is the most
    common
    example. My example is one of them: the line number could be considered the
    vertical and the position of a character in a line the horizontal dimension.
     
    Peter Pichler, Nov 3, 2003
    #16
  17. Neptune

    David Rubin Guest

    Neptune wrote:
    >
    > David Rubin wrote:
    > >
    > > Two-dimensional arrays are useful in many circumstances; numerical
    > > programming is an obvious one. For example, this is how you would do
    > > matrix addition, transposition, multiplication by a scalar, etc.

    >
    > Thanks David. I wouldn't know where to start with the examples you list,
    > but I get the basic idea. Cheers.


    Start with Google. No problem.

    /david

    --
    Andre, a simple peasant, had only one thing on his mind as he crept
    along the East wall: 'Andre, creep... Andre, creep... Andre, creep.'
    -- unknown
     
    David Rubin, Nov 3, 2003
    #17
  18. Ben Pfaff <> writes:
    > Neptune <neptune@no_spam_here> writes:
    >
    > > Ben Pfaff wrote:
    > > > int bars[] = {1, 6, 2, 4, 9};
    > > > int i;
    > > > for (i = 0; i < sizeof bars / sizeof *bars; i++) {

    >
    > > That was helpful. Gives me an idea of its usage outside of text book
    > > example. I haven't come across "sizeof" before. I presume that it is
    > > some standard way of referencing the length of the array?

    >
    > sizeof yields the number of bytes in its operand. `sizeof bars'
    > is the number of bytes in array bars[]; `sizeof *bars' is the
    > number of bytes in a single element of bars[]. Thus, the
    > quotient of those two expressions is the number of elements in
    > bars[]; in this case, 5.


    This is, of course, quite correct.

    One thing to watch out for is the distinction between arrays and
    pointers. They are *not* the same thing (though some people might try
    to tell you they are), but there are some contexts in which a pointer
    name and an array name can be used in the same way. There are times
    when you have to be very careful to know whether you're applying
    sizeof to an array object or to a pointer.

    Section 6 of the C FAQ at <http://www.eskimo.com/~scs/C-faq/top.html>
    covers this well.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    San Diego Supercomputer Center <*> <http://www.sdsc.edu/~kst>
    Schroedinger does Shakespeare: "To be *and* not to be"
     
    Keith Thompson, Nov 3, 2003
    #18
  19. Neptune wrote:

    > David Rubin wrote:
    >
    >>
    >> Two-dimensional arrays are useful in many circumstances; numerical
    >> programming is an obvious one. For example, this is how you would do
    >> matrix addition, transposition, multiplication by a scalar, etc.

    >
    >
    > Thanks David. I wouldn't know where to start with the examples you list,
    > but I get the basic idea. Cheers.
    >


    A simpler more concrete example. Consider an othello game
    <http://www.ugateways.com/bof4.html>

    You have a board which is made up of 8 by 8 squares. You decide
    to represent the state of a squares as an integer.

    #define UNOCCUPIED -1
    #define BLACK 0
    #define WHITE 1

    Bonus question, why is it a good (and is it good?) idea to make
    black 0 and white 1 instead of any other two numbers?

    Now you need the board

    #define SIZE 8

    int board[SIZE][SIZE];

    To start of the game you need some simple code
    int i;
    int j;

    for(i = 0;i < SIZE;i++)
    {
    for(j = 0;j < SIZE;j++)
    {
    board[j] = UNNOCCUPIED;
    }
    }

    board[3][3] = WHITE;
    board[3][4] = BLACK;
    board[4][3] = WHITE;
    board[4][4] = BLACK;

    Ok, You are now ready to start the game. (And that you can do
    yourself ;)

    <OT>
    I saw your signature. Tool fan? Or "just" Bill Hicks? :)
    IMNSVHO they both rock!
    </OT>

    --
    Thomas.
     
    Thomas Stegen, Nov 3, 2003
    #19
  20. Neptune

    Allan Bruce Guest

    "Neptune" <neptune@no_spam_here> wrote in message
    news:3fa6a878@212.67.96.135...
    > Hello.
    >
    > I am working my way through Zhang's "Teach yourself C in 24 hrs (2e)"
    > (Sam's series), and for nested loops, he writes (p116) "It's often
    > necessary to create a loop even when you are already in a loop." Then he
    > goes on to portray a contrived example that doesn't tell me under what
    > conditions a nested loop might be favoured as a solution? i.e. what are
    > nested loops useful for? What kinds of algorithms are served by nested
    > loops? etc. Is any of this making sense? :)
    >
    > Anyway - thoughts welcomed.
    >
    > - Andy
    >


    One example you may come across in your book is a basic bubble-sort which
    will sort an array of elements, e.g.

    for (i=0; i<MAX-1; i++)
    for (j=0; j<MAX-1-i; j++)
    if (ELEMENT[j+1]>ELEMENT[j])
    {
    /*swap the elements*/
    TEMP = ELEMENT[j+1];
    ELEMENT[j+1] = ELEMENT[j];
    ELEMENT[j] = TEMP;
    }

    HTH
    Allan
     
    Allan Bruce, Nov 4, 2003
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Allan Bruce

    dynamic number of nested loops

    Allan Bruce, Jul 1, 2004, in forum: Java
    Replies:
    5
    Views:
    9,916
    Tor Iver Wilhelmsen
    Jul 3, 2004
  2. Porthos
    Replies:
    3
    Views:
    498
    Joris Gillis
    Feb 7, 2005
  3. SplaTTer
    Replies:
    2
    Views:
    399
    SplaTTer
    Jul 2, 2003
  4. viza

    break or continue out of nested loops

    viza, Jul 16, 2003, in forum: C Programming
    Replies:
    5
    Views:
    1,058
    sunil
    Jul 17, 2003
  5. Me
    Replies:
    2
    Views:
    263
Loading...

Share This Page