CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 2 of 2 FirstFirst 12
Results 16 to 24 of 24

Thread: just4fun

  1. #16
    Join Date
    Jun 2002
    Location
    Moscow, Russia.
    Posts
    2,176

    Re: just4fun

    2 DeepButi
    Sorry, I meant "8 squares but for biggest"...

    Anyway, I don't think brute-force is a subject of consideration since you are talking about n=9973...
    "Programs must be written for people to read, and only incidentally for machines to execute."

  2. #17
    Join Date
    Dec 2003
    Location
    St. Cugat - Catalunya
    Posts
    441

    Re: just4fun

    Step 1) recursive function to find a better decomposition than the actual solution.
    Step 2) recursive function to arrange it. If success we have a new actual solution.

    Forget about recursivity, it's nice but time consuming. It can be translated to iterations in a known way.

    Reasonable guesses:
    a) solution contains one (n+1)/2 and two (n-1)/2
    b) located at [0,0], [0,(n+1)/2] and [(n+1)/2,0]

    b) implies there is always at least one 1-square, so Step1 skips decompositions without 1-squares.

    Only non brute force trick on Step2: squares of identical size to last located (they are tried in decreasing order) only try posterior placements.

    Obviously, 1-squares are not tried to be placed: they fit always

    So, Step2 is by far THE problem. How do you improve it? Any ideas?
    Did it help? rate it.

    The best conversation I had was over forty million years ago ... and that was with a coffee machine.

  3. #18
    Join Date
    Jun 2002
    Location
    Moscow, Russia.
    Posts
    2,176

    Re: just4fun

    One more method: greedy dynamics.
    You form any decomposition, then create a temporary decomposition by cutting the area with a parrern. Pattern may be for example a square with a lower side, then you "mark" all cells on that pattern and replace them with the least number of squares, then replace with the least number of squares the remnants of squares outside the pattern cutted by it. If the resulted decomposition has a smaller number of squares, then you replace the current decomposition with the resulted, and so on. I think that the rectangles and squares with cutted (by another square) corner as patterns would be enough to reach the minimum from any starting decomposition, but I have no idea how to prove any thing like that... I'll implement my method, but at any rate it can't catch n=9973... It is (n^5) at least...
    Last edited by RoboTact; September 2nd, 2004 at 12:32 PM.
    "Programs must be written for people to read, and only incidentally for machines to execute."

  4. #19
    Join Date
    Dec 2003
    Location
    St. Cugat - Catalunya
    Posts
    441

    Re: just4fun

    Just a curious pattern,
    being xi the size of the ith-square, best solutions (seem to) have:

    old guess
    a) x1=(n+1)/2, x2=x3=(n-1)/2
    more guesses
    b) x4+x5=x1
    c) x6=x5
    d) x4 placed at [x2,n-x2] i.e. top right of free area


    Last edited by DeepButi; September 3rd, 2004 at 03:24 AM.
    Did it help? rate it.

    The best conversation I had was over forty million years ago ... and that was with a coffee machine.

  5. #20
    Join Date
    Sep 2004
    Posts
    5

    Smile Re: just4fun

    Still new in this forum!u

    How's this going? I go with others that said by decomposition. I think by recursion. Cut the square, then cut remaining polygons until end.

    By the way,

    when n = 4, how many squares?

  6. #21
    Join Date
    Dec 2003
    Location
    St. Cugat - Catalunya
    Posts
    441

    Re: just4fun

    dennisb_palma,
    for any n=2*k ... allways 4 squares size k. Only prime numbers are interesting, read the whole thread .

    ... and I'm not on it anymore ... just working with some MTD(f) algorithms for other problems.
    Did it help? rate it.

    The best conversation I had was over forty million years ago ... and that was with a coffee machine.

  7. #22
    Join Date
    Aug 2004
    Location
    Bucharest, Romania... sometimes
    Posts
    1,039

    Re: just4fun

    Hi!
    Prime numbers are interesting as input for this problem, but not only. Take for example n = 143. Since 11 and 13 are divisors of 143, the square can be divided as a square of 11 or 13, but which one you should choose? Both 11 and 13 squares can be devided in minimum 11 squares. Can anyone prove the following?
    Theorem 1: Considering the mentioned problem's conditions, if n1 and n2 are two prime numbers such as n1 < n2, then the solution (minimum number of squares required to divide a square of side n) for n = n1 is <= than for n = n2.
    The proof for the above theorem can be quite helpful in solving the problem for numbers that are not prime.

    Another interesting statement that requires proof is:
    Theorem 2: Considering the mentioned problem's conditions, if n is prime number, then for any valid division of this square (solution or not), the sum of sides of all squares used in the division is >= 3*n-2.
    Can anyone prove it? Yes? Then, how about trying to prove that the solution will add up to exactly 3*n-2...

    One more thing: this problem made me recall the generalized Fibonacci series, and if you want to make it more complex, just change it to a 3D problem, by having cubes instead of squares.

    You'll never be bored again
    Bogdan Apostol
    ESRI Developer Network

    Compilers demystified - Function pointers in Visual Basic 6.0
    Enables the use of function pointers in VB6 and shows how to embed native code in a VB application.

    Customize your R2H
    The unofficial board dedicated to ASUS R2H UMPC owners.

  8. #23
    Join Date
    Jun 2002
    Location
    Moscow, Russia.
    Posts
    2,176

    Re: just4fun

    I don't know if there would be an answer after so much time, but I still wonder how this problem can be solved, how these theorems are related to original problem and how these theorems can be proved... None was advanced for a long time...
    "Programs must be written for people to read, and only incidentally for machines to execute."

  9. #24
    Join Date
    Dec 2004
    Location
    Örebro, Sweden
    Posts
    58

    Re: just4fun

    Why is just prime numbers interesting in this problem? Why isn't, like say 9 interesting or something? or does it fit into the group n = prime * prime ???

    This sounds really interesting, This will keep me some time with pen and paper ^^

    EDIT: Aha maybe I understand the thing that the nonprimes are not interesting, is it because, a square that can be divided has it's smallest number of smaller squares = the smallest divided number * 2? Okay I didn't even understand my self, example:

    If I have, let's say 21 than 21 can be divided into the factors 3 and 7, the smallest factor is 3, so the smallest number of squares in a 21 square, is 3 * 2 = 6 ?

    EDIT: (again) noop sorry, that was a bad statement, I think I get it now, it is not that you take the smallest factor * 2 but you take the smallest factor, and than you see how many squares fit in a square with the side of the smallest factor, okay, taht makes it really stupid to look for things that are not primes...
    Last edited by Pixlegamer; January 4th, 2005 at 03:08 PM.

Page 2 of 2 FirstFirst 12

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured