一个“散点均匀分布”问题的求解

在最近的开发过程中遇到一个算法问题,描述如下:

问题:有从左到右依次排列的格子m个,同时有小球n个(m>n),如何将小球放入格子中使得小球分布近似均匀?(每个格子最多放置一个小球)。比如,格子有197个,而小球有74个,如何分配小球?

分析:如果格子数m可以整除小球数n,那么问题很简单,每隔 m/n – 1 个格子放置一个小球即可。如果m无法整除n,那么问题就麻烦一点。比如,在m=197, n=74的情况下,m/n=2.66…,也就是说需要每隔1个或者2个格子放置一个小球。那么,如何确定每一个小球的放置呢?

解法:在与同事进行讨论后发现,可以用四舍五入的方法决定具体每一个小球的位置。还是以m=197, n=74为例:

  1. 74/197=0.37…,因此第1个格子中应该有0.37…个小球,0.37…四舍五入取整为0,所以第一个格子中小球数为0。小球计数变量i=0。
  2. (74/197) * 2 = 0.75…,因此前2个格子中总共应该有0.75…个小球,0.75…四舍五入取整为1,所以第二个格子中小球数为1-i=1。小球计数变量i=1。
  3. (74/197) * x = k,因此前x个格子中总共应该有k个小球。将k四舍五入后减去当前i变量的值,就是第x个格子中小球的数目。在计算完成后需要对变量i进行更新。

Chuan Shao

Read more posts by this author.

Shanghai

Subscribe to Chuan's blog

Get the latest posts delivered right to your inbox.

or subscribe via RSS with Feedly!