当前位置：首页 > 资讯 > 技术文档

C#算法之大牛生小牛的问题高效解决方法

时间：2021-12-06 09:53 编辑：来源：阅读：
扫一扫，手机访问

摘要：C#算法之大牛生小牛的问题高效解决方法

[b]问题：[/b] 　　一只刚出生的小牛，4年后生一只小牛，以后每年生一只。现有一只刚出生的小牛，问20年后共有牛多少只？ [b]思路：[/b] 　　这种子生孙，孙生子，子子孙孙的问题，循环里面还有循环的嵌套循环，一看就知道是第归问题。于是乎,第一个版本出现：

public long Compute1(uint years)
{
  //初始化为1头牛
  long count = 1;
  if (years <= 3)
  {
    return count;
  }
  int i = 4;
  while (i <= years)
  {
    int subYears = i - 3;
    count += Compute1((uint)(subYears));
    i++;
  }
  return (long)count;
}

　　可是这种循环在循环的做法可要把cpu老兄累坏了，你不信输入一个100年测试一下上面的方法，我等了半天，都没结果，改进一下吧，老牛（牛魔王）和小牛（红孩儿，奶奶的串种了），具有相同的生育能力，他们的生育曲线是一样的，所以小牛可以复用老牛的生育经验亚，这样就解决了重复计算一只牛第n年的时候一共生多少只的问题了，当年龄比较大的时候，明显大大降低cpu的运算次数，下面是基于这种思路的算法

Hashtable table = new Hashtable();
public long Compute(uint years)
{
  //初始化为1头牛
  long count = 1;
  if (years <= 3)
  {
    return count;
  }
  int i = 4;
  while (i <= years)
  {
    int subYears = i - 3;
    if (table.ContainsKey(subYears))
    {
      count = (long)table[subYears];
    }
    else
    {
      count += Compute((uint)(subYears));
    }
    if (!table.ContainsKey(subYears))
    {
      table.Add(subYears, count);
    }
    i++;
  }
  return (long)count;
}

[b]用测试程序测试一下上面的推论吧，结果如下:[/b] 1）当输入years比较小的时候，第一种方法耗时短，但两者的时间基本在一个数量级上 2）当输入years比较大的时候，比如40以上的，第二种算法比第一种性能比在100以上，而且输入years越高，性能比越悬殊。 [b]测试结果截图： [/b] 20年 [img]http://files.jb51.net/file_images/article/201606/2016061609491722.jpg[/img] 50年 [img]http://files.jb51.net/file_images/article/201606/2016061609491723.jpg[/img] 源程序以及测试程序：[url=http://xiazai.jb51.net/201606/yuanma/HowMoneyCows(jb51.net).rar]http://xiazai.jb51.net/201606/yuanma/HowMoneyCows(jb51.net).rar[/url] 以上就是本文的全部内容，希望能给大家一个参考，也希望大家多多支持编程素材网。

全部评论(0)

上一篇：DevExpress之ChartControl实现柱状图演示实例
下一篇：C#编程获取客户端计算机硬件及系统信息功能示例

资讯排行榜
更多>>