Manoel Menezes | 9 Jul 04:17 2013
Picon

Harder Question - Chapter 4 - 4.12 - haskell the craft of functional programming - Second Edition

Hi everybody!

I am trying to solve the question for a long time:

[4.12 Harder] Find out the maximum number of pieces we can get by making a given
number of flat (that is planar) cuts through a solid block. It is not the same
answer as we calculated for straight-line cuts of a flat piece of paper.
 
I find out that this function has the following results:

f 0 = 1
f 1 = 2
f 2 = 4
f 3 = 8

That is, from 0 to 3, the flat cuts all the pieces in two other pieces, so the number of pieces is doubled.

But, starting from f 4, the flat can not cuts all the pieces, in case of f 4, the flat can cut 6 out of the 8 pieces, resulting
in 12 pieces plus 2 pieces 2 = 14 pieces.

But I can not reach a general case.

Can anybody help me to find out the solution?

Thank you very much!

Manoel Menezes.
__________________________________
 Manoel Messias da Silva Menezes Jr
 M.Sc.in Computer Science
 Federal University of Pernambuco
 System Analyst - Petrobras
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
Anton Nikishaev | 9 Jul 14:06 2013
Picon

Re: Harder Question - Chapter 4 - 4.12 - haskell the craft of functional programming - Second Edition

Manoel Menezes <manoel.menezes.jr <at> gmail.com> writes:

> Hi everybody!
>
> I am trying to solve the question for a long time:
>
> [4.12 Harder] Find out the maximum number of pieces we can get by
> making a given number of flat (that is planar) cuts through a solid
> block. It is not the same answer as we calculated for straight-line
> cuts of a flat piece of paper.    I find out that this function has
> the following results:
>
> f 0 = 1
> f 1 = 2
> f 2 = 4
> f 3 = 8
>
> That is, from 0 to 3, the flat cuts all the pieces in two other
> pieces, so the number of pieces is doubled.
>
> But, starting from f 4, the flat can not cuts all the pieces, in case
> of f 4, the flat can cut 6 out of the 8 pieces, resulting in 12 pieces
> plus 2 pieces 2 = 14 pieces.

It can cut 7, so it is 2*7+1.

Forget about block borders and suppose you have n-1 planes and add a new
place.  It will cut each n-1 planes.  Now look at this new plane with
intersection lines (n-1 ones) in it. Each region in plane adds one new
3D piece, so

  F(0) = 1;
  F(n) = F(n-1) + P(n-1),

where P(n) is max number of pieces slicing plane with n cuts.

Spoiler: cake numbers

--

-- 
lelf

_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe <at> haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Gmane