du熊的机器人
【du熊的机器人】
Description
du熊正在玩一个别人刚送给它的机器人。这个机器人只能在一个棋盘中行走,棋盘的左上角格子为(0, 0),右下角格子为(X, Y)。
du熊控制这个机器人从棋盘的左上角,走到右下角,再从右下角回到左上角。当机器人从左上角走到右下角的过程中,如果它当前所在格子为(x, y),则它只能走到(x+1, y)或(x, y+1)的格子;当机器人从右下角走回左上角的过程中,如果它当前所在的格子为(x, y),则它只能走到(x-1, y)或(x, y-1)的格子。并且du熊要求机器人从左上角走到右下角再走回左上角的整个过程中,最多经过同一个格子一次。
请你帮du熊计算出这个机器人一共有多少种不同的路线。
Resolution
设所求的解为F(x,y)。
从(0,0)走到(x,y),所有可能解法是C(x+y,x)(C代表求组合数)。可以理解成从(0,0)走到(x,y),一共需要走(x+y)步,其中x步是横向移动,y步是横向移动。 所有可能走法对应于从(x+y)步中挑出x步,做横向移动。
同样地,从(x,y)走到(0,0),同样有C(x+y,x)种方案。从C(x+y,x)中方案中选出不同的两种路线,路线A作为从(0,0)走到(x,y)的路线 ,路线B作为从(x, y)走到(0, 0)的路线,路线A和路线B的组合共有C(C(x+y,x),2)种选择。但是这些组合中, 有些方案并不满足“最多经过同一个格子一次”的要求,所以需要将其剔除掉。
假设路线A和路线B不满足“最多经过同一个格子一次”,A和B经过两次的格子中(不考虑(1,1)和(x,y)),最左上角的格子的坐标是(i,j)。如下图所示,(i,j)只可能是(1,0),(0,1)或橘色方框中除(4,5)外的一个。两个在(x,0)(x>0)相交的路线必先在(1,0)相交。 两个在(0,y)(y>0)相交的路线必先在(0,1)相交。
分别计算这三种情况下,剔除的方案数:
- 路线A和路线B最先在(1,0)相遇,需要剔除掉的方案数相当于从(1,0)到(x,y)选择两条不同路线的方案数,共有C(C(x-1+y,x-1),2)种。
- 路线A和路线B最先在(0,1)相遇,需要剔除掉的方案数相当于从(0,1)到(x,y)选择两条不同路线的方案数,共有C(C(x+y-1,y-1),2)种。
- 路线A和路线B最先在橘色方框中的一点(i,j)相遇,需要剔除掉的方案数等于从(0,0)到(i,j)两条不相交的方案数即F(i,j),乘以从(i,j)到(x,y)任选两条路线(可以重复)的方案数,即(C(x-i+y-j,x-i)2)种。
故可以得到如下的计算F(x,y)的公式:
转自:http://weihethu.github.io/blog/2013/04/14/du-bear-robots/
最新文章
- PermGen space
- Android SDK 百度云盘分享链接
- ubuntu 安装 phpmyadmin
- codeforces 425B Sereja and Table (枚举、位图)
- WPF Dispatcher 一次小重构
- Mongodb 笔记05 创建副本集
- destoon短信接口修改方法
- 安装完Oracle之后的注意事项
- Spring AOP原理解析
- LogstashL reference 重要章节
- .net+easyui系列--datagrid
- Java[2] 分布式服务架构之java远程调用技术浅析(转http://www.uml.org.cn/zjjs/201208011.asp)
- HDU 1896 Stones(优先队列)
- 算法-java代码实现计数排序
- Struts2 之值栈
- 【XSY3370】道路建设 最短路
- 光纤网卡与HBA卡区别
- rsyslog+loganalyzer配置
- PostgreSQL 锁等待诊断详解
- 通过Cloudera Manager部署CDH5.15.1的webUI界面详解
热门文章
- Alpha阶段贡献分配规则
- spring MVC 使用 modelAndView.setViewName(";forward:*.action";) 发送重定向
- 【java多线程】ConCurrent并发包 - Lock详解
- StreamSets 部署 Pipelines 到 SDC Edge
- UNIX 时间戳 C#
- elasticsearch安装入门
- CentOS 6.0 VNC远程桌面配置方法(转帖)
- 归并排序算法-python实现
- 02 - Unit07:显示笔记下拉菜单、笔记的分享功能、笔记的删除功能
- gradle windows上面安装配置