求和组合中的无限循环

Question

我有以下代码来搜索适合给定总和的组合。但问题是低小数。

就像，当我尝试用 3.15 和 0.40 拟合总和 11.90 时，程序开始无限循环。当我尝试使用 3.15 和 2.45 时，我收到以下正确结果 (3.15 | 3.15 | 3.15 | 2.45)。

public static void findNumbers(List<double> ar, double sum, List<List<double>> res, List<double> r, int i)
{   
    // If current sum becomes negative 
    if (sum < 0)
    {
        return;
    }
    // if we get exact answer 
    if (sum < 2)
    {
        res.Add(r);
        return;
    }

    // Recur for all remaining elements that 
    // have value smaller than sum. 

    while (i < ar.Count() && sum - ar[i] >= 0)
    {
        // Till every element in the array starting 
        // from i which can contribute to the sum 
        r.Add(ar[i]); // Add them to list
        // recur for next numbers                 
        findNumbers(ar, sum - ar[i], res, r, i);
        i++;

        r.RemoveAt(r.Count() - 1);
    }
}

我会知道如何去掉这个循环。

Answer 1

恕我直言，您的代码有 2 个可讨论的要点

if (sum < 2)

你不应该寻找一个确切的总和吗？例如sum == 0 或更好 Math.Abs(sum) < tolerance (like 0.0005) 因为你使用的是双打。

res.Add(r);

使用 res.Add(r) 您将添加对 r 的引用。但是然后 r.RemoveAt(r.Count() - 1);您在 res 列表中引用的 r 也会受到影响。所以我建议将 r 的副本添加到 res:

res.Add(r.GetRange(0, r.Count));

编辑：

在 https://github.com/hcetinkaya/Combinations.git

查看工作示例

您的样本总和 = 11.90，数组为 3.15 和 0.4，公差为 2.0 => 9.90 <= 总和 <= 11.90，产生以下结果：

(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 0,4, 3,15, 3,15, 3,15)
(0,4, 0,4, 0,4, 0,4, 3,15, 3,15, 3,15)
(0,4, 0,4, 0,4, 3,15, 3,15, 3,15)
(0,4, 0,4, 3,15, 3,15, 3,15)

求和组合中的无限循环

Infinity loop in sum combination

combinations

loops

sum

infinite-loop

c#-2.0