Prev: M,I-5,Perse cution my r esponse to th e harassmen t
Next: M-I'5`Persecut ion ` thei r methods and tacti cs
From: Stuart Golodetz on 7 Jan 2008 11:10
"Richard Heathfield" <rjh(a)see.sig.invalid> wrote in message
news:kt6dnZhitdg8FebanZ2dnUVZ8vqdnZ2d(a)bt.com...
> yaojiaxing said:
>
>> (nbytes + sizeof(Header) - 1) / sizeof(Header) ,here why should minus by
>> one,
>> i think (nbytes + sizeof(Header) ) / sizeof(Header) is right,can you tell
>> me???
>
> When you divide an integer by an integer, any remainder is lost.
>
> Programming 101, Jan 2008 - mid-year examination (continued)
>
> Q739: You have B bottles of wine, and you want to get some wine-racks on
> which to store them, but you don't want to spend any money unnecessarily.
> A wine-rack can store R bottles. B and R are integers. Derive an
> expression for the *minimum* number of wine racks you need to buy such
> that you can store all the bottles on racks.
>
> Hmmm, let's see. Obviously it should be B / R. Let's test that. Let's say
> we have 100 bottles and 9 bottles per rack. 100 / 9 is 11 (remainder is
> discarded). But 11 racks * 9 bottles per rack will only hold 99. So let's
> try (B + 1) / R. That works for 100 and 9, but what if I had 101 bottles?
> Oh dear. AHA! (B + R) / R ! That'll do it, won't it? Let's see - (101 + 9)
> / 9 = 110/9 = 12, and 12 racks will store 108 bottles. Oh, but wait. What
> if I have exactly 108 bottles? Then (B + R) / R comes to 117/9 which is
> 13, which is 1 too many. In fact, what I need is... ah! If the number of
> bottles is an exact multiple of the rack size, I want B / R, otherwise I
> want (B + R) / R. Now, integer division is lossy - to increase the
> quotient by 1, I need to increase the dividend by the divisor. So if I use
> (B + R - 1) / R, that has exactly the effect I want. 107 bottles -> (107 +
> 9 - 1) / 9 = 115 / 9 = 12. 108 bottles -> (108 + 9 - 1) / 9 = 116 / 9 =
> 12. For 109 bottles, I'll need an extra rack. Does that work? (109 + 9 -
> 1) / 9 = 117 / 9 = 13, yep.
>
> A739: (B + R - 1) / R
>
> HTH. HAND.
>
> --
> Richard Heathfield <http://www.cpax.org.uk>
> Email: -http://www. +rjh@
> Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
> "Usenet is a strange place" - dmr 29 July 1999

For what it's worth, we could also write what Richard's saying here as:

ceil(a / b) = floor((a + b - 1) / b)

Clearly the expression for the number of racks needed is ceil(B / R), but
we're looking for a way to write that using only integer division (note that
a div b = floor(a / b), where here a / b means normal division). The reason
the two are equal can be seen from the following:

Suppose a = qb + r for integral q and r such that 0 <= r < b, then:

ceil(a / b) =
{ q if r = 0
{ q+1 otherwise

Now:

floor((a + b - 1) / b)
= floor(((q+1)b + r - 1) / b)
= floor(q+1 + (r-1)/b)

If r = 0, then (r-1)/b = -1/b < 0 and the expression will evaluate to
floor(q+1 - 1/b) = q.
Otherwise, since (r-1)/b < (b-1)/b < 1, the expression will evaluate to q+1.

So the two expressions are equal and we can use floor((a + b - 1) / b) = (a
+ b - 1) div b in place of ceil(a / b).

Hope this helps,
Stu


First  |  Prev  | 
Pages: 1 2
Prev: M,I-5,Perse cution my r esponse to th e harassmen t
Next: M-I'5`Persecut ion ` thei r methods and tacti cs