求从坐标零点到坐标n点点最小步数,一次只能沿横坐标轴向左或者向右移动2或者3
时间: 2023-09-27 22:02:48 浏览: 68
要求从坐标零点到坐标n点的最小步数,一次只能沿横坐标轴向左或者向右移动2或者3。
设f(n)为到达坐标n点的最小步数。那么f(n)可以由f(n-2)和f(n-3)得到:
当n为偶数时,可以通过f(n-2)再向右移动两步到达坐标n点,所以f(n) = f(n-2) + 1;
当n为奇数时,可以通过f(n-3)再向右移动三步到达坐标n点,所以f(n) = f(n-3) + 1。
现在来考虑边界情况:当n为0时,只需要原地不动,所以f(0) = 0;
当n为1时,只能向右移动三步到达坐标1点,所以f(1) = 1;
当n为2时,只能向右移动两步到达坐标2点,所以f(2) = 1;
当n为3时,只能向右移动三步到达坐标3点,所以f(3) = 1。
按照以上递推关系,可以通过计算得到f(n)的最小步数。最终的结果就是f(n)。
例如,求从坐标零点到坐标9点的最小步数,可以得到:
f(0) = 0;
f(1) = 1;
f(2) = 1;
f(3) = 1;
f(4) = f(2) + 1 = 1 + 1 = 2;
f(5) = f(3) + 1 = 1 + 1 = 2;
f(6) = f(4) + 1 = 2 + 1 = 3;
f(7) = f(5) + 1 = 2 + 1 = 3;
f(8) = f(6) + 1 = 3 + 1 = 4;
f(9) = f(7) + 1 = 3 + 1 = 4;
所以从坐标零点到坐标9点的最小步数为4步。
阅读全文