[itint5]跳马问题加强版

http://www.itint5.com/oj/#12

首先由跳马问题一,就是普通的日字型跳法,那么在无限棋盘上,任何点都是可达的。证法是先推出可以由(0,0)到(0,1),那么由对称型等可知任何点都可以到了。

加强版是可以跳到(p,q),当然对称的也可以跳到(q,p)。那么接下来是数学推导:http://www.itint5.com/discuss/16/%E8%B7%B3%E9%A9%AC%E9%97%AE%E9%A2%98%E5%8A%A0%E5%BC%BA%E7%89%88

1. 计算dx=x-x2,dy=y-y2。
2. 求出p,q的最大公约数g,如果dx或者dy不能被g整除,那么很显然无解。
3. 将p,q,dx,dy都除以g,现在p和q互质了。
4. 注意到马可以跳到点(0,2p)(先(p,q)跳一下,然后(p,-q)跳一下),重复这个过程,马可以跳到任意(0,2kp)的点,由于对称性,也可以跳到任意(2kp,0)的点。
5. 下面这一步很关键,由于p,q互质,那么存在x,y满足px+qy=1(扩展欧几里德定理)。这样,马可以跳到(0,2)和和(2,0),由于对称性,马可以跳到任意坐标都为偶数点。[因为在一条线上可以前进2p和2q为单位,那么组合后可以到任意2n]
6. 有了上面的结论,其实只用考虑(0,0),(0,1),(1,0),(1,1)这4个点是否可达。(0,0)是可达的,(0,1)和(1,0)由于对称性只用考虑(0,1)。
7. 对于(1,1),其实是永远可达的。如果q,p都为奇数,可以先跳到(1+p,1+q)的点(利用5中的结论),然后(-p,-q)跳到(1,1)。如果p,q一奇一偶,可以先跳到(1+p+q,1+q+p)的点(利用5中的结论),然后(-p,-q),(-q,-p)两步跳到(1,1)。[因为1+q和1+p都是偶数]
8. 对于(0,1),如果p,q一奇一偶,那么也是永远可达的(同7可证)。如果p,q都是奇数,那么是不可能跳到(0,1)的,因为两个奇数不管怎么加减交替运算都不可能变成一奇一偶。[因为规则是p和q可以调换,所以根据奇偶性(0,1)可达。而全部是奇数,那么只能由(奇,奇)到(偶,偶)或反之]
所以最后的结论就是:第3步之后,如果p,q一奇一偶,那么可达。否则dx,dy同奇或同偶才可达。

注:扩展欧几里得定理:

对于与不完全为 0 的非负整数 a, b; gcd(a, b)表示 a,b 的最大公约数。那么存在唯一的整数 x,y 使得 gcd(a, b)=ax+by。互质时有px+qy=1。

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
 
bool canJump(int p, int q, int x, int y, int x2, int y2) {
    if (p == 0 && q == 0) return (x == x2) && (y == y2);
    int dx = x2 - x;
    int dy = y2 - y;
    int g = gcd(p, q);
    if (dx % g != 0 || dy % g != 0) return false;
    dx /= g;
    dy /= g;
    p /= g;
    q /= g;
    if ((dx - dy) % 2 == 0) return true;
    if ((p - q) % 2 != 0) return true;
    return false;
}

  

[itint5]跳马问题加强版

上一篇:二零一三年终总结,二十四的我,如何去做?


下一篇:【Flutter】Flutter 混合开发 ( Flutter 与 Native 通信 | Android 端实现 BasicMessageChannel 通信 )(一)