Path: csiph.com!news.swapon.de!eternal-september.org!feeder.eternal-september.org!reader01.eternal-september.org!.POSTED!not-for-mail From: Tim Rentsch Newsgroups: comp.lang.c Subject: Re: max of 3 Date: Sat, 29 Aug 2020 05:19:38 -0700 Organization: A noiseless patient Spider Lines: 127 Message-ID: <861rjpabl1.fsf@linuxsc.com> References: <7d71a0a9-5db4-44ea-b2e7-50a41bd846dao@googlegroups.com> <86h7srbv7p.fsf@linuxsc.com> <2bdc9afb-769d-4bce-a6f3-372cc0c22f30o@googlegroups.com> Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Injection-Info: reader02.eternal-september.org; posting-host="fa701d7c3dfeeb40f6257600f67e6301"; logging-data="16695"; mail-complaints-to="abuse@eternal-september.org"; posting-account="U2FsdGVkX19Lg43od07whHG+6JiUF7DD6Lv1Lj80Zgs=" User-Agent: Gnus/5.11 (Gnus v5.11) Emacs/22.4 (gnu/linux) Cancel-Lock: sha1:uIEAtyvZeLm3FhNgBHxF5dhEDRc= sha1:PF3OslHKPsi2ukPVHtNPnODUIIs= Xref: csiph.com comp.lang.c:154168 luser droog writes: > On Monday, August 24, 2020 at 4:16:55 PM UTC-5, Tim Rentsch wrote: > >> luser droog 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>>> if(b>>> 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 >>> return a; >>> if >>> return b; >>> if >>> 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 > b && a < c ) >>> >>> = >>> ( b > c ) /* we've already covered a */ >>> >>> = >>> ( 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.