算法分析与设计——2.8 半数集问题_分治法解决半数集-程序员宅基地

技术标签：算法 c++

问题描述：给定一个自然数n，由自然数n开始可以依次产生半数集set(n)中的数如下：
                 (1)n属于set(n)
                 (2)在n的左边添加一个自然数，但该数不能超过最近添加的数的一半
                 (3)按此规则，直到不能添加为止
                 例如：set(6)={6,16,26,36,126,136}=6

算法设计：对于给定的自然数n，计算set(n)中的元素个数

输入：自然数n

输出：元素个数和元素内容

算法思想：以6为例。按照规则，新加入的数字小于等于6的一半——3。所以6进行一轮，添加了1，2，3三个数字组合为16，26，36。接下来发现只有26和36可以按照规则继续加数字。

根据规则，对每一个数n最多可以添加n/2个数字且不重复，如果把每一个自然数看作树的节点，那么对一棵树上的节点来说都有n/2个子节点。符合分治策略的使用条件。有如下递归式：

根据树的性质，我们可以采用一维数组来遍历set(n)中的元素。

6
6	1
6	2	1
6	3	1

代码如下

#include<iostream>
#include<cstring>
using namespace std;
int a[10^5];

int  set(int n, int i) {
	a[i] = n;
	for (int j = i; j >= 1; j--) {  
		cout << a[j];
	}
	cout << endl;
	int ans = 1;
	for (int k = 1; k <= n / 2; k++) {
		ans += set(k, i + 1);
	}
	return ans;
}

递归的时间复杂度为O(n^n)。

通过递归式，我们发现包含许多重复计算和重复元素。重复计算浪费了很多计算时间。

对此，针对重复计算问题，优化代码如下：

//递归优化
int set_new(int n, int i)
{
	a[i] = n;
	for (int j = i; j >= 1; j--) {  //遍历数组(从后往前)
		cout << a[j];
	}
	cout << endl;
	int ans = 1;
	if (b[n] > 0)return b[n];
	for (int k = 1; k <= n / 2; k++) {
		ans += set(k, i + 1);
	}
	b[n] = ans;
	return ans;
}

对于半数单集问题：

//半数单集
int set_new_new(int n, int i)
{
	a[i] = n;
	for (int j = i; j >= 1; j--) {  //遍历数组(从后往前)
		cout << a[j];
	}
	cout << endl;
	int ans = 1;
	if (b[n] > 0)return b[n];
	for (int k = 1; k <= n / 2; k++) {
		ans += set(k, i + 1);
		if ((i > 10) && (2 * (i / 10) <= i))
			ans -= a[i / 10];
	}
	b[n] = ans;
	return ans;
}

本文链接：https://blog.csdn.net/ray_kong/article/details/120919321

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

Linux下简单的取点阵字模程序_旺仔的博客-程序员宅基地

Linux操作系统下进行简单的图形开发，经常会用到取字模的软件，但是Linux并没有像Windows下的小工具可用，我们也并不希望为了取字模而频繁地切换操作系统。(由于是完全由C语言编写，所以不需要任何修改，这个字库同样可以用在嵌入式环境的Windows操作系统下面)本人结合网上的资料，对这个问题进行了总结，整理了代码，供有需要的朋友使用我参考。转载请注明出处：http://blog.cs

11g RAC OCR备份与恢复_cijinli4767的博客-程序员宅基地

Backing Up Oracle Cluster RegistryThis section describeshow to back up OCR content and use it for recovery. The f...

虚拟内存--虚拟内存到物理内存的映射_虚拟内存映射_敲码阿怪的博客-程序员宅基地

系统实现地址翻译的大致流程_虚拟内存映射

叩丁狼培训实战教程之Java的动态代理_weixin_44782140的博客-程序员宅基地

　　叩丁狼培训实战教程之Java的动态代理　　前面我们已经介绍了代理的好处了,前面写的是静态代理,要手工创建代理类。下面,我们说说它的问题，我们发现,代理类和老板类都实现了一个接口,如果业务繁多,这样的接口会有很多,如果代理的功能是通用的,就需要对每个接口创建相应的代理类,这个叫类爆炸(类太多了),所以Java提供了动态代理,即程序运行时动态创建代理类的.class.　　来看一下动态代理：　　JDK动态代理中包含一个类和一个接口：　　InvocationHandler接口：代表代理对象关联

python数组求和与平均值_python 数组平均值_裸禄棍交比火牛的博客-程序员宅基地

python数组求和与平均值ls=[4,9,19,8,391,39,9,283,45]sum(ls)average=sum(ls)/len(ls)print('累加值',sum(ls),'平均值',average)_python 数组平均值

程序员学数学读哪本书？（文末赠送精美礼品）_人工智能与算法学习的博客-程序员宅基地

关注我们丨文末赠书在互联网一直流传了一个这样的段子——“一流程序员靠数学，二流靠算法，三流靠逻辑，四流靠SDK，五流靠Google和StackOverFlow，六流靠百度和CSDN。低端的..._最适合搞计算机学生的数学书