给定一个整数n(n >= 1)和一个数字k,返回所有可能的方式将n写成k次幂不同的整数。例如,如果n = 100且k = 2:
100 = 1**2 + 3**2 + 4**2 + 5**2 + 7**2
= 6**2 + 8**2
= 10**2
或者如果k = 3:
100 = 1**3 + 2**3 + 3**3 + 4**3
所以program(100,2)
返回类似[(2, [1, 3, 4, 5, 7]), (2, [6, 8]), (2, [10])]
和program(100,3)
[(3, [1, 2, 3, 4])]
的值。
只要输入n很小,或者k很“大”(>=3),一切都可以正常工作。我的方法是首先得到一个所有整数的列表,其k次幂<= n。
def possible_powers(n,k):
arr,i = [],1
while i**k <= n:
arr.append(i)
i += 1
return arr
然后(这里是错误),我创建了这个列表的所有子集(作为列表):
def subsets(L):
subsets = [[]]
for i in L:
subsets += [subset+[i] for subset in subsets]
return subsets
最后我循环了所有这些子集,把每个元素的k次方加起来,只选择那些加起来等于n的元素。
def kth_power_sum(arr,k):
return sum([i**k for i in arr])
def solutions(n,k):
return [(k,i) for i in subsets(possible_powers(n,k)) if kth_power_sum(i,k) == n]
我知道问题出在子集创建上,但我不知道如何优化它。比如,如果我尝试解决方案(1000,2),它会创建一个大集合,占用超过4GB的内存。我的猜测是筛选出一些子集,但这不会有太大帮助,除非我有一个非常有效的筛子。
任何帮助都非常感谢。如果有什么不清楚的地方,或者我在发布这个时犯了错误,请告诉我。
5条答案
按热度按时间pengsaosao1#
如果你将其实现为一个递归生成器,你将不需要存储大量的值(甚至不需要存储结果):
a2mppw5e2#
你的问题是你在
subsets
中保存了太多不相关的组合,我在这里写了一些代码,只保存相关的列表,所以应该可以做到这一点,(我在这里写了多行,这样更容易理解)下面是相同的代码,但用一行程序编写,以最大限度地提高效率
zaqlnxep3#
@Reggie-florade和@Ohad-sharet,可以让代码运行得更快。请看下面的代码。我的解决方案与@Ohad-sharet非常相似,但运行速度要快得多。我的函数名是“kth_power_and_n”。
下面是两种方法的时间比较。
pinkon5k4#
我的解决方案是基于这个问题Finding all possible combinations of numbers to reach a given sum的答案。链接问题中的目标是通过添加列表
numbers
中的元素来达到值target
。在我们的例子中,numbers
将是从1
到target**(1/k)
的整数提升到k
。这是另一个答案的函数。唯一的修改是我们知道
numbers
是按升序排列的。这意味着我们可以更早地停止迭代。如果numbers[0]
太大,则以下幂的其余部分也会太大。现在让我们正确地调用这个函数。这里重要的一点是
subset_sum
需要幂,但我们的解决方案将使用这些数字而不增加它们。要做到这一点,让我们定义一个字典,其中键是幂,值是答案中的数字。在此之后,我们只需要给予subset_sum
一个包含字典键的列表。在我的机器上,这段代码花了9秒才完成
solutions(2000, 2)
。toiithl65#
好吧,只是为了好玩,我试着写一个递归函数来做这个;下面是结果(power_sum(2000,2)在我的机器上大约10秒内就能得到答案,所以尽管它可能不是最优的,但它仍然不算太坏)。