给定分数中数字的第一次出现
分数的十进制展开是分数值的十进制表示。在下文中，我们将讨论两种在 a/b 中查找 c 第一次出现的方法。
问题陈述
给定三个整数 a、b、c，在小数点后找到分数 a/b 中 c 的第一个实例。如果不存在，则打印 -1。
示例
输入
a = 5, b = 6, c = 3
输出
2
解释
$$\mathrm{\frac{a}{b}=\frac{5}{6}=0.83333}$$
所以 c=3 出现在小数点后第二位。因此输出为 2。
输入
a = -10, b = 25, c = 4
输出
1
解释
$$\mathrm{\frac{a}{b}=\frac{-10}{25}=-0.4}$$
所以 c=4 出现在小数点后第一位。因此输出为 1。
输入
a = 47, b = 9, c = 3
输出
-1
解释
$$\mathrm{\frac{a}{b}=\frac{47}{9}=5.222}$$
因此，小数点后的任何位置都不会出现 c=3。它不存在;因此输出为 -1。
简单解决方案方法
基本思想是存储 a 除以 b 后得到的商。我们将得到的结果转换为字符串，并检查小数点后第一次出现 c。这种方法直观且易于理解;但是，当编程语言对答案进行四舍五入时，它会给出错误的结果。
例如，
设 a = 4，b = 6，c = 7
根据这种方法，a/b = 4/6 = 0.66667。因此，它将在第 5 位显示 c = 7 的第一次出现，而它应该是 -1。
可以通过下面提供的 C++ 程序来理解该方法的实现。
示例:C++ 程序
以下程序代码基本上是在小数点后的小数扩展中查找数字的第一次出现。函数 find_first_occurrence() 将 a/b 的小数扩展存储在变量 q 中。我们将 q 转换为字符串并遍历字符串以查找小数点后 c 的第一次出现并将其返回为 pos。如果 pos = -1，则表示小数点后不存在该数字。
// C++ 程序用于查找分数中数字的第一次出现
#include <bits/stdc++.h>
using namespace std;
// 函数用于在 a/b 的十进制扩展中查找小数点后第一次出现 c 的位置
int find_first_occurrence(int a, int b, int c){
// q = 商 = a/b 的十进制扩展
float q = (float)a / b;
// 使用 to_string() 函数将 q 转换为字符串
string s = to_string(q);
// 增加 i 直到到达小数点
int i = 0;
while (i < s.length()){
if (s[i] != '.')
{
i++;
}
else
{
break;
}
}
// 如果小数点不存在，即 a 完全可以被 b 整除;返回 -1，即该位置不存在
if (i >= s.length()){
return -1;
}
// 增加 i 以指向小数点后的第一个值
i = i + 1;
// 遍历字符串以查找小数点后第一次出现 c 的位置
for (i; i < s.length(); i++){
if (s[i] == (c + '0')){
break;
}
}
return i - 1;
}
// main function
int main(){
int a = 22;
int b = 7;
int c = 2;
int pos = find_first_occurrence(a, b, c);
if (pos != -1){
cout << "The digit " << c << " first occurs at position " << pos << " after the decimal point.";
}
else{
cout << "The digit " << c << " is not found in the decimal expansion of the fraction " << a << "/" << b;
}
return 0;
}
输出
The digit 2 first occurs at position 3 after the decimal point.
时间和空间复杂度
O(d)其中 d 是 a/b 十进制展开式中小数点后的位数。
高效的解决方法
这种简单的方法有一个缺点，即程序会对商进行四舍五入，从而引入不应该出现在 a/b 十进制展开式中的整数值，因为在某些情况下，它可能会产生不正确的结果，如上所述。
一种有效的方法是首先将分数减少为其模数 (a %= b)，然后遍历每个小数位，直到找到数字"c"或达到最大迭代次数，以避免无限循环。
while 循环一直运行，直到"a"变为零或达到最大迭代次数。在每次迭代中，小数位是通过将余数 (a % b) 乘以 10，然后取结果与"b"的商 (q = a / b) 来获得的。如果获得的商等于所需数字 c，则函数返回当前迭代次数。
如果在最大迭代次数后仍未找到所需数字 c，则函数返回 -1 以表示未找到该数字。
算法
函数 find_first_occurrence(a, b, c)
当 a 大于或等于 b 时
将 a 设置为 a - b
将 i 设置为 1
将 q 设置为 a 除以 b
将 max_iterations 设置为 1000
当 a 不等于 0 且 i 小于或等于 max_iterations 时，执行以下操作:
将 a 设置为 (a 模数 b) 乘以 10
将 q 设置为 a 除以 b
如果 q 等于 c，则返回 i
增加 i
返回 -1 表示小数点后未找到 c。
main 函数
将 a 设置为 22，将 b 设置为 7，将 c 设置为 2
打印 a 除以 b 的值
使用参数 a、b 和 c 调用函数 find_first_occurrence
打印 find_first_occurrence 的返回值
示例:C++ 程序
此程序旨在查找分数 a/b 的小数扩展中小数点后第一次出现的特定数字"c"。它将分数简化为其模，然后遍历每个小数位，直到找到数字 c 或达到最大迭代次数以避免无限循环。如果找到数字，则返回当前迭代计数，否则，函数返回 -1 以指示未找到数字。
// C++ 程序用于查找分数中数字的第一次出现
#include <iostream>
using namespace std;
// 函数用于在 a/b 的十进制扩展中查找小数点后第一次出现 c
int find_first_occurrence(int a, int b, int c){
// 将数字简化为其模
while (a >= b){
a -= b;
}
//遍历每个小数位
int i = 1;
int q = a / b;
int max_iterations = 1000; // 设置最大迭代次数以避免无限循环
while (a != 0 && i <= max_iterations) {
a = (a % b) * 10;
q = a / b;
if (q == c) {
return i;
}
i++;
}
// 如果没有找到数字
return -1;
}
//main function
int main(){
int a = 22, b = 7, c = 2;
cout << find_first_occurrence(a, b, c);
return 0;
}
输出
3
时间和空间复杂度分析
时间复杂度:O(max_iterations)
给定代码的时间复杂度取决于最大迭代次数 max_iterations 的值。遍历分数小数位的 while 循环最多执行 max_iterations 次。因此，时间复杂度为 O(max_iterations)。
空间复杂度:O(1)
代码的空间复杂度为 O(1)，因为使用的内存量不取决于输入的大小。代码中使用的唯一变量是 a、b、c、i、q 和 max_iterations。所有这些变量都占用恒定空间。
结论
本文讨论了两种在分数小数展开中查找小数点后第一次出现给定数字的方法。为了加深理解，对方法的概念、示例、使用的算法、C++ 程序解决方案以及时间和空间复杂度分析进行了彻底的解释。
