一、算法实现题：半数集问题
1、问题描述：
给定一个自然数n，由n开始可以依次产生半数集set(n)中的数如下：
（1）n ∈ set(n);
（2）在n的左边加上一个自然数，但该自然数不能超过最近添加的数的一半
（3）按此规则进行处理，直到不能再添加自然数为止。
例如，set(6) = {6,16,26,126,36,136}。半数集set(6)中有6个元素。
注意，该半数集是多重集
2、编程任务：
对于给定的自然数n,计算半数集set(n)中的元素个数
3、数据输入：
输入数据由文件名为input.txt的文本文件提供。每个文件只有1行，给出整数n （0<n<1000）。
4、结果输出:
将计算结果输出到文件output.txt.输出文件只有一行，给出半数集set(n)中的元素个数。
输入文件示例 输出文件示例
Input.txt output.txt
6 6
二、解题思路
1、用递归实现
l 统计的结果用一个全局变量来记录，不能够在使用递归的函数中定义。
在主函数中定义一个记录结果的整形变量count，初始值为1。代码如下：
int count = 1;
l 用循环从文件input.txt读取数据并将计算的结果存入output.txt文件中
while(fin_test_num>>Num)
{
count = 1;
fun(Num/2,count);
fout_test_num<<count<<"/n";
}
l 关闭文件
fout_test_num.close();
fin_test_num.close();
l 自定义递归函数set计算，得到结果
在函数中利用一个for循环，每调用一次count 就增加n/2。
2、算法改进（使用备忘录的方法）：
l 使用递归算法效率较低，重复计算了先前已经计算过的值
set(6/2)
↙ ↓ ↘
set(1/2) set(2/2) set(3/2)
↓ ↓
set(1/2) set(1/2)
如上图，重复计算了set(0)与set(1)
为了解决上述问题，就应将已经计算的结果保存起来。
设p[n]表示自然数m产生半数集的个数，则有如下关系：
p[m] = 1+p[1]+p[2]+p[3]+ … +p[n/2] ( p[0] = 0 )
l 定义一个整形数组p ，空间大小为自然数n的一半。用count来记录p[n]的值，即最终结果。这样做的好处可以使循环的次数大大减小。
while(fin>>N)
{
count = 0;
n = N/2;
p = new int [n+1];
for(i=0;i<=n;i++)
p[i] = 0;
for(i= 1;i<=n;i++)
{
int k = i/2;
for(int j = 1;j <= k;j++)
p[i] += p[j];
p[i] += 1;
count += p[i];
}
count += 1;
fout<<count<<"/n";
}
三、算法描述
1、用递归实现
#include <iostream>
#include <fstream>
using namespace std;
void set(int num,int &count) //递归函数
{
for (int i = 1; i <= num; i++)
{
count += 1;
set(i/2,count);
}
}
int main()
{
int count = 1;
int Num;
//文件操作
ifstream fin_test_num;
ofstream fout_test_num;
fout_test_num.open("output.txt");
fin_test_num.open("input.txt");
while(fin_test_num>>Num) //从文件中读取数据
{
count = 1; //重新设置count的值
set(Num/2,count); //调用递归函数进行计算
fout_test_num<<count<<"/n"; //向文件中写入数据
}
fout_test_num.close(); //关闭文件
fin_test_num.close();
return 0;
}
2、用备忘录方法实现
#include <iostream>
#include <fstream>
using namespace std;
void main()
{
int n,N,*p,count;
int i = 0;
ifstream fin;
ofstream fout;
fin.open("input.txt");
fout.open("output.txt");
while(fin>>N)
{
count = 0;
n = N/2;
p = new int [n+1];
for(i=0;i<=n;i++)
p[i] = 0;
for(i= 1;i<=n;i++)
{
int k = i/2;
for(int j = 1;j <= k;j++)
p[i] += p[j];
p[i] += 1;
count += p[i];
}
count += 1;
fout<<count<<"/n";
}
fin.close();
fout.close();
}