算法分析_半数集问题

2024-01-11 17:20
文章标签 算法 分析 问题 半数

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

问题描述:
给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下:
(1) n∈set(n);
(2) 在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半;
(3) 按此规则进行处理,直到不能再添加自然数为止。

例如,set(6)={6,16,26,126,36,136},半数集set(6)中有6个元素。
输入:整数n(0<n<1000)
输出:半数集set(n)中的元素个数。

分析:
首先应该明确什么是半数集,半数集就是给定一个数,在这个数的左边添加新的数字(如6,左边添加新的数字2,就变为26),新添加的数字应该小于或等于这个数的左边第一个数字的一半(如59,则应当小于5/2),所以叫做半数,而由这些数字构成的集合就是半数集。

以6为例,6的半数集求解图示如下:
在这里插入图片描述


源代码如下(递归与非递归均有):

package recursion;import java.util.Scanner;public class Half_set {int set(int n) {int sum=1;//该数本身也属于半数集,故初始个数为1if(n<=1)return 1;for(int i=1;i<=n/2;i++) {sum=sum+set(i);}return sum;}int set(int n,int a[]){//优化后,非递归算法int ans = 1;if(a[n]>0) return a[n];for(int i = 1;i<=n/2;i++){ans += set(i);}a[n] = ans;return ans;}public static void main(String[] args) {// TODO 自动生成的方法存根Half_set temple=new Half_set();Scanner scanner=new Scanner(System.in);int a[]=new int[1024];int n=scanner.nextInt();//int sum=temple.set(n);//递归调用int sum=temple.set(n, a);//非递归调用System.out.println(sum);}}

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



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

相关文章

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数据处理的问题,尤其是