今天看到了一個(gè)比較有意思的算法題，其實(shí)更有意思的是其解法，讓人頓時(shí)有一種耳目一新的感覺，愛不釋手，拿來分享一下。

題目：假設(shè)生成26個(gè)非負(fù)隨即數(shù)，要求其和是301，求程序生成此列數(shù)字

哈哈，元芳，你如何看？

解法一： 關(guān)于此種算法原理，我們可以假想是一根長(zhǎng)301單位的繩子，然后隨即在其上面截25個(gè)點(diǎn)，于是得到26根子繩，這26根子繩之和恰好就是繩子總長(zhǎng)301。

于是，我們可以：

初始化27的數(shù)組

該數(shù)組0位和26位分別為0和301，其他位置填充0到301之間的隨即數(shù)字

對(duì)數(shù)組排序

數(shù)組相鄰數(shù)字相減，所得的26個(gè)差值即為所求數(shù)列。

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();   
   }         
   } 

解決方案二，這種方案利用了非負(fù)這個(gè)不顯眼的條件，思路非常簡(jiǎn)單，就是將1隨即加到一個(gè)26位數(shù)組中，隨即301次，有點(diǎn)劍走偏鋒，另辟蹊徑，讓人耳目一新阿，有謀有啊有謀有！

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();   
      }   
  } 

多謝@另一個(gè)石頭，@八字和尚，@firstrose等等朋友的質(zhì)疑指證，我測(cè)試了一下，如果將數(shù)字增大，i <3000001，確實(shí)得出來的數(shù)字比較的平均，看來我扔了我這塊石頭確實(shí)引來了不少玉啊，嘿嘿，我仔細(xì)的看了下，第二種算法確實(shí)隱藏著缺陷，此方法的意圖是通過利用概率的隨機(jī)性，等于將301個(gè)1按照等概率分布在26個(gè)位置，random函數(shù)均勻拋出數(shù)字，所以其分布應(yīng)該大概按照301/26分布，在301次的時(shí)候其實(shí)已經(jīng)有表現(xiàn)了，當(dāng)數(shù)字變大此種現(xiàn)象更加明顯。

不過由于此種算法確實(shí)太過奇妙，所以我覺得用于小數(shù)字的隨機(jī)還是可以的，元芳，你怎么看呢？  

第三種解法：下象棋的朋友都知道一種常見的開局方式，兵三進(jìn)一或者兵七進(jìn)一，即仙人指路局，此種著法能進(jìn)能退，能起馬能飛炮，算起來中規(guī)中矩，其實(shí)也不乏一種方法，于是我也中規(guī)中矩的按照正常的思路又寫了一種所謂的“中規(guī)中矩”的算法：

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出來一個(gè)數(shù)字，然后301減去此數(shù)字得出目前需要拋出數(shù)字的總和，然后再從0-目前總合中再random出來一個(gè)數(shù)字。。。如此知道第26個(gè)數(shù)字，不再random，直接賦值為***剩下的目前數(shù)字之和，測(cè)試后發(fā)現(xiàn)這個(gè)方法***會(huì)拋出大串的0，也在意料之中，因?yàn)殡S著random次數(shù)的增加，random的震蕩范圍越來越小，最終會(huì)在大于0附近徘徊。

鑒于此種現(xiàn)象，稍微改進(jìn)了一下方案，控制了一下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);//控制震蕩范圍在動(dòng)態(tà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();   
       }   
   } 

但是覺得這樣并不好，控制了震蕩范圍，就等于間接控制了隨機(jī)數(shù)字的出現(xiàn)概率，算來算去還是***種方法和第二種方法好，元芳，你認(rèn)為呢？

原文鏈接：http://www.cnblogs.com/songsz1/archive/2012/10/31/2748098.html