网站首页
网站导航
Ctrl+D收藏
首 页
代码段
源码包
文档库
工具箱
代码语言
.
CSharp
.
JS
Java
Asp.Net
C
MSSQL
PHP
Css
PLSQL
Python
Shell
EBS
ASP
Perl
ObjC
VB.Net
VBS
MYSQL
GO
Delphi
AS
DB2
Domino
Rails
ActionScript
Scala
代码分类
文件
系统
字符串
数据库
网络相关
图形/GUI
多媒体
算法
游戏
Jquery
Extjs
Android
HTML5
菜单
网页交互
WinForm
控件
企业应用
安全与加密
脚本/批处理
开放平台
其它
【
】
递归-整数划分
作者:
memristor
/ 发布于
2014/9/10
/
599
将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。 正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数 将n中最大加数是m的划分个数记作f(n,m)。可以建立f(n,m)的如下递归关系 (1)当 n = 1 时,不论m的值为多少(m > 0 ),只有一种划分即 { 1 }; (2) 当 m = 1 时,不论n的值为多少,只有一种划分即 n 个 1,{ 1, 1, 1, ..., 1 }; (3) 当 n = m 时,根据划分中是否包含 n,可以分为两种情况: (a). 划分中包含n的情况,只有一个即 { n }; (b). 划分中不包含n的情况,这时划分中最大的数字也一定比 n 小,即 n 的所有 ( n - 1 ) 划分。 因此 f(n, n) = 1 + f(n, n-1); (4) 当 n < m 时,由于划分中不可能出现负数,因此就相当于 f(n, n); (5) 但 n > m 时,根据划分中是否包含最大值 m,可以分为两种情况: (a). 划分中包含 m 的情况,即 { m, { x1, x2, ..., xi } }, 其中 { x1, x2, ..., xi } 的和为 n - m,可能再次出现 m,因此是(n - m)的 m 划分,因此这种划分个数为 f(n-m, m); (b). 划分中不包含 m 的情况,则划分中所有值都比 m 小,即 n 的 ( m - 1 ) 划分,个数为 f(n, m - 1); 因此 f(n, m) = f(n - m, m) + f(n, m - 1); unsigned long GetPartitionCount(int n, int max) { if (n == 1 || max == 1) return 1; else if (n < max) return GetPartitionCount(n, n); else if (n == max) return 1 + GetPartitionCount(n, max-1); else return GetPartitionCount(n,max-1) + GetPartitionCount(n-max, max); }
评论列表
本站所提供的代码,版权归原作者所有,若有侵犯作者版权,请与我们联系,我们将立即删除或修改。谢谢!
本站所有代码发布及提供者。
试试其它关键字
整数划分
同语言下
.
StringHelper.cs 对html标签过滤
.
不调用Dbhelper数据库的后台代码
.
后台弹出提示框,防止页面刷新。
.
倒计时间表
.
JAVA集成SVN,查看应用更新日志
.
输入一串无序数,返回出现次数最多的数字,并返回个数
.
table中连续字符换行
.
WPF 获取屏幕分辨率
.
简单的实现用户注册时,向其油箱发送激活码邮件,并进
.
JavaMail发送邮件
可能有用的
.
SQL查询 多列合并成一行用逗号隔开
.
一行一行读取txt的内容
.
C#动态修改文件夹名称(FSO实现,不移动文件)
.
c# 移动文件或文件夹
.
c#图片添加水印
.
Java PDF转换成图片并输出给前台展示
.
网站后台修改图片尺寸代码
.
处理大图片在缩略图时的展示
.
实现对图片上传的接收
.
判断用户输入的是否为IP地址
memristor
贡献的其它代码
(
1
)
.
递归-整数划分
地图
本站
我们
服务
版权
联系
回馈
博客