MEGChai MEGChai
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
首页 › 数据结构与算法 › 在线评测 › UVaOJ 202 - Repeating Decimals
AOAPC II

UVaOJ 202 - Repeating Decimals

Chai
2021-11-24 0:00:00在线评测阅读 303

问题描述

p202

原题链接:UVaOJ 202 - Repeating Decimals

相关说明:本题为《算法竞赛入门经典(第2版)》习题 3-8

解法一:模拟(数论)

这题虽然输入输出是字符串,但本质上是一个模拟除法过程,求循环节长度的数论题。

核心结论是:如果在模拟除法计算的过程中,出现了相同的余数(Remainder),则表明商(Quotient)的循环节完成了。

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  const int MAX_LEN = 50;
  int numerator, denominator;
  while (cin >> numerator >> denominator) {
    cout << numerator << "/" << denominator << " = ";
    vector<int> index(denominator, -1), quotient;
    quotient.push_back(numerator / denominator);
    int remainder = numerator % denominator, pos = 0;
 
    while (remainder && index[remainder] == -1) {
      index[remainder] = pos++;
      quotient.push_back(remainder * 10 / denominator);
      remainder = remainder * 10 % denominator;
    }
 
    int cur_index = 0;
    cout << quotient[cur_index++] << ".";
 
    if (remainder) {
      while (cur_index <= pos && cur_index <= MAX_LEN) {
        if (cur_index == index[remainder] + 1) cout << "(";
        cout << quotient[cur_index++];
      }
      cout << (pos < MAX_LEN ? ")\n" : "...)\n");
    } else {
      while (cur_index <= pos) cout << quotient[cur_index++];
      cout << "(0)\n";
    }
 
    cout << "   " << (remainder ? pos - index[remainder] : 1)
         << " = number of digits in repeating cycle\n\n";
  }
  return 0;
}
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
MAX_LEN = 50
while True:
    try:
        numerator, denominator = map(int, input().split())
        print("{numerator}/{denominator}", end="")
        index = [-1 for _ in range(denominator)]
        quotient = [numerator // denominator]
        remainder = numerator % denominator
 
        pos = 0
        while remainder and index[remainder] == -1:
            index[remainder] = pos
            quotient.append(remainder * 10 // denominator)
            remainder = remainder * 10 % denominator
            pos += 1
 
        cur_index = 0
        print("{quotient[cur_index]}.", end="")
 
        cur_index += 1
        if remainder:
            while cur_index <= pos and cur_index <= MAX_LEN:
                if cur_index == index[remainder] + 1:
                    print("(", end="")
                print("{quotient[cur_index]}.", end="")
                cur_index += 1
            print(")" if pos < MAX_LEN else "...)")
        else:
            while cur_index <= pos:
                print("{quotient[cur_index]}.", end="")
                cur_index += 1
            print("(0)")
 
        res = pos - index[remainder] if remainder else 1
        print("   {res} = number of digits in repeating cycle\n")
 
    except EOFError:
        break
AOAPC II UVaOJ 字符串 数论
赞赏 赞(0)
订阅
提醒
guest
guest
0 评论
内嵌评论
查看所有评论
  • 0
  • 0
Copyright © 2020-2023 MEGChai.
  • 文章
    • 随笔
    • 笔记
    • 教程
  • 关于
# 生活 # # 心理 # # 编程 # # 音乐 # # 写作 #
Chai
95
文章
4
评论
58
喜欢
wpDiscuz