Teaching Kids Programming – Compute the Maximal Perimeter by Forming a Rectangle from N squares


Teaching Kids Programming: Videos on Data Structures and Algorithms

Given N squares which side is M, we want to re-arrange it to form a larger rectangle. We want to maximize the Perimeter.

Algorithm to Compute Maximal Perimeter by Forming a Rectangle from N squares

For N=6 squares M=3, we have the following two solutions: 3×2 or 1×6. We have other variants but they are the same (not affecting the permiter because it can be simply rotated or flipped from existing variant).

white-board-max-perimter-n-squares-rectangle Teaching Kids Programming - Compute the Maximal Perimeter by Forming a Rectangle from N squares algorithms greedy algorithm math programming languages teaching kids programming

If we place it like 3×2 (or 2×3) – like this:

AAA
AAA

The permiter is 72-14*3=30

If we place it horizontally one by one – like this:

AAAAAA

The permiter is 72-10*3=42

So, the greedy strategy is to avoid more internal joint edges by putting them one by one next to each other along the same row:

The answer is tex_2b427fe4247bb69ebc92e7a8f65c54e6 Teaching Kids Programming - Compute the Maximal Perimeter by Forming a Rectangle from N squares algorithms greedy algorithm math programming languages teaching kids programming which is tex_853ee631c9d2e1a9edcabfdde4e43cd9 Teaching Kids Programming - Compute the Maximal Perimeter by Forming a Rectangle from N squares algorithms greedy algorithm math programming languages teaching kids programming

Translated into Python code:

1
2
def maxPerimeter(n, m):
    return (2*n+2)*m
def maxPerimeter(n, m):
    return (2*n+2)*m

The time and space complexity is O(1) constant.

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
400 words
Last Post: Teaching Kids Programming - Compute the Max Fence Area via Bruteforce Algorithm or Parabola Quadratic Equation
Next Post: Teaching Kids Programming - Finding Real Roots of a Quadratic Equation

The Permanent URL is: Teaching Kids Programming – Compute the Maximal Perimeter by Forming a Rectangle from N squares

Leave a Reply