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おそらく私の高校の物理学をもう一度読んでください！）

Rubyを持ってください。

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（数学的には、整数除算ではありません）です。1つずつ異なるルールを適用するためのオプションは、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 
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 に答える
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

持っているのが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 に答える