最少次数
有一个整数 A=2021,每一次,可以将这个数加 1 、减 1 或除以 2,其中除以 2 必须在数是偶数的时候才允许。
例如,2021 经过一次操作可以变成 2020、2022。
再如,2022 经过一次操作可以变成 2021、2023 或 1011。
请问,2021 最少经过多少次操作可以变成 1。
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int ans=1e9;
int vis[10000];
void dfs(int n,int time){
vis[n]=1;
if(n==1){
ans=min(time,ans);
return;
}
if(n%2==0&&vis[n/2]==0){
dfs(n/2,time+1);
}
if(vis[n+1]==0){
dfs(n+1,time+1);
}
if(vis[n-1]==0){
dfs(n-1,time+1);
}
}
int main(){
dfs(2021,0);
cout<<ans<<endl;
return 0;
}