题目描述

地上有一排格子,共 n 个位置。机器猫站在第一个格子上,需要取第 n 个格子里的东西。

机器猫当然不愿意自己跑过去,所以机器猫从口袋里掏出了一个机器人!这个机器人的行动遵循下面的规则:

初始时,机器人位于 11 号格子若机器人目前在 x 格子,那么它可以跳跃到 x−1,x+1,2x 里的一个格子(不允许跳出界)

问机器人最少需要多少次跳跃,才能到达 n 号格子。

输入格式

仅一行,一个正整数,表示 n。

输出格式

仅一行,一个正整数,表示最少跳跃次数。

分析:

题目要求从1到n步数最小,反过来看,就是从n到1步数最小,要步数最小那肯定要能够一直除以2这样才能使步数最小。

所以如果n为偶数的时候就一定要n/2,这样才能让步数变小,如果n为奇数时则n+1或者n-1使得n变为偶数。

#include

#include

using namespace std;

long long n;

long long search(long long n,long long count) //寻找步数最小的

{

if (n < 1)return 100000; //如果n小于1则说明这条路不行,赋值一个大数

if (n == 1)return count; //如果等于1说明这条路可以,返回步数;

else

{

if (n % 2 == 0)

search(n / 2, count + 1); //偶数则除2

else //奇数则加一或者减一寻找

{

long long l=search(n + 1, count + 1);

long long r=search(n - 1, count + 1);

return min(l, r); //返回哪一种路径是步数最少的

}

}

}

int main()

{

cin >> n;

cout<

}

相关文章

评论可见,请评论后查看内容,谢谢!!!
 您阅读本篇文章共花了: