EDIT:其实就是n个球,插n-1个板,板可以相邻…… 以下都是废话了……
恩 我承认标题党了
这个问题是昨天晚上找Monster.Q和Jay-ZW吃饭的时候,他们再研究的一个问题。仅仅3个元素的话,数一下就可以了,10个。但是元素一多肯定没法数了,也没法说数一下能控制n个元素的情况。
一开始,我们3个人都往排列组合上想了,各种思路总觉得都不靠谱。
Jay-ZW给出了一个n=3时的解:
3个盒子,3个球。 3种情况:
一个盒子里一个球(1+1+1): C(3,3) = 1 种
一个盒子两个,另外一个盒子一个(2+1): C(3,1) * C(2,1) = 6 种
一个盒子里放3个(3): C(3,1) = 3 种
一共10种
很明显,这种方法在n稍微增大的时候,就会让人吐血了 比如5个的时候就要考虑这几种情况
5
4+1
3+2
3+1+1
2+2+1
2+1+1+1
1+1+1+1+1
这个没法让人接受。
==========糗百风格的昏割线0x01==========
想起来当时用来数n=3情况的时候用的一个小技巧:
Q W E
Q W E
Q W E
这样从上往下画线,但是只能向下和向右拐,比如这样
Q W
E
Q W
E
Q W E
或者这样
Q W
E
Q W E
Q W E
==========糗百风格的昏割线0x02==========
我们定义一个函数f(x, y),f(x, y)的值代表Kael可以控制x种元素,在同时拿出y种元素的情况下,总共的技能数。真实的Kael的话就是f(3,3)=10。
(1) 首先考察一下,x = 1的情况
呃 很明显,只有一种元素可以控制,那就只能拿出一种技能了。。
所以f(1, y) = 1
比如f(1,3) 对应着
Q
Q
Q
即只有QQQ一种
(2) 再考虑一下, y = 1的情况
恩 x种元素,拿出一个, 那就是x个技能了
即f(x, 1) = x
比如
Q W E
对应着Q、W、E三种
(3) 恩 正题了
观察楼下是个8x8的矩阵,我们要算出来f(8,8)来。
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
总不能不选把,好,我们从先选一个,Q吧!
Q
W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
选好了,第二行再选什么? 等等,如果我们观察一下,就会发现,8x8在第一行选Q的情况下,其实与8x7矩阵的所有情况数量相等,因为8x7的每一种情况头上添个Q就是这种情况了。
同理,如果我第一行选W,情况数与7x7的全部情况数是相等的!
Q W
E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
Q W E R T Y U I
所以,当我取完第一行的Q、W、E、R……的时候,把他们都加起来,就是8x8矩阵的所有情况!
所以f(8,8) = f(8,7)+f(7,7)+ ... + f(1,7)
推广到x和y,得到:
f(x,y) = f(x, y-1) + f(x-1, y-1) + ... + f(1, y-1)
加上(1)、(2)推出的结论,得出:
{
f(x, y) = Sum(f(i, y-1), i = 1 to x)
f(x, 1) = x
f(1, y) = 1
}
==========糗百风格的昏割线0x03==========
写出程序来,也不是特别复杂,附赠C源代码:
#include <stdio.h>
#include <stdlib.h>
int cache[100][100]; // 偷懒,n别过99就不会出错。 其实n到了一定大小就会溢出f(n,n)就会溢出了
int f(int x, int y)
{
int i, sum;
if(cache[x][y]) return cache[x][y]; // 计算过则直接返回结果
if(y == 1) return x;
if(x == 1) return 1;
for(i=1, sum=0; i <= x; i++) {
sum += f(i, y-1);
}
return cache[x][y] = sum;
}
int main()
{
int n;
memset(cache, 0, sizeof(cache));
scanf("%d", &n);
printf("%d\n", f(n, n));
return 0;
}
==========糗百风格的昏割线0x03==========
下面提供n<=10的情况:
f(1,1) = 1
f(2,2) = 3
f(3,3) = 10
f(4,4) = 35
f(5,5) = 126
f(6,6) = 462
f(7,7) = 1716
f(8,8) = 6435
f(9,9) = 24310
f(10,10) = 92378
蛋疼的同学可以拿去验证以下
分享到:
相关推荐
Kael-Qrcode, 二维码生成库,基于canvas,灵活轻巧,美观多变。
WINCE远程同步显示操作工具,可以在PC端通过USB连接显示的控制WINCE设备,截图录像,分WINCE6和WINCE7两个版本。
取名卡尔,缘由dota英雄Kael;一生二,二生三,三生万物 … 简单地配置Kael-Qrcode,帮助你变换出无穷样式的二维码。 使用 Usage: 1、入手 Demo Base - 基本 var kaelBase = new KaelQrcode(); kaelBase.init...
如果您愿意,可以给它一个Star ,分叉或克隆以使用 ;) 如果有任何问题或要求,只需在这里打开一个问题,我会帮助你。 文档 开始 组件 评论与分析 先进的 定制 标题图片 搜索引擎优化标题 页面构建警告 常问问题 ...
这个Mod是做什么的 请参阅 去做 发布之前,请记住禁用调试模式。 播放器应该能够在选项菜单中调整两个选项。 A.(滑条)单个游戏会话允许多少分钟。 (默认为60) B.(滑块)到达A.之后,在公民开始抗议之前还...
现在是2020年5月4日0:51分,2020年五四青年节,我终于解决了这个问题 问题描述: 原创文章 74获赞 31访问量 7781 关注 私信 展开阅读全文 作者:GRIT_Kael
还需要安装 xcode 命令行工具才能使 phantomjs 工作 所需的包 phantomjs,全局安装(-g)并将PATH设置为其bin文件夹 幻影 汤选择 html解析器 数据库 英雄输出示例 { "_id": "kaelthas/", "name": "Kael'thas", ...
(c) 2005 - 2007 Lomig, Liadora et Nyx (Kael'Thas et Elune - 欧盟/法国) (c) 2008 - 2010 Lomig & ArPharazon(纳格兰 - 美国/大洋洲) (c) 2019 – Doppie 的 2019 经典更新 (c) 2019 – urnati 经典更新...
复制到system32文件夹下,基本上就可以运行,如果缺少DLL文件,请再下载DLL复制过去
IOS特定条件上UITABLEVIEWCELL不刷新的现象
10天学会ASP.NET教程 asp.net完全入门pdf教程 零基础学ASP.NET.2.0(PPT)
Android安全_FDE与FBE原理与流程.docx
asp.net C# 常用的正则表达式 asp.net C# 常用的正则表达式 免费的
配合博客的测试工程,测试启动图片和布局关系
复制到system32文件夹下应该就可以了,适应于没安装Borland C++又需要调试的人
SQLITT3 3.7.7版本,AES,MD5加密,PC机和WINCE6.0上的VS2005工程源码,目标文件,SDK,WINCE加密解密测试工程,以及移植使用文档,全部测试通过。
校网客户端
小巧的局域网聊天工具,适合学生下载学习使用。