问题描述：
给定一个自然数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)
{ int ans=1；
if(n>1)
for(int i=1；i<=n/2；i++)
ans+=bsj(i)；
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)
{ int ans=1；
if(a[n]>0) //避免重复计算的判断语句（在主函数中将数组a的元素全部初始化为0）
return a[n]；
for(int i=1;i<=n/2;i++)
ans+=bsj(i)；
a[n]=ans；
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;
- }
16. long bsj(int n)
17. {
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;
}
问题描述
我们称序列Z = < z1, z2, ..., zk >是序列X = < x1, x2, ..., xm >的子序列当且仅当存在严格上升的序列< i1, i2, ..., ik >，使得对j = 1, 2, ... ,k, 有xij = zj。比如Z = < a, b, f, c > 是X = < a, b, c, f, b, c >的子序列。
现在给出两个序列X和Y，你的任务是找到X和Y的最大公共子序列，也就是说要找到一个最长的序列Z，使得Z既是X的子序列也是Y的子序列。
输入数据
输入包括多组测试数据。每组数据包括一行，给出两个长度不超过200的字符串，表示两个序列。两个字符串之间由若干个空格隔开。
输出要求
对每组输入数据，输出一行，给出两个序列的最大公共子序列的长度。
解题思路
如果我们用字符数组s1、s2存放两个字符串，用s1[i]表示s1中的第i个字符，s2[j]表示s2中的第j个字符（字符编号从1开始，不存在“第0个字符”），用s1i表示s1的前i个字符所构成的子串， s2j表示s2的前j个字符构成的子串，MaxLen(i, j)表示s1i 和s2j的最长公共子序列的长度，那么递推关系如下：
if( i ==0 || j == 0 ) {
MaxLen(i, j) = 0 //两个空串的最长公共子序列长度当然是0
}
else if( s1[i] == s2[j] )
MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1;
else {
MaxLen(i, j) = Max( MaxLen(i, j-1), MaxLen(i-1, j));
}
#define MaxSize 200
#include <stdio.h>
#include <string.h>
char p[MaxSize+10];
char q[MaxSize+10];
int MaxComLen[MaxSize+10][MaxSize+10]; //MaxComLen[i][j]表示以第一个串第i个元素，第二个串第j个元素为终点的最大公共子串
int main()
{
int i,j,max;
int plen=0,qlen=0;
while(scanf("%s%s",p+1,q+1)>0)
{
int maxlen=0;
plen=strlen(p+1);
qlen=strlen(q+1);
for (i=0;i<=plen;i++)
MaxComLen[i][0]=0;
for (j=0;j<=qlen;j++)
MaxComLen[0][j]=0; //如果i或者j为0，最长公共字串为0
for(i=1;i<=plen;i++)
{
for (j=1;j<=qlen;j++)
{
if (p[i]==q[j])
MaxComLen[i][j]=MaxComLen[i-1][j-1]+1;//如果p[i]=q[j],MaxComLen[i][j]=MaxComLen[i-1][j-1]+1
else
{
if(MaxComLen[i-1][j]>MaxComLen[i][j-1])//如果p[i]!=q[j],MaxComLen[i][j]=MAX(MaxComLen[i][j-1],MaxComLen[i-1][j])
MaxComLen[i][j]=MaxComLen[i-1][j];
else
MaxComLen[i][j]=MaxComLen[i][j-1];
}
if (MaxComLen[i][j]>maxlen) //输出最大的长度，按照定义应该为最后一个元素
maxlen=MaxComLen[i][j];
}
}
printf("%d/n",maxlen);
}
return 0;
}