Re: ruler

Discussion in 'C Programming' started by Phil Carmody, Dec 8, 2009.

  1. Phil Carmody

    Phil Carmody Guest

    superpollo <> writes:
    > hello clc.
    >
    > this is a simple program based on sedgewick's algorithms in c, 3ed,
    > pag. 202. it draws a ruler (like this:
    > http://cs.oberlin.edu/~jdonalds/150/ruler-final.png), recursively
    > defined upon the height of middle mark.
    >
    > :) superpollo@192.168.1.152:~/test$ cat ruler.c
    > #include <stdio.h>
    > #include <stdlib.h>
    > #include <math.h>
    > #define ENOUGH 10000


    > void Mark(int Ruler[] , int Pos , int Height)


    If this is a private helper function not for general use,
    consiser marking it as static.

    Your choice of capitalisation may turn a few heads. C tends
    to be mostly lower case.

    > {
    > Ruler[Pos] = Height;
    > }
    > void Rule(int Ruler[] , int Left , int Right , int Height)
    > {
    > int Middle = (Left+Right)/2;
    > if (Height > 0)
    > {
    > Rule(Ruler , Left , Middle , Height-1);
    > Mark(Ruler , Middle , Height);
    > Rule(Ruler , Middle , Right , Height-1);
    > }


    Well, odd things will happen if odd lengths are encountered.

    > }
    > void PrintRlr(int Ruler[] , int Last)


    Ruler's not modified, nor would you want it to be modified -
    make it const.

    > {
    > int Pos , Height;
    > for (Pos = 0 ; Pos <= Last ; Pos++)
    > {
    > for (Height = 1 ; Height <= Ruler[Pos] ; Height++)


    C loops desiring N repetitions traditionally count from 0 to N,
    exiting once <N is false, rather than counting from 1 to N+1,
    exiting once <=N is false.

    > printf("-");
    > printf("\n");


    Consider putchar() instead for calls so simple.

    > }
    > }
    > int main(int argc, char *argv[])
    > {
    > int Ruler[ENOUGH];
    > int MaxHt;
    > int Last;
    > if (argc == 1)
    > {
    > printf("usage: %s HEIGHT_OF_MIDDLE_MARK\n" , argv[0]);
    > return EXIT_FAILURE;
    > }
    > MaxHt = atoi(argv[1]);
    > Last = pow(2 , MaxHt);


    No need for floating point. Just use << to create a power of 2.

    > Ruler[0] = 0;
    > Ruler[Last] = 0;


    But for pity's sake check it's within a usable range before using it.

    > Rule(Ruler , 0 , Last , MaxHt);
    > PrintRlr(Ruler , Last);
    > return EXIT_SUCCESS;
    > }
    > :) superpollo@192.168.1.152:~/test$ cc -ansi -pedantic -Wall -o ruler
    > ruler.c -lm
    > :) superpollo@192.168.1.152:~/test$ ./ruler
    > usage: ./ruler HEIGHT_OF_MIDDLE_MARK
    > :( superpollo@192.168.1.152:~/test$ ./ruler 4
    >
    > -
    > --
    > -
    > ---
    > -
    > --
    > -
    > ----
    > -
    > --
    > -
    > ---
    > -
    > --
    > -
    >
    > :) superpollo@192.168.1.152:~/test$
    >
    > any comments and suggestions are more than welcome, and so is criticism.


    While printing the ruler, also print out Pos^(Pos-1) using %x as the
    format string. See if you can find a relationship between the value
    printed and the length of the tick mark printed.

    Phil
    --
    Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
    Phil Carmody, Dec 8, 2009
    #1
    1. Advertising

  2. Phil Carmody

    Phil Carmody Guest

    superpollo <> writes:
    > Phil Carmody ha scritto:
    >> superpollo <> writes:
    >>> hello clc.

    >
    > mr carmody,
    >
    > i would like to thank you for your very thorough comments, and i would
    > take further advantage of you courtesy -- so to speak ;-) -- by asking
    > for some deeper explanation (or pointer to relevant documents such as
    > the faq).


    It's late. It's probably best someone else chimes in. Still daytime
    in the land of Keith, for example ...

    >>> this is a simple program based on sedgewick's algorithms in c, 3ed,
    >>> pag. 202. it draws a ruler (like this:
    >>> http://cs.oberlin.edu/~jdonalds/150/ruler-final.png), recursively
    >>> defined upon the height of middle mark.
    >>>
    >>> :) superpollo@192.168.1.152:~/test$ cat ruler.c
    >>> #include <stdio.h>
    >>> #include <stdlib.h>
    >>> #include <math.h>
    >>> #define ENOUGH 10000

    >>
    >>> void Mark(int Ruler[] , int Pos , int Height)

    >>
    >> If this is a private helper function not for general use,

    >
    > what is the meaning of "private helper function" ?


    I just meant that it's a function that exists only in order to help
    out a few other functions in the same module, but isn't intended to
    be used by arbitrary other code.

    >> consiser marking it as static.

    >
    > would you please explain the advantages of doing so, and disadvantage
    > of not doing so?


    You don't pollute the global namespace if you don't make it visible
    to the outside world.

    >> Your choice of capitalisation may turn a few heads. C tends
    >> to be mostly lower case.

    >
    > i read at pag. 41 of c unleashed (heathfield) that mixed case is an
    > option, though. also, sedgewick uses this style too from time to time.


    Everything's an option. (Apart from the few things that aren't.)

    >>> {
    >>> Ruler[Pos] = Height;
    >>> }
    >>> void Rule(int Ruler[] , int Left , int Right , int Height)
    >>> {
    >>> int Middle = (Left+Right)/2;
    >>> if (Height > 0)
    >>> {
    >>> Rule(Ruler , Left , Middle , Height-1);
    >>> Mark(Ruler , Middle , Height);
    >>> Rule(Ruler , Middle , Right , Height-1);
    >>> }

    >>
    >> Well, odd things will happen if odd lengths are encountered.

    >
    > given that the first invocation of Rule is given a power-of-2 RIght
    > argument, successive recursive calls are warranted to be given too (or
    > so sedgewick claims). the case Right == 1 is ok, since then it is
    > Height == 0, so no call is performed.


    You might want to add a check that the parameter is indeed a power
    of 2, or at least even, to ensure that nothing unexpected happens.
    However, if you know that the only function(s) calling it will call
    it with an appropriate argument, then the chances are that it can
    be made a static function too. If you export it, then it might be
    called by someone who doesn't play by your rules.

    >>> }
    >>> void PrintRlr(int Ruler[] , int Last)

    >>
    >> Ruler's not modified, nor would you want it to be modified -
    >> make it const.

    >
    > now for a silly question: Last is not mod too, so why not const int
    > Last also?


    Because Ruler represents memory referenced by some other part of the
    code. In fact, despite what it looks like, it's a pointer to that
    memory. Arrays and pointers to their first element were designed to
    look practically identical, such that if you see the use of one you
    can rarely know whether it's one or the other. The extreme case of
    that is the use of array syntax to represent the pointer in examples
    such as the above. C physically cannot pass naked arrays by value,
    the above int Ruler[] is an illusion. (And you can pass them by
    wrapping them in other things too, but that's another matter.)

    >>> {
    >>> int Pos , Height;
    >>> for (Pos = 0 ; Pos <= Last ; Pos++)
    >>> {
    >>> for (Height = 1 ; Height <= Ruler[Pos] ; Height++)

    >>
    >> C loops desiring N repetitions traditionally count from 0 to N,
    >> exiting once <N is false, rather than counting from 1 to N+1,
    >> exiting once <=N is false.

    >
    > ok in general, and i thought about it writing it in the first place,
    > but in this case Height denotes the height of the mark, which goes
    > from 1 to Ruler[Pos] included. would not the other way be more opaque?


    I'm not asking you to change how you represent the height of the mark,
    merely suggesting a more common idiom for counting up to it.

    And just as an aside - I'm sure I saw 2 height 0 gaps in your ruler
    that followed. It looks like you too easily forget 0s.

    It might be because I take the lift up 1 floor to get to the 1st
    floor, and up 6 floors to get to the th floor that I'm perfectly happy
    counting from zero.

    >>> printf("-");
    >>> printf("\n");

    >>
    >> Consider putchar() instead for calls so simple.

    >
    > ok.
    >
    >>> }
    >>> }
    >>> int main(int argc, char *argv[])
    >>> {
    >>> int Ruler[ENOUGH];
    >>> int MaxHt;
    >>> int Last;
    >>> if (argc == 1)
    >>> {
    >>> printf("usage: %s HEIGHT_OF_MIDDLE_MARK\n" , argv[0]);
    >>> return EXIT_FAILURE;
    >>> }
    >>> MaxHt = atoi(argv[1]);
    >>> Last = pow(2 , MaxHt);

    >>
    >> No need for floating point. Just use << to create a power of 2.

    >
    > like this?
    >
    > Last = 1 << MaxHt;


    That would do.

    >>> Ruler[0] = 0;
    >>> Ruler[Last] = 0;

    >>
    >> But for pity's sake check it's within a usable range before using it.
    >>

    >
    > like this?
    >
    > ...
    > MaxHt = atoi(argv[1]);
    > Last = 1 << MaxHt;
    > if (Last > ENOUGH-1)
    > return EXIT_FAILURE;


    It's possible to break even that. Checking MaxHt itself catches the
    problem even earlier. However, it's possible to confuse atoi with
    deliberately crafted strings, so the safest way is to use a function
    which lets you know that it's parsed the value unambiguously and
    correctly. I believe that strtol does a far better job than atoi.

    > Ruler[0] = 0;
    > ...
    >
    >>> Rule(Ruler , 0 , Last , MaxHt);
    >>> PrintRlr(Ruler , Last);
    >>> return EXIT_SUCCESS;
    >>> }
    >>> :) superpollo@192.168.1.152:~/test$ cc -ansi -pedantic -Wall -o ruler
    >>> ruler.c -lm
    >>> :) superpollo@192.168.1.152:~/test$ ./ruler
    >>> usage: ./ruler HEIGHT_OF_MIDDLE_MARK
    >>> :( superpollo@192.168.1.152:~/test$ ./ruler 4
    >>>


    That was height 0, I'm sure.

    >>> -
    >>> --
    >>> -
    >>> ---
    >>> -
    >>> --
    >>> -
    >>> ----
    >>> -
    >>> --
    >>> -
    >>> ---
    >>> -
    >>> --
    >>> -
    >>>
    >>> :) superpollo@192.168.1.152:~/test$
    >>>
    >>> any comments and suggestions are more than welcome, and so is criticism.

    >>
    >> While printing the ruler, also print out Pos^(Pos-1) using %x as the
    >> format string. See if you can find a relationship between the value
    >> printed and the length of the tick mark printed.

    >
    > :) superpollo@192.168.1.152:~/test$ grep -A 10 "void DisplayRlr" ruler02.c
    > void DisplayRlr(const int Ruler[] , int Last)
    > {
    > int Pos , Height;
    > for (Pos = 0 ; Pos <= Last ; Pos++)
    > {
    > printf("%x\t" , Pos^(Pos-1));
    > for (Height = 1 ; Height <= Ruler[Pos] ; Height++)
    > putchar('-');
    > putchar('\n');
    > }
    > }
    > :) superpollo@192.168.1.152:~/test$ cc -ansi -pedantic -Wall -o ruler
    > ruler02.c -lm
    > :) superpollo@192.168.1.152:~/test$ ./ruler 4
    > ffffffff
    > 1 -
    > 3 --
    > 1 -
    > 7 ---
    > 1 -
    > 3 --
    > 1 -
    > f ----
    > 1 -
    > 3 --
    > 1 -
    > 7 ---
    > 1 -
    > 3 --
    > 1 -
    > 1f
    > :) superpollo@192.168.1.152:~/test$
    >
    > mmm... seems like the binary representation of Pos... in fact
    > sedgewick wrote something similar in the following pages (counting the
    > number of trailing zeros in the binary rep of even integers).


    Bingo!

    > thanks for help and insight.


    It's a pleasure having someone learning who not only asks appropriate
    questions, but also pays attention to the answers. Now pay attention
    to all the people who correct me!

    Phil
    --
    Any true emperor never needs to wear clothes. -- Devany on r.a.s.f1
    Phil Carmody, Dec 8, 2009
    #2
    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.

Share This Page