极客笔记C++ 通过乘以X或将数字右旋，将1转换为N的最小费用
我们可以使用以下技术来找到从1到N乘以X或右旋数字的最便宜的方式。为了监控最低初始成本，创建一个成本变量。在从N到1的过程中，检查N是否可以被X均匀地整除。如果可以，将N除以X来更新它并继续进行过程。如果N不能被X整除，则将N的数字向右旋转以增加它的值。在这种情况下增加成本变量。最终的成本变量值将是将1转换为N所需的最少量。该算法有效地确定使用数字旋转或乘法进行所需转换的最少操作。
使用的方法
- Naive方法：数字的右旋
-
高效方法：乘以X
Naive方法：数字的右旋
Naive方法涉及从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。由于其更快捷和更有效的特性，这是计算最低转换成本的首选方法。
步骤
- 为了跟踪最低成本，将变量“成本”初始化为0。
-
从固定乘数X和给定的目标数N开始。
-
只要N大于1，重复步骤4到6。
-
假设
N%X==0，判断N是否可以被X整除。 -
如果可以被整除，将N除以X(N=N/X)，并将“成本”变量加一。
-
如果不能被整除，将N的数字向右旋转（将最后一位移到第一位），并将“成本”增加一。
-
重复步骤3到6，直到N变为1。
-
最后的“成本”表示乘以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的最低成本。高效的方法提供了更简化的步骤，来达到想要的数字N。而天真方法可能会无效且耗时，特别是对于较大的N值。通过使用高效的方法，我们可以减少所需的步骤，并确定将1转换为N的最经济的方法。这种策略解决了确定此转换过程的最低成本的问题，并且被证明是一种更有用和有效的算法。