我们可以使用以下技术来找到乘以 X 或将其数字从 1 右旋转到 N 的最便宜方法。要监控初始最低成本，请创建一个成本变量。当从 N 到 1 时，检查每个阶段 N 是否被 X 整除。如果是，则将 N 除以 X 来更新它并继续该过程。如果 N 不能被 X 整除，则将 N 的数字向右循环以增加其值。在这种情况下增加成本变量。最终的成本变量值将是将 1 变为 N 所需的最少数量。该算法有效地确定使用数字旋转或乘法进行所需转换所需的最少操作。
使用的方法
Naive Approach: 数字的右旋转
高效方法：乘以 X
简单的方法：数字右旋
天真的方法是从数字1开始，反复将其数字向右旋转，直到达到目标数字N。在每次旋转中，最后一位数字变为第一位数字。虽然概念上简单，但对于较大的N值来说，这种策略可能效率低下，可能需要许多步骤才能达到目标数字。随着N的增加，旋转次数也迅速增加，使其成为确定将1转换为N的最小成本的方法效果较差。由于其低效性，不建议在大N值的情况下使用这种方法，而其他方法，如将N除以X，被证明在找到转换的最低成本方面更有效。
算法
创建变量“cost”来跟踪到达 N 所需的步骤，并将其初始化为 1 以表示当前值。
按照这些指令重复操作，直到当前数字等于N：
将当前数字的数字向右旋转，使最后一位数字成为第一位数字。
通过增加“cost”变量1来记录所需旋转的次数。
一旦当前数字等于 N，“cost”变量将存储使用右旋转将原始整数 (1) 旋转到 N 所需的最少步骤。
示例
#include <iostream>
#include <cmath>
int rotateDigits(int num, int numDigits) {
return (num / 10) + (num % 10) * std::pow(10, numDigits - 1);
}
int main() {
int N = 123; // Replace this with your desired N value
int current = 1;
int cost = 0;
bool found = false;
while (current != N) {
int numDigits = std::to_string(current).length();
current = rotateDigits(current, numDigits);
cost++;
if (cost > N) {
std::cout << "N cannot be reached from 1 using right rotations." << std::endl;
found = true;
break;
}
}
if (!found) {
std::cout << "Minimum steps to reach N: " << cost << std::endl;
}
return 0;
}
输出
N cannot be reached from 1 using right rotations.
高效方法：乘以X
将1乘以N的成本最小化的最佳方法是将N周期性地除以X，直到结果为1。为了实现这一点，初始化一个成本变量来监视最低成本。我们通过从N的值开始确定N是否可以被X整除。如果N和X都可以整除，成本增加并进行除法运算。重复这个过程，直到N等于1。这种方法比“数字右旋转”更高效，因为它需要更少的步骤才能得到结果1。由于其更快和更有效的特性，它是确定最低转换成本的首选方法。
算法
要跟踪最低成本，请将变量“cost”初始化为 0。
从给定的目标数N开始，使用固定的乘数X。
只要N大于1，重复步骤4到6。
假设N% X == 0，判断N是否能被X整除。
如果 N 可整除（N = N / X），则将 N 除以 X，然后向“cost”变量加 1。
如果不可整除，则将 N 的数字向右循环（通过将最后一位数字移至第一位）并将“成本”增加 1。
在N变为1之前，重复步骤3到6。
最后一个"cost"表示乘以X或将数字右移以将1变为N所需的最低要求。
示例
#include <iostream>
#include <cmath>
int main() {
int X = 3;
int N = 100;
int cost = 0;
while (N > 1) {
if (N % X == 0) {
N /= X;
cost++;
} else {
int lastDigit = N % 10;
N = (N / 10) + (lastDigit * std::pow(10, std::floor(std::log10(N))));
cost++;
}
}
std::cout << "Final cost: " << cost << std::endl;
return 0;
}
输出
Final cost: 2
结论
总而言之，在确定通过乘以 X 或右旋转数字来将 1 转换为 N 的最低成本时，乘以 X 的有效方法超越了数字右旋转的朴素方ૢ
.........................................................