c - 指定された正方形に収まる可能性のある最小の正方形の数を見つけるにはどうすればよいですか

Question

私は7x7の正方形を持っているとしましょう.私は他の正方形で正方形を埋めることができます. .

Answer 1

寸法 の正方形を考えてみましょうs x s。より小さい寸法の正方形を切り取ると、 のm x m正方形m x m、 の正方形n x n、および寸法の 2 つの長方形ができます。m x nここで、 はm + n = sです。

が偶数の場合s、正方形は のように分割できますm = n。この場合、長方形も正方形になり、答えは 4 になります。

ただし、sが奇数の場合、 と の値はm、n結果の四角形が可能な限り少ない数の正方形で埋められるように選択する必要があります。最適な構成をすぐに見つけ出す明白な方法はないように思われるので、あるサイズの長方形を埋めるために使用できる正方形の最小数を割り出すアルゴリズムを考え出すことをお勧めしますm x n(これはわずかな数です)。より単純な問題であり、再帰アルゴリズムで解決できると思います)。必要な正方形の総数は に等しくなり2 x ([number of squares in m x n rectangle] + 1)ます。ループを使用して、1との間の m のすべてのサイズを確認できますs/2。

これで始められることを願っています。