2025年3月16日 星期日 甲辰(龙)年 月十五 设为首页 加入收藏
rss
您当前的位置:首页 > 计算机 > 编程开发 > 数据结构与算法

程序员的算法趣题Q16:3根绳子折成四边形

时间:12-27来源:作者:点击数:41

1. 问题描述

本题来自《程序员的算法趣题》中的第16题。

假设分别将3根长度相同的绳子摆成3个四边形。其中2根摆成长方形,另外1根摆成正方形。这时,当长度选择适当的话,会出现两个长方形的面积之和等于正方形的面积的情况(假设绳子长度和各四边形的边长都是整数)。

此外,将同比整数倍的结果看作是同一种解法。

2. 初始解法

令绳子长度为L=4*a,即正方形的边长为a。令另外两个长方形的较短的边分别为x1和x2,并且不失一般性可以假定它们满足关系:x1<=x2<a。

这个问题可以通过遍历搜索来解决。其中,对于任意的a,基于以上假设必然有,进一步可以推导出。这样可以将x1的搜索范围缩小。代码如下:

  • import sys
  • import time
  • import random
  • from math import gcd, sqrt, ceil
  • from typing import List
  • # from queue import Queue
  • class Solution:
  • def lines2rectangles1(self, L:int)->int:
  • """
  • :L: The length of the lines
  • :
  • :ret: The number of the solutions
  • """
  • aMax = L // 4
  • valid_cnt = 0
  • for a in range(1,aMax+1):
  • for x1 in range(1,ceil(a/sqrt(2))): # Assuming that x1 <= x2 < a, without loss of generality
  • for x2 in range(x1,a):
  • if x1*(2*a-x1) + x2*(2*a-x2) == a*a:
  • if gcd(a,x1) == 1: # gcd(a,x1) --> gcd(a,x1,x2)
  • valid_cnt = valid_cnt + 1
  • # print('a = {0}, x1 = {1}, x2 = {2}'.format(a,x1,x2))
  • return valid_cnt

2.1 三者互素的判断

其中,将同比整数倍的结果看作是同一种解法,这意味着,{a,x1,x2}必须满足三者互素,换句话说三者的最大公约数为1,才被计算为一个独立的答案。容易证明,在本题中,如果{a,x1,x2}满足题设要求的平方和关系的话,{a,x1,x2}三者互素等价于任何两者互素。因此,在代码中仅判断a和x1是否互素(用python中math模块中的gcd()函数)。

3. 改进1

在解法1中,每次条件判断都是直接计算“x1*(2*a-x1) + x2*(2*a-x2) == a*a”,这会导致非常多的重复计算。事实上针对每个a(即针对最外层的每个循环),只需要计算一次a*a;同理针对每个x1(即针对第2层的每个循环),只需要计算一次x1*(2*a-x1)。这样可以将代码优化如下:

  • def lines2rectangles2(self, L:int)->int:
  • """
  • :L: The length of the lines
  • :
  • :ret: The number of the solutions
  • """
  • aMax = L // 4
  • valid_cnt = 0
  • for a in range(1,aMax+1): # Assuming that x1 <= x2 < a, without loss of generality
  • a_squ = a*a
  • for x1 in range(1,ceil(a/sqrt(2))):
  • area1 = x1*(2*a-x1)
  • area2 = a_squ - area1
  • for x2 in range(x1,a):
  • if x2*(2*a-x2) == area2:
  • if gcd(a,x1) == 1: # gcd(a,x1) --> gcd(a,x1,x2)
  • valid_cnt = valid_cnt + 1
  • # print('a = {0}, x1 = {1}, x2 = {2}'.format(a,x1,x2))
  • return valid_cnt

运行结果表明这一简单的改进导致了运行时间下降了60%!

4. 改进2

  • def lines2rectangles3(self, L:int)->int:
  • """
  • :L: The length of the lines
  • :
  • :ret: The number of the solutions
  • """
  • aMax = L // 4
  • valid_cnt = 0
  • for a in range(1,aMax+1): # Assuming that x1 <= x2 < a, without loss of generality
  • a_squ = a*a
  • for x1 in range(1,ceil(a/sqrt(2))):
  • if gcd(a,x1) == 1: # gcd(a,x1) --> gcd(a,x1,x2)
  • area1 = x1*(2*a-x1)
  • area2 = a_squ - area1
  • for x2 in range(x1,a):
  • if x2*(2*a-x2) == area2:
  • valid_cnt = valid_cnt + 1
  • # print('a = {0}, x1 = {1}, x2 = {2}'.format(a,x1,x2))
  • return valid_cnt

运行结果表明这一简单的改进导致了运行时间进一步下降了30%!至少说明在本实现中,平方和关系的判断比互素关系的判断更为耗时。

5. 改进3

进一步思考可以发现,当三个四边形满足题设条件时,假设其中一个长方形(不失一般性记为长方形1)的边长分别为a-x和a+x,则长方形2的面积必然为a*a – (a-x)(a+x)=x*x。反过来,令长方形2的边长分别为a-y和a+y,可以得到长方形1的面积必然为a*a – (a-y)(a+y)=y*y,也即三者的面积(的平方根)构成一组勾股数的关系!反之,容易证明,任何满足a*2=x*2+y*2的一组数{a,x,y}都对应着满足题设条件的三个四边形。由此可知,求满足题设条件下的解等价于寻找勾股数!

  • def lines2rectangles4(self, L:int)->int:
  • """
  • :L: The length of the lines
  • :
  • :ret: The number of the solutions
  • """
  • aMax = L // 4
  • valid_cnt = 0
  • for a in range(1,aMax+1): # Assuming that x1 <= x2 < a, without loss of generality
  • a_squ = a*a
  • for x1 in range(1,ceil(a/sqrt(2))):
  • if gcd(a,x1) == 1: # gcd(a,x1) --> gcd(a,x1,x2)
  • diff = a_squ - x1*x1
  • for x2 in range(ceil(a/sqrt(2)),a):
  • if x2*x2 == diff:
  • valid_cnt = valid_cnt + 1
  • # print('a = {0}, x1 = {1}, x2 = {2}'.format(a,x1,x2))
  • return valid_cnt

6. 测试结果

测试代码如下所示:

  • if __name__ == '__main__':
  • sln = Solution()
  • L = 20
  • tStart = time.time()
  • num = sln.lines2rectangles1(L)
  • tCost = time.time() - tStart
  • print('L = {0}, numSlns = {1}, tCost = {2}(sec)'.format(L,num,tCost))
  • L = 500
  • tStart = time.time()
  • num = sln.lines2rectangles1(L)
  • tCost = time.time() - tStart
  • print('#1: L = {0}, numSlns = {1}, tCost = {2}(sec)'.format(L,num,tCost))
  • tStart = time.time()
  • num = sln.lines2rectangles2(L)
  • tCost = time.time() - tStart
  • print('#2: L = {0}, numSlns = {1}, tCost = {2}(sec)'.format(L,num,tCost))
  • L = 2000
  • tStart = time.time()
  • num = sln.lines2rectangles1(L)
  • tCost = time.time() - tStart
  • print('#1: L = {0}, numSlns = {1}, tCost = {2}(sec)'.format(L,num,tCost))
  • tStart = time.time()
  • num = sln.lines2rectangles2(L)
  • tCost = time.time() - tStart
  • print('#2: L = {0}, numSlns = {1}, tCost = {2}(sec)'.format(L,num,tCost))
  • tStart = time.time()
  • num = sln.lines2rectangles3(L)
  • tCost = time.time() - tStart
  • print('#3: L = {0}, numSlns = {1}, tCost = {2}(sec)'.format(L,num,tCost))
  • tStart = time.time()
  • num = sln.lines2rectangles4(L)
  • tCost = time.time() - tStart
  • print('#4: L = {0}, numSlns = {1}, tCost = {2}(sec)'.format(L,num,tCost))

运行后得到结果:

#1: L = 2000, numSlns = 80, tCost = 4.635588645935059(sec)

#2: L = 2000, numSlns = 80, tCost = 1.9797470569610596(sec)

#3: L = 2000, numSlns = 80, tCost = 1.2058100700378418(sec)

#4: L = 2000, numSlns = 80, tCost = 0.340120792388916(sec)

最终的算法所需要的时间只有初始算法的十分之一。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门