用C语言给出一个整数n,问是否可以通过以下两种操作将n变为m n=n×2 n=n×3 若可以,请输出最小的操作次数,若不可以,输出−1。 输入格式: 输入的第一行给出两个整数n,m。 1≤n≤m≤5×10 8 输出格式: 输出一个整数,表示n变为m的最小次数,若不可以,输出−1。
时间: 2024-02-12 07:06:08 浏览: 41
好的,这是一道简单的搜索题目,我们可以使用广度优先搜索(BFS)来解决。
以下是 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXN 50000010
int n, m;
bool vis[MAXN] = { false }; // 标记是否访问过
int step[MAXN] = { 0 }; // 记录到达该数的步数
int Queue[MAXN]; // 定义队列
int head = 0, tail = 0;
void bfs(int n)
{
Queue[tail++] = n;
vis[n] = true;
step[n] = 0;
while (head < tail)
{
int x = Queue[head++];
if (x == m)
{
printf("%d\n", step[x]);
return;
}
if (x * 2 <= m && !vis[x * 2])
{
vis[x * 2] = true;
step[x * 2] = step[x] + 1;
Queue[tail++] = x * 2;
}
if (x * 3 <= m && !vis[x * 3])
{
vis[x * 3] = true;
step[x * 3] = step[x] + 1;
Queue[tail++] = x * 3;
}
}
printf("-1\n"); // 无法到达 m
}
int main()
{
scanf("%d%d", &n, &m);
bfs(n);
return 0;
}
```
我们使用 vis 数组记录某个数是否访问过,step 数组记录到达该数的步数。使用 Queue 数组实现队列,head 和 tail 分别表示队列的头和尾。在 BFS 的过程中,我们从队列头部依次取出一个数 x,然后分别尝试将 x 乘以 2 和 3,如果得到的结果没有超过 m,同时没有访问过,我们就将其加入队列中,同时记录访问次数。如果最终无法到达 m,就输出 -1。
注意:我们需要开辟足够的数组空间,否则会出现“段错误”等问题。