XChiChiX


這不是很戲劇化的發展嗎

d672: 10922 - 2 the 9s

  • ~1.90K 字
  • 次閱讀
  • 則評論
  1. 1. 內容
  2. 2. 範例輸入
  3. 3. 範例輸出
  4. 4. 想法
  5. 5. 程式碼

CPE 一顆星選集 49 道必考題

題目連結:https://zerojudge.tw/ShowProblem?problemid=d672

內容

使用遞迴方法判斷一數 N (可能很大)是否為 9 的倍數，並且求出此遞迴的深度。

遞迴方法(假設 N = 837):
8 + 3 + 7 -> 18 深度:1
1 + 8 -> 9 深度:2(結束)。

當 N = 0 代表輸入結束。

範例輸入

999999999999999999999
9
9999999999999999999999999999998
837
0

範例輸出

999999999999999999999 is a multiple of 9 and has 9-degree 3.
9 is a multiple of 9 and has 9-degree 1.
9999999999999999999999999999998 is not a multiple of 9.
837 is a multiple of 9 and has 9-degree 2.

想法

使用 string 讀取輸入，先進行第一次的運算，得到的數值一定為 int 範圍，之後每次得到新數值都將其轉為 string 型態方便操作(利用 stringstream 進行轉換)，直到數值等於 9 。

像是 999999999999999999999 (string 型態) 即可用字元方式分別取出，得到新數值 189 (int 型態)，此為一個深度。
接者將其轉為 string 型態，189 (string 型態)，用字元方式分別取出，得到新數值 18 (int 型態)。此為第二個深度。
18 (int 型態) -> 18 (string 型態)，得到 9 (int 型態)，此為第三個深度。

程式碼

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
#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(false), cin.tie(nullptr)
using namespace std;

int degree(string);
int main(){
    fastio;
    string s;
    int ans;
    while(cin >> s){
        if(s == "0") break;
        ans = degree(s);
        cout << s << " is ";
        if(ans > 0) cout << "a multiple of 9 and has 9-degree " << ans << ".\n";
        else cout << "not a multiple of 9.\n";
    }
    return 0;
}
int degree(string s1){
    int c = 1, sum = 0;
    stringstream ss;
    string temp;
    for(int i = 0; i < s1.length(); ++i){
        sum += s1[i]-'0';
    }
    while(sum > 10){
        ss << sum, ss >> temp;
        sum = 0;
        for(int i = 0; i < temp.length(); ++i){
            sum += temp[i]-'0';
        }
        ++c;
        ss.str(""), ss.clear();
    }
    if(sum == 9) return c;
    else return 0;
}