3

我正在尝试将整数 N <= 12（即工作日数）除以 12 个月，这样如果我将 12 个月分为 1、2、3、4 或 6 个月的时间段，则天数在这些时期应尽可能相等。

例如：

如果 N = 6，则数组应如下所示：

1 0 1 0 1 0 1 0 1 0 1 0或者0 1 0 1 0 1 0 1 0 1 0

N = 4

1 0 0 1 0 0 1 0 0 1 0 0

N = 3

1 0 0 1 0 0 1 0 0 0 0 0

N = 2

1 0 0 0 0 0 1 0 0 0 0 0

编辑：

我所说的“尽可能相等”的意思是，当我将此数组划分为多个时段时，这些时段中的工作日数的差异不应超过 1。

4

5 回答 5

3

编辑——针对一般情况进行了改进，假设您只要求 1,2,3,4,6 有问题！

你想要的是通过给定的周期调制 N 。（我的术语可能完全错误：D 可能应该再次阅读我的高中物理！）

来点红宝石吧。。

def spread_it(n)
  d = 12.0 / n
  (0..11).map do |index|
    (12.0 - (index % d) > 11.0) ? '1' : '0'
  end
end

(1..12).each do |n|
  puts "N=#{n} - #{spread_it n}"
end

输出是：

N=1 - ["1", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0"]
N=2 - ["1", "0", "0", "0", "0", "0", "1", "0", "0", "0", "0", "0"]
N=3 - ["1", "0", "0", "0", "1", "0", "0", "0", "1", "0", "0", "0"]
N=4 - ["1", "0", "0", "1", "0", "0", "1", "0", "0", "1", "0", "0"]
N=5 - ["1", "0", "0", "1", "0", "1", "0", "0", "1", "0", "1", "0"]
N=6 - ["1", "0", "1", "0", "1", "0", "1", "0", "1", "0", "1", "0"]
N=7 - ["1", "0", "1", "0", "1", "0", "1", "1", "0", "1", "0", "1"]
N=8 - ["1", "0", "1", "1", "0", "1", "1", "0", "1", "1", "0", "1"]
N=9 - ["1", "0", "1", "1", "1", "0", "1", "1", "1", "0", "1", "1"]
N=10 - ["1", "0", "1", "1", "1", "1", "1", "0", "1", "1", "1", "1"]
N=11 - ["1", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"]
N=12 - ["1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1"]

现在好点了？:)

于 2012-10-22T20:35:57.173 回答
3

每个区间的平均长度是12/N（在数学术语中，不是整数除法）。要强制执行“一比一”规则，唯一的选项是ceil(12/N)("long") 和floor(12/N)("short")。每个所需的数量是12 % N和N - (12 % N)。即在Python中

def allocate_intervals(N):
    short = 12 // N # integer division
    long = short + 1

    # lists of [1,0, ..., 0] lists
    short_intervals = [[1] + [0] * (short - 1)] * (N - (12 % N))
    long_intervals =  [[1] + [0] * (long - 1)] * (12 % N)

    # concatenate to get [1, 0, ..., 1, 0, ...]
    return sum(short_intervals + long_intervals, [])

上面的代码创建了每个间隔的适当数量，然后连接起来。

（此方法完全通用，可以将12s 替换为任何正整数。）

在 C/C++ 等中对上述内容的实现略有不同。

// array is [0, 0, ..., 0] with 12 elements. It is modified in-place.
void allocate_intervals(int N, int array[12]) {
   // length of each interval
   int len_short = 12 / N, len_long = len_short + 1;

   // number of each interval
   int num_long = 12 % N, num_short = N - num_long;

   int step = 0;
   for (int i = 0; i < num_long; i++) {
      array[step] = 1;
      step += len_long;
   }
   for (int i = 0; i < num_short; i++) {
      array[step] = 1;
      step += len_short;
   }
}
于 2012-10-22T20:38:04.593 回答
0

如果你所拥有的只是一个 12 个元素的数组，那么你可以使用暴力递归回溯：

Arr = [ ] // holds best solution
tempArr = [ ] // temproray

function rec( i, n )
     if n == 0
        return
     if i == Arr.length
        checkBest(Arr, tempArr) // copies tempArr to Arr if it is better solution
        return
     tempArr[i] = 1
     rec(i + 1, n - 1)
     tempArr[i] = 0
     rec(i + 1, n)

用法：rec(0, 1234)

于 2012-10-22T20:37:50.563 回答
0

这个想法是int n = 12 / N给出期间。

更新了代码。 这适用于从 1 到 12 的所有情况。超过 6 的情况使用对称性来避免连续的 1

public int[] Splitter(int N, int max) // max = 12 for above problem.
{
    if (max < 1 || N < 1 || N > max)
    {
        throw new ArgumentException();
    }

    if (N != max && N > max / 2)
    {
        return Splitter(max - N, max).Select(s => s == 1 ? 0 : 1).ToArray();
    }

    int[] a = new int[max];
    int n = max / N;
    int count = 0;

    for (int i = 0; i < max; i++)
    {
        if (i % n == 0 && count < N)
        {
            a[i] = 1;
            count++;
        }
        else
        {
            a[i] = 0;
        }
    }

    return a;
}

旧代码：

int n = 12 / N;
for(int i = 0; i < 12; i++)
{
  if (i % n == 0)
  {
    a[i] = 1;
  }
  else
  {
    a[i] = 0;
  }
}
于 2012-10-22T20:29:47.857 回答
0 
def alloc(N, length=12):

    result = zeros(length) # preinitialise an array with zeros

    short_gap = length // N # where // is integer division
    long_gap = short_gap + 1

    change_over_index = (N - (length % N)) * (length // N)

    result[0:change_over_index:short_gap] = 1
    result[change_over_index:length:long_gap] = 1
    # above two lines of code is called slicing. arr[x:y:z] = 1 means:
    # set all indexes from x to y by increments of z to be 1... eg.
    # for (int i = x; i < y; i += z) arr[i] = 1;

    return result
于 2012-10-22T22:34:20.687 回答