单数集问题

小鱼儿 2022-08-05 02:54 209阅读 0赞

问题描述：给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下：

（1）set(n)中包含n；

（2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；

（3）按此规则进行处理，直至不能添加自然数为止。

例如，set(6)=\{6,16,26,126,36,136\}。

编程任务：对于给定的自然数n，编程计算半数集set(n)中元素的个数。

注意：该半数集是多重集。

参考代码：

//递归算法

#include<stdio.h>
    int banshuji(int n)
    {
    	int i;
    	int count=0;
    	if(n>1)
    	{
    		for(i=n/2;i>0;i--)
    		{
    			count+=banshuji(i);
    		}
    	}
    	return count+1;
    }
    int main()
    {
    	int i,j;
    	int n;
    	scanf("%d",&n);
    
    	printf("%d\n",banshuji(n));
    
    	return 0;
    }

算法改进：

猜想一：奇数的半数集合元素个数等于其前一个偶数的半数集合元素的个数

即：

f(n)=f(n-1)      (n%2==1)

这样一来，奇数的半数集合元素个数问题就转化为了求偶数的半数集合元素个数问题。

猜想二：偶数的半数集合元素个数等于其前一个数的半数集合元素个数加上其半数的半数集合元素个数。

等价公式的证明：

![Image 1][]

算法改进：

猜想一：奇数的半数集合元素个数等于其前一个偶数的半数集合元素的个数

即：

f(n)=f(n-1)      (n%2==1)

这样一来，奇数的半数集合元素个数问题就转化为了求偶数的半数集合元素个数问题。

猜想二：偶数的半数集合元素个数等于其前一个数的半数集合元素个数加上其半数的半数集合元素个数。

等价公式的证明：

![SouthEast][]

<span style="font-size:18px;">//改进后的算法</span>

<span style="font-size:18px;">#include<stdio.h>
    int*a;
    int banshuji(int n)
    {
    	int i;
    	for(i=2;i<=n;i++)
    	{
    		if(i%2)
    			a[i]=a[i-1];
    		else
    			a[i]=a[i-1]+a[i/2];
    	}
    	return a[n];
    }
    int main()
    {
    	int i,j;
    	int n;
    	scanf("%d",&n);
    	a=new int[n+1];
    	for(i=0;i<=n;i++)
    		a[i]=0;
    	a[1]=1;
    	printf("%d\n",banshuji(n));
    	return 0;
    }
    </span>

测试结果：

![SouthEast 1][]

[Image 1]: 
[SouthEast]: /images/20220805/c09d1fbf171e43298f60747aa2ef93b0.png
[SouthEast 1]: /images/20220805/7f38495cc6744a3fa229a9a804995a7d.png