首页 新闻 论坛 群组 Blog 文档 下载 读书 Tag 网摘 搜索 .NET Java 游戏 视频 人才 外包 培训 数据库 书店 程序员
中国软件网
欢迎您:游客 | 登录 注册 帮助
    • 一道排列组合题的升级版~
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • gz_jason
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    • 揭贴率：
    发表于：2008-08-21 21:49:58 楼主
    这道题的原型是另一个较为简单的问题，如下：

      1.现有完全相同的球n个，每次至少取一个球，问有多少种取法取完这些球？

    答案是有2的n-1次方种取法。

    将题目深化：

      2.现有完全相同的白球a个、黑球b个，每次至少取一个球、颜色不限，问有多少种取法取完这些球？

    望赐教~

    又或，有A球a个、B球b个、C球c个......N球n个呢？
    20  修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • gz_jason
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-21 22:19:091楼 得分:0
    补充：

    例如，每次取1个，取n次可取完，这样算一种取法；
          每次取n个，取1次可取完，又是一种取法。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • dlyme
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 4
    发表于：2008-08-22 09:27:292楼 得分:0
    记第1种颜色的球有n(1)个，第2种颜色的球有n(2)个，...，第k种颜色的球有n(k)个
    用dp(n(1),n(2),...,n(k))来表示总共的取法，那么状态转移方程：
    dp(n(1),n(2),...,n(k))=∑dp(x(1),x(2),...,x(k))
    对于1 <=i <=n来说，都有0 <=x(i) <=n(i)，且至少得有一个x(i) <n(i)成立
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • dlyme
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 4
    发表于：2008-08-22 09:28:583楼 得分:0
    对于1 <=i <=n来说，都有0 <=x(i) <=n(i)，且至少得有一个x(i) <n(i)成立
    ==>
    对于1 <=i <=k来说，都有0 <=x(i) <=n(i)，且至少得有一个x(i) <n(i)成立
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • daniel_yao
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-22 16:55:454楼 得分:0
    1 首先对白球 黑球进行排列 如果有n排列
    2 然后把这些球当作同种颜色的来处理m
    3 最后的解就是nm种方法

    不管有几种球 先求出排列的值
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • daniel_yao
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-08-22 18:10:555楼 得分:0
    上面的方法有点问题，再想想
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • northwolves
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：

    • 2
    发表于：2008-08-31 09:02:216楼 得分:0
    递归。
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • hacklew1985
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-01 14:40:437楼 得分:0
    先排列后组合的问题
    修改 删除 举报 引用 回复
    进入用户个人空间
    加为好友
    发送私信
    在线聊天
    • cymandhxl
    • 等级:
    • 可用分等级：
    • 总技术分：
    • 总技术分排名：
    发表于：2008-09-05 15:24:118楼 得分:0
    既然颜色不限，那岂不是n=a+b了。
    修改 删除 举报 引用 回复
    网站简介－广告服务－网站地图－帮助－联系方式－诚聘英才－English－ 问题报告
    北京创新乐知广告有限公司 版权所有 京 ICP 证 070598 号
    世纪乐知(北京)网络技术有限公司 提供技术支持
    Copyright © 2000-2008, CSDN.NET, All Rights Reserved