C++ 给定一个分数在给定的小数点之后找到数字c的第一次出现

一个分数的小数展开是该分数值的小数表示。在下面的文章中，我们讨论了两种方法来找到a/b分数中c的第一次出现。

问题描述

给定三个整数a、b、c，在小数点后找到分数a/b中数字c的第一次出现的位置。如果不存在，则打印-1。

示例示例

输入

a = 5, b = 6, c = 3

输出

解释
$\frac{a}{b}=\frac{5}{6}=0.83333$

因此c=3出现在小数点后的第2位。因此输出为2。

输入

a = -10, b = 25, c = 4

输出

解释
$\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。

单纯的解法思路

基本思想是在除以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的值
调用find_first_occurrence函数，参数为a，b和c
打印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;
}