[当算法遇上数学]元芳,你怎么能随即生成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();
}
}

 多谢朋友指正阿,我测试了一下,如果将数字增大,i <3000001,确实得出来的数字比较的平均,元芳,你怎么看?

   

本文链接



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量