Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
Help us understand the problem. What is going on with this article?

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

More than 5 years have passed since last update.

問題設定

正の整数 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 個となります。
つまり、全員に均等に分けたあとにその余りを後ろからひとつずつ配っているのと同じことです。

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away