数をだいたい等しく分配するアルゴリズムの仕組みがよくわからない

ある数が与えられたとき、それをいくつかの塊にだいたい等しく分配するコードとして以下を見かけました。

たしかに上手く動くのですが、なぜこれで動作するのかが理解できないでいます。
どなたか解説していただけないでしょうか。

例: 100個のお菓子を7人に分配する。

python
1total = 100
2num_splits = 7
3
4chunks = []
5for i in range(num_splits):
6    n = (i + 1) * total // num_splits - i * total // num_splits
7    chunks.append(n)
8
9print(chunks, sum(chunks))  # [14, 14, 14, 15, 14, 14, 15] 100

行動規範の内容に同意します

回答2件

ベストアンサー

全部足してみれば、合計が一致することはわかるかと思います。

i = 0: 1 * 100 // 7 - 0 * 100 // 7
i = 1: 2 * 100 // 7 - 1 * 100 // 7
i = 2: 3 * 100 // 7 - 2 * 100 // 7
i = 3: 4 * 100 // 7 - 3 * 100 // 7
i = 4: 5 * 100 // 7 - 4 * 100 // 7
i = 5: 6 * 100 // 7 - 5 * 100 // 7
i = 6: 7 * 100 // 7 - 6 * 100 // 7

足し合わせると、上下の式で消し合う部分があるので、7 * 100 // 7 - 0 * 100 // 7だけが残って、これはもちろんきれいに割り切れて100となります。

投稿2019/07/10 11:42

maisumakun

総合スコア145183

tiitoi

2019/07/10 11:59

ご回答ありがとうございます。分割した後の和が一致することは maisumakun さんの説明で理解できました。各値が質問の例でいうと、14または15といったようにうまい具合？に分割できているのはどう理解したらいいでしょうか？

maisumakun

2019/07/10 12:13

割り算が小数までできるとすれば、すべて同じ値になることはわかるかと思います。実際には切り捨てが入りますが、切り捨てで変化する範囲は本来の値～1引いた値までなので、式の結果は小数まで計算した値とプラスマイナス1の範囲に収まります。

tiitoi

2019/07/10 15:53

疑問点について理解できました。補足していただきありがとうございます。

行動規範の内容に同意します

maisumakunさんの回答とコメントですでに理解されたかもしれませんが、コードを書き換えてわかりやすくしてみます。

とりあえず床関数で書き直します。単に書き換えるとtotal / num_splitsが2回出てくるので、変数Nとしておきます。

python
1import math
2
3total = 100
4num_splits = 7
5N = total / num_splits
6
7chunks = []
8for i in range(num_splits):
9    n = math.floor((i + 1) * N) -\
10        math.floor(i * N)
11    chunks.append(n)
12
13print(chunks, sum(chunks))
14

後ろの床関数を通った結果は整数なので、まるごと前の床関数の中に入れます（わかりやすいように）。ついでに元々あった(i + 1) * Nを展開。

python
1import math
2
3total = 100
4num_splits = 7
5N = total / num_splits
6
7chunks = []
8for i in range(num_splits):
9    n = math.floor(i * N + N - math.floor(i * N))
10    chunks.append(n)
11
12print(chunks, sum(chunks))
13

i * N - math.floor(i * N)はi * Nの小数部なので、そのへんを加味して整理できます。

python
1import math
2
3total = 100
4num_splits = 7
5N = total / num_splits
6
7chunks = []
8for i in range(num_splits):
9    iN = i * N
10    iN_frac = iN - math.floor(iN)
11    n = math.floor(N + iN_frac)
12    chunks.append(n)
13
14print(chunks, sum(chunks))
15