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

2024-09-27 01:11:51

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

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

用测试程序测试一下上面的推论吧，结果如下:

1）当输入years比较小的时候，第一种方法耗时短，但两者的时间基本在一个数量级上
2）当输入years比较大的时候，比如40以上的，第二种算法比第一种性能比在100以上，而且输入years越高，性能比越悬殊。

测试结果截图：

20年

50年

源程序以及测试程序：http://xiazai.jb51.net/201606/yuanma/HowMoneyCows(jb51.net).rar

以上就是本文的全部内容，希望能给大家一个参考，也希望大家多多支持我们。

C#递归算法之快速排序

上两片第归算法学习: 1)递归算法之分而治之策略 2)递归算法之归并排序上一篇学习中介绍了了递归算法在排序中的一个应用:归并排序,在排序算法中还有一种算法用到了递归,那就是快速排序,快速排序也是一种利用了分而治之策略的算法,它由C.A.R发明,它依据中心元素的值,利用一系列递归调用将数据表划分成越来越小的子表.在每一步调用中,经过多次的交换,最终为中心元素找到最终的位置.与归并算法不同,快速排序是就地排序,而归并排序需要把元素在临时向量中拷贝,下面通过对以下向量进行排序来理解和加深快速排序算法
C#用递归算法解决经典背包问题

1.引子我们人类是一种贪婪的动物,如果给您一个容量一定的背包和一些大小不一的物品,裝到背包里面的物品就归您,遇到这种好事大家一定不会错过,用力塞不一定是最好的办法,用脑子才行,下面就教您如何解决这样的问题,以获得更多的奖品. 2.应用场景在一个物品向量中找到一个子集满足条件如下 : 1)这个子集加起来的体积大小不能大于指定阀值 2)这个物品子集加起来价值大小是向量V中所有满足条件1的子集中最大的 3.分析背包问题有好多版本,本文只研究0/1版本,即对一个物体要么选用,要么就抛弃,不能将一个
C#递归算法寻找数组中第K大的数

1.概述国人向来喜欢论资排辈的,每个人都想当老大,实在当不成,当个老二,老三,老K也不错,您一定看过这样的争论: 两个人吵架,一个人非常强势,另外一个忍受不住了便说:"你算老几呀?",下面就通过这篇文章就是要解决找出老几的问题! 2.应用场景在向量V[first,last)中查找出第K大元素的值 3.分析如果利用排序算法将向量V排好序,那么第K大元素就是索引为v.length-k的元素了,这样能解决问题,但效率不高,因为这相当于为了歼灭敌人一个小队而动用了我们全军的力量,得不偿失
C#递归算法之归并排序

归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表,再对半子表排序,最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列,归并排序包括两个步骤,分别为: 1)划分子表 2)合并半子表首先我们来讨论归并算法,归并算法将一系列数据放到一个向量中,索引范围为[first,last],这个序列由两个排好序的子表构成,以索引终点(mid)为分界线,以下面一个序列为例 7,10,19,25,12,17,21,30,48 这样的一个序列中,分为两个子序列 7,10,19,25 和
C#递归算法之分而治之策略

1.分而治之的概念分而治之是一种使用递归解决问题的算法,主要的技巧是将一个大的复杂的问题划分为多个子问题,而这些子问题可以作为终止条件,或者在一个递归步骤中得到解决,所有子问题的解决结合起来就构成了对原问题的解决 2.分而治之的优点和缺点分而治之算法通常包括一个或者多个递归方法的调用,当这些调用将数据分隔成为独立的集合从而处理较小集合的时候,分而治之的策略将会有很高的效率,而在数据进行分解的时候,分而治之的策略可能会产生大量的重复计算,从而导致性能的降低. 3.画标尺程序的分析讲解画标
C#用递归算法解决八皇后问题

1.引子中国有一句古话,叫做"不撞南墙不回头",生动的说明了一个人的固执,有点贬义,但是在软件编程中,这种思路确是一种解决问题最简单的算法,它通过一种类似于蛮干的思路,一步一步地往前走,每走一步都更靠近目标结果一些,直到遇到障碍物,我们才考虑往回走.然后再继续尝试向前.通过这样的波浪式前进方法,最终达到目的地.当然整个过程需要很多往返,这样的前进方式,效率比较低下. 2.适用范围适用于那些不存在简明的数学模型以阐明问题的本质,或者存在数学模型,但是难于实现的问题. 3.应用场景在
C#算法之关于大牛生小牛的问题

本文实例讲述了C#算法之关于大牛生小牛的问题.分享给大家供大家参考.具体分析如下: 问题: 一只刚出生的小牛,4年后生一只小牛,以后每年生一只.现有一只刚出生的小牛,问20年后共有牛多少只? 刚开始觉得递归比较好,想了很长时间,没想出来,于是想了下面一种方法来实现,先生成一个数据,并且数据第i个表示牛的年龄,数组i的值表示今年有几头牛实现代码如下: const int YEAR = 50; static void Main(string[] args) { int[] yearAmount =
C#用递归算法实现：一列数的规则如下: 1、1、2、3、5、8、13、21、34，求第30位数是多少

方法一:递归算法 /// <summary> /// 一列数的规则如下: 1.1.2.3.5.8.13.21.34求第30位数是多少, 用递归算法实现.(C#语言) /// </summary> /// <param name="pos"></param> /// <returns></returns> public int GetNumberAtPos(int pos) { if(pos==0||pos==1)
C#算法之大牛生小牛的问题高效解决方法

问题: 一只刚出生的小牛,4年后生一只小牛,以后每年生一只.现有一只刚出生的小牛,问20年后共有牛多少只? 思路: 这种子生孙,孙生子,子子孙孙的问题,循环里面还有循环的嵌套循环,一看就知道是第归问题. 于是乎,第一个版本出现: public long Compute1(uint years) { //初始化为1头牛 long count = 1; if (years <= 3) { return count; } int i = 4; while (i <= years) { int sub
Golang算法问题之数组按指定规则排序的方法分析

本文实例讲述了Golang算法问题之数组按指定规则排序的方法.分享给大家供大家参考,具体如下: 给出一个二维数组,请将这个二维数组按第i列(i从1开始)排序,如果第i列相同,则对相同的行按第i+1列的元素排序, 如果第i+1列的元素也相同,则继续比较第i+2列,以此类推,直到最后一列.如果第i列到最后一列都相同,则按原序排列. 样例输入: 1,2,3 2,3,4 2,3,1 1,3,1 按第2列排序,输出: 1,2,3 2,3,1 1,3,1 2,3,4 代码实现: 复制代码代码如下: pac
Python cookbook（数据结构与算法）将序列分解为单独变量的方法

本文实例讲述了Python cookbook(数据结构与算法)将序列分解为单独变量的方法.分享给大家供大家参考,具体如下: 如果对象是可迭代的(任何序列),则可以进行分解操作,包括元组.列表.字符串.文件.迭代器以及生成器,可通过简单的一个赋值操作分解为单独的变量. 唯一要求:变量的总数和序列相吻合,否则将出错: Python 2.7.11 (v2.7.11:6d1b6a68f775, Dec 5 2015, 20:32:19) [MSC v.1500 32 bit (Intel)] on wi
Python cookbook（数据结构与算法）实现查找两个字典相同点的方法

本文实例讲述了Python实现查找两个字典相同点的方法.分享给大家供大家参考,具体如下: 问题:寻找两个字典中间相同的地方(相同的键.相同的值等) 解决方案:通过keys()或者items()方法来执行常见的集合操作(比如求并集.交集和差集) >>> a={'x':1,'y':2,'z':3} >>> b={'ww':10,'x':11,'y':2} >>> a.keys()& b.keys() #键的交集 {'y', 'x'} >>
PHP实现RSA加解密算法示例(生成密钥位数为1024位的方法)

大家可以先到http://web.chacuo.net/netrsakeypair这个网站,在线生成公钥和私钥 RSA非对称加密算法,如果是公钥加密,就得用私钥解密,反过来也一样,私钥加密的就用公钥解密,以下是相关实现函数 /** * RSA私钥加密 * @param string $private_key 私钥 * @param string $data 要加密的字符串 * @return string $encrypted 返回加密后的字符串 * @author mosishu */ fun
Python cookbook(数据结构与算法)将名称映射到序列元素中的方法

本文实例讲述了Python将名称映射到序列元素中的方法.分享给大家供大家参考,具体如下: 问题:希望通过名称来访问元素,减少结构中对位置的依赖性解决方案:使用命名元组collections.namedtuple().它是一个工厂方法,返回的是python中标准元组类型的子类,提供给它一个类型名称以及相应的字段名称,它就返回一个可实例化的类,为你以定义好的字段名称传入值等. 命名元组的主要作用在于将代码同它所控制的元素位置间进行解耦 >>> from collections import
C++数据结构与算法之判断一个链表是否为回文结构的方法

本文实例讲述了C++判断一个链表是否为回文结构的方法.分享给大家供大家参考,具体如下: 题目: 给定一个链表头节点head,请判断是否为回文结构例如: 1->2->1 true 1->2->2->1 true 1->2->3->4->2->1 false 解题思路及代码 1.找到链表中间节点,然后将链表中间节点的右边所有节点放入一个栈中. 2.然后从链表首节点和栈顶元素一一对比,不相等则return false. 算法C++代码: 链表节点结构
C语言实现的排列组合问题的通用算法、解决方法

尽管排列组合是生活中经常遇到的问题,可在程序设计时,不深入思考或者经验不足都让人无从下手.由于排列组合问题总是先取组合再排列,并且单纯的排列问题相对简单,所以本文仅对组合问题的实现进行详细讨论.以在n个数中选取m(0<m<=n)个数为例,问题可分解为: 1. 首先从n个数中选取编号最大的数,然后在剩下的n-1个数里面选取m-1个数,直到从n-(m-1)个数中选取1个数为止. 2. 从n个数中选取编号次小的一个数,继续执行1步,直到当前可选编号最大的数为m. 很明显,上述方法是一个递归的过程,也
全排列算法的非递归实现与递归实现的方法(C++)

(一)非递归全排列算法基本思想是: 1.找到所有排列中最小的一个排列P. 2.找到刚刚好比P大比其它都小的排列Q, 3.循环执行第二步,直到找到一个最大的排列,算法结束.下面用数学的方法描述:给定已知序列 P = A1A2A3An ( Ai!=Aj , (1<=i<=n , 1<=j<=n, i != j ) )找到P的一个最小排列Pmin = P1P2P3Pn 有 Pi > P(i-1) (1 < i <= n)从Pmin开始,总是目

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

相关推荐

随机推荐