编程基本算法普及组.docx
- 文档编号:2166695
- 上传时间:2023-05-02
- 格式:DOCX
- 页数:17
- 大小:19.31KB
编程基本算法普及组.docx
《编程基本算法普及组.docx》由会员分享,可在线阅读,更多相关《编程基本算法普及组.docx(17页珍藏版)》请在冰点文库上搜索。
编程基本算法普及组
编程基本算法(普及组)
ForNOIP2009
ByClimber
Pascal
计算程序运行时间
usesdos;
var
h,m,s,ss:
word;
t1,t2:
real;
begin
gettime(h,m,s,ss);
t1:
=h*3600+m*60+s+ss/100;
****//主程序
gettime(h,m,s,ss);
t2:
=h*3600+m*60+s+ss/100;
writeln((t2-t1):
0:
2);
end.
高精度运算
初始化
【加减法初值】tmp[0]:
=1;
【乘法初值】tmp[0]:
=1;tmp[1]:
=1;
【高精度类型】typehp=array[0..250]ofinteger;//hp[0]表示该数的长度
比较大小(Max)
if(a[0]>b[0])thenmax:
=trueelsemax:
=false;//比较
fori:
=a[0]downto1do
ifa[i]>b[i]thenmax:
=trueelsemax:
=false;
ifmax=falsethenbegintmp:
=a;a:
=b;b=tmp;end;//交换
高精度(a)+整型(b)=高精度(c)
Inc(a[1],b);//相加
while(a[a[0]]>9)dobegin//进位
inc(a[a[0]+1],a[a[0]]div10);
a[a[0]]:
=a[a[0]]mod10;inc(a[0]);end;
dec(a[0]);c:
=a;
高精度(a)-整型(b)=高精度(c)
Whilex<>0dobegin//相减
dec(c[c[0]],xmod10);
x:
=xdiv10;inc(c[0]);end;
fori:
=1toc[0]doifc[i]<0then//退位
begininc(c[i],10);dec(c[i+1]);end;
while(c[c[0]]=0)and(c[0]>1)dodec(c[0]);
高精度(a)×整型(b)=高精度(c)
fori:
=1toa[0]doc[i]:
=a[i]*x;c[0]:
=a[0]+10;
fori:
=1toc[0]doifc[i]>9then
begininc(c[i+1],c[i]);c[i]:
=c[i]mod10;end;
while(c[c[0]]=0)and(c[0]>1)dodec(c[0]);
高精度(a)÷整型(b)=高精度(c)
voiddiv_int(hpa,intx,hp&res,int&rest)
{
memset(res,0,sizeof(res));
rest=0;
for(inti=a[0];i>=1;i--)
{
rest=rest*10+a[i];
if(rest>=x)res[i]=rest/x,rest%=x;
}
intl=a[0];
while(res[l]==0&&l>1)l--;
res[0]=l;
return;
}
高精度(a)+高精度(b)=高精度(c)
fori:
=1toa[0]dotmp[i]:
=a[i]+b[i];//相加
fori:
=1toa[0]+1doifc[i]>9then//进位
begininc(c[i+1]);dec(c[i],10);end;
inc(c[0]);while(c[c[0]]=0)and(c[0]>1)dodec(c[0]);//长度计算
高精度(a)-高精度(b)=高精度(c)
Max(a,b);
fori:
=1toa[0]doc[i]:
=a[i]-b[i];//相减
fori:
=1toa[0]doifc[i]<0then//进位
begindec(c[i+1]);inc(c[i],10);end;
while(c[[c[0]]=0)and(c[0]>1)dodec(c[0]);//长度计算
高精度(a)×高精度(b)=高精度(c)
fori:
=1toa[0]doforj:
=1toa[0]do
inc(c[i+j-1],a[i]*b[j]);
c[0]:
=a[0]+b[0];
fori:
=1toc[0]doifc[i]>9then
begininc(c[i+1],tmp[i]div10);tmp[i]:
=tmp[i]mod10;end;
while(c[c[0]]=0)and(c[0]>1)dodec(c[0]);
高精度(a)÷高精度(b)=高精度(c)
intdiv_hp(hp&a,hp&b,hp&rest)
{
hptmp;
intl=MIN_RES,r=MAX_RES,mid;
while(l<=r)
{
mid=(l+r)/2;
mul_int(b,mid,tmp);
if(compare(a,tmp)==false)r=mid;
else
{
sub_hp(a,tmp,tmp);
if(compare(tmp,b)==true)l=mid;
else
{
memcpy(rest,tmp,sizeof(tmp));
returnmid;
}
}
}
return0;
}
高精度进制转换
首先需要一个改良版的高精度数除整型取余,增加一个k参数表示当前高精度数的进制。
代码如下,返回值为余数:
intchange_div_int(hpa,intx,hp&res,intk)
{
intrest;
hptmp;
memset(tmp,0,sizeof(tmp));
rest=0;
for(inti=a[0];i>=1;i--)
{
rest=rest*k+a[i];
if(rest>=x)tmp[i]=rest/x,rest%=x;
}
intl=a[0];
while(tmp[l]==0&&l>1)l--;
tmp[0]=l;
memcpy(res,tmp,sizeof(tmp));
returnrest;
}
高精度进制转换的主函数,n为当前进制,k为目标进制,b为结果:
voidN_to_K(hp&a,intn,intk,hp&b)
{
memset(b,0,sizeof(b));
while(a[0]!
=1||a[1]!
=0)
{
b[0]++;
b[b[0]]=change_div_int(a,k,a,n);
}
return;
}
压位高精度
voidInit(hp&a)
{
strings;
inttmp=0,t=0,l,k;
cin>>s;
memset(a,0,sizeof(a));
l=s.size();
k=l/8;
if(l%8!
=0)k++;
a[0]=k;
for(inti=1;i { t=l-8*i; tmp=0; for(intj=0;j<=7;j++) tmp=tmp*10+(s[t+j]-'0'); a[i]=tmp; } l=l-(a[0]-1)*8,tmp=0; for(intt=0;t tmp=tmp*10+s[t]-'0'; a[a[0]]=tmp; return; } voidadd(hpa,hpb,hp&c) { intl=max(a[0],b[0]); hptmp; memset(tmp,0,sizeof(tmp)); for(inti=1;i<=l;i++) tmp[i]=a[i]+b[i]; for(inti=1;i<=l;i++) if(tmp[i]>=0) tmp[i+1]++,tmp[i]-=0; l++; while(tmp[l]==0&&l>1)l--; tmp[0]=l; memcpy(c,tmp,sizeof(c)); return; } voidZero(intx)//补零 { if(x<10){cout<<"0000000";return;} if(x<100){cout<<"000000";return;} if(x<1000){cout<<"00000";return;} if(x<10000){cout<<"0000";return;} if(x<100000){cout<<"000";return;} if(x<1000000){cout<<"00";return;} if(x<){cout<<"0";return;} return; } voidprin(hpa) {
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 编程 基本 算法 普及