Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Why does this recursion work for this problem?

  1. #1
    Junior Member
    Join Date
    Mar 2013
    Posts
    7
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Why does this recursion work for this problem?

    You are given a rectangular floor that is to be tiled with square tiles. The tiles come in a variety of sizes, but they all measure in some power of two: 1, 2, 4, 8, etc. A 5x6 space can be tiled with 30 of the smallest tile, but the minimum number of tiles required is only 9. Refer to the pattern below.

    http://nayuki.eigenstate.org/res/dwi...-201010-p3.png

    Find the minimum number of tiles.

        private static int getFloorTileCount(int width, int height) {
            if (width == 0 || height == 0) {
                return 0;
            } else if (width % 2 == 0 && height % 2 == 0) {
                return getFloorTileCount(width / 2, height / 2);
            } else if (width % 2 == 0 && height % 2 == 1) {
                return width + getFloorTileCount(width / 2, height / 2);
            } else if (width % 2 == 1 && height % 2 == 0) {
                return height + getFloorTileCount(width / 2, height / 2);
            }
            return width + height - 1 + getFloorTileCount(width / 2, height / 2);
        }

    I can't seem to understand why this code is able to get the minimum number of tiles required.


  2. #2
    Member Chris.Brown.SPE's Avatar
    Join Date
    May 2008
    Location
    Fort Wayne, Indiana
    Posts
    190
    Thanks
    1
    Thanked 31 Times in 31 Posts

    Default Re: Why does this recursion work for this problem?

    A normal person doing this problem would prolly figure out what the biggest block is that they could put in the grid and work their way to the smaller tiles. This program is doing the opposite. It starts with determining if any of the smallest tiles are required then divides the grid width and height by 2 (this is equivalent of increasing your grid size). I'll explain that another way. Your grid of 5x6 can fit 5x6 small tiles, but a 4x6 grid could fit 2x3 of the next larger tiles. Make sense? The if statement is trying to determine if the height or width is odd therefore requiring the size tile you are on. If neither is odd, it just increases the size of the tile (by dividing the grid by 2) then calls itself again.

    Order of execution for 5x6 grid...
    Width is odd so we need 6 (value of height) tiles to make it even
    Now increase the size of the tile by dividing the grid: grid now 2x3 (Remember an int of 5 divided by 2 is 2. You drop the remainder)
    Height is odd so we need 2 (value of width) tiles to make it even
    Now increase the size of the tile by dividing the grid: grid now 1x1
    Both are odd so we need 1 tile (width + height -1 => this is basically getting the left and bottom border with tiles but we only need one)
    Now we increase the size of the tile by dividing the grid: grid now 0x0
    Empty grid now we return and add all the results we've gotten along the way. 1 big tile, 2 medium tiles, 6 small tiles = 9 tiles.
    Writing code is your job, helping you fix and understand it is mine.

    <-- Be sure to thank and REP (Star icon) those who have helped you. They appreciate it!

Similar Threads

  1. Recursion /String problem
    By imrllyhandsome in forum What's Wrong With My Code?
    Replies: 4
    Last Post: January 9th, 2013, 10:37 PM
  2. Need help with Java recursion problem!
    By eyesackery in forum Java Theory & Questions
    Replies: 2
    Last Post: June 5th, 2012, 08:12 AM
  3. recursion problem, please help
    By nil in forum What's Wrong With My Code?
    Replies: 2
    Last Post: October 18th, 2010, 12:59 PM
  4. New Recursion problem need lil help
    By Delstateprogramer in forum Algorithms & Recursion
    Replies: 21
    Last Post: July 8th, 2010, 06:35 PM
  5. Recursion Problem Need Help ASAP
    By Delstateprogramer in forum Algorithms & Recursion
    Replies: 6
    Last Post: June 26th, 2010, 08:36 PM