将一个数字拆分为多个范围

本文关键字：拆分 范围 数字 一个 | 更新日期: 2023-09-27 18:35:59

我正在尝试将一个数字分成适合预定义范围的较小数字，但我似乎无法正确获得算法。我正在使用 C#。

例

将 20 拆分为三个数字，其中数字必须适合以下范围：1-3、3-10 和 0-15。最终数字可能如下所示：1，5，14 或 2，3，15

另一个示例是将 100 拆分为适合以下范围的四个数字：0-10、0-10、0-40、0-40。结果自然是 10，10，40，40。在相同的范围内拆分 90 可能会导致 5、8、38、39 等。

你能把我踢到正确的方向吗？

（不，这不是家庭作业，这是个人项目）

将一个数字拆分为多个范围

您可以使用递归来做到这一点。

该算法的思想是这样的：

  • 在每次执行中，您将遍历间隔的所有可能数字。

  • 递归调用以生成下一个间隔的下一个数字。

  • 如果在任何时候总和超过所需的值，则回溯。

  • 生成所有数字后，如果总和等于所需的数字，则您有一个可能的组合。

它可以改进，但它是一个解决方案。

以下代码在控制台中打印所有有效序列：

SplitNumber(100, new Interval[]
{
    new Interval { Min = 0, Max = 11 },
    new Interval { Min = 0, Max = 11 },
    new Interval { Min = 0, Max = 40 },
    new Interval { Min = 0, Max = 40 },
});
public static void SplitNumber(int n, Interval[] intervals)
{
    SplitNumber(n, 0, intervals, "");
}
public static void SplitNumber(int n, int k, Interval[] intervals, string s)
{
    if (n < 0) return;
    if (k >= intervals.Length) { if (n == 0) Console.WriteLine(s); }
    else
        for (int i = intervals[k].Min; i <= intervals[k].Max; i++)
            SplitNumber(n - i, k + 1, intervals, string.Format("{0} {1}", s, i));
}

Interval类是这样的：

public class Interval
{
    public int Min { get; set; }
    public int Max { get; set; }
}

下面描述了一种非常有效的方法，假设存储桶具有某种排序。

首先为每个范围选择最小值并将它们相加。

  • 如果总和等于您的数字，则停止。
  • 如果总和大于您的数字，则发出错误。
  • 如果总和小于您的数字，请继续。

接下来，从每个范围中减去最小值，使它们全部归一化为 0 . . n 并从您的数字中减去总和。 这不是绝对必要的，但它有助于解释算法的其余部分。

接下来，对最大范围值进行累积总和。 找到您的新总和所在的存储桶（对于前一个存储桶来说太大，但适合）。 如果未找到任何内容，则发出错误。

然后分配箱，使前面的存储桶达到最大值，并将找到的存储桶设置为适当的值。

这为您提供了一组满足条件的值。

如果您希望值更多地位于范围的"中间"，则从范围的中间值开始。 然后，在所有存储桶中以块为单位添加或减去值，直到达到最大值。 这需要更多的迭代，但它也非常有效。

试试这个：

List<KeyValuePair<int, int>> ranges = new List<KeyValuePair<int, int>>();
ranges.Add(new KeyValuePair<int, int>(1, 3));
ranges.Add(new KeyValuePair<int, int>(1, 3));
ranges.Add(new KeyValuePair<int, int>(1, 100));
int totalSum = ranges.Sum(i => i.Value - i.Key);
double ws = 0.0;
int rIndex = 0;
var rangeAndWeight = ranges.Select(i => new { index = rIndex++, range = i, maxw = (ws += (double)(i.Value - i.Key) / totalSum) }).ToList();
int[] nums = ranges.Select(i => i.Key).ToArray();
int number = 50;
Random r = new Random();
while (nums.Sum() != number)
{
    double rDouble = r.NextDouble();
    var index = rangeAndWeight.SkipWhile(i => i.maxw < rDouble).First().index;
    if (nums[index] < ranges[index].Value)
        nums[index] += 1;
}

nums数组包含您需要的较小数字

您可以编写一个程序，该程序只是尝试对允许范围内的可能数字进行汇总，并希望结果是正确的，如果结果是错误的，则回溯。它非常低效

...
相关文章：