2025年36数字游戏

科技前沿 • 2025-03-12 14:49 • 阅读 19

大家好，我是讯享网，很高兴认识大家。

题目描述

有一天，小明给佳佳出了一道题，
给出一个正整数n，佳佳可以进行如下三种操作：
1、使n减去1
2、如果n是2的倍数，使n除以2
3、如果n是3的倍数，使n除以3
问佳佳最少可以通过几步操作，将n变为0。
为了考验佳佳的知识水平，小明给出了T个数字n1,n2,…,nT，让佳佳对每个数字都给出答案。然而佳佳一心只想着晚上吃啥，想让聪明的你来帮助他解决这个问题，并答应解决后请你吃饭，于是你义不容辞地接下了这个任务。

输入

输出

共T行，每行一个数字，第i行为对于ni的答案。

样例输入 Copy

2 7 10

讯享网

样例输出 Copy

讯享网

讯享网4 4

提示

【样例解释】
7->6->2->1->0
10->9->3->1->0

【数据范围】
对于40%的数据，T≤10，ni≤30
对于70%的数据，T≤20，ni≤1000
对于100%的数据，T≤20，ni≤

错误代码，超时

思路：dfs求出所有可能的组合，sort排序，再输出最小的

 #include <iostream> #include <cstring> #include <algorithm> using namespace std; int t; int n; int ans[]; int o=0; int h[]; void dfs(int n,int u) { if(n==0) { ans[++o]=u; return; } if(h[n]>0) { ans[++o]=u+h[n]; return; } if(n%2==0) { dfs(n/2,u+1); } if(n%3==0) { dfs(n/3,u+1); } dfs(n-1,u+1); } int main() { cin>>t; for(int k=1;k<=t;k++) { cin>>n; o=0; dfs(n,0); sort(ans+1,ans+1+o); cout<<ans[1]<<endl; h[n]=ans[1]; } return 0; }

思路二：dp

讯享网#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 1e6+10; int f[N]; void init() { f[0]=0,f[1]=1; for(int i=2;i<=N;i++) { f[i]=f[i-1]+1; if(i%2==0) f[i]=min(f[i],f[i/2]+1); if(i%3==0) f[i]=min(f[i],f[i/3]+1); } } int main() { int t,x; cin>>t; init(); while(t--) { cin>>x; cout<<f[x]<<endl; } return 0; }

2025年36数字游戏

相关推荐