实现题2

实现题2

实验名称
实现题2-3 半数集问题。

实验目的
通过上机实验，实现题2-3 半数集问题。

实验原理
设set(n)中的元素个数为f(n)，6的前面可以加上1、2、3，2、3的前面又都可以加上1，也就是f(6)=1+f(3)+f(2)+f(1)。
则显然有递归表达式：
f(n)=1+∑f(i)，i=1,2……n/2。

实验步骤
① 设set(n)中的元素个数为f(n)，6的前面可以加上1、2、3，2、3的前面又都可以加上1，也就是f(6)=1+f(3)+f(2)+f(1)。则显然有递归表达式：
f(n)=1+∑f(i)，i=1,2……n/2。
据此设计出求f(n)的递归算法：
int f(int n)
{
int temp=1;
if(n>1)
for(int i=1；i<=n/2；i++)
temp+=f(i)；
return temp；
}
② 这样有很多的重复子问题计算。例如，当n=4时，f(4)=1+f(1)+f(2)，而f(2)=1+f(1)，在计算f(2)的时候又要重复计算一次f(1)。
③ 用数组来存储已计算过的子问题结果，就可以避免重复，提高算法效率。改进的递归算法：
int f(int n)
{
int temp=1;
if(a[n]>0)return a[n];
for (int i = 1;i <= n/2;i++)
{
temp+=f(i);
}
a[n]=temp;
return temp;
}

算法时间复杂度
n/2个相加，每一个需要计算1+…+i/2，因此时间复杂度为O(n^2)
实验心得 通过这次实验，我回顾了递归的算法思想，并学会利用数组存储已计算过的子问题来避免重复，提高算法的效率。

#include<fstream>
#include<ctime>
using namespace std;
const int N=1e4;
int a[N+10]={0};
int f(int n)
{int temp=1;if(a[n]>0)return a[n];for (int i = 1;i <= n/2;i++){temp+=f(i);}a[n]=temp;return temp;
}
int main()
{ifstream in;in.open(&#");ofstream out;int n;in>>n;in.close();out.open(&#");clock_t start,end;start=clock();out<<f(n);end=clock();printf("时间：%fmsn",(double)(end-start)/CLK_TCK);out.close();return 0;
}

#include<fstream>
#include<iostream>
using namespace std;
int main()
{int n; cin>>n; ofstream out(&#");out<<n<<'n';out.close();return 0;
}