问题 18E: 数的计数

Question

问题 18E: 数的计数
内存限制：128 MB

题目描述
我们要求找出具有下列性质数的个数(包含输入的自然数n):
先输入一个自然数n（n≤1000）, 然后对此自然数按照如下方法进行处理：

1．不作任何处理；

2．在它的左边加上一个自然数，但该自然数不能超过原数的一半；

3．加上数后，继续按此规则进行处理，直到不能再加自然数为止。
输入
输入一个自然数n（n≤1000）
输出
输出具有题目描述性质数的个数

样例输入
6
样例输出
6

满足条件的数分别为 6 16 26 126 36 136

求大2佬指点~

Answer 1

#include <iostream>
using namespace std;

int cnt;

int add(int n)
{
    if (n <= 0) return -1;
    int x = 0;
    int arr[20];
    while (n > 0)
    {
        arr[x++] = n % 10;
        n /= 10;
    }
    if (arr[x - 1] == 1)
    {
        return -1;
    }
    else
    {
        int newnum = 0;
        arr[x] = arr[x - 1] / 2;
        for (int i = x; i >= 0; i--)
        {
            newnum *= 10;
            newnum += arr[i];
        }
        return newnum;
    }
}
int next(int n)
{
    if (n <= 10) return -1;
    int x = 0;
    int arr[20];
    while (n > 0)
    {
        arr[x++] = n % 10;
        n /= 10;
    }
    if (arr[x - 1] <= 1)
    {
        return -1;
    }
    else
    {
        int newnum = 0;
        arr[x - 1] = arr[x - 1] - 1;
        for (int i = x - 1; i >= 0; i--)
        {
            newnum *= 10;
            newnum += arr[i];
        }
        return newnum;
    }
}
int op(int n, int type)
{
    if (type == 0)
    {
        //cout << n << " ";
        cnt = 1;
        op(n, 1);
    }
    else if (type == 1)
    {
        int a = n;
        while (1)
        {
            a = add(a);
            if (a == -1) break;
            op(a, 2);
            //cout << a << " ";
            cnt++;
        }
    }
    else
    {
        int a = n;
        while (1)
        {
            a = next(a);
            if (a == -1) break;
            op(a, 1);
            //cout << a << " ";
            cnt++;
        }     
    }
    return 0;        
}
int main()
{
    int n;
    cin >> n;
    op(n, 0);
    cout << cnt;
    return 0;
}