【算法趣题】Q16 3根绳子折成四边形

引言

【算法趣题】是来自图灵程序设计丛书绝云译的《程序员的算法趣题》，书中是用Ruby实现的。这里是用python来实现。

问题描述

假设分别3根长度相同的绳子摆成3个四边形。其中2根摆成长方形，剩下1根摆成正方形。这时，会出现2个长方形的面积之和等于正方形面积的情况（假设长方形和正方形的各边长都是整数）。

例】 绳子长度为20时，可以折出以下这些正方形和长方形。
第 1 根 长 1 × 宽 9 的长方形 →→ 面积 = 9
第 2 根 长 2 × 宽 8 的长方形 →→ 面积 = 16
第 3 根 长 5 × 宽 5 的正方形 →→ 面积 = 25

进一步改变绳子长度并摆成长方形和正方形，统计满足条件的长方形和正方形的组合。这里，将同比整数倍的结果看作同一种解法。

例】 绳子长度为40,60，...时，可以通过对上例进行等比运算得出以下这些正方形和长方形的组合，但要将它们看作同一种解法，所以这一类只统计为1种。

• 绳子长度 = 40
  第 1 根 长 2 × 宽 18 的长方形 →→ 面积 = 36
  第 2 根 长 4 × 宽 16 的长方形 →→ 面积 = 64
  第 3 根 长 10 × 宽 10 的正方形 →→ 面积 = 100

• 绳子长度 = 60
  第 1 根 长 3 × 宽 27 的长方形 →→ 面积 = 81
  第 2 根 长 6 × 宽 24 的长方形 →→ 面积 = 144
  第 3 根 长 15 × 宽 15 的正方形 →→ 面积 = 225

【问题】求绳子长度从1增长到500时，共有多少种组合能使摆出的2个长方形面积之和等于正方形的面积？

思路及Python3实现

3根绳子的长度一样，可以摆成正方形，所以绳子的长度应该是4的倍数。所以绳子长度的集合为 range(4, 501, 4)

假设绳子长度为i，则正方形边长为 c = int(i/4)

假设长方形的短边长度为j，则j的集合为  range(1,c)，长方形面积为j*（2*c-j）

size_set = set()

for i in range(4, 501, 4):

    c = int(i/4) # 正方形边长

    for j in range(1,c):

        widthA = j # 长方形端边长

        areaA = widthA * (2*c-widthA)

        # 两个长方形互换试为同一种情况，

        # 仅考虑第2个长方形的短边长大于第一个长方形的短边长的情况

        for k in range(j,c):

            widthB = k #第2个长方形短边长

            areaB = widthB * (2*c-widthB)

            if areaA + areaB == c*c:                

                size = (1,areaB/areaA,c*c/areaA) # 为了整数倍的情况，稍后去重用

                size_set.add(size)

print(len(size_set)) 

运行结果即20种（两个长方形互换视为同一种，长方形长宽长度互换也视为同一种）