| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2423 人关注过本帖
标题:整数划分的问题
只看楼主 加入收藏
YOGIOH
Rank: 1
等 级:新手上路
帖 子:102
专家分:0
注 册:2007-5-8
收藏
 问题点数:0 回复次数:5 
整数划分的问题

// 将一个正整数n表示成一系列正整数之和,
// n = n1 + n2 + ... + nk ( 其中, n1 >= n2 >= ... >= nk , k >= 1 )
// 正整数n的一个这种表示称为正整数n的一个划分。
// 正整数n的不同的划分个数称为正整数n的划分数。

// 求划分数

// 将最大数n1不大于m的划分个数记作q(n,m)。
// 递归关系如下:
// 1、q(n,1) = 1 , n >= 1;
// 2、q(n,m) = q(n,n) , m >= n;
// 3、q(n,n) = 1 + q(n,n-1);
// 4、q(n,m) = q(n,m-1) + q(n-m,m) , n > m > 1;

////////////////////////////////////////
#include "iostream.h"

int q( int n , int m )
{
if( n < 1 || m < 1 )
return 0;
if( n == 1 || m == 1 )
return 1;
if( n < m )
return q( n , n );
if( n == m )
return q( n , m - 1 ) + 1;
return q( n , m - 1 ) + q( n - m , m );
}
void main()
{
cout<<q(6,6)<<endl;
}

////////////////////////////////////////
////////////////////////////////////////
////////////////////////////////////////
////////////////////////////////////////
////////////////////////////////////////

对于 1 2 点 还可以理解 对于3 4 就理解不了了
谁能详细的解释一下这个思想?
搜索更多相关主题的帖子: 整数 大数 之和 DIV htmlcode 
2007-10-03 21:30
nuciewth
Rank: 14Rank: 14Rank: 14Rank: 14
来 自:我爱龙龙
等 级:贵宾
威 望:104
帖 子:9786
专家分:208
注 册:2006-5-23
收藏
得分:0 
3.q(n,n) = 1 + q(n,n-1);

这个1就表示只能用n来表示这一种啦.(n=n)

4、q(n,m) = q(n,m-1) + q(n-m,m) , n > m > 1;
用不大于m-1来划分n和一定要用 m来划分n刚好是n的不大于m的划分.
举个例子 q(10,4)=q(10,3)+q(6,4)
用不大于3来表示10的和一定要用4来表示10的相加是不是表示用不大于4来表示10.
而刚好用了一次4,所以一定要用4表示10和用不大于4来表示6的个数是不是相等.

明白没?

倚天照海花无数,流水高山心自知。
2007-10-03 21:42
mp3aaa
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:2013
专家分:8
注 册:2006-2-15
收藏
得分:0 
王晓东 编的 计算机算法设计与分析 ?
这本书不错 原来我就是看了楼主这个程序得到的启发写的另一个程序
如果楼主根据书上的解释还看不懂的话 那建议楼主先看看数据结构什么的 在累计一点经验 毕竟这个程序在里面算是很简单的一个了

羊肉串 葡萄干 哈密瓜!!
2007-10-03 23:07
YOGIOH
Rank: 1
等 级:新手上路
帖 子:102
专家分:0
注 册:2007-5-8
收藏
得分:0 
网上碰到的问题
没看过这本书

2007-10-04 02:47
mp3aaa
Rank: 5Rank: 5
等 级:贵宾
威 望:17
帖 子:2013
专家分:8
注 册:2006-2-15
收藏
得分:0 
  不好意 这个题是书的上原题

羊肉串 葡萄干 哈密瓜!!
2007-10-04 03:12
zx19899891
Rank: 1
等 级:新手上路
帖 子:1
专家分:0
注 册:2009-8-8
收藏
得分:0 
回复 2楼 nuciewth

最后一句话还是不怎么明白?我就不知道怎么就会想到它们俩会相等
2009-08-08 12:09
快速回复:整数划分的问题
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.063438 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved