C++程式：將兩個數字的分數表示為字串格式

給定兩個整數分子和一個分母。我們需要將這兩個整數的分數表示為字串格式。如果某個小數是迴圈的，我們需要用括號來表示其迴圈序列。

演算法（步驟）

以下是執行所需任務的演算法/步驟：

  • 在確定小數部分之前，先確定整數商（小數點前的絕對部分）。

  • 將餘數（分子 % 分母）放入對映中，鍵為餘數，值為該餘數出現的索引位置，以檢視小數部分是否重複。

  • 如果在任何時刻餘數為零，則不存在重複小數。

  • 如果餘數已在對映中出現，則存在重複小數。

示例

假設一個整數為分子'8'，另一個整數為分母'6'。

int numerator = 8, denominator = 6;
res = solve(numerator, denominator);

所以分數是 8/6，也就是 1.333... 所以我們需要輸出 "1.(3)"。括號表示重複的小數部分，如果沒有重複部分，則直接輸出字串值。

我們首先可以計算整數部分並將其儲存在字串中。之後，我們可以使用餘數找到小數部分，直到它變為 0 或直到我們找到一個重複序列。為了找到重複序列，我們可以將餘數儲存在對映中，如果我們在對映中碰巧看到相同的餘數，我們可以確定該序列是重複的。對映中的值部分將是該小數第一次出現的索引，以便我們可以在該索引處放置括號。

#include <iostream>
#include <map>
using namespace std;
string solve(int numerator, int denominator) {
   if (numerator == 0) {
      return "0";
   }
   if(denominator == 0) {
      return "INFINITY";
   }
   string ans = "";
   if ( ((numerator < 0) ^ (denominator < 0)) ) {
      ans+="-";
   }
   numerator = abs(numerator);
   denominator = abs(denominator);
   ans+=to_string(numerator/denominator);
   if(numerator%denominator == 0) return ans;
      ans+=".";
   int remainder = numerator % denominator;
   map<int, int> mp;
   while (remainder > 0) {
      if (mp.find(remainder) != mp.end()) {
         ans += ")";
         ans.insert(mp[remainder], "(");
         break;
      }
      else {
         mp[remainder] = ans.size();
      }
      remainder*=10;
      ans+= to_string(remainder/denominator);
      remainder = remainder % denominator;
   }
   return ans;
}
int main() {
   int numerator = 8, denominator = 6;
   cout << solve(numerator, denominator) << endl;
   return 0;
}

輸出

1.(3)

結論

我們可以看到，使用對映作為雜湊來查詢重複的餘數，並存儲我們可以再次開始序列的索引作為鍵值對中的值，這使得跟蹤和查詢答案變得容易得多。這個問題需要使用正確的資料結構和一些觀察。

更新於：2022年8月10日

瀏覽量 1K+

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.