翻转的立方体 - 辕门射虎 - 轩辕春秋文化论坛 20周年


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#1

发表于 2010-12-25 02:14 资料主页文集短消息只看该作者

翻转的立方体

一个边长为1的立方体放置于坐标(0,0)处，其顶面被染为红色，其余五面均为白色。

允许该立方体向右和向上两种翻转，每次翻转可向x或y坐标增大的方向移动距离1。

现需要把该立方体翻转至(x,y)，其中x和y均为正整数。翻转过程中始终保持白色向上，但到达目标点后恢复红色向上。

问有多少条翻转路线可以达到以上要求。

[广告] 《精忠报国岳飞传完整版》火热发布


	dimeterio (李秀辰)

组别	校尉
级别	镇西将军
好贴	1
功绩	45
帖子	3985
编号	266634
注册	2008-2-7

#2

发表于 2010-12-25 18:07 资料个人空间短消息只看该作者

不是每个x，y都有解的吧。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	阿尔法孝直 (雀力日进)


	闽国公遂安军节度使 ★★★★★★

组别	节度使
级别	卫将军
好贴	2
功绩	1796
帖子	6036
编号	19070
注册	2004-10-16
家族	轩辕雀党

#3

发表于 2010-12-26 13:18 资料个人空间短消息只看该作者

程序很好写，但我也只知道不考虑颜色要求的话，答案是C(x+y,x)

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！


	周瑜


	栎阳侯谏议大夫 ★

组别	翰林学士
级别	征西将军
好贴	10
功绩	943
帖子	4716
编号	1808
注册	2003-11-3
家族	瓦岗寨

#4

发表于 2010-12-28 22:23 资料主页文集短消息只看该作者

首先，定义红色面改变方向的翻转为有效翻转，红色面不改变方向的翻转为无效翻转。每经过四次有效翻转，红色面就会恢复向上。根据题意，从起点到终点恰好有四次有效翻转。

以“右”表示向 x 轴正向翻转，“上”表示向 y 轴正向翻转。那么，这四次有效翻转可以是以下组合：右右右右，上上上上，右右上上，上上右右。

在第一、二次有效翻转，和第三、四次有效翻转之间，可以加入若干另一方向的无效翻转。因此构成四类路线：

1. 右(上...上)右右(上...上)右
2. 上(右...右)上上(右...右)上
3. 右(上...上)右上(右...右)上
4. 上(右...右)上右(上...上)右

易知，以上四类路线完全独立，两两无交集。

路线1，存在条件为 x=4，共有 y+1 条路线。(因为前后两个括号里的“上”总共有 y 个)
路线2，存在条件为 y=4，共有 x+1 条路线。
路线3，存在条件为 x≥2 且 y≥2，共有 1 条路线。
路线4，存在条件为 x≥2 且 y≥2，共有 1 条路线。

根据以上路线存在条件，可以得出到达任意 (x,y) 的路线数量。

1. 若 x=y=4，存在路线1、2、3、4，总计 12 条路线。
2. 若 x=4 且 y≠1 且 y≠4，存在路线1、3、4，总计 y+3 条路线。
3. 若 y=4 且 x≠1 且 x≠4，存在路线2、3、4，总计 x+3 条路线。
4. 若 x=4 且 y=1，存在路线1，总计 2 条路线。
5. 若 y=4 且 x=1，存在路线2，总计 2 条路线。
6. 若 x≥2 且 x≠4 且 y≥2 且 y≠4，存在路线3、4，总计 2 条路线。
7. 若 x=1 且 y≠4，或 y=1 且 x≠4，无任何路线存在，总计 0 条路线。

[广告] 安装Alexa工具条，提高轩辕排名，支持轩辕发展！