问题描述:
给定一个自然数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)中的元素个数
解题思路
半数集的公式是
一 递归过程分析
通过分析所描述问题的特点可知,半数集set(n)中元素个数的求解是个递归的过程。设set(n)中的元素个数为f(n),则显然有递归表达式:
f(n)=1+∑f(i),i=1,2……n/2
据此,可很容易设计出求f(n)的递归算法如下:
int bsj(int n)<wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr>
{<wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr>int
ans=1;
<wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>if(n>1)
<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>for(int
i=1;i<=n/2;i++)
<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>ans+=bsj(i);
<wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>return
ans;
}
对于此递归过程,是存在有缺陷的,即有很多的重复子问题计算。比如说:当n=4时,f(4)=1+f(1)+f(2),而f(2)=1+f(1),因此,在计算f(2)的时候又要重复计算一次f(1)。更进一步,当n较大时,类似的重复子问题计算将会变得非常多。
二 改进的递归算法
可以对如上的递归算法进行改进,用数组来存储已计算过的子问题结果,就可以避免重复,提高算法效率。改进的递归算法如下:
int bsj(int n)
{<wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr>int
ans=1;
<wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>if(a[n]>0)<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>//避免重复计算的判断语句(在主函数中将数组a的元素全部初始化为0)
<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>return a[n];
<wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>for(int i=1;i<=n/2;i++)
<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>ans+=bsj(i);
<wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>a[n]=ans;
<wbr><wbr><wbr><wbr><wbr><wbr><wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>return ans;
}
#include<iostream>
long a[10001];
using namespace std;
int main()
{
long bsj(int n);
int n;
while(cin>>n)
{
memset(a,sizeof(a),0);
a[1]=1;
cout<<bsj(n)<<endl;
}
return 0;
}
long bsj(int n)
{
long ans=1;
if(a[n]>0)
return a[n];
for(int i=1;i<=n/2;i++)
ans+=bsj(i);
a[n]=ans;
return ans;
}
<wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><wbr><p></p>
<br><p style="margin-top:0px; margin-bottom:0px; padding-top:0px; padding-bottom:0px">
<br></p>
</wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr></wbr>
分享到:
相关推荐
半数集问题 给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下。 (1) n∈set(n); (2) 在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半; (3) 按此规则进行处理,直到不能再添加...
计算机算法设计与分析,算法实现题2-3半数集问题。
算法分析与设计 半数集问题,算法分析与设计 半数集问题
给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下。 (1) n∈set(n); (2) 在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半; (3) 按此规则进行处理,直到不能再添加自然数为止。 例如,...
实现2-3半数集问题.cpp
计算机算法设计与分析 求解半数集问题的算法
半数集问题是一个很经典的问题,通过这个问题我们能很好的学习C#语言。
备忘录方法实现半数集问题的算法,C++实现代码。用c[n]保存由n产生的半数集的大小。开始时将数组c[1..n]初始化为0.表明1到n的每一个自然数所产生的半数集的大小是多少 这个问题都没被处理过 一旦检测到数组中元素c[i...
FZU ACM 上的半数集问题 的源代码
半数集问题解决源码 可运行 决定完美运行
对于计算机算法半数集问题是详细解决思路讲解
给定一个自然数n,由n 开始可以依次产生半数集set(n)中的数如下。 (1) n∈set(n); (2) 在n 的左边加上一个自然数,但该自然数不能超过最近添加的数的一半; (3) 按此规则进行处理,直到不能再添加自然数为止。 例如...
给定一个自然数n,由n开始可以依次产生半数集set(n)中的数如下。(1) n set(n);(2) 在n的左边加上一个自然数,但该自然数不能超过最近添加的数的一半;(3) 按此规则进行处理,直到不能...用自底向上的方法求半数集问题
半数问题半数问题半数问题半数问题半数问题半数问题半数集问题
数据输入: 1 行,给出整数n。(0) 结果输出: 1 行,给出半数集set(n)中的元素个数。
本程序是用c#2008编写的,包括递归的有重复元素的排列问题和半数集问题,动态规划的导弹问题,贪心算法的找零钱问题。
实现2-4半数单集问题.cpp
实验四 半数集问题 实验五 集合划分问题 实验六 最少硬币问题 实验七 编辑距离问题 实验八 程序存储问题 实验九 最优服务次序问题 实验十 汽车加油问题 实验十一 工作分配问题 实验十二 0-1背包问题 实验十三 最小...