今天看到了一个比较有意思的算法题,其实更有意思的是其解法,让人顿时有一种耳目一新的感觉,爱不释手,拿来分享一下。
题目:假设生成26个非负随即数,要求其和是301,求程序生成此列数字
哈哈,元芳,你如何看?
解法一: 关于此种算法原理,我们可以假想是一根长301单位的绳子,然后随即在其上面截25个点,于是得到26根子绳,这26根子绳之和恰好就是绳子总长301。
于是,我们可以:
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; } } |
联系客服