g****y
发帖数: 323 | 1 有一个地区有有限个城堡, 每个城堡都有三条路相通, 且路和路之间
不相通, 也就是说不能从一条路走到另一条路上而不经过城堡. 现在
有一个伟大的骑士从一个城堡出发了. 不久他到达了下一个城堡.
OK他现在遵循下列原则, 以他进入城堡的路的方向为基准, 相对来说
有左边的一条路和右边的一条路之分, 如果他在上一个城堡选择了走
左边, 这次就要走右边. 同理, 上次右边, 这次左边. 求证, 骑士总
能回到他所出发的城堡. (第一次的选择随意啦) | C******a
发帖数: 115 | 2 假设第k次走过的城堡是f(k)，出发时的是f(0)。
如果知道任意连续的三个城堡f(n), f(n+1)和f(n+2)，
那么其它所有的f(k)都可以知道，而且f(k)只依赖于
上述三个城堡和k-n的值，可以是负值，也即是
f(k)=g(k-n,f(n),f(n+1),f(n+2)), g与n, k无关。
因为城堡数是有限的，所以三个城堡的组合数也是有限的。
因此存在n
所以f(0)=g(-n,f(n),f(n+1),f(n+2))
=g(-n,f(m),f(m+1),f(m+2))=f(m-n)。
【在 g****y 的大作中提到】
: 有一个地区有有限个城堡, 每个城堡都有三条路相通, 且路和路之间
: 不相通, 也就是说不能从一条路走到另一条路上而不经过城堡. 现在
: 有一个伟大的骑士从一个城堡出发了. 不久他到达了下一个城堡.
: OK他现在遵循下列原则, 以他进入城堡的路的方向为基准, 相对来说
: 有左边的一条路和右边的一条路之分, 如果他在上一个城堡选择了走
: 左边, 这次就要走右边. 同理, 上次右边, 这次左边. 求证, 骑士总
: 能回到他所出发的城堡. (第一次的选择随意啦)
| g****y
发帖数: 323 | 3 不知道大家是不是看懂了Catalina的解释. 还是用文字来叙述可能更
好理解一些. 按照一定的规则, 在本题中, 按照我的规则, 如果知道
了骑士通过的任意三个连续的城堡, 即两条城堡之间的路, 那么我们
就可以推之他以后的路径和以前的路径, 当然也就知道了所通过的城
堡. 城堡的数目是有限的, 城堡之间的相互组合的数目(三个城堡之
间的组合, 有顺序组合)也是有限的, 在足够多的组合之后, 必然出
现两次相同的三城堡组合, 其中一次出现的早, 一次晚. 由早的那一
次往钱推, 可以推出起始点, 由晚的那一次推, 也可以推出起始点,
而且这两次推出的起始点是不一样的, 或者说, 由晚的那一次推出的
就是第二次经过的起始点. 为什么, 大家可以想一想, 很简单的说(
路径唯一).
【在 C******a 的大作中提到】
: 假设第k次走过的城堡是f(k)，出发时的是f(0)。
: 如果知道任意连续的三个城堡f(n), f(n+1)和f(n+2)，
: 那么其它所有的f(k)都可以知道，而且f(k)只依赖于
: 上述三个城堡和k-n的值，可以是负值，也即是
: f(k)=g(k-n,f(n),f(n+1),f(n+2)), g与n, k无关。
: 因为城堡数是有限的，所以三个城堡的组合数也是有限的。
: 因此存在n: 所以f(0)=g(-n,f(n),f(n+1),f(n+2))
: =g(-n,f(m),f(m+1),f(m+2))=f(m-n)。
|
|
