找规律


无限大的棋盘有一只走‘日’的马呆在0,0处,也是坐标原点,(存在四个象限),给你(x,y)问你要至少跳多少步才能跳过去

不妨设$x>y$

$x\le2y$,可以证明当x和y足够大的时候

$(x+y)\mod3=0$时,我们只需要$\frac{x+y}{3}$步,这些步数由两种跳跃组成,他们分别是(1,2)和(2,1)

$(x+y)\mod 3=1$时,我们选择(1,-2)或者(-2,1)来跳跃,跳跃之后$(x+y)\mod3=0$所以一共需要$\frac{x+y}{3}+1$步

同理$(x+y)\mod 3=2$时一共需要$\frac{x+y}{3}+2$步

综合为需要$\frac{x+y}{3}+((x+y)\mod 3)$步

同样分析出$x>2y$在$x$和$y$足够大的时候,需要$y+\frac{x-2y}{4}\times2+(x-2y)%4$步

那么这个足够大是多少呢?是x>3&&y>3


文章作者: fightinggg
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 fightinggg !
  目录