数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究给定分数中数字的首次出现
分数的小数展开式是分数值的十进制表示。在以下文章中，我们讨论了两种查找 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 位。因此输出为 2。
输入
a = -10, b = 25, c = 4
输出
1
解释
$$\mathrm{\frac{a}{b}=\frac{-10}{25}=-0.4}$$
所以 c=4 出现在小数点后第 1 位。因此输出为 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。因此，它将显示 c = 7 在第 5 个位置首次出现，而它应该是 -1。
可以通过下面提供的 C++ 程序了解该方法的实现。
示例：C++ 程序
以下程序代码基本上查找小数点后十进制展开式中数字的首次出现。函数 find_first_occurrence() 将 a/b 的十进制展开式存储在变量 q 中。我们将 q 转换为字符串并在字符串上迭代以查找小数点后 c 的首次出现，并将其作为 pos 返回。如果 pos = -1，则表示该数字在小数点后不存在。
// C++ program to find the first occurrence of a number in a fraction
#include <bits/stdc++.h>
using namespace std;
// function to find the first occurrence of c after the decimal point in decimal expansion of a/b
int find_first_occurrence(int a, int b, int c){
// q = quotient = decimal expansion of a/b
float q = (float)a / b;
// convert q to string using to_string() function
string s = to_string(q);
// increment i till we reach decimal point
int i = 0;
while (i < s.length()){
if (s[i] != '.')
{
i++;
}
else
{
break;
}
}
// if decimal point does not exist i.e a is completely divisible by b; return -1 i.e. the position does not exist
if (i >= s.length()){
return -1;
}
// increment i to point to the first value after the decimal point
i = i + 1;
// traverse the string to find the first occurrence of c after the decimal point
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。
主函数
将 a 设置为 22，b 设置为 7，c 设置为 2
打印 a 除以 b 的值
使用参数 a、b 和 c 调用函数 find_first_occurrence
打印 find_first_occurrence 的返回值
示例：C++ 程序
该程序旨在查找分数 a/b 的十进制展开式中小数点后特定数字“c”的首次出现。它将分数约简到其模，然后遍历每个小数位，直到找到数字 c 或达到最大迭代次数以避免无限循环。如果找到该数字，则返回当前迭代计数，否则，函数返回 -1 以指示未找到该数字。
// C++ program to find the first occurrence of a number in a fraction
#include <iostream>
using namespace std;
// function to find the first occurrence of c after the decimal point in decimal expansion of a/b
int find_first_occurrence(int a, int b, int c){
// Reduce the number to its mod
while (a >= b){
a -= b;
}
// Traverse for every decimal place
int i = 1;
int q = a / b;
int max_iterations = 1000; // set a maximum number of iterations to avoid an infinite loop
while (a != 0 && i <= max_iterations) {
a = (a % b) * 10;
q = a / b;
if (q == c) {
return i;
}
i++;
}
// If digit not found
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++ 程序解决方案以及时间和空间复杂度分析进行了详细解释。
96 次查看
