Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #154168

Re: max of 3

Show all headers | View raw

luser droog <luser.droog@gmail.com> writes:

> On Monday, August 24, 2020 at 4:16:55 PM UTC-5, Tim Rentsch wrote:
>
>> luser droog <luser.droog@gmail.com> writes:
>>
>>> On Saturday, August 22, 2020 at 4:12:26 AM UTC-5, axel porin wrote:
>>>
>>>> hi
>>>> why it doesn't work
>>>>
>>>> int max3(int a,int b,int c){
>>>>     if(a<b)
>>>>     if(b<c)
>>>>     return c;
>>>>     else
>>>>     return b;
>>>> }
>>>>
>>>> int main(){
>>>>     int a=2,b=-4,c=6;
>>>>    printf("%d ",max3(a,b,c));
>>>> }
>>>>
>>>> output:
>>>> 2
>>>
>>> One way to approach this kind of function is to break it up into
>>> cases and make sure each case is covered.  The obvious cases here
>>> (to me) is whether to return a, b, or c.  So that leads directly to
>>> pseudocode:
>>>
>>>   if <a is the max>
>>>       return a;
>>>   if <b is the max>
>>>       return b;
>>>   if <c is the max>
>>>       return c;
>>>
>>> Since there branches are returning, I'm leaving out the 'else's so
>>> the top level structure is simpler.
>>>
>>> Then all that's needed is appropriate tests
>>>
>>> <a is the max>=
>>>   ( a > b && a < c )
>>>
>>> <b is the max>=
>>>   ( b > c )     /* we've already covered a */
>>>
>>> <c is the max>=
>>>   ( 1 )          /* we've already covered a and b */
>>>
>>> So that's how I recommend structuring your tests.  Nesting
>>> the expressions makes it harder to make sure all the
>>> possibilities are covered.  The code can certainly be
>>> simplified from there, but I think this gives a methodology
>>> to get these sort of functions written correctly.
>>
>> This approach seems the wrong way round.  It can do more
>> comparisons than it has to (at most two are needed), and that is
>> more evident if we consider larger problems of four or five, etc,
>> inputs.  The predicate "a is the answer" needs a global test.  In
>> contrast, the predicate "a is obviously not the answer" can be
>> done with a simple local test.  That insight helps construct a
>> solution.
>>
>> First we do the easy case, starting at the bottom.  With just one
>> input, the answer is the input:
>>
>>     int
>>     max1( int a ){  return  a;  }
>>
>> With two inputs, if a < b then the answer can't be a (and so it
>> must be b), but otherwise it can be a:
>>
>>     int
>>     max2( int a, int b ){  return  a < b ? b : a;  }
>>
>> With three inputs, a, b, and c, reduce three inputs to two by
>> doing one comparison.  If a < b, then the answer can't be a, and
>> so must be either b or c;  otherwise, the answer can choose
>> between a and c.  We know how to do tests for two inputs, so three
>> inputs is a simple step up from that:
>>
>>     int
>>     max3( int a, int b, int c ){
>>         return
>>             a < b
>>               ?    b < c ? c : b
>>               :    a < c ? c : a
>>         ;
>>     }
>>
>> or if max2() is present
>>
>>     int
>>     max3( int a, int b, int c ){
>>         return  a < b  ? max2( b, c )  : max2( a, c );
>>     }
>>
>> This approach scales easily, and linearly, for any fixed number
>> of inputs.
>
> Marvelous!  I think my tendency has been to code bottom up, and then
> you beat me with top down design.  Here I tried to be top down, and
> you beat me with mathematical induction.

Yes, in fact I noticed the irony when I was writing the response.

Another way to view the difference is this.  Both of our solutions
are top down, but they reduce the problem by looking at opposite
ends of the spectrum.  My scheme (even though the answer is
explained in a bottom-up way) reduces the problem by slicing off
as little of the problem as it can:  if a < b then we know the
answer cannot be a, etc.  In contrast, your scheme starts by
slicing off a big piece, in the sense that the test for "a being
the answer" is a more elaborate test.  As a general rule in
decomposing a problem it often helps to narrow the problem just a
little bit at a time, and let subsequent refinements take care of
the rest.  A common mistake (and I too am guilty of this at times)
is to try to do too much in the first refinement, leading to code
that is overly complicated, or hard to understand, or both.  Here
is a rule of thumb to counteract this tendency:  when you notice a
function starting to be too large or complicated, take a step back
and slice off just a little piece in the current function, leaving
the rest of the problem for the next level of refinement.

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

max of 3 axel porin <porinaxel@gmail.com> - 2020-08-22 02:12 -0700
  Re: max of 3 Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-08-22 02:38 -0700
    Re: max of 3 axel porin <porinaxel@gmail.com> - 2020-08-22 03:24 -0700
      Re: max of 3 David Brown <david.brown@hesbynett.no> - 2020-08-22 15:53 +0200
    Re: max of 3 Elijah Stone <elronnd@elronnd.net> - 2020-08-22 19:03 -0700
      Re: max of 3 James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-08-22 22:13 -0400
      Re: max of 3 David Brown <david.brown@hesbynett.no> - 2020-08-23 13:42 +0200
  Re: max of 3 Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-22 10:54 +0100
    Re: max of 3 Bart <bc@freeuk.com> - 2020-08-22 11:24 +0100
      Re: max of 3 axel porin <porinaxel@gmail.com> - 2020-08-22 03:29 -0700
        Re: max of 3 axel porin <porinaxel@gmail.com> - 2020-08-22 03:38 -0700
          Re: max of 3 axel porin <porinaxel@gmail.com> - 2020-08-22 04:06 -0700
          Re: max of 3 James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-08-22 07:49 -0400
        Re: max of 3 David Brown <david.brown@hesbynett.no> - 2020-08-22 15:58 +0200
          Re: max of 3 Poprocks <please@replytogroup.com> - 2020-08-22 15:15 -0400
            Re: max of 3 James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-08-22 16:49 -0400
            Re: max of 3 Jorgen Grahn <grahn+nntp@snipabacken.se> - 2020-08-22 20:56 +0000
            Re: max of 3 David Brown <david.brown@hesbynett.no> - 2020-08-22 22:56 +0200
              Re: max of 3 James Kuyper <jameskuyper@alumni.caltech.edu> - 2020-08-22 17:04 -0400
                Re: max of 3 David Brown <david.brown@hesbynett.no> - 2020-08-23 13:55 +0200
              Re: max of 3 Poprocks <please@replytogroup.com> - 2020-08-22 17:33 -0400
                Re: max of 3 Jorgen Grahn <grahn+nntp@snipabacken.se> - 2020-08-23 05:54 +0000
                Re: max of 3 axel porin <porinaxel@gmail.com> - 2020-08-23 01:59 -0700
                Re: max of 3 Jorgen Grahn <grahn+nntp@snipabacken.se> - 2020-08-23 10:22 +0000
                Re: max of 3 Öö Tiib <ootiib@hot.ee> - 2020-08-23 03:27 -0700
                Re: max of 3 David Brown <david.brown@hesbynett.no> - 2020-08-23 14:05 +0200
                Re: max of 3 Bart <bc@freeuk.com> - 2020-08-23 14:09 +0100
                Re: max of 3 David Brown <david.brown@hesbynett.no> - 2020-08-23 15:58 +0200
                Re: max of 3 Bart <bc@freeuk.com> - 2020-08-23 11:33 +0100
                Re: max of 3 Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-08-23 07:04 -0700
                Re: max of 3 John Forkosh <forkosh@panix.com> - 2020-08-24 10:26 +0000
            Re: max of 3 Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-08-22 16:26 -0700
        Re: max of 3 Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-08-22 16:06 -0700
          Re: max of 3 Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-08-22 16:41 -0700
      Re: max of 3 Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-22 19:42 +0100
  Re: max of 3 Daniel Hyde <Daniel.Hyde71@gmail.com> - 2020-08-22 12:27 +0200
    Re: max of 3 Siri Cruise <chine.bleu@yahoo.com> - 2020-08-22 04:20 -0700
      Re: max of 3 Daniel Hyde <Daniel.Hyde71@gmail.com> - 2020-08-22 17:14 +0200
        Re: max of 3 Siri Cruise <chine.bleu@yahoo.com> - 2020-08-22 13:55 -0700
          Re: max of 3 Daniel Hyde <Daniel.Hyde71@gmail.com> - 2020-08-23 11:18 +0200
    Re: max of 3 Ben Bacarisse <ben.usenet@bsb.me.uk> - 2020-08-22 20:08 +0100
  Re: max of 3 Bart <bc@freeuk.com> - 2020-08-22 13:01 +0100
    Re: max of 3 gazelle@shell.xmission.com (Kenny McCormack) - 2020-08-22 16:23 +0000
      Re: max of 3 Bart <bc@freeuk.com> - 2020-08-22 20:45 +0100
  Re: max of 3 Barry Schwarz <schwarzb@delq.com> - 2020-08-22 08:26 -0700
  Re: max of 3 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-22 14:45 -0700
    Re: max of 3 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-22 14:47 -0700
      Re: max of 3 axel porin <porinaxel@gmail.com> - 2020-08-22 15:16 -0700
        Re: max of 3 luser droog <luser.droog@gmail.com> - 2020-08-22 15:28 -0700
        Re: max of 3 Real Troll <real.troll@trolls.com> - 2020-08-22 19:50 -0400
          Re: max of 3 Paul <nospam@needed.invalid> - 2020-08-22 19:44 -0400
            Re: max of 3 Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-08-24 14:29 -0700
          Re: max of 3 Barry Schwarz <schwarzb@delq.com> - 2020-08-22 18:32 -0700
            Re: max of 3 Real Troll <real.troll@trolls.com> - 2020-08-23 12:30 -0400
        Re: max of 3 Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-08-22 16:37 -0700
    Re: max of 3 Ike Naar <ike@sdf.org> - 2020-08-22 22:10 +0000
      Re: max of 3 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-22 16:49 -0700
    Re: max of 3 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-22 16:50 -0700
  Re: max of 3 Real Troll<real.troll@trolls.com> - 2020-08-22 17:17 -0400
    Re: max of 3 Barry Schwarz <schwarzb@delq.com> - 2020-08-22 18:22 -0700
  Re: max of 3 luser droog <luser.droog@gmail.com> - 2020-08-22 15:42 -0700
    Re: max of 3 luser droog <luser.droog@gmail.com> - 2020-08-22 15:52 -0700
    Re: max of 3 Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-08-24 14:16 -0700
      Re: max of 3 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-24 14:37 -0700
        Re: max of 3 Malcolm McLean <malcolm.arthur.mclean@gmail.com> - 2020-08-24 15:25 -0700
          Re: max of 3 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-24 20:15 -0700
            Re: max of 3 luser droog <luser.droog@gmail.com> - 2020-08-24 20:32 -0700
              Re: max of 3 luser droog <luser.droog@gmail.com> - 2020-08-24 23:35 -0700
              Re: max of 3 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-27 14:03 -0700
              Re: max of 3 "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2020-08-28 23:35 -0700
        Re: max of 3 Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-08-29 04:52 -0700
      Re: max of 3 luser droog <luser.droog@gmail.com> - 2020-08-24 20:27 -0700
        Re: max of 3 Vir Campestris <vir.campestris@invalid.invalid> - 2020-08-27 22:19 +0100
          Re: max of 3 Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2020-08-27 14:36 -0700
            Re: max of 3 Kaz Kylheku <793-849-0957@kylheku.com> - 2020-08-27 22:27 +0000
              Re: max of 3 Vir Campestris <vir.campestris@invalid.invalid> - 2020-08-31 22:07 +0100
                Re: max of 3 Richard Damon <Richard@Damon-Family.org> - 2020-09-01 07:19 -0400
        Re: max of 3 Tim Rentsch <tr.17687@z991.linuxsc.com> - 2020-08-29 05:19 -0700
  Re: max of 3 DFS <nospam@dfs.com> - 2020-08-26 19:25 -0400

csiph-web