自然数处理算法题

题目

问题描述:

要求找出具有下列性质数的个数(包含原数n)

输入一个自然数n(1<=n<=1000),对此自然数按照如下方法进行处理:

  1. 不作任何处理;
  2. 在它的左边加上一个自然数,但该自然数不能超过原数的一半;
  3. 加上数后,继续按照这个规则进行处理,直到不能再加数为止

举个例子:

比如输入的自然数n为6

经过上述规则处理后,一共有6个数满足所需的性质,它们分别是:

6
16
26
126
36
136

因此,输出结果为6.

输入

有N个测试用例
【输入】 N+1 行
第一行一个数N,表示测试用例个数
以下N行,每行一个数,代表每一个用例的输入数字

输出

每行一个数,代表每一用例的结果

分析

首先,我们来看一下问题规模:

输入一个自然数n(1<=n<=1000)

最大规模是1000,可不可以用穷举呢?

注意到用穷举的话,问题的时间复杂度为O(n^2),肯定会超时。所以不能用穷举。

思考一下用穷举算法时,哪些步骤是重复计算的。

假设当前输入是100,那么某个输出为:

100
1100
2100
12100
...

我们用“

Compra Minocin Online

,”号分隔一下新增的数字,如下:

100
1,100
2,100
1,2,100

注意到其中的:

2
1,2

正是我们求2的排列时的结果。也就是说:

f(1000) = 1 + f(500) + f(250) + f(125) + ... + f(1)

于是我们可以用递推来写。

注意到求f(250)时,会计算f(125),如果算完之后遇到f(125)时(例如计算f(500))再算一次的话,就重复计算了。所以我们可以用一个数组来保存中间结果,即

cache = [f(1), f(2), ... , f(1000)]

再注意到,问题规模最大为1000,就是说cache只需500就行了(f(1000)只会算一次,不用保存)。

再思考一下,由于题目要求“该自然数不能超过原数的一半”,所以当输入为奇数时,结果跟前一个数(偶数)的结果是相同的。所以cache可以再缩一半。

好了,我们可以用代码实现之。

代码实现:

#include<stdio.h>

int cache[251];

int process(int next) {
    if(next != 1000 && cache[next/2] != 0) {
        return cache[next/2];
    }
    int count = 1;
    int i;
    for(i = next/2; i >= 1 ; i--) {
        cache[i/2] = process(i);
        count += cache[i/2];
    }
    return count;
}

int main()
{
    memset(cache,0,sizeof(cache));

    int N;
    scanf("%d", &N);
    int i;
    for(i = 0; i < N; i++) {
        int cur;
        scanf("%d", &cur);
        printf("%d\n", process(cur));
    }
    return 0;
}

发表评论

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据