二上

物件導向程式設計︱HW4

計算階乘並計算數字的出現次數

題目敘述

略

答題思路

使用動態規劃(Dynamic Programing)的方式計算階乘，並將每個數字轉換成字串，再計算字串中數字m出現的次數。這種方式可以避免重複計算，並且可以快速的計算出階乘的值。

需要注意的是，當n很大時，階乘的值會很大，可能會超過int的範圍，因此需要使用大數運算的方式來計算階乘。

參考答案 

 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 <iostream>
#include <vector>
#include <string> 

using namespace std;

int main() {
    int n, m;
    vector<int> fac{1};
    while(cin >> n >> m and n != 0) {
        for(int i=fac.size(); i<=n; i++) {
            fac.push_back(fac.back() * i);
        }
        
        int count = 0;
        for(int i=1; i<=n; i++) {
            string s = to_string(fac[i]);
            for(auto &c: s) {
                if(c - '0' == m) count++;
            }
        }
        cout << count << endl;

        /* C++11 */
        // #include <algorithm>
        // #include <numeric>
        // vector<int> count(n+1);
        // transform(fac.begin()+1, fac.begin()+n+1, count.begin(), [m](int x) {
        //     string s = to_string(x);
        //     return count_if(s.begin(), s.end(), [m](char c) {
        //         return c - '0' == m;
        //     });
        // });
        // cout << accumulate(count.begin(), count.end(), 0) << endl;
    }
    return 0;
}