java半数集问题_半数集问题与动态规划_刘一帝的博客-程序员宅基地

技术标签: java半数集问题  

首先给出如下的半数集问题

给定一个自然数n,由n 开始可以依次产生半数集set(n)中的数如下。

(1) n∈set(n);

(2) 在n 的左边加上一个自然数,但该自然数不能超过最近添加的数的一半;

(3) 按此规则进行处理,直到不能再添加自然数为止。

例如,set(6)={6,16,26,126,36,136}。半数集set(6)中有6 个元素。

注意半数集是多重集。

首先分析题目意思:已知一个数n,要整数k1∈[1,n/2],依次放到这个数的左边(实际上就是放到高位),然后再进行类似操作,只不过再次操作时,添加到左边的数k2的取值范围为k2∈[1,k1/2],然后依次进行操作,直到不能操作为止。当时看到这个问题,第一印象就是用一个变长容器,找到一个元素就添加进去,最后统计元素个数。基于上述流程,很容易用递归的方法写出程序。最初用C++的STL vector容器写出的程序如下:

1 #include

2 #include

3 using namespacestd;4 int getScale(intnum);5 int calcHalfSetNum(intstartNum);6 void addElementInHalfSet(int num, int lastNum, vector &set);7 intmain() {8 intn,i;9 vectorsource;10 while (cin >>n)11 source.push_back(n);12 for (i = 0; i < source.size(); i++)13 cout << calcHalfSetNum(source[i]) < 0) {20 result *= 10;21 num /= 10;22 }23 returnresult;24 }25 int calcHalfSetNum(intstartNum) {26 vectordynArray;27 addElementInHalfSet(startNum, startNum, dynArray);28 returndynArray.size();29 }30 void addElementInHalfSet(int num,int lastNum, vector &set) {31 inti;32 set.push_back(num);33 for (i = 1; i <= lastNum / 2; i++)34 addElementInHalfSet(num + i*getScale(num), i, set);35 return;36 }

本身题目不要求输出目标集合中的所有元素,因此没有必要用vector来保存集合中的所有元素。根据题意,很容易得出一个一般性的递推式:h(n)=1+h(1)+...+h(k),其中k=n/2。得到这个递推式,也很容易使用递归来写出程序。但是,时间复杂度和刚才的程序一样依然是指数阶的,只是常数小一点(省却了容器操作和动态内存分配的开销)。但是基于这个递推式,很容易发现会有很多重复计算,用动态规划的方法能够避免这类重复计算。

在《算法导论》一书中,提及动态规划有两种设计方法。一种方法是带备忘的自顶向下的方法,另一种是自底向上的方法。两种方法具有相同的复杂度,常数略有差别。对于这个问题,显然对于子问题h(i)中i越小,子问题越小,即越基本。一半情况下,会选择自顶向下的方法,在自顶向下的方法中,需要在主体函数外部维护一个额外的数组,来保存中间计算结果。算法导论书中使用的是用一个“引子函数”的方法,即用一个辅助函数,先分配一个数组(更一般的,进行动态数据结构的初始化),然后把这个数组作为参数传递给主体函数,主题函数在递归时,依然将这个数组传递下去,从而保证了在整个递归过程中,所有的子情况都能够访问这个数组。对于这个问题而言,为了简单起见,可以设置一个全局数组。对于辅助数组,还需要做的一点工作就是,需要确认这个数组中的值,是不是我所需要的已经计算的子问题的结果。可以采取的方法很多,这里使用了不属于子问题的解的集合的元素(0)作为标志,有些时候,当问题的解覆盖了整个数据类型的取值范围时,也可能需要更为复杂的方式。

基于这种自顶向下的思路,我的C++代码实现如下:

1 #include

2 #include

3 using namespacestd;4 int calcHalfSetNum(intstartNum);5 int a[10000];6 intmain() {7 intn;8 unsigned i;9 vectorsource;10 while (cin >>n)11 source.push_back(n);12 for (i = 0; i < source.size(); i++)13 cout << calcHalfSetNum(source[i]) < 0)20 returna[startNum];21 for (i = 1; i <= startNum / 2; i++)22 result +=calcHalfSetNum(i);23 a[startNum] =result;24 returnresult;25 }26

对于另一种自底向上的方法,就是从h(1)开始计算,计算h(i)时,所计算过的结果都存放在数组的对应位置里,直接拿来用就可以了,直到i=n时,循环结束。这种方法就不需要在函数体外维护一个数组了,因为不需要递归调用,函数开头声明的数组在整个算法过程中都是可见的。这里是我一个哥们用C写的代码,以供参考:

1 #include

2 intmain()3 {4 int a[1000]={0},i,j,n;5 a[0]=1;a[1]=1;6 for(i=2;i<1000;i++)7 for(j=0;j<=i/2;j++)8 a[i]+=a[j];9 while(scanf("%d",&n)!=EOF)10 printf("%d\n",a[n]);11 return 0;12 }

最后还要提及一下就是,如果要输出所有元素时,因为每个元素都不一样,动态规划的方法就不可行了。动态规划算法的核心之一要求问题必须有重复的子问题的解。

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_36478866/article/details/114509570

智能推荐

c#,winform实现获取当前经纬度坐标(极其便捷)_c#获取经纬度-程序员宅基地

近期开发winform桌面应用时,需要获取当前的经纬度坐标,并显示在地图上(我们要实现的是arcgis engine的地图,但事实上不论是百度还是googel这些地图,只要获取了当前的经纬度坐标,一切都好说)。我花费了快一天的时间终于解决这个问题。急切地想解决问题的话,请跳到Part 2直接扫一眼,copy代码用起,否则可以慢慢读,有帮助。Part one 在国内的网站找了一_c#获取经纬度

YOLOV4结构图_yolov4系统架构图_HowHardYouAre的博客-程序员宅基地

CSPDarkNet主干网络结构图:CBM:conv+batchNorm+Mish(激活函数)整个网络构架:CSPDarkNet就是上面的结构CBL:conv+batchNorm+LeakyCBLi:conv+batchNorm+line_yolov4系统架构图

递归下降子程序实现LL(1)文法的语法分析_已知如下所示文法g[a],请写出每个产生式的predict集,并用c语言写出递归下降的语-程序员宅基地

这是一次编译原理的实验,总结输出一下:原理:对每一个非终结符(分别代表一个语法单位)按其产生方式结构构造相应的语法子程序,以完成非终结符号所对应的语法单位的分析和识别任务。其中终结符号产生匹配命令,而非终结符号则产生过程调用命令。因为文法可以递归,相应子程序也是递归的。1)示范,示例LL(1)文法如下:G[A]:(1)S::=pA(2)S::=qB(3)A::=cAd(4)A::=a(5)B::=..._已知如下所示文法g[a],请写出每个产生式的predict集,并用c语言写出递归下降的语

新员工入职培训感受总结-程序员宅基地

这个事情虽然已经过去快有一个月了,我把给我留下深刻意义的点点滴滴都写下来。 01:刚进入公司时,公司的行政人员会把公司的规章制度都会发给我,让我有个事先有个了解。02:行政人员会在会议室把重要注意事项口述一遍,防止你阅读不仔细,有些关键的事项没注意好的会特别强调一下,同时也会解答一些疑问。 03:指纹打卡等都会设置好,防止你作弊,你想让别人代替打卡等问题不容易发生了,其实一个公司...

深度学习初学者,如何下载常用公开数据集并使用呢?_如何下载数据集并运行_EP Fitwin的博客-程序员宅基地

深度学习初学者,如何下载常用公开数据集并使用呢?1.前言2.官方文档怎样看3.动手写代码4.如何可视化1.前言刚开始进行深度学习的时候,难免要用到一些公开数据集,现在闲来无事,记录一下如何快速下载一些经典数据集。通过官方文档学习,是一些大牛们挂在嘴边经常推荐的方法,那么我们本篇博客就从官方文档开始学习。因为我是做CV方向的,所以用TorchVision这个库举例。来自官网:This library is part of the [PyTorch](http://pytorch.org/) projec_如何下载数据集并运行

圆弧中点坐标值求解(二维平面&三维空间)(3.1增加三维部分)-①_三维空间圆弧中点坐标值_王嘉翀的博客-程序员宅基地

转自知乎:https://www.zhihu.com/question/22529500/answer/21670472%二维圆弧中点坐标syms r x0 x1 x y0 y1 y theta%eq1 = abs(x1*x-2*x*x0+x0^2+y1*y-2*y0*y+y0^2) == cos(theta)*(r^2);eq1 = x1*x-2*x*x0+x0^2+y1*y-2*y0*y+y0^2 == cos(theta)*(r^2);eq2 = sqrt((x-x0)^2+(y-y0)^2_三维空间圆弧中点坐标值

随便推点

Hive实现wordCount程序-程序员宅基地

Hive实现wordCount程序a. 创建一个数据库,如create database word;b. 建表create external table word_data(line string) row format delimited fields terminated by '\n' stored as textfile location '/home/hadoop

java.lang.ClassCastException:org.hibernate.hql.ast.tree.SqlNode无法转换为org.hibernate.hql.ast.tree.FromR_org.hibernate.sql.ast.tree.sqlastnode-程序员宅基地

我正在尝试使用HQL查询更新记录,但我遇到了CastException.如果有人可以帮助我,我将非常感激.我已经检查了一段时间的互联网,但是找不到任何信息.如果您有关于此例外的更多信息,请告诉我.完整的错误消息返回:Exception in thread "AWT-EventQueue-0" java.lang.ClassCastException: org.hiber..._org.hibernate.sql.ast.tree.sqlastnode

JavaScript正则表达式替换字符串中图片地址(img src)的方法_js 正则替换html中的图片地址-程序员宅基地

今天开发中遇到一个问题:如何替换一段HTML字符串中包含的所有img标签的src值?开始想到的解决方法是:? 1 2 3 content.replace(/&lt;img [^&gt;]*src=['"]([^'"]+)[^&gt;]*&gt;/gi, function (match) { console.log(match);..._js 正则替换html中的图片地址

百练 / 2017研究生推免上机考试 C:肿瘤检测-程序员宅基地

题目来源:http://hljssyzx.openjudge.cn/2016/47/肿瘤检测-----------------------------------------------------总时间限制: 1000ms 内存限制: 65536kB描述一张CT扫描的灰度图像可以用一个N*N(0 &lt; N &lt;=100)的矩阵描述,矩阵上的每个点对应一个灰度值(整数),其取值范围是0-2...

【Pop_OS】Python运行环境配置_pop!_os mirror-程序员宅基地

Pop!_OS Python运行环境配置1. 更改环境变量Pop!_OS 默认自带了pyhton3,使用命令python3可运行python,此处更改环境变量使python命令直接运行python3echo alias python=python3 >> ~/.bashrc使环境变量生效source ~/.bashrc2.Pip换源首先在用户目录创建.pip目录mkdir ~/.pip创建并编辑pip.config文件vim ~/.pip/pip.conf将下面的内_pop!_os mirror

Centos7下安装Anaconda3+tensorflow-程序员宅基地

在学习linux开发过程中新鸟遇到不少问题,但是又苦于没有师傅带,出了问题只能google来解决,但是网上的资源真的有很多坑,很多,很多。在centos7单独安装python3.6进行开发时,遇到一个问题苦苦搜寻一天没有解决,无奈出现了本篇本章。问题:在单独安装python3.6进行开发时,当导入import matplotlib包进行开发时,会出现No module named '_tkinte...

推荐文章

热门文章

相关标签