search
LoginSignup
41
Help us understand the problem. What are the problem?

More than 5 years have passed since last update.

posted at

整数をできるだけ均等になるように n分割

問題設定

正の整数 xn があるとします。xn等分してください。
xnで割り切れるとは限りませんが、できるだけ均等にn分割したいです。
例えば、x=13, n=4 に対して (つまり13の4等分) は [3, 3, 3, 4] で、
割り切れる場合には、例えば x=15, n=3 に対してはもちろん [5, 5, 5] となります。
どうやったらこのn等分が求まるでしょうか?

結論

// を整数除算 (小数点以下を切り捨てる除算) とします。
求めたい等分リストlは、[(x+0)//n, (x+1)//n, ..., (x+(n-1))//n] です。
Python3で実装するなら、

x = 13
n = 4
l = [(x + i) // n for i in range(n)]

です。

議論とか

まずはじめに、この方法は有名な事実らしいです。
私が知らないだけで常識なのかもしれません。

整数のn分割はわりとよくやる処理なので、たまに書くことがありますが、いつも次のように実装していました:

x = 13
n = 4
# 同じ量を全員に配るとすると、もらえる量は
div = 13 // 4  # 13 // 4 = 3
# 同じ量を全員に配った後のあまりを求める
rem = 13 % 4  # 13 % 4 = 1
# n人中rem人は余りをひとつずつもらえる
l = [div] * (n - rem) + [div+1] * rem

計算効率的にはむしろ後者のほうが良いですが、綺麗じゃないといつも思っていたので、前者の綺麗な実装を見てちょっと感動したためわざわざ記事にしました。

ちなみに:前者の綺麗な実装がなぜ動くか?

xn で割り切れる場合、x+0からx+(n-1)nによる切り捨て除算はすべてx//nと同じ値となり、等分割ができます。

0001.png
xn で割り切れない場合は、その余りを rem とすると、x + (n-rem)n で割り切れます。すると、x+0からx+(n-1)のリストのうち、x+(n-rem)から先はnによる切り捨て除算がすべてx//n + 1となります。 x+(n-rem),...,x+(n-1)のリストの長さはremですから、結局、他の人よりひとつずつ多くもらえるのは後ろから rem 個となります。
つまり、全員に均等に分けたあとにその余りを後ろからひとつずつ配っているのと同じことです。

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
41
Help us understand the problem. What are the problem?