半数集问题(算法设计与分析)

2024-01-11 17:20

本文主要是介绍半数集问题(算法设计与分析),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

给定一个自然数n给定一个自然数n,由n 开始可以依次产生半数集set(n)中的数如下。
(1) n∈set(n);
(2) 在n 的左边加上一个自然数,但该自然数不能超过最近添加的数的一半;
(3) 按此规则进行处理,直到不能再添加自然数为止。
例如,set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。
注意半数集是多重集。
对于给定的自然数n,计算半数集set(n)中的元素个数。
输入样例:

6

输出样例:

6

算法设计
首先,先了解一下半数集是如何产生的,以set(6)为例,有如下图示:
在这里插入图片描述

我们找到了三个满足条件的数,即1、2、3,他们分别与6构成了16、26、36,依照这三个数继续向集合中添加元素,对于16,1是最近添加的数,但因为比1的一半小的自然数只有0,所以这一步就结束了。对于26,2是最近添加的数,1满足(2)的条件,所以将126也添加到了半数集中。同理,将136也添加到了半数集中。
由此,我们可以应用递归的思想,来解决问题,对于set(n)中的元素个数f(n),有以下公式:
在这里插入图片描述

设计的递归算法如下:

int halfset(int n){int sum = 1;for(int i=1;i<=n/2;i++){sum += halfset(i);}return sum;
}

该算法在n较大时,运行时间较长,原因是进行了很多重复的递归。比如n=16时,满足条件的数中有4和8,在对8进行递归中,也包含了4这个数,这样就产生了重复。我们可以设置一个数组,存放已经计算好的结果,改进算法的效率,改进的代码如下所示:

int a[1005]={0};
int dfs(int n){int sum = 1;if(a[n]>0)return a[n];for(int i=1;i<=n/2;i++){sum += dfs(i);}a[n]=sum;return sum;
}

完整代码:

#include<bits/stdc++.h>
using namespace std;
int a[1005]={0}; //存放已计算的数据
int halfset(int n){int sum = 1;if(a[n]>0) //如果f(n)已经得出,就不必再重复计算return a[n];for(int i=1;i<=n/2;i++){sum += halfset(i);}a[n]=sum;return sum;
}
int main()
{int n;FILE* fin=fopen("input.txt","r+");FILE* fout=fopen("output.txt","r+");fscanf(fin,"%d",&n);int result=halfset(n);cout << result <<endl;fprintf(fout,"%d",result);fclose(fin);fclose(fout);return 0;
}

规模 改进前 改进后
n=1000 7.648s 1.681s
n=1200 18.226s 1.738s

这篇关于半数集问题(算法设计与分析)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/595110

相关文章

MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析

《MyBatis-Plus中Service接口的lambdaUpdate用法及实例分析》本文将详细讲解MyBatis-Plus中的lambdaUpdate用法,并提供丰富的案例来帮助读者更好地理解和应... 目录深入探索MyBATis-Plus中Service接口的lambdaUpdate用法及示例案例背景

MyBatis-Plus中静态工具Db的多种用法及实例分析

《MyBatis-Plus中静态工具Db的多种用法及实例分析》本文将详细讲解MyBatis-Plus中静态工具Db的各种用法,并结合具体案例进行演示和说明,具有很好的参考价值,希望对大家有所帮助,如有... 目录MyBATis-Plus中静态工具Db的多种用法及实例案例背景使用静态工具Db进行数据库操作插入

Flask解决指定端口无法生效问题

《Flask解决指定端口无法生效问题》文章讲述了在使用PyCharm开发Flask应用时,启动地址与手动指定的IP端口不一致的问题,通过修改PyCharm的运行配置,将Flask项目的运行模式从Fla... 目录android问题重现解决方案问题重现手动指定的IP端口是app.run(host='0.0.

Seata之分布式事务问题及解决方案

《Seata之分布式事务问题及解决方案》:本文主要介绍Seata之分布式事务问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Seata–分布式事务解决方案简介同类产品对比环境搭建1.微服务2.SQL3.seata-server4.微服务配置事务模式1

mysql关联查询速度慢的问题及解决

《mysql关联查询速度慢的问题及解决》:本文主要介绍mysql关联查询速度慢的问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录mysql关联查询速度慢1. 记录原因1.1 在一次线上的服务中1.2 最终发现2. 解决方案3. 具体操作总结mysql

一文教你解决Python不支持中文路径的问题

《一文教你解决Python不支持中文路径的问题》Python是一种广泛使用的高级编程语言,然而在处理包含中文字符的文件路径时,Python有时会表现出一些不友好的行为,下面小编就来为大家介绍一下具体的... 目录问题背景解决方案1. 设置正确的文件编码2. 使用pathlib模块3. 转换路径为Unicod

Spring MVC跨域问题及解决

《SpringMVC跨域问题及解决》:本文主要介绍SpringMVC跨域问题及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录跨域问题不同的域同源策略解决方法1.CORS2.jsONP3.局部解决方案4.全局解决方法总结跨域问题不同的域协议、域名、端口

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

SpringBoot自定义注解如何解决公共字段填充问题

《SpringBoot自定义注解如何解决公共字段填充问题》本文介绍了在系统开发中,如何使用AOP切面编程实现公共字段自动填充的功能,从而简化代码,通过自定义注解和切面类,可以统一处理创建时间和修改时间... 目录1.1 问题分析1.2 实现思路1.3 代码开发1.3.1 步骤一1.3.2 步骤二1.3.3

基于.NET编写工具类解决JSON乱码问题

《基于.NET编写工具类解决JSON乱码问题》在开发过程中,我们经常会遇到JSON数据处理的问题,尤其是在数据传输和解析过程中,很容易出现编码错误导致的乱码问题,下面我们就来编写一个.NET工具类来解... 目录问题背景核心原理工具类实现使用示例总结在开发过程中,我们经常会遇到jsON数据处理的问题,尤其是