一道有趣智力算法的讨论？

Question

关于有效合理分配算法，题目如下：
第1个人有a1个苹果，第2个人有a2个苹果，第3个人有a3个苹果……第n个人有an个苹果。现有
M个苹果分给n个人，如何分配大到最大平均分配法？

Answer 1

第1个人分M(a1/a1+a2+...+an)个苹果，第2个人分M(a2/a1+a2+...+an)个苹果，第3个人分分M(a３/a1+a2+...+an)个苹果……第n个人分M(an/a1+a2+...+an)个苹果。

Answer 2

To:liu_kewei(可为)
此种方法分配后结果更会拉大差距，我们假设从第1个人到第n个人拥有的苹果数a1……an是从小到大排序的，那么此时第n个人拥有的苹果数更加增多，拉大每个人拥有苹果数的距离。所谓的达到最大平均分配数的意思是这n个人分配这M 个苹果之后所拥有的苹果数尽量一样多。

Answer 3

看题目因该是M/N，是每个人的初始拥有数，M%N是因该再次分的，给 1，2，...每个一个分
直到该余数平分完你这个条件 
第1个人有a1个苹果，第2个人有a2个苹果，第3个人有a3个苹果……第n个人有an个苹果
干吗的

Answer 4

第N个人分得:
(M+ a1+a2+...+an)/n +(n-1)(a1+a2+...+an)/n^2  - a1

Answer 5

To:sss_624
第1个人有a1个苹果，第2个人有a2个苹果，第3个人有a3个苹果……第n个人有an个苹果是开始他们所拥有的苹果数，不参与以后这M个苹果的分配

Answer 6

总算弄明白了题意。我来翻译一下，大家看一看对不对。假设有3个人 A、B、C
A有1个苹果、B有2个苹果、C有3个苹果现在有 m=3 个苹果，分配给他们，要达到每个人的苹果数目都很接近那么
A：1 + 2 = 3 B: 2 + 1 = 3C: 3 + 0 = 3 这样分配后，每个人就都有3个苹果了。

Answer 7

先求中苹果数 allCount =  m + a1 + a2 + ... + am然后求平均数 这里应该取整  int(allCount / m)然后用平均数  int(allCount / m) - a(m)就是每一个人分得的苹果数了

Answer 8

TO:Cannot(I will)
你的解题算法很有意思,能向大家解释说明一下吗?

Answer 9

TO:jyk(喜欢编程。和气生财。共同提高。共同进步) 
题目的意思就是那样.但你的这种分配算法能否达到最大平均?

Answer 10

这个应当是从最小的分起，直到所有苹果分完吧，也就是找一个数 s 使得sigma( G(s - a[i]) ) = M, i = 1 ~ N其中 G(x) 函数 := (x < 0) ? 0 : x

Answer 11

我的思路:
    设第k个数为a(k),
    满足以下条件: 使得表达式[a(k)-a(k-1)]+[a(k)-a(k-2)]+......[a(k)-a(k-j)]最接近M值,
并使j最大的分配方法.

Answer 12

public class Test
{
  public static void Main(string [] args)
  {
    int n = 5, m = 7, p = 0;
    int [] a = new int []{1,2,4,7,9};
    int m1 = 0, m2 = 0;
    int s = 0;
    for(p = 0; p < n - 1; p++)
    {
      m2 = (p+1) * a[p+1] - s - a[p];
      if(m2 > m) break;
      m1 = m2; s += a[p];
    }
    int r =  (m - m1) % p;
    for(int i = 0; i < n; i++)
    {
      int g = (i<p)?((a[p] - a[i])+(m-m1)/p+((i<r)?1:0)):0;
      System.Console.WriteLine(
        "手里有[{0}]个苹果的人分得[{1}]个, 共[{2}]个。", 
        a[i], g, a[i] + g);
    }
  }
}

Answer 13

上面代码 n 是总人数， m 是要分得苹果数，a 是开始时每个人手里的苹果数例子输出这样：手里有[1]个苹果的人分得[4]个, 共[5]个。
手里有[2]个苹果的人分得[3]个, 共[5]个。
手里有[4]个苹果的人分得[0]个, 共[4]个。
手里有[7]个苹果的人分得[0]个, 共[7]个。
手里有[9]个苹果的人分得[0]个, 共[9]个。

Answer 14

注意上面代码 a 数组要默认从小到大排序(不失一般性)如果一开始是乱的，可以调一下 Array.Sort 方法

Answer 15

tiaoci(我挑刺，我快乐) :
按照你这样,7个苹果分给他们,为什么不这样分,更大:手里有[1]个苹果的人分得[3]个, 共[4]个。
手里有[2]个苹果的人分得[2]个, 共[4]个。
手里有[4]个苹果的人分得[0]个, 共[4]个。
手里有[7]个苹果的人分得[0]个, 共[7]个。
手里有[9]个苹果的人分得[0]个, 共[9]个。
手里有[1]个苹果的人分得[0]个, 共[1]个。
手里有[2]个苹果的人分得[0]个, 共[2]个。
手里有[4]个苹果的人分得[5]个, 共[9]个。
手里有[7]个苹果的人分得[2]个, 共[9]个。
手里有[9]个苹果的人分得[0]个, 共[9]个。

Answer 16

to GSXiaoXiao, 这样 9 和 1 之间的贫富差距不是更大了吗，不均匀了，

Answer 17

to GSXiaoXiao, 这样 9 和 1 之间的贫富差距不是更大了吗，不均匀了，

Answer 18

先取a1~aN的平均值ai，然后分配给Min（an）〈最少的人〉ai-an个苹果。然后在取平均值再分配，直到M〈=0为止。
       int a1， a2...........an
         while(m>0)
          {
             int a_avg = avg(a1..an);
             min(a1...an);
               M = M - a_avg+min(a1..an);
               min(a1..an) = a_avg;
           }
          int avg(.....)
           {
               return (a1+a2+.....+an)/n;
           }
          int min(.....)  用排序的办法找出最小的值！

Answer 19

public class Test
  {
    public static void Main(string [] args)
    {
      int n = 5, m = 30, p = 0;
      int [] a = new int []{1,2,4,7,9};
      int m1 = 0, m2 = 0;
      int s = 0;
      while(p < n - 1)
      {
        m2 = (p+1) * a[p+1] - s - a[p];
        if(m2 > m) break;
        m1 = m2; s += a[p++];
      }
      int q = (p + 1 > n) ? p : p + 1;
      int r =  (m - m1) % q;
      for(int i = 0; i < n; i++)
      {
        int g=(i<q)?((a[p]-a[i])+(m-m1)/q+((i<r)?1:0)):0;
        System.Console.WriteLine(
          "手里有[{0}]个苹果的人分得[{1}]个, 共[{2}]个。",
          a[i], g, a[i] + g);
      }
    }
  }

Answer 20

好了，上面应当没有错了，看看谁还能找到错误to GSXiaoXiao，我想楼主的意思是 "最平均" 吧 :)希望没有理解错 :P

Answer 21

for i= n to 2
    p=0
    do while m>=0
        j=i
        m=m-(a(j)-a(j-p-1))
        p=p+1
    loop
    b(i,0)=j
    b(i,1)=p
next ip 最大的即为人数最多的.j为从第j个数往前分.

Answer 22

我的是这样：1、averge = (M+a1+a2+......+an)/n;//算出可能出现的最大平均2、写个循环找出这n个人中谁的初始苹果数小于average，并给个变量num累加这些人的总苹果数和变量count累计有多少人3、把M个苹果分给这些人求最大平均数max=(num + M)/count

Answer 23

TO :Sunnydavid1(不能没有你):
我是这样解的:
M个苹果中,设分给第i个人的为Xi,X1+X2+X....Xn=M
这样每个人手上有的苹果分别为:
ai+xi
要大家尽可能有相同的苹果,应该使N个人的方差最小,即:
设  (a1+a2+....an+M)/n =AVG;
要使:
  (a1+x1-AVG)^2 + (a2+x2-AVG)^2 + .... +(an+xn-AVG)^2
最小.
因为X1+X2+....XN=M
可求出上面那个式子最小时候的X1,X2,....Xn
就是上面我说的那么多,
(如果没解错的话,:))

Answer 24

TO:cannot(I will)
你的理解没错，正是此意。问题在于如何求Xi,还是回到题如何最大平均分配的问题？

Answer 25

假设a1=1,a2=2,a3=4,a4=7,a5=9,M=7
答案一：
a1手里有[1]个苹果的人分得[4]个, 共[5]个。
a2手里有[2]个苹果的人分得[3]个, 共[5]个。
a3手里有[4]个苹果的人分得[0]个, 共[4]个。
a4手里有[7]个苹果的人分得[0]个, 共[7]个。
a5手里有[9]个苹果的人分得[0]个, 共[9]个。
答案二：
a1手里有[1]个苹果的人分得[0]个, 共[1]个。
a2手里有[2]个苹果的人分得[0]个, 共[2]个。
a3手里有[4]个苹果的人分得[5]个, 共[9]个。
a4手里有[7]个苹果的人分得[2]个, 共[9]个。
a5手里有[9]个苹果的人分得[0]个, 共[9]个。请问Sunnydavid1(不能没有你)，哪个答案正确，还是另有答案。

Answer 26

要使:
  (a1+x1-AVG)^2 + (a2+x2-AVG)^2 + .... +(an+xn-AVG)^2
最小.
因为X1+X2+....XN=M
可求出上面那个式子最小时候的X1,X2,....Xn这个用数学方法求下就可以了
设f(X1,X2,...Xn,t)=(a1+x1-AVG)^2 + (a2+x2-AVG)^2 + .... +(an+xn-AVG)^2 + t*(X1+X2+....XN-M)
f分别对x1,x2...xn,t求偏导数,
由于求最大值的时候上述导数均为0
解方程就可以求出最大值时候的x1,x2,x3,....xn:)

Answer 27

TO:stoneallen(我不想说，我很亲切)
按照你提供的答案和依据题意思,答案1是对的

Answer 28

TO:cannot(I will) 
思路慢慢趋向正确了,能用自然算法描述一下吗?最好能证明.

Answer 29

TO:Sunnydavid1(不能没有你)
这样的话最大平均数是唯一的，但是分法可就不是唯一的哦，比如这样也对吧
答案三：
a1手里有[1]个苹果的人分得[3]个, 共[4]个。
a2手里有[2]个苹果的人分得[3]个, 共[5]个。
a3手里有[4]个苹果的人分得[1]个, 共[5]个。
a4手里有[7]个苹果的人分得[0]个, 共[7]个。
a5手里有[9]个苹果的人分得[0]个, 共[9]个。

Answer 30

那这样的话，我的算法也没错啊
1、averge = (M+a1+a2+......+an)/n;//算出可能出现的最大平均2、写个循环找出这n个人中谁的初始苹果数小于average，并给个变量num累加这些人的总苹果数和变量count累计有多少人3、把M个苹果分给这些人求最大平均数max=(num + M)/count我求的就是最大平均数啊