資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
