数的计算(数的计数)

题目描述

我们要求找出具有下列性质数的个数(包含输入的自然数n)。先输入一个自然数n(n<=1000),然后对此自然数按照如下方法进行处理:

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

例如:

输入:  6

           满足条件的数为  6 (此部分不必输出)

                          16

                          26

                         126

                          36

                         136

输出:  6

输入

只有一行一个整数，为自然数n（n<=1000）

输出

输出满足条件数的个数

样例输入

样例输出

分析

手动按照上述过程进行计算，会发现这是个递归的过程，对每一个原始数字m，在前面加i(1,2,3,...m/2)，即h(n)=1+h(1)+f(2)+...+h(n/2)，对于每一个i，要按照同样的规则进行，这用递归可以实现（见例程1），递归过程中，每遇到一个原始数，计数器加1，用来统计个数。
例程1在OJ中会显示超时，这是必然的，当n很大时，递归的过程就会很长，这主要源于其中会做大量的重复计算，每次计算h(n)，都要重复计算h(1)....h(n/2)，这样的问题在使用递归计算斐波那契数f(n)时，也会遇到，程序效率很低。解决的一个途径是使程序具有记忆功能，已计算出的数字就无需再次计算，直接使用即可。例程2使用数组实现了带记忆功能的递归，可以通过OJ系统。
也可以使用递推的方法来解决问题：已知h(n)=1+h(1)+h(2)+...+h(n/2)，这就是一个递归式，程序写起来很容易（见例程3），两层for循环就可完成，递推比起无记忆的递归来效率要高得多。例程1是指数级的时间复杂度，而例程3的时间复杂度为O(n²)。
问题可以进一步简化。通过对上面的公式进行推导可以发现：n为奇数时，h(n)=h(n-1)，n为偶数时，h(n)=h(n-1)+h(n/2)，看懂了吗，使用这两个公式，可以将时间复杂度降低到O(n)，见例程4。

例程1

#include<iostream>

using namespace std;

int ans;                    //计数器

void dfs(int m){

	ans++;                  //每出现一次原始数，ans++

	for(int i=1; i<=m/2; i++){

		dfs(i);             //递归

	}

}

int main(){

	int n;

	cin>>n;

	dfs(n);

	cout<<ans;

	return 0;

}

例程2

#include<iostream>

using namespace std;

int h[1001];                //记忆数组，存储计算出的h[m]

void dfs(int m){

	if(h[m]!=0)		return; //有记忆，不再递归

	h[m]=1;                 //无记忆，初始化为1，递归累加计算

	for(int i=1; i<=m/2; i++){

		dfs(i);             //递归

		h[m]+=h[i];         //累加

	}

}

int main(){

	int n;

	cin>>n;

	dfs(n);

	cout<<h[n];

	return 0;

}

例程3

#include<iostream>

using namespace std;

int h[1001];

int main(){

    int n;

    cin>>n;

    h[1]=1;                 //初始化第一项h[1]

    for(int s=2;s<=n;s++){  //对第s项

        h[s]=1;             //数字s自己算一个

        for(int i=1;i<=s/2;i++) h[s]+=h[i];

    }

    cout<<h[n];

    return 0;

}

例程4

#include<iostream>

using namespace std;

int main(){

    int n;

    cin>>n;

    h[1]=1;                         //初始化第一项

    for(int i=2; i<=n; i++){

        h[i]=h[i-1];                //递推

        if(i%2==0)  h[i]+=h[i/2];   //i为偶数时

    }

    cout<<h[n];

    return 0;

}

巴特西

LFYZ-OJ ID: 1026 数的计数（数的计算）NOIP2001

数的计算(数的计数)

题目描述

输入

输出

样例输入

样例输出

分析

例程1

例程2

例程3

例程4

最新文章

热门文章