http://www.iteye.com/topic/963980#1983213
题目
将任一个数字进行拆解,例如:
3 = 2+1 = 1+1+1 所以3有三種拆法
4 = 3 + 1 = 2 + 2 = 2 + 1 + 1 = 1 + 1 + 1 + 1 共五種
5 = 4 + 1 = 3 + 2 = 3 + 1 + 1 = 2 + 2 + 1 = 2 + 1 + 1 + 1 = 1 + 1 +1 +1 +1 共七种
随便给一个数字,对其进行拆解,并打印可拆解情况和拆解结果数。
动态规划思想:
这个可以用动态规划来做:
状态:dp[x][y]表示将x拆分成的最大值为y的方法总数。
过程:dp[x][y] = dp[x-y][1] + dp[x-y][2] + … +dp[x-y][y];
结果:result = dp[n][1] + dp[n][2] + dp[n][3] + … + dp[n][n];
递归思想:
就是走楼梯算法:
给定n阶楼梯,可以一次跨1阶、2阶……k阶(k<=n,问共有多少走法,并记录每种走法
递归公式: f(n) = f(n-1) + f(n-2) + f(n-3)+……+f(n-k) n>=1
private void climb(int n, int step,List<int> steps)
{
if (step > n)
return;
steps.Add(step);
if (n == step)
{
//当剩余楼梯的阶数等于第一步所跨的阶数
//则到达最后一阶楼梯,此时为其中一种走法
//记录每次走法
this.count++;
print(steps);
}
else
{
//如果没有达到最后一层,则递归剩余楼梯的走法
//此时,第一可跨最大阶数由允许所跨最大阶数和剩余楼梯阶数的较小值决定
for (int i = 1; i <= stemp&& i <= n - step; i++)
{
//递归剩余楼梯第一步的每种走法
climb(n - step, i);
//退出递归时,清除剩余楼梯的走法
//以记录新的走法
list.RemoveAt(list.Count - 1);
}
}
}
测试结果 :n=5,step=5时,共有16种走法:
1 1 1 1 1
1 1 1 2
1 1 2 1
1 1 3
1 2 1 1
1 2 2
1 3 1
1 4
2 1 1 1
2 1 2
2 2 1
2 3
3 1 1
3 2
4 1
5
这是考虑顺序的,你上面的就更简单了,不考虑顺序,放进set对象里过滤一下就可以了
分享到:
相关推荐
基于单片机数字拆分的一种高效算法.pdf
基于订单拆分生产的MTO企业生产调度及算法研究.pdf
这是一个数字查分的代码源程序,初学者的天堂,非常好懂,里面有解释。
拆分自然数的几种算法,用了递归和回溯法。
一个字拆分成高低字节 西门子1200的库,添加到博图v14sp1及以上版本软件的全局库文件夹中,在程序中即可调用;
这个代码是老师要用c++编写的,用于算法设计与分析课程中的拆分
本文主要讲了数码管多位数字拆分的方法,下面一起来学习一下
超额发票单据按照限额拆分
二进制分割用JavaScript编写的简单二进制拆分算法。
整数拆分整数拆分整数拆分整数拆分整数拆分整数拆分整数拆分整数拆分
十进制数字拆分成4字节十六进制数.vi十进制数字拆分成4字节十六进制数.vi
第一章 引论 1.1 组合数学研究的对象 1.2 组合问题典型实例 1.2.1 分派问题 1. 2.2 染色问题 1.2.3 幻方问题 1.2.4 36军官问题 1.2.5 中国邮路问题 习 题 第二章 排列与组合 2.1 两个基本计数...
CSV表格拆分,可以把一个CSV文件按固定行数拆分成多个文件
Map拆分和List拆分在对于大数据处理的时候起到了很大的作用。
孙维琴老师struts1书中代码,一个Form数据拆分到不同的jsp中。实现方式struts+hibernate。数据脚本齐全。
将一个整数S随机拆分为N个在min~max之间的整数
将这个线性表拆分成一个奇数线性表和一个偶数线性表线,性表的最大长度为20.
将一个整数线性表拆分成奇数和偶数线性表,课后习题,完整好用
按行把一个txt文件平均拆分成N个txt文件,结果是一行文本组成一个txt文件,适用于语料的按行切分。
HITS算法是另外一个链接算法,部分原理与PageRank算法是比较相似的,HITS算法引入了权威值和中心值的概念,HITS算法是受用户查询条件影响的,他一般用于小规模的数据链接分析,也更容易遭受到攻击。详细介绍链接 K-...