12 / 2 页下一页

查看: 8948|回复: 19

分配难题

[复制链接]

字体大小: 正常放大

maybe_madio

2 主题	3 听众	16 积分

升级 11.58%

该用户从未签到

电梯直达

1^#

发表于 2010-10-24 09:28 |只看该作者 |正序浏览

|招呼Ta 关注Ta

设有4个盒子，标号为1，2，3，4. 有15个颜色相同的小球, 现在要将15个颜色相同的小球分配到4个盒子中,
要求每个盒子至少有一个小球，并且对于盒子中小球的数目，盒子1>盒子2>盒子3>盒子4. 请问一共有多少种分配方法.

zan

转播0 淘帖0 分享0 收藏0 支持0 反对0 微信

使用道具举报

漂流者

10 主题	5 听众	1234 积分

升级 23.4%

TA的每日心情

	郁闷 2014-9-19 13:56

签到天数: 380 天

[LV.9]以坛为家II

群组: 2011年第一期数学建模

群组: 学术交流A

群组: 第四届数学中国美赛实

群组: 数学中国2013版主团队

20^#

发表于 2012-1-5 18:29 |只看该作者 |招呼Ta 关注Ta

可以先把15个球排成一排，然后从他们之间的14个间隔里插入3块板，就可以把15个小球分成4份了，用这个思想，可以很容易解决你的问题，隔板法是很经典的东西。

我也说一句

发表

使用道具举报

whui

0 主题	4 听众	192 积分

升级 46%

TA的每日心情

	奋斗 2013-4-3 01:13

签到天数: 61 天

[LV.6]常住居民II

19^#

发表于 2012-1-1 18:35 |只看该作者 |招呼Ta 关注Ta

13种。。。。。。。。。。。。。

我也说一句

发表

使用道具举报

whui

0 主题	4 听众	192 积分

升级 46%

TA的每日心情

	奋斗 2013-4-3 01:13

签到天数: 61 天

[LV.6]常住居民II

18^#

发表于 2012-1-1 15:54 |只看该作者 |招呼Ta 关注Ta

13种呀。。。。。。。。。。。。。。。。

我也说一句

发表

使用道具举报

linmatsas

53 主题	13 听众	3591 积分

逍遥游

TA的每日心情

	奋斗 2014-12-2 09:53

签到天数: 54 天

[LV.5]常住居民I

自我介绍: 额。。。。世界上最讨厌的事情就是自我介绍。。。

群组: Matlab讨论组

群组: 数学建模

群组: 小草的客厅

群组: 2012数学一考研交流

群组: C 语言讨论组

17^#

发表于 2010-10-25 23:21 |只看该作者 |招呼Ta 关注Ta |邮箱已经成功绑定

要是好多好多球好多好多盒子可怎么办呢…………这真是一个问题呀………………不过一时想不出来其他算法了……应该穷举能做呀…………应该用不了几个小时吧…………

我也说一句

发表

渺万里层云，千山暮雪

使用道具举报

guoshaoming

24 主题	5 听众	1034 积分

升级 3.4%

TA的每日心情

	奋斗 2014-4-16 09:54

签到天数: 9 天

[LV.3]偶尔看看II

自我介绍: 200 字节以内

不支持自定义 Discuz! 代码

16^#

发表于 2010-10-25 23:17 |只看该作者 |招呼Ta 关注Ta

回复 maybe_madio 的帖子
当你的变量大到一定程度的时候，你可以将约束条件写成一个循环语句，判断、输出也可以写成相应的循环语句！
反正程序的总体思路就是上面那个，过多的我就不多说了

我也说一句

发表

使用道具举报

guoshaoming

24 主题	5 听众	1034 积分

升级 3.4%

TA的每日心情

	奋斗 2014-4-16 09:54

签到天数: 9 天

[LV.3]偶尔看看II

自我介绍: 200 字节以内

不支持自定义 Discuz! 代码

15^#

发表于 2010-10-25 22:52 |只看该作者 |招呼Ta 关注Ta

回复 maybe_madio 的帖子
本身这个算法就很具有一般性，如果你增加变量，只要对程序稍加改动就可以了，
for(xm=1;xm<n;xm++)
然后判断语句和输出也做相应改变

我也说一句

发表

使用道具举报

maybe_madio

2 主题	3 听众	16 积分

升级 11.58%

该用户从未签到

14^#

发表于 2010-10-25 19:47 |只看该作者 |招呼Ta 关注Ta

回复 guoshaoming 的帖子

虽然对于15来说，比较容易算出，那如果我的变量再增多呢？假设有x1+x2+..xm=n呢？（m<n）
能否有更好的程序算法来解决这个问题呢？你的穷举算法也只能适用于少量的变量和n较小的特例，当变量增多，或是n变大，这是阶乘级的时间复杂度哦！

我也说一句

发表

使用道具举报

guoshaoming

24 主题	5 听众	1034 积分

升级 3.4%

TA的每日心情

	奋斗 2014-4-16 09:54

签到天数: 9 天

[LV.3]偶尔看看II

自我介绍: 200 字节以内

不支持自定义 Discuz! 代码

13^#

发表于 2010-10-25 00:04 |只看该作者 |招呼Ta 关注Ta

本帖最后由 guoshaoming 于 2010-10-25 00:08 编辑

回复 maybe_madio 的帖子
分配方案如下：
6    4    3    2
6    5    3    1
7    4    3    1
7    5    2    1
8    4    2    1
9    3    2    1
其代码如下：
#include < iostream >

using namespace std;

int main()
{
int x1,x2,x3,x4;
int t=0;

for(x1=1;x1<15;x1++)
for(x2=1;x2<15;x2++)
for(x3=1;x3<15;x3++)
for(x4=1;x4<15;x4++)
{
if((x1+x2+x3+x4==15)&&(x1>x2)&&(x2>x3)&&(x3>x4))
cout<<x1<<"\t"<<x2<<"\t"<<x3<<"\t"<<x4<<endl;

}
return 0;
}