分享

[当算法遇上数学]元芳,你怎么能随即生成m个数,让其和等于n?(加强版)

 Fredanf 2012-10-31

[当算法遇上数学]元芳,你怎么能随即生成m个数,让其和等于n?(加强版)

今天看到了一个比较有意思的算法题,其实更有意思的是其解法,让人顿时有一种耳目一新的感觉,爱不释手,拿来分享一下。

题目:假设生成26个非负随即数,要求其和是301,求程序生成此列数字

哈哈,元芳,你如何看?

解法一: 关于此种算法原理,我们可以假想是一根长301单位的绳子,然后随即在其上面截25个点,于是得到26根子绳,这26根子绳之和恰好就是绳子总长301。

           于是,我们可以:

  1. 初始化27的数组
  2. 该数组0位和26位分别为0和301,其他位置填充0到301之间的随即数字
  3. 对数组排序
  4. 数组相邻数字相减,所得的26个差值即为所求数列。
class Random301
   {
       static void Main(string[] args)
       {
       int[] arryTemp=new int[27];
       int[] arryRandom = new int[26];
       //get random number,from 0 to 301
       Random ran=new Random((int)DateTime.Now.Ticks);
       arryTemp[0] = 0;
       arryTemp[26] = 301;
       for (int i = 1; i < 26; i++)
       {
           arryTemp[i] = ran.Next(0,301);
       }
        
       //sort the arry
       int temp;
       for (int m = arryTemp.Length-1; m > 0; m--) {
           for (int n = 0; n < m;n++ ) {
               if (arryTemp[m] < arryTemp[n]) {
                    temp=arryTemp[n];
                    arryTemp[n] = arryTemp[m];
                    arryTemp[m] = temp;
               }
           }
       }
       //get the lastest random arry
       for (int j = 0; j < arryRandom.Length;j++) {
           arryRandom[j] = arryTemp[j + 1] - arryTemp[j];
       }
       
       //check the arry
       int sum = 0;
       for (int k = 0; k < arryRandom.Length; k++) {
           sum = sum + arryRandom[k];
       }
       Console.WriteLine(sum);
       Console.ReadKey();
   }     
   }

 解决方案二,这种方案利用了非负这个不显眼的条件,思路非常简单,就是将1随即加到一个26位数组中,随即301次,有点剑走偏锋,另辟蹊径,让人耳目一新阿,有谋有啊有谋有!

class Radom301Arry
  {
      static void Main(string[] args) {
          int[] arryRandom = new int[26];
          Random ran = new Random();
          //add 1 301times into the arry
          for (int i = 0; i <301;i++ ) {
              arryRandom[ran.Next(0, 26)]++;
          }
          //chenck the arry
          int sum = 0;
          for (int j = 0; j < arryRandom.Length; j++) {
              Console.WriteLine(arryRandom[j]);
              sum = sum + arryRandom[j];
          }
          Console.WriteLine("sum:"+sum);
          Console.ReadKey();
      }
  }

 多谢@另一个石头,@八字和尚,@firstrose等等朋友的质疑指证,我测试了一下,如果将数字增大,i <3000001,确实得出来的数字比较的平均,看来我扔了我这块石头确实引来了不少玉啊,嘿嘿,我仔细的看了下,第二种算法确实隐藏着缺陷,此方法的意图是通过利用概率的随机性,等于将301个1按照等概率分布在26个位置,random函数均匀抛出数字,所以其分布应该大概按照301/26分布,在301次的时候其实已经有表现了,当数字变大此种现象更加明显。

不过由于此种算法确实太过奇妙,所以我觉得用于小数字的随机还是可以的,元芳,你怎么看呢?  

 

第三种解法:下象棋的朋友都知道一种常见的开局方式,兵三进一或者兵七进一,即仙人指路局,此种着法能进能退,能起马能飞炮,算起来中规中矩,其实也不乏一种方法,于是我也中规中矩的按照正常的思路又写了一种所谓的“中规中矩”的算法:

class List301
   {
       static void Main(string[] args) {
           //store the 26 random numbers
           List<int> templist = new List<int>();
           Random ran = new Random((int)DateTime.Now.Ticks);
           int temp = 0;
           int total = 301;
           for (int i = 0; i < 26; i++)
           {
               if (25 != i)
                   temp = ran.Next(0, total);
               else
                   temp = total;
               total = total - temp;
               templist.Add(temp);
           
             int sum = 0;
           for (int m = 0; m <templist.Count; m++)
           {
               sum = sum + templist[m];
               Console.WriteLine(m+":"+templist[m]);
           }
           Console.WriteLine(sum);
           Console.ReadKey();
       }
   }

 这种方法就是先从0-301之间random出来一个数字,然后301减去此数字得出目前需要抛出数字的总和,然后再从0-目前总合中再random出来一个数字。。。如此知道第26个数字,不再random,直接赋值为最后剩下的目前数字之和,测试后发现这个方法最后会抛出大串的0,也在意料之中,因为随着random次数的增加,random的震荡范围越来越小,最终会在大于0附近徘徊。

鉴于此种现象,稍微改进了一下方案,控制了一下random的震荡范围:

class List301
   {
       static void Main(string[] args) {
           //store the 26 random numbers
           List<int> templist = new List<int>();
           Random ran = new Random((int)DateTime.Now.Ticks);
           int temp = 0;
           int total = 301;
           for (int i = 0; i < 26; i++)
           {
               if (25 != i)
               {
                   int avg = total / (26 - i);//控制震荡范围在动态平均值附近
                   temp = ran.Next(0, avg * 2);
                   total = total - temp;
               }
               else
                   temp = total;
               templist.Add(temp);
           }
 
           //check
           int sum = 0;
           for (int m = 0; m <templist.Count; m++)
           {
               sum = sum + templist[m];
               Console.WriteLine(m+":"+templist[m]);
           }           
           Console.WriteLine(sum);
           Console.ReadKey();
       }
   }

 但是觉得这样并不好,控制了震荡范围,就等于间接控制了随机数字的出现概率,算来算去还是第一种方法和第二种方法好,元芳,你认为呢?

 

第四种方案,感谢@追杀同学的回复中提到了这种方法,因为着急下班,还没仔细看,回家看看去,哈哈:

class Program {
    static void Main(string[] args) {
        var nums = Test(26, 301);
        Console.WriteLine(string.Join(",", nums));
        Console.WriteLine("Sum:{0}", nums.Sum());
    }
  
    static IEnumerable<int> Test(int count, int sum) {
        List<int> numSeq = new List<int>(count);
        Random rand = new Random();
        for (var i = 0; i < count - 1; i++) {
            var num = rand.Next(0, sum + 1);
            numSeq.Add(num);
        }
        numSeq.Add(sum);
        numSeq.Sort();
        List<int> numResult = new List<int>(count);
        for (var i = 0; i < count; i++) {
            if (i == 0) {
                numResult.Add(numSeq[i]);
            } else {
                numResult.Add(numSeq[i] - numSeq[i - 1]);
            }
        }
        return numResult;
    }
}

    本站是提供个人知识管理的网络存储空间,所有内容均由用户发布,不代表本站观点。请注意甄别内容中的联系方式、诱导购买等信息,谨防诈骗。如发现有害或侵权内容,请点击一键举报。
    转藏 分享 献花(0

    0条评论

    发表

    请遵守用户 评论公约

    类似文章 更多