Vijos1130. 數的計數

試題請參見: https://vijos.org/p/1130

題目概述

我們要求找出具有下列性質數的個數(包含輸入的自然數n): 先輸入一個自然數n(n≤1000)，然後對此自然數按照如下方法進行處理

1. 不作任何處理;

2. 在它的左邊加上一個自然數，但該自然數不能超過原數的一半;

3. 加上數後，繼續按此規則進行處理，直到不能再立生自然數為止.

輸入

一個自然數n.

輸出

一個整數, 總的個數.

解題思路

我不得不說, 這題意叙述得實在是...非常棒! 舉個栗子說: 若n = 6, 則會有如下再生數:

    6, 16, 26, 126, 36, 136

提取目前這個數的最高位x, 這個數可能産生的再生數的個數為x / 2.

将最終結果加上x / 2即可.

遇到的問題

一道AC率為83%的題貌似不會遇到什麼問題 0 0

源代碼

#include <iostream>

void getNumbers(int n, int& counter) {
    counter += n / 2;
    for ( int i = 1; i <= n / 2; ++ i ) {
        getNumbers(i, counter);
    }
}

int main() {
    int n = 0, counter = 1;

    std::cin >> n;
    getNumbers(n, counter);
    std::cout << counter << std::endl;

    return 0;
}