清华06-09计算机复试机试题

THU0601大数阶乘2010年02月07日星期日17:27清华06计算机复试机试题1试题一（5个测试数据，每个5分，共25分）求N的阶乘变量条件：N为正整数，且N≤1000。运行时限：1秒/测试数据。输入格式：仅一个数，N。输出格式：仅一个数，N！的结果。可执行文件：program1.exe样例一：Input.txt4Output.txt24样例二：Input.txt15Output.txt1307674368000//THU1大?数?阶?乘?#include"stdio.h"#include"string.h"#include"time.h"//usingnamespacestd;intmain(){clock_tstart,end;doubleduration;start=clock();FILE*fr,*fw;fr=fopen("Input.txt","r");if(fr==NULL){printf("ERRORinInput.txt");return0;}fw=fopen("Output.txt","w");if(fw==NULL){printf("ERRORinOutput.txt");return0;}longr[1000],t,add;intn,i,j,len;//,w;while(fscanf(fr,"%d",&n)!=EOF){memset(r,0,sizeof(r));r[0]=1;len=0;for(i=2;i<=n;i++){add=0;for(j=0;j<=len;j++){t=r[j]*i+add;r[j]=t%10000;add=t/10000;}if(add)r[++len]=add;}//w=m*4+log(r[len])+1;fprintf(fw,"%ld",r[len]);for(i=len-1;i>=0;i--)fprintf(fw,"%4.4ld",r[i]);fprintf(fw,"\n");}end=clock();duration=(double)(end-start)/CLOCKS_PER_SEC*1000;printf("%lfms\n",duration);return0;}Input.txt:12

20

100

666

1000Output.txt:479001600

2432902008176640000

93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

1010632056840781493390822708129876451757582398324145411340420807357413802103697022989202806801491012040989802203557527039339704057130729302834542423840165856428740661530297972410682828699397176884342513509493787480774903493389255262878341761883261899426484944657161693131380311117619573051526423320389641805410816067607893067483259816815364609828668662748110385603657973284604842078094141556427708745345100598829488472505949071967727270911965060885209294340665506480226426083357901503097781140832497013738079112777615719116203317542199999489227144752667085796752482688850461263732284539176142365823973696764537603278769322286708855475069835681643710846140569769330065775414413083501043659572299454446517242824002140555140464296291001901438414675730552964914569269734038500764140551143642836128613304734147348086095123859660926788460671181469216252213374650499557831741950594827147225699896414088694251261045196672567495532228826719381606116974003112642111561332573503212960729711781993903877416394381718464765527575014252129040283236963922624344456975024058167368431809068544577258472983979437818072648213608650098749369761056961203791265363665664696802245199962040041544438210327210476982203348458596093079296569561267409473914124132102055811493736199668788534872321705360511305248710796441479213354542583576076596250213454667968837996023273163069094700429467106663925419581193136339860545658673623955231932399404809404108767232000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

4023872600770937735437024339230039857193748642107146325437999104299385123986290205920442084869694048004799886101971960586316668729948085589013238296699445909974245040870737599188236277271887325197795059509952761208749754624970436014182780946464962910563938874378864873371191810458257836478499770124766328898359557354325131853239584630755574091142624174743493475534286465766116677973966688202912073791438537195882498081268678383745597317461360853795345242215865932019280908782973084313928444032812315586110369768013573042161687476096758713483120254785893207671691324484262361314125087802080002616831510273418279777047846358681701643650241536913982812648102130927612448963599287051149649754199093422215668325720808213331861168115536158365469840467089756029009505376164758477284218896796462449451607653534081989013854424879849599533191017233555566021394503997362807501378376153071277619268490343526252000158885351473316117021039681759215109077880193931781141945452572238655414610628921879602238389714760885062768629671466746975629112340824392081601537808898939645182632436716167621791689097799119037540312746222899880051954444142820121873617459926429565817466283029555702990243241531816172104658320367869061172601587835207515162842255402651704833042261439742869330616908979684825901254583271682264580665267699586526822728070757813918581788896522081643483448259932660433676601769996128318607883861502794659551311565520360939881806121385586003014356945272242063446317974605946825731037900840244324384656572450144028218852524709351906209290231364932734975655139587205596542287497740114133469627154228458623773875382304838656889764619273838149001407673104466402598994902222217659043399018860185665264850617997023561938970178600408118897299183110211712298459016419210688843871218556461249607987229085192968193723886426148396573822911231250241866493531439701374285319266498753372189406942814341185201580141233448280150513996942901534830776445690990731524332782882698646027898643211390835062170950025973898635542771967428222487575867657523442202075736305694988250879689281627538488633969099598262809561214509948717012445164612603790293091208890869420285106401821543994571568059418727489980942547421735824010636774045957417851608292301353580818400969963725242305608559037006242712434169090041536901059339838357779394109700277534720000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000008.000000ms

Pressanykeytocontinue============================外部学习链接：大数阶乘之计算从入门到精通本系列文章全面而深入详细的探讨大数阶乘的各种算法，包括求大数阶乘近似值的算法、精确值的算法。系列章将由浅入深地介绍各种大数阶乘算法。也会逐一讨论各种大数乘法，包括硬乘法，分治法，FNT和FFT大数乘法。系列文章还会讨论一些程序优化技巧和方法，包括SIMD指令的使用，循环展开，地址表直接跳转，汇编程序生成器等。系列文章将会给出十数个算法各异的C/C++程序，甚至包括完整的16位/32位汇编语言程序。/liangbch/category/292924.aspxTHU0602最大子序列和2010年02月07日星期日17:31清华06计算机复试机试题2试题二（7个测试数据，每个5分，共35分） 给出一个整数序列S，其中有N个数，定义其中一个非空连续子序列T中所有数的和为T的“序列和”。对于S的所有非空连续子序列T，求最大的序列和。变量条件：N为正整数，N≤1000000，结果序列和在范围（-2e63,2e63-1）以内。运行时限：2秒/测试数据输入格式：第一行为一个正整数N，第二行为N个整数，表示序列中的数。输出格式：仅一个整数，表示最大序列和。可执行文件：program2.exe样例一：Input.txt515-324Output.txt9解释：子序列“1，5，-3，2，4”具有最大的序列和，9=1+5+(-3)+2+4样例二：Input.txt61-234-106Output.txt7解释：子序列“3，4”具有最大的序列和，7=3+4样例三：Input.txt4-3-1-2-5Output.txt-1解释：子序列“-1”具有最大的序列和，-1=-1测试用例：试题二1.N=100，全正整数2.N=100，全负整数3.N=20000，直接使用二重循环，如果效率高可以出解4.N=500005.N=1000006.N=500000，序列和超过2^32，必须使用64位整数类型7.N=1000000//THU2最?大?子?序?列?和?#include<iostream>usingnamespacestd;intmain(){FILE*fr,*fw;fr=fopen("Input.txt","r");if(fr==NULL){printf("InputError\n");return0;}fw=fopen("Output.txt","w");__int64cur,sum;intn,i,a;//,a[1000005];while(fscanf(fr,"%d",&n)!=EOF){cur=0;sum=-32767;for(i=0;i<n;i++){fscanf(fr,"%d",&a);cur+=a;if(cur>sum)sum=cur;if(cur<0)cur=0;}fprintf(fw,"%ld\n",sum);}return0;}VC6下64位整数用__int64THU0603====》HDOJ1710&POJ22552010年02月06日星期六14:37清华06计算机复试机试题3试题三（8个测试数据，每个5分，共40分） 二叉树的前序、中序、后序遍历的定义：前序遍历：对任一子树，先访问跟，然后遍历其左子树，最后遍历其右子树；中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树；后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。给定一棵二叉树的前序遍历和中序遍历，求其后序遍历（提示：给定前序遍历与中序遍历能够唯一确定后序遍历）。变量条件：二叉树中的结点名称以大写字母表示：A，B，C....最多26个结点。运行时限：1秒/测试数据。输入格式：两行，第一行为前序遍历，第二行为中序遍历。输出格式：若不能根据前序和中序遍历求出后序遍历，输出NOANSWER；否则输出一行，为后序遍历。可执行文件：program3.exe样例一：Input.txtABCBACOutput.txtBCA样例二：Input.txtFDXEAGXDEFAGOutput.txtXEDGAF样例三：Input.txtABCDBDACOutput.txtNOANSWER这题原题没写代码，因为写完后不好找数据验证。找了相关的两个OJ题目如下，做参考二叉树前序中序求后序HDOJ1710//THU3BinaryTreeTraverse

///showproblem.php?pid=1710第一个做法是构建二叉树，然后再后序遍历输出。BestSolution里有15ms的算法，不知道怎么实现的20703722010-02-0612:15:18Accepted171031MS280K902BC++zd987#include<iostream>

usingnamespacestd;

intpre[1001],mid[1001];

typedefstructbt{

intinfo;

bt*left;

bt*right;

}bt;

bt*create(intprei,intmidi,intlen)

{

inti;

bt*p;

if(len<=0)

returnNULL;

for(i=0;i<len&&pre[prei]!=mid[midi+i];i++);

p=newbt;

p->info=pre[prei];

p->left=create(prei+1,midi,i);

p->right=create(prei+i+1,midi+i+1,len-i-1);

returnp;

}

voidpostorder(bt*t)

{

if(t==NULL)

return;

postorder(t->left);

postorder(t->right);

printf("%d",t->info);

deletet;

}

intmain()

{

intn,i,top1,top2;

bt*t;

while(scanf("%d",&n)!=EOF)

{

top1=top2=0;

for(i=0;i<n;i++)scanf("%d",&pre[i]);

for(i=0;i<n;i++)scanf("%d",&mid[i]);

t=create(0,0,n);

postorder(t->left);

postorder(t->right);

printf("%d\n",t->info);

}

return0;

}=================================================================================

后来参考网上资料，没有构建二叉树，直接输出后序序列20707862010-02-0614:29:22Accepted171031MS240K731BC++zd987#include<iostream>

usingnamespacestd;

shortintpre[1001],mid[1001];

voidprintpost(intstart1,intstart2,intsize,boolflag)

{

if(size==1)

{

printf("%hd",pre[start1]);

return;

}

elseif(size<=0)

return;

inti;

for(i=0;i<size&&pre[start1]!=mid[start2+i];i++);

printpost(start1+1,start2,i,false);

printpost(start1+i+1,start2+i+1,size-i-1,false);

if(flag)

printf("%hd\n",pre[start1]);

else

printf("%hd",pre[start1]);

}

intmain()

{

intn,i;

while(scanf("%d",&n)!=EOF)

{

for(i=0;i<n;i++)scanf("%hd",&pre[i]);

for(i=0;i<n;i++)scanf("%hd",&mid[i]);

printpost(0,0,n,true);

}

return0;

}==================================================================================POJ2255//THU3BinaryTreeTraverse///showproblem.php?pid=1710///JudgeOnline/problem?id=2255#include<iostream>usingnamespacestd;charpre[27],mid[27];voidprintpost(intstart1,intstart2,intsize,boolflag){if(size==1){printf("%c",pre[start1]);return;}elseif(size<=0)return;inti;for(i=0;i<size&&pre[start1]!=mid[start2+i];i++);printpost(start1+1,start2,i,false);printpost(start1+i+1,start2+i+1,size-i-1,false);if(flag)printf("%c\n",pre[start1]);elseprintf("%c",pre[start1]);}intmain(){intn,i;charch;while(scanf("%c",&ch)!=EOF){n=0;pre[n++]=ch;while(scanf("%c",&ch),ch!='')pre[n++]=ch;i=0;while(scanf("%c",&ch),ch!='\n')mid[i++]=ch;printpost(0,0,n,true);}return0;}THU0701质因数个数2010年02月26日星期五01:13清华07复试机试题1第一题（可执行文件名：program1.exe）

求正整数N(N>1)的质因数的个数。注意：1不是N的质因数：若N为质数，N是N的质因数。相同的质因数需要重复计算。如120=2*2*2*3*5，共有5个质因数。

正整数N，1<N<109

输出：

N的质因数的个数

样例输入：

120

样例输出

5别人的代码#include<fstream>#include<iostream>usingnamespacestd;boolZi(inti){for(intj=2;j<i+1;j++)if(i%j==0)returntrue;returnfalse;}intmain(){ifstreamin("input.txt");if(!in){cout<<"cannotopenthefile";return1;}intn,i;in>>n;in.close();intcount=1;for(i=2;i<n/2+1;i++)if(Zi(i)){while(n%i==0){n=n/i;count++;}}ofstreamout("output.txt");out<<count;out.close();return0;}==============下面这个代码自己在vc6下试的时候N只能到10e7，再大就不行了/**********************************************************************************

**本程序功能：计算从2—N的所有整数的质因数分解个数。用这个方法可以找到从2-N的所有素数

**主要的思想：用数组下标作为素数表的指针，每一个素数都指向下一个素数，线性时间查找素数

**

用第一维数组存储质因数分解的个数，当为1时是素数，否则为可分解的整数

**主要的方法：动态规划法、线性链表法。

**时间复杂度：线性时间复杂度

**作者：

BUG_lauo

**完成日期：2009-5-10

*************************************************************************************/

#include<iostream>

#include<stdlib.h>

#include<time.h>

usingnamespacestd;

#defineN100000000//2-N为要分解的整数

intnum[N][2];

voidcalc()//动态规划法及线性链表查找质因数分解（可以找到素数、质因数个数为m的数）

{

num[1][0]=1;//1表明2为质数

num[1][1]=0;//指向后一个质数，此时未计算，为结束标志符0

inti,j,k,l;

for(i=2;i<N;i++)//从三开始计算，不断地进行动态规划式的质因数分解

for(j=1;;)//从质因数二开始，查找能分解i的质因数

{

k=j+1,l=i+1;

if(l%k)//不能分解

{

if(k*k<l)//&&num[j][1])//如果前向指针不为0，并且k*k<l(可以为其质因数）

j=num[j][1];

else//表明不能用任何一个质数去分解它

{

num[i][0]=1,num[j][1]=i;num[i][1]=0;

break;

}

}

else//如果能分解，计算得到分解的质因数个数

{

num[i][0]=num[j][0]+num[l/k-1][0];//这里使用了动态规划的思想

break;

}

}

}

intmain()

{

clock_tt0=clock();

calc();

/*//输出质因数分解个数为1的所有整数（即素数）

for(inti=1;i<N;i++)

if(num[i][0]==1)

cout<<i+1<<"";

cout<<endl;

*/

cout<<clock()-t0<<endl;

}

/****************************测试结果如下

*当N=10,000时，所需时间：1毫秒左右

*当N=100,000时，所需时间：10毫秒

*当N=1,000,000时，所需时间：104毫秒

*当N=10,000,000时，所需时间：1155毫秒

*当N=100,000,000时，所需时间：12185毫秒

*当N>=1000,000,000时，数组超过所允许的最大长度，不能再计算了。

*由此可见，此函数的时间复杂度为：线性时间复杂度

*这已经是非常难能可贵的了

**************************************************************************************/

===================原理在这里：

from:/t/20020529/15/762184.html楼主wuyi8808（空间/IV）2002-05-2915:22:06在专题开发/技术/项目/数据结构与算法提问写了一个分解质因数的程序:

#include<fstream>#include<iostream>usingnamespacestd;boolZi(inti){for(intj=2;j<i+1;j++)if(i%j==0)returntrue;returnfalse;}intmain(){ifstreamin("input.txt");if(!in){cout<<"cannotopenthefile";return1;}intn,i;in>>n;in.close();intcount=1;for(i=2;i<n/2+1;i++)if(Zi(i)){while(n%i==0){n=n/i;count++;}}ofstreamout("output.txt");out<<count;out.close();return0;}运行结果如下:

>123456

#123456=2^6*3*643

>1234567890

#1234567890=2*3^2*5*3607*3803

程序中用到了doublesqrt(double)函数。实际上只需求出一个整数的平方根，返回整数值就可以了，是否用手算开平方的算法(只要精确到个位数)而不是调用sqrt()函数效率会更高？

另外，如果待分解的因子不是质数的话，就不需求平方根了，是不是有更好的方法。

欢迎大家讨论。

===============from/suno/archive/2008/02/04/1064368.html线性筛素数法boolnotp[mr];//素数判定__int64pr[670000],pn,ans;//pr存放素数,pn当前素数个数。voidgetprime(){pn=0;memset(notp,0,sizeof(notp));for(inti=2;i<mr;i++){if(!notp[i])pr[pn++]=i;for(intj=0;j<pn&&pr[j]*i<mr;j++){notp[pr[j]*i]=1;if(i%pr[j]==0)break;}}}===============================================================试着写了一个求解10e9范围内质因数的程序，线性筛选法使得时间消耗少了很多。#include<iostream>#include<windows.h>#include<time.h>#definemr1000000boolnotp[mr];__int64pr[670000],pn,ans;voidgetprime(){pn=0;memset(notp,0,sizeof(notp));for(inti=2;i<mr;i++){if(!notp[i])pr[pn++]=i;for(intj=0;j<pn&&pr[j]*i<mr;j++){notp[pr[j]*i]=1;if(i%pr[j]==0)break;}}}intmain(){intx,i;clock_tt=clock();getprime();FILE*fi,*fo;fi=fopen("input.txt","r");fo=fopen("output.txt","w");if(fi==NULL){printf("input.txtnotexist.\n");return1;}while(fscanf(fi,"%d",&x)!=EOF){for(i=0;i<pn;i++){while(x%pr[i]==0){fprintf(fo,"%d\n",pr[i]);x/=pr[i];}}}printf("%d\n",(clock()-t)/CLOCKS_PER_SEC*1000);return0;}THU0702二进制逆序数数制转换高精度除法2010年02月26日星期五02:37清华07复试机试题2第二题（可执行文件名：program2.exe）

对于一个十进制数A，将A转换为二进制数，然后按位逆序排列，再转换为十进制数B，我们称B为A的二进制逆序数。

例如对于十进制数173，它的二进制形式为101011101，逆序排列得到10110101，其十进制数为181，181即为173的二进制逆序数

输入：

一个1000位(即10999)以内的十进制数。

输出：

输入的十进制数的二进制逆序数。

样例输入：

173

样例输出：

181

=========================用了之前的任意进制转换的代码，进制转换的思想就是类似十进制转二进制，除二取余，反向取结果。这大数运算我还是不熟练，对着模板敲出来的。输入输出忘了走文件了，直接控制台显示的//THU0702#include<iostream>charx[1005];intt[40005],r[40005],a[40005];voidconvert(intm,intn){inti,k;while(a[0]>=1){for(i=a[0],k=0,r[0]=a[0];i>=1;i--){k=k*m+a[i];r[i]=k/n;k%=n;}t[++t[0]]=k;for(i=r[0];i>=1&&r[i]==0;i--,r[0]--);for(i=0;i<=r[0];i++)a[i]=r[i];memset(r,0,sizeof(r));}}intmain(){inti,len;while(scanf("%s",&x)!=EOF){len=strlen(x);for(i=1;i<=len;i++)a[i]=x[len-i]-'0';a[0]=len;t[0]=0;convert(10,2);len=t[0];for(i=1;i<=len;i++)a[i]=t[len-i+1];a[0]=len;t[0]=0;convert(2,10);for(i=t[0];i>=1;i--)printf("%d",t[i]);printf("\n");}return0;}=========================测试了10e999-1的逆序数，还有例题的数据999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999999

的二进制逆序数是1313879718456104225921995528497555855625152414017051819746489965175418594035237238181967239932841927943368022817082758088019245450978689926961358127631787144754373062120106902504163460853000843067796699510293924385333858122456855065858902248896798237625003273316840048212276610565777594650220087971045314428320151058750005609342489147979118966490742443460736039394240428715665805756852759038723483340673925976817738927482964402114965714304799463800409934310052632086140432337493715425228996938065617480808907282921149941529086583159223153433532316951801713658335729580873494927221089873496316794783258832015870740392981030767767381694472595414756562852923541765689073587747670092391424031753121396336709016851711661836346306563758330003792689969766198614622422147947840673020602402034420577569330700364058353336945488941858118999625840877707428774364480314067091860847013172017510649429383727243331385716379002573225953218262698752159526809155395451676718979338250747665133291785612263576853884955459THU07032010年02月26日清华07复试机试题3第三题（可执行文件名：program3.exe）

有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。

如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。

首先是要求凑成的邮票总值M，M<100

然后是一个数N，N〈20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。

输出：

能够凑成总值M的最少邮票张数。若无解，输出0。

样例输入：

10513334

样例输出：

3================01背包问题，//THU0703#include<iostream>#defineMAX9999intf[105],w[25];intmain(){inti,j,n,m;while(scanf("%d",&m)!=EOF){scanf("%d",&n);for(i=0;i<n;i++)scanf("%d",&w[i]);for(i=1;i<=m;i++)f[i]=MAX;f[0]=0;for(i=0;i<n;i++)for(j=m;j>=w[i];j--)if(f[j-w[i]]+1<f[j])f[j]=f[j-w[i]]+1;if(f[m]==MAX)printf("0\n");elseprintf("%d\n",f[m]);}return0;}=================别人的代码，参考：#include<iostream>#include<fstream>usingnamespacestd;boolcheck(intpost[],intpostCount,inttemp,intsum);intmain(){intpost[21];intpostCount;intsum;intresult=0;inti,j,k,m;ifstreamin("input.txt");in>>sum;in>>postCount;for(i=1;i<=postCount;i++)in>>post[i];in.close();ofstreamout("output.txt");boolflag=false;for(i=1;i<=postCount;i++)if(check(post,postCount,i,sum)){out<<i<<endl;return0;}out<<'0'<<endl;out.close();return0;}boolcheck(intpost[],intpostCount,inttemp,intsum){if(temp==1){for(inti=1;i<=postCount;i++){if(post[i]==sum)returntrue;}}elsefor(intj=1;j<=postCount;j++){if(check(post,postCount,temp-1,sum-post[j]))returntrue;}returnfalse;}2008年清华大学计算机系上机题（回忆版）

一、输入：两行

第一行：M和N

第二行：X

M和N是一个十进制数，M和N都在[2-36]之间，X是一个M进制数，X在[1-2*10^19]

输出：一行

第一行：现在要求你将M进制数X转换成N进制数输出

输入一：

1610

F

输出一：

15

=========//THU0801#include<iostream>intm,n;charx[2010];intt[2010],r[2010],a[2010];intlen;intmain(){inti,k;FILE*fi,*fo;fi=fopen("input.txt","r");fo=fopen("output.txt","w");if(fi==NULL)return1;while(fscanf(fi,"%d%d",&m,&n)!=EOF){fscanf(fi,"%s",&x);len=strlen(x);for(i=1;i<=len;i++)if(x[len-i]<='9'&&x[len-i]>='0')a[i]=x[len-i]-'0';elseif(x[len-i]>='A'&&x[len-i]<='Z')a[i]=x[len-i]-'A'+10;a[0]=len;while(a[0]>=1){for(i=a[0],k=0,r[0]=a[0];i>=1;i--){k=k*m+a[i];r[i]=k/n;k%=n;}t[++t[0]]=k;for(i=r[0];i>=1&&r[i]==0;i--,r[0]--);for(i=0;i<=r[0];i++)a[i]=r[i];}for(i=t[0];i>=1;i--)if(t[i]>=10&&t[i]<26)fprintf(fo,"%d",t[i]+'A'-10);elsefprintf(fo,"%d",t[i]);fprintf(fo,"\n");}return0;}==========类似题目：POJ1220///JudgeOnline/problem?id=1220#include<iostream>intm,n;charx[2010];intt[2010],r[2010],a[2010];intlen;intmain(){inti,k,nn;scanf("%d",&nn);while(nn--){scanf("%d%d%s",&m,&n,&x);len=strlen(x);for(i=1;i<=len;i++)if(x[len-i]<='9'&&x[len-i]>='0')a[i]=x[len-i]-'0';elseif(x[len-i]>='A'&&x[len-i]<='Z')a[i]=x[len-i]-'A'+10;elsea[i]=x[len-i]-'a'+36;a[0]=len;t[0]=0;while(a[0]>=1){for(i=a[0],k=0,r[0]=a[0];i>=1;i--){k=k*m+a[i];r[i]=k/n;k%=n;}t[++t[0]]=k;for(i=r[0];i>=1&&r[i]==0;i--,r[0]--);for(i=0;i<=r[0];i++)a[i]=r[i];memset(r,0,sizeof(r));}printf("%d%s\n%d",m,x,n);for(i=t[0];i>=1;i--)if(t[i]>=10&&t[i]<36)printf("%c",'A'+t[i]-10);elseif(t[i]>=36)printf("%c",'a'+t[i]-36);elseprintf("%d",t[i]);printf("\n\n");}return0;}=====思路：-problem:高精度进制转换.solution:迭代进制转换方法就是除留取余,只是不用把原数计算出来再去除,从高位到低位一位一位像手算除法一样每位都计算一下商和余数,最后的余数就是目标数的最低位,而每位的商的序列就是下一次迭代所使用的原数.这里注意一下处理好每次迭代原数的位数为第一次商不为0的位置.from:/View?id=dgtsspfh_78g4cq66dgTHU08022010年02月25日星期四22:48清华08复试机试题2二、按照手机键盘输入字母的方式，计划所花费的时间

如：a,b,c都在“1”键上，输入a只需要按一次，输入c需要连续按三次。

如果连续两个字符不在同一个按键上，则可直接按，如：ad需要按两下，kz需要按6下

如果连续两字符在同一个按键上，则两个按键之间需要等一段时间，如ac，在按了a之后，需要等一会儿才能按C。

现在假设每按一次需要花费一个时间段，等待时间需要花费两个时间段。

现在给出一串字符，需要计划出它所需要花费的时间。

输入一：bob

输出一：7

输入二：www

输出二：7==============

别人的代码：#include<iostream>#include<fstream>usingnamespacestd;intmain(){charch,pre;pre='\0';ifstreamin("input.txt");in>>ch;inttime=0;while(!in.eof()){switch(ch){case'a':case'd':case'g':case'j':case'm':case'p':case't':case'w':if(ch==pre)time+=3;elsetime+=1;pre=ch;break;case'b':case'e':case'h':case'k':case'n':case'q':case'u':case'x':if(ch==pre)time+=4;elsetime+=2;pre=ch;break;case'c':case'f':case'i':case'l':case'o':case'r':case'v':case'y':if(ch==pre)time+=5;elsetime+=3;pre=ch;break;case's':case'z':if(ch==pre)time+=6;elsetime+=4;pre=ch;break;default:cout<<"inputerror";exit(1);}in>>ch;}in.close();ofstreamout("output.txt");out<<time;out.close();return0;}===========THU0901递归求解矩阵二分求幂2010年02月25日星期四16:45清华09复试机试题1一、recur

数列

a0＝p；

a1＝q；

ak＝r*a(k-1)+s*a(k-2);

输入

pqrsk

输出

ak%10000

30%的数据K<20

80%的数据K<2000000

0<k<20000000001.递推数列,给定a0,a1,以及an=p*a(n-1)+q*a(n-2)中的p,q。这里n>=2。求第k个数对10000的模。

测试点区分度很分明，一个阴人点k=0，两到三个小k点，直接递归可过，四到五个中k点，直接线性递推可过，两个大k，必须用矩阵二分乘，否则TLE。另外，数组开得太大的直接runtimeerror=====//THU0901#include<iostream>intmain(){FILE*fin,*fout;fin=fopen("input.txt","r");fout=fopen("output.txt","w");if(fin==NULL)return1;intp,q,r,s,k,m,a[2][2],b[2][2],c[2][2],x,t,i,j,l;m=10000;while(fscanf(fin,"%d%d%d%d%d",&p,&q,&r,&s,&k)!=EOF){c[0][0]=r,c[0][1]=s,c[1][0]=1,c[1][1]=0;b[0][0]=b[1][1]=1;b[0][1]=b[1][0]=0;if(k==0){fprintf(fout,"%d\n",p);continue;}elseif(k==1){fprintf(fout,"%d\n",q);continue;}for(x=k-1;x>1;){if(x&1){for(i=0;i<2;i++)for(j=0;j<2;j++){for(t=0,l=0;l<2;l++)t+=b[i][l]*c[l][j];a[i][j]=t%m;}for(i=0;i<2;i++)for(j=0;j<2;j++)b[i][j]=a[i][j];x--;}else{for(i=0;i<2;i++)for(j=0;j<2;j++){for(t=0,l=0;l<2;l++)t+=c[i][l]*c[l][j];a[i][j]=t%m;}for(i=0;i<2;i++)for(j=0;j<2;j++)c[i][j]=a[i][j];x=x>>1;}}for(i=0;i<2;i++)for(j=0;j<2;j++){for(t=0,l=0;l<2;l++)t+=b[i][l]*