项目Euler 76-列出给定数量的所有分区

生成数字分区-在python中，我无法阅读/运行/理解.任何帮助将不胜感激，在此先感谢您！解决方案如所承诺的，以下代码使用自然数最多N进行N(存储在ub中)的分区，但不包括N.稍作修改，它应该可以按任何功能进行分区，包括带浮点输出的功能.基本思想是，对于分区中使用的每个值，我们都使用系数存储桶，它是该值的乘数.在每一步中，我们要么将值收取到最大可用值，要么向左或向右移动，减小电流乘数并测试是否达到总和.成功地对总和进行分区后，wayCount就会增加，并且结果会显示在屏幕上.这可能是一个有点肮脏的实现，但是即使在有问题的范围内(在我的计算机上不到5分钟)，它也可以在合理的时间内工作，每秒生成数百万个分区.始终欢迎健康的批评！ Dim ub As Integer = 10Dim availableIncrements(ub-2)作为整数昏暗的weightCoefficients(ub-2)作为整数对于i = 0至ub-2availableIncrements(i)= ub-i-1weightCoefficients(i)= -1'表示枚举尚未开始下一个昏暗wayCount为整数= 0Dim pos，总和为整数pos = 0:总和= 0做如果weightCoefficients(pos)= -1，则'当我们首先来到这里时，充电系数应达到最大weightCoefficients(pos)=(ub-sum)\ availableIncrements(pos)否则，如果weightCoefficients(pos)>0然后'定期循环:减少一倍weightCoefficients(pos)-= 1别的'返回上一个存储桶如果pos = 0，则退出执行pos-= 1继续做万一'计算当前总和总和= 0对于k = 0到pos总和== availableIncrements(k)* weightCoefficients(k)下一个'找到组合如果sum = ub且weightCoefficients(pos)>0然后wayCount + = 1'打印到屏幕上，在期望许多组合时将其移除将printList变暗为新列表(整数)对于i = 0至pos'要打印哪个数字对于k = 1 To weightCoefficients(i)'多少次打印一个数字printList.Add(availableIncrements(i))下一个下一个Console.WriteLine(String.Join("+"，printList))如果我们在最后一个存储桶中，并且只是对数字进行了分区，'无需下降并检查所有较低的系数，而后移一列.如果pos = UBound(availableIncrements)然后pos-= 1继续做万一万一如果pos<UBound(availableIncrements)然后pos + = 1weightCoefficients(pos)= -1'准备充电万一``这会让你很忙(所以你知道它没有挂起来)'对于长时间枚举不建议'如果wayCount Mod 100000 = 0然后Console.WriteLine(wayCount)环形Console.WriteLine("count ="& wayCount) Here is how Project Euler Problem #76 sounds like:"How many different ways can one hundred be written as a sum of at least two positive integers?"I've struggled to get it right for a couple of days, tried to solve in different ways and got mostly the same results for small numbers (those that are easy to check). I ended up with an algorithm that lists all partitions for a given number in alphabetical order, descending (starting from "N-1 + 1"). Written in VB.NET:Dim ub As Integer = 6Dim wayCount As Integer = 0For n = ub - 1 To 1 Step -1 'init value array (first combination) Dim s As New List(Of Integer) For m = 1 To ub \ n : s.Add(n) : Next Dim b As Integer = ub Mod n If b <> 0 Then s.Add(b) 'from where to start decrementing Dim k As Integer = s.Count - 1 While k > 0 And s(k) = 1 : k -= 1 : End While Do wayCount += 1 : Console.WriteLine(String.Join(" + ", s) & " = " & s.Sum) If s(k) = 1 Then k -= 1 If k = -1 Then Exit Do s(k) -= 1 s.Add(1) Loop While k >= 1NextConsole.WriteLine("count=" & wayCount)The code works for numbers 1-6 inclusive and starts failing for N=7, with 1 combination missed. For N=8 it misses 2 (19 instead of 21). For N=100 the answer is 4576, which is several orders of magnitude less than required. Clearly, I am missing some very important detail.If you don't have time or means to compile and run the above code, here is the output (N=7):6 + 1 = 75 + 2 = 75 + 1 + 1 = 74 + 3 = 74 + 2 + 1 = 74 + 1 + 1 + 1 = 73 + 3 + 1 = 73 + 2 + 1 + 1 = 73 + 1 + 1 + 1 + 1 = 72 + 2 + 2 + 1 = 72 + 2 + 1 + 1 + 1 = 72 + 1 + 1 + 1 + 1 + 1 = 71 + 1 + 1 + 1 + 1 + 1 + 1 = 7count=13I've studied these links:(ProjectEuler) Sum Combinations - provides a mathematical solution, which does not list all combinationsGenerating the partitions of a number - is in python, which I cannot read/run/understand.Any help would be much appreciated, thanks in advance! 解决方案 As promised, here is some code that does partitioning of N (stored in ub) using natural numbers up to N, but not including it. With slight modification, it should be able to partition by any function, including that with floating point output.Basic idea is that for every value used in partitioning we are using coefficient bucket, which is a multiplier of that value. On every step we either charge the value to maximum available, move left or right, decrement current multiplier and test if we get to the sum. Once sum was successfully partitioned, wayCount is incremented and result is printed to the screen.This might be a somewhat dirty implementation, but it works in a reasonable time even for the scope of the problem in question (under 5 minutes on my machine), generating several millions of partitions per second. Healthy criticism is always welcome!Dim ub As Integer = 10Dim availableIncrements(ub - 2) As IntegerDim weightCoefficients(ub - 2) As IntegerFor i = 0 To ub - 2 availableIncrements(i) = ub - i - 1 weightCoefficients(i) = -1 'indicates that enumeration has not started yetNextDim wayCount As Integer = 0Dim pos, sum As Integerpos = 0 : sum = 0Do If weightCoefficients(pos) = -1 Then 'when we came here first, charge coefficient to maximum available weightCoefficients(pos) = (ub - sum) \ availableIncrements(pos) ElseIf weightCoefficients(pos) > 0 Then 'regular cycle: decrease by one weightCoefficients(pos) -= 1 Else 'return to previous bucket If pos = 0 Then Exit Do pos -= 1 Continue Do End If 'calculate current sum sum = 0 For k = 0 To pos sum += availableIncrements(k) * weightCoefficients(k) Next 'found combination If sum = ub And weightCoefficients(pos) > 0 Then wayCount += 1 'printing to screen, remove when expecting many combinations Dim printList As New List(Of Integer) For i = 0 To pos 'which number to print For k = 1 To weightCoefficients(i) 'how many times to print a number printList.Add(availableIncrements(i)) Next Next Console.WriteLine(String.Join(" + ", printList)) 'if we were in the last bucket and we just partitioned the number, 'no need to go down and check all lower coefficients, instead move one column back. If pos = UBound(availableIncrements) Then pos -= 1 Continue Do End If End If If pos < UBound(availableIncrements) Then pos += 1 weightCoefficients(pos) = -1 'prepare to charge End If 'this is something to keep you busy (so you know it's not hanging) 'uncomment for long enumerations 'If wayCount Mod 100000 = 0 Then Console.WriteLine(wayCount)LoopConsole.WriteLine("count=" & wayCount) 这篇关于项目Euler 76-列出给定数量的所有分区的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！