C#算法之大牛生小牛的问题高效解决方法
问题: 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比较小的时候,第一种方法耗时短,但两者的时间基本在一个数量级上 测试结果截图: 20年 50年 源程序以及测试程序:http://xiazai.aspzz.cn/201606/yuanma/HowMoneyCows(aspzz.cn).rar 以上就是本文的全部内容,希望能给大家一个参考,也希望大家多多支持编程小技巧。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |
- React Native与Android原生通信
- 斯威夫特错误:二元运算符“\u0026\u002
- postgresql – 如何在postgres中的单个查询语句中
- oracle ebs 采购订单导入 来源参考 Oracle metal
- c# – 如何配置EnyimMemcachedCore以访问AWS Lam
- React-Redux 源码解析系列 -- React-Redux的作用
- Mybatise,在xml中循环list或map
- iphone上无法解释的分段故障
- Wince6使用K9F4G08U0A升级至512MNandFlash
- c# – FileHelpers:非引用CSV中的可选字段