半数单集问题

半数单集问题

算法分析与设计第一次实验 半数单集问题

一、问题描述

【问题简述】
给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下：
(1) n ∈set(n)；
(2) 在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半；
(3) 按此规则进行处理，直到不能再添加自然数为止。
注意，半数单集不是多重集，集合中已经有的元素不再添加到集合中。
【输入形式】
输入数据由文件名为的文本文件提供。每个文件只有一行，给出整数n（0<n<201）。
【输出形式】
将计算结果输出到文件。输出文件只有一行，给出半数集set(n)中的元素个数。

二、问题分析

​ 通过分析所描述问题的特点可知，半数集set(n)中元素个数的求解是个递归的过程。设set(n)中的元素个数为f(n)，则显然有递归表达式:
​ f(n)=1+∑f(i)，i=1,2……n/2
​ 我们可以根据数学公式用分治法来解决问题，但半数单集与半数集的区别在于：半数集是多重集，而半数单集不是多重集，即集合中已有的元素不再添加到集合中。例如：n=30，那么半数集set(30)中的元素1530就有如下两种方式可以生成：30 → 1530或者是30 →530 → 1530所以，1530就是一个被重复计算的元素。
​ 所以，与半数集相比，我们还要考虑如何剔除重复元素，题目中有一个限制条件：0<n<201。即此时可能产生重复的元素只能是两位数。一个两位数x产生重复的条件是：在1位数y=x%10的半数集中已经产生x，即x/10 ≤y/2 即 2(x/10) ≤x%10，问题分析完毕。

三、算法设计

通过上述分析，将采用下面的方法解决相关问题：
​ 1.使用整型来保存存入的数字；
​ 2.将递归表达式:f(n)=1+∑f(i)，i=1,2……n/2 转化为递归方程，从而求出set(n)中元素个数；
​ 3.在递归方程中添加限制条件，剔除重复元素；

四、**关键代码 **

【递归方程】

int set(int n)
{int num=1; if(n>1){//f(n)=1+∑f(i)for(int i=1;i<=n/2;i++){num+=set(i);//剔除重复元素if((i>10)&&(2*(i/10)<=i%10)) num-=set(i/10);}}return num;
}

【文件流对文件的读取与写入操作】

int main()
{fstream file;int n;file.open(&#",ios::in);		//打开输入文件file>>n;	//读取数据file.close();	//关闭输入文件 file.open(&#",ios::out); 	//打开输出文件file<<set(n);		//将结果输出到输出文件 file.close();return 0;
}

五、实验心得

【心得体会】
通过这次实验，我熟练掌握了用分治法对问题进行求解，使用递归算法求解问题时，首先需要得出所求问题的递归方程，递归方程需要有一个初始值，这个初始值也称为边界条件。递归方程是自然数上的一个函数T(n)，它使用一个或多个小于n时的值的不等式来描述。递归方程通常有三种方法可以计算：迭代方法，替换方法和主方法。

【实验可改进的地方】
对于此递归过程，是存在有缺陷的，即有很多的重复的子问题计算。例如：当n=4时，f(4)=1+f(1)+f(2)，而f(2)=1+f(1)，因此，在计算f(2)的时候又要重复计算一次f(1)。更进一步，当n较大时，类似的重复子问题计算将会变得非常多。
可以对如上的递归算法进行改进，用数组来存储已计算过的子问题结果，就可以避免重复，提高算法效率。
改进的递归算法如下：

int set(int n)
{int num=1;//避免重复计算的判断语句（在主函数中将数组a的元素全部初始化为0）if(a[n]>0) return a[n];for(int i=1;i<=n/2;i++){num+=set(i);//剔除重复元素if((i>10)&&(2*(i/10)<=i%10)) num-=a[i/10];}a[n]=num;return num;
}

六、完整代码

#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
int a[2000];
int set(int n)
{int num=1;//避免重复计算的判断语句（在主函数中将数组a的元素全部初始化为0）if(a[n]>0) return a[n];for(int i=1;i<=n/2;i++){num+=set(i);//剔除重复元素if((i>10)&&(2*(i/10)<=i%10)) num-=a[i/10];}a[n]=num;return num;
}
int main()
{memset(a,sizeof(a),0);a[1]=1;fstream file;int n;file.open(&#",ios::in);		//打开输入文件file>>n;file.close();	//关闭输入文件 file.open(&#",ios::out); 	//打开输出文件file<<set(n);		//将结果输出到输出文件 file.close();return 0;
}