半数集 pascal
作者&投稿：虿要 （若有异议请与网页底部的电邮联系）
虽然这里引用的是C++的实现,不过实现语句较简单,pascal选手也能轻易看懂，如果实在看不懂可以M我，可以帮你解释~不过关键在于解题的思维和方法，明白怎么做就行了，不必照着代码抄，那样没用！ 通过分析所描述问题的特点可知，半数集set(n)中元。
半数集set(n)元素个数f(n)=1+f(1)+f(2)+...+f(floor(n/2)). 用递推法求解。
#include#includeint main(){ int n; int i,j,s; int buf[106]; char *in="input.txt",*out="output.txt"; FILE *ip,*op; if((ip=fopen(in,"r"))==NULL)return 1; if((op=fopen(out,"w"))==NULL)return 2; fscanf(ip,"%d",&n); fclose(ip); buf[1]=1; buf[2]=2; buf[3]=2; for(i=4;i*2<=n;i++){ s=1; for(j=1;j<=i/2;j++){ s+=buf[j]; } buf[i]=s; } s=1; for(j=1;j<=n/2;j++){ s+=buf[j]; } fprintf(op,"%d
",s); fclose(op);/* system("pause");*/ return 0;}
通过分析所描述问题的特点可知，半数集set(n)中元素个数的求解是个递归的过程。设set(n)中的元素个数为f(n)，则显然有递归表达式：
f(n)=1+∑f(i)，i=1,2……n/2
据此，可很容易设计出求f(n)的递归算法如下：
int comp(int n)
{ int ans=1；
if(n>1)
for(int i=1；i<=n/2；i++)
ans+=comp(i)；
return ans；
}
对于此递归过程，是存在有缺陷的，即有很多的重复子问题计算。比如说：当n=4时，f(4)=1+f(1)+f(2)，而f(2)=1+f(1)，因此，在计算f(2)的时候又要重复计算一次f(1)。更进一步，当n较大时，类似的重复子问题计算将会变得非常多。
3.2、改进的递归算法
可以对如上的递归算法进行改进，用数组来存储已计算过的子问题结果，就可以避免重复，提高算法效率。改进的递归算法如下：
int comp(int n)
{ int ans=1；
if(a[n]>0) //避免重复计算的判断语句（在主函数中将数组a的元素全部初始化为0）
return a[n]；
for(int i=1;i<=n/2;i++)
ans+=comp(i)；
a[n]=ans；
return ans；
}
四、半数单集问题
4.1、概念说明
半数单集类似半数集，区别在于：半数集是多重集，而半数单集不是多重集，即集合中已有的元素不再添加到集合中。
例如：n=24，那么半数集set(24)中的元素1224就有如下两种方式可以生成：
24 → 1224
24 →224 → 1224
所以，1224就是一个被重复计算的元素。
4.2、如何剔除重复元素
笔者只考虑了n≤200的情况。
在n≤200时，n/2≤100，也就是说，此时可能产生重复的元素是2位数。一个两位数x产生重复的条件是：其个位上的数y=x%10的半数集中已产生x，即
x/10 ≤y/2 或 2(x/10) ≤x%10
例如n=24时，x=24/2=12，y=12%10=2即：2的半数集中已产生12。
因此，在三中的算法里加入剔除重复元素的语句即可实现重复元素的剔除。剔除重复元素的递归算法如下：
int comp(int n)
{ int ans=1；
if(a[n]>0)
return a[n]；
for(int i=1;i<=n/2;i++)
{
ans+=comp(i)；
if((i>10)&&(2*(i/10)<=i%10)) //剔除重复元素的判断语句
ans-=a[i/10]；
}
a[n]=ans；
return ans；
}
五、小结
使用递归算法求解问题时，首先需要得出所求问题的递归方程，递归方程需要有一个初始值，这个初始值也称为边界条件。递归方程是自然数上的一个函数T(n)，它使用一个或多个小于n时的值的不等式来描述。递归方程通常有三种方法可以计算：迭代方法，替换方法和主方法。
附：求解半数集set(n)中元素个数的基本程序
此程序只是求半数集set(n)中元素个数的一个基本示例，半数单集的程序可在此上适当改动得来。由于图片不好上传，因而没有给出测试结果，读者可以在此基本程序上自行测试，也可对程序做适当改动以满足不同输出要求。
#include<iostream.h>
#include<stdio.h>
int a[1001];
int comp(int n) //改进的递归算法
{
int ans=1;
if(a[n]>0)
return a[n];
for(int i=1;i<=n/2;i++)
ans+=comp(i);
a[n]=ans;
return ans;}
void main()
{
int n;
cout<<"请输入一个不大于1000的自然数：n=";
cin>>n;
for(int i=0;i<=n;i++)
a[i]=0;
a[1]=1;
if(n<=0||n>1000)
{
cout<<endl<<"输入错误，请注意输入值n的范围."<<endl;
getchar();
return;
}
else
{
cout<<endl<<"半数集set("<<n<<")中的元素个数为：";
cout<<comp(n)<<endl;
getchar();
}
}
典型的递归题：
program set;
var n:byte;
function f(n:byte):word;
var i:byte;
begin
f:=1;
if n=1 then exit;
for i:=1 to n div 2 do
inc(f,f(i));
end;
begin
assign(input,'set.in');assign(output,'set.out');
reset(input);rewrite(output);
read(n);
writeln(f(n));
close(input);close(output);
end.
贝纯云芝：[答案] 虽然这里引用的是C++的实现,不过实现语句较简单,pascal选手也能轻易看懂,如果实在看不懂可以M我,可以帮你解释~不过关键在于解题的思维和方法,明白怎么做就行了,不必照着代码抄,那样没用! 通过分析所描述问题的特点可知,半数集...
涿州市17884453155： 什么是PASCAL矩阵 - ？
贝纯云芝： 帕斯卡矩阵:由杨辉三角形表组成的矩阵称为帕斯卡(Pascal)矩阵. 杨辉三角形表是二次项 (x+y)^n 展开后的系数随自然数 n 的增大组成的一个三角形表. 如4阶帕斯卡矩阵为: Pascal(4)= [1 1 1 1 1 2 3 4 1 3 6 10 1 4 10 20]
涿州市17884453155： pascal字符集 系统字符集 ASCLL字符集的区别？
贝纯云芝： 不是ASCLL而是ASCII(小写为i)pascal字符集:就是pascal语言中使用的、在程序中可以出现在标识符以及运算中的符号和字符;系统字符集:是系统中能够使用的所有符号的集合,现在使用的有大字符集和uncode字符集. ascii是美国标准信息交换码(字符集),这是计算机中的第一个字符集,现在属于unicode编码的子集.
涿州市17884453155： PASCAL集合类型有什么用? - ？
贝纯云芝： 有时还是有用的,比如判断一个字符是否在A到Z,直接可以写成 if ch in ['A'..'Z'] then ...还是有他的用途
涿州市17884453155： pascal 中 set of的用法 - ？
贝纯云芝： s1:set of 0..9 是集合,是一堆数 s2:0..9是整型数,是一个数 s1:=[0,2,4,6,8]; s2:=0;s2:=2; 这就是差别.
涿州市17884453155： Pascal一般所有函数 例如:case...of ,eof等等和用法 - ？
贝纯云芝： Pascal用到的数和符号 1、PASCAL语言的字符表 是ASCII字符集,主要有:⑴26个英文字母(不分大小写)⑵十个数字符号⑶特殊符号.如+-*/=><][:;.等 2、标识符 以字母开头的字母数字序列(大小写等效,可跟下划线_),用来标识常...
涿州市17884453155： pascal 函数 - ？
贝纯云芝： delete(s,pos,len); 把s串从第pos位开始连续len个字符删除,后面的字符向左靠齐 concat(s1,s2,s3...sn); 返回括号里的串从左到右连接起来后形成的字符串,可以自己试一下 val(s,r,p); 将串s转换成数字r,p为查错用.若s合法,例如s=“12345...
涿州市17884453155： pascal中fillchar()的意义是什么 - ？
贝纯云芝： fillchar(a,sizeof(a),0); 意思就是把数组A的每一个单位赋初值为0 类似的还可以写成 fillchar(s,sizeof(s),''); 就是把S数组的每一个单位赋为空的意思
涿州市17884453155： pascal 数组程序？
贝纯云芝： var a,b:array[1..10,1..10]of integer; i,j,m:integer; begin readln(m); for i:=1 to m do for j:=1 to m do read(a[i,j]); readln; for i:=1 to m do for j:=1 to m do b[j,i]:=a[i,j]; for i:=1 to m do begin for j:=1 to m do write(b[i,j]:4); writeln; end; readln; end. 次数不会就是m(m-1)/2吧...不是这么简单吧..
涿州市17884453155： pascal介绍？
贝纯云芝： PASCAL是一种结构程序设计语言,由瑞士苏黎世联邦工业大学的沃斯(N.Wirth)教授研制,于1971年正式发表.是从ALGOL60衍生的,但功能更强且容易使用.目前,作为一个能高效率实现的实用语言和一个极好的教学工具,PASCAL语言...
