程序设计题型_第1页
程序设计题型_第2页
程序设计题型_第3页
程序设计题型_第4页
程序设计题型_第5页
已阅读5页,还剩46页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

程序设计题型PAGE1PAGE31、输出图形(本题100分) 22、旋转数字(本题100分) 33、求和(本题100分) 54、多项式相乘 75、二叉树 106、二叉树1 147、哈夫曼树及编码(100分) 168、哈夫曼树、编码及译码(100分) 199、判定连通图(100分) 2110、LeastTime(最短时间,100分) 2411、取序号判定素数 2612、名次与分数 2813、快速排序(100分) 3214、堆排序(100分) 3315、归并排序(100分) 3516、基数排序(100分) 3717、表达式求值 4018、取数相加 4219、大整数排序 45程序设计题型全文共51页,当前为第1页。程序设计题型全文共51页,当前为第1页。1、输出图形(本题100分)(graph.cpp)【题目描述】编写程序打印n行如下图形,其中1≤n≤26。n=4输出图形如下:DDCDDCBCDDCBABCD【输入】输入文件graph.in包含1个整数。【输出】输出文件graph.out。【输入输出样例1】graph.ingraph.out4DDCDDCBCDDCBABCD#include<iostream>usingnamespacestd;intmain(){ freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); inti,j,n; cin>>n; for(j=1;j<=n;j++) { for(i=1;i<=n-j;i++) cout<<""; for(i=1;i<=j;i++) cout<<(char)('A'+n-i); for(i=1;i<=j-1;i++) cout<<(char)('A'+n+i-j); cout<<endl; } return0;程序设计题型全文共51页,当前为第2页。}程序设计题型全文共51页,当前为第2页。2、旋转数字(本题100分)【题目描述】编写程序打印n行如下菱形图形(1≤n≤99),图形有n行n列个整数,图形从第1行的中间开始,数字分别是1,2,……n*n-1,n*n,并且顺时针向中间转入,如果1个数据项宽度不足n*n位,用0补足到n*n位。提醒:图案中没有数字的地方用空格填满,每行最后一个数字后面没有多余的空格。【输入】输入文件rotation.in包含1个整数n。【输出】输出文件rotation.out是一个菱形图形,图形从第1行的中间开始,数字分别是n*n,n*n-1,n*n-2,……1,并且顺时针向中间转入。【输入输出样例1】例如n=7,输出:01240223250322402604213941270520384842280619374749432907183646443008173545310916343210153311141213【限制】1≤n≤99【提示】 m=4 i=15;.printf("%0*d",m,i);//这里用*表示系数待定,m即为指定的宽度//上面语句输出“0015”,数据宽度为4,不足4位,前补0printf("%*c",m,‘‘);//左边语句输出“”,即输出4个空格#include"stdio.h"constintN0=2*100-1+10;inta[N0][N0]={0};structnode{ introw,col;}dir[4]={{1,1},{1,-1},{-1,-1},{-1,1}};程序设计题型全文共51页,当前为第3页。intmain()程序设计题型全文共51页,当前为第3页。{ inti,j,n; introw,col,row1,col1,d,m=0; freopen("rotation.in","r",stdin); freopen("rotation.out","w",stdout); scanf("%d",&n); row=1; col=n; d=0; intt=n*n; while(t!=0) { m++; t/=10; } for(i=1;i<=n*n;i++) { a[row][col]=i; row1=row+dir[d].row; col1=col+dir[d].col; if(row1<1||col1<1||row1>2*n-1||col1>2*n-1 ||a[row1][col1]!=0) { d=(d+1)%4; row1=row+dir[d].row; col1=col+dir[d].col; } row=row1; col=col1; } for(i=1;i<=2*n-1;i++) { for(j=1;j<=2*n-1;j++) if(a[i][j]!=0) printf("%0*d",m,a[i][j]); else if(i<=n&&j<n+i||i>n&&j<3*n-i)printf("%*c",m,''); printf("\n"); } return0;}3、求和(本题100分)(total.cpp)【问题描述】程序设计题型全文共51页,当前为第4页。有1个n×n的矩阵,从左上到右下称为主斜线(倾角135º),从右上到左下称为次斜线(倾角45º),在主斜线上最大,次斜线上最小的元素称为该矩阵的斜线鞍点,求出该矩阵所有斜线鞍点的和。程序设计题型全文共51页,当前为第4页。如5×5的矩阵:3259810441211286761457191221335633536789019次斜线主斜线元素7为上面矩阵的一个斜线鞍点,元素10和19也是上面矩阵的斜线鞍点。【输入】输入文件total.in第一行是一个整数n((1≤n≤100)),接下去是n行×n列的矩阵,矩阵的每个元素都是整数。【输出】输出文件total.out也只有1个整数,即该矩阵所有斜线鞍点的和(0≤和≤1010)。【输入输出样例1】otal.out5325981044121128676145719122133563353678901936#include<stdio.h>#defineNO100intmain(){ freopen("total.in","r",stdin); freopen("total.out","w",stdout); inti,j,x,y,max,min,n=0,sum=0; scanf("%d",&n); int**a=newint*[n]; i=-1; while(++i<n) { a[i]=newint[n]; j=-1; while(++j<n)scanf("%d",a[i]+j); } i=-1; while(++i<n) { j=-1;程序设计题型全文共51页,当前为第5页。 while(++j<n)程序设计题型全文共51页,当前为第5页。 { x=i,y=j; max=1,min=1; while(x>0&&y>0){x--;y--;} while(x<n&&y<n) { if(a[x][y]>a[i][j]) { max=0; break; } x++;y++; } x=i,y=j; while(x>0&&y<n-1){x--;y++;} while(x<n&&y>=0) { if(a[x][y]<a[i][j]) { min=0; break; } x++,y--; } if(!max||!min)continue; elsesum+=a[i][j]; } } printf("%d\n",sum); i=-1; while(++i<n)delete[]a[i]; delete[]a; return0;}4、多项式相乘(conv.cpp/c)【题目描述】编程实现若干个多项式相乘。多项式的输入输出格式为:系数在前,指数在后,各项按指数递增排列,每个多项式输入时以两个0结束。系数为0的项不输出。例如:1+4X3-9X5输入格式为:1001024304-9500或者1043-9500,其输出只能是:程序设计题型全文共51页,当前为第6页。1043-95程序设计题型全文共51页,当前为第6页。【输入】输入文件conv.in每行为一个多项式,多项式输入时以两个0结束。数据为若干行的多项式,例如:10110010-1100101200表示(1+x)(1-x)(1+x2)【输出】输出文件conv.out包含1行,为上述多项式相乘结果。上例的输出为:10-14表示1-x4【输入输出样例1】conv.inconv.out10110010-110010120010-14【数据限制】所有系数、指数均为整数(int类型)#include"stdio.h"typedefstructnode{ intc,e; structnode*next;}ND;ND*createLink(){ ND*head,*p; head=p=newND; intc,e; while(true) { if(scanf("%d%d",&c,&e)!=2)break; if(c==0&&e==0)break; p->next=newND; p=p->next; p->c=c; p->e=e; } p->next=NULL; returnhead;}voidprintLink(ND*head){ ND*p=head->next;程序设计题型全文共51页,当前为第7页。 while(p)程序设计题型全文共51页,当前为第7页。 { printf("%d%d",p->c,p->e); p=p->next; } printf("\n");}voidfreeLink(ND*head){ ND*p; while(head) { p=head; head=head->next; deletep; }}ND*addPoly(ND*ha,ND*hb){ ND*hc,*pc,*pa=ha->next,*pb=hb->next; hc=pc=newND; intc,e; while(pa||pb) { if(pa&&(pb==NULL||pa->e<pb->e)) { c=pa->c; e=pa->e; pa=pa->next; } elseif(pb&&(pa==NULL||pb->e<pa->e)) { c=pb->c; e=pb->e; pb=pb->next; } else { c=pa->c+pb->c; e=pa->e; pa=pa->next; pb=pb->next; } if(c) { pc->next=newND; pc=pc->next; pc->c=c; pc->e=e; }程序设计题型全文共51页,当前为第8页。 }程序设计题型全文共51页,当前为第8页。 pc->next=NULL; returnhc;}ND*oneXmulty(ND*pa,ND*hb){ ND*hc,*pc,*pb=hb->next; hc=pc=newND; while(pb) { pc->next=newND; pc=pc->next; pc->c=pa->c*pb->c; pc->e=pa->e+pb->e; pb=pb->next; } pc->next=NULL; returnhc;}ND*multyXmulty(ND*ha,ND*hb){ ND*hc,*ht,*pa=ha->next; hc=newND; hc->next=NULL; while(pa) { ht=oneXmulty(pa,hb); hc=addPoly(hc,ht); freeLink(ht); pa=pa->next; } returnhc;}intmain(){ ND*ha,*hc; freopen("conv.in","r",stdin); //freopen("conv.out","w",stdout); hc=createLink(); while(true) { ha=createLink(); if(ha->next==NULL)break; hc=multyXmulty(hc,ha); freeLink(ha); } printLink(hc);程序设计题型全文共51页,当前为第9页。 freeLink(hc);程序设计题型全文共51页,当前为第9页。 return0;}5、二叉树(bTree.cpp/c)【题目描述】已知二叉树的先序遍历序列和中序遍历序列,输出其后序遍历序列和层次序遍历序列。【输入】输入文件bTree.in有二行,分别是二叉树的先序遍历序列和中序遍历序列。【输出】输出文件bTree.out包含二行,分别是上述二叉树的后序遍历序列和层次序遍历序列。【输入输出样例1】bTree.inbTree.outabdeijfcghdijefbghcajifedhgcbaabdcegifhj【数据限制】所有序列字串长度<=100#include"stdio.h"#include"string.h"constintN0=100;structnode{ chardata; intlch,rch;}tree[N0+1];introot=1;voidcreateTree(introot,char*pri,char*mid){ char*p; intk; if(root==0||*pri=='\0'||*mid=='\0')return; tree[root].data=*pri; p=strchr(mid,*pri); *p='\0';//中序:mid(1)p+1(2) k=strlen(mid);//先序:pri+1(1),pri+k+1(2) if(k>0) { tree[root].lch=root+1; createTree(root+1,pri+1,mid); } if(strlen(p+1)>0) { tree[root].rch=root+k+1; createTree(root+k+1,pri+k+1,p+1); }程序设计题型全文共51页,当前为第10页。}程序设计题型全文共51页,当前为第10页。voidpostOrder(introot){ if(root) { postOrder(tree[root].lch); postOrder(tree[root].rch); printf("%c",tree[root].data); }}voidlayerOrder(introot){ intqu[N0+5],f=0,r=0; intt; if(root==0)return; qu[r++]=root; while(r!=f) { t=qu[f++]; printf("%c",tree[t].data); if(tree[t].lch) qu[r++]=tree[t].lch; if(tree[t].rch) qu[r++]=tree[t].rch; }}voidshowTree(introot,inttab,charch){ if(root==0)return; inti; for(i=1;i<tab;i++) printf(""); printf("%c(%c)\n",tree[root].data,ch); if(tree[root].lch) showTree(tree[root].lch,tab+6,'L'); if(tree[root].rch) showTree(tree[root].rch,tab+6,'R');}inthigh(introot){ if(root==0)return0; intlh,rh; lh=high(tree[root].lch); rh=high(tree[root].rch); return1+(lh>rh?lh:rh);}intleafNumber(introot){ if(root==0)return0;程序设计题型全文共51页,当前为第11页。 if(tree[root].lch==0&&tree[root].rch==0)程序设计题型全文共51页,当前为第11页。 return1; returnleafNumber(tree[root].lch)+leafNumber(tree[root].rch);}intmain(){ charpri[N0+1],mid[N0+1]; freopen("Btree.in","r",stdin);// freopen("Btree.out","w",stdout); gets(pri); gets(mid); createTree(root,pri,mid); postOrder(root); printf("\n"); layerOrder(root); printf("\n"); showTree(root,1,'T'); printf("%d\n",high(root)); printf("%d\n",leafNumber(root)); return0;}方法二:

#include<stdio.h>#include<string.h>structNode{charch;Node*lch;Node*rch;}*root;charpri[105],mid[105];Node*buildTree(char*pri,char*mid){char*pos=strchr(mid,*pri);if(pos){Node*temp=newNode;temp->ch=*pos;temp->lch=temp->rch=NULL;*pos='\0';intk=strlen(mid);if(*(pri+1))temp->lch=buildTree(pri+1,mid);程序设计题型全文共51页,当前为第12页。if(*(pos+1))程序设计题型全文共51页,当前为第12页。temp->rch=buildTree(pri+k+1,1+pos);returntemp;}returnNULL;}voidaftShowTree(Node*root){if(root!=NULL){aftShowTree(root->lch);aftShowTree(root->rch);putchar(root->ch);}}voidlevShowTree(Node*root){Node*arr[105]={0},*p;inttop=0,tail=0;arr[++tail]=root;while(tail!=top){p=arr[++top];if(p->lch)arr[++tail]=p->lch;if(p->rch)arr[++tail]=p->rch;putchar(p->ch);}}voidfree(Node*root){if(root){if(root->rch)free(root->rch);if(root->lch)free(root->lch);deleteroot;}}intmain(void){gets(pri);程序设计题型全文共51页,当前为第13页。gets(mid);程序设计题型全文共51页,当前为第13页。root=buildTree(pri,mid);aftShowTree(root);puts("");levShowTree(root);puts("");free(root);return0;}6、二叉树1(bTree1.cpp/c)【题目描述】已知一颗二叉树的先序遍历序列和中序遍历序列,输出该树的高度和该树的叶子数。【输入】输入文件bTree1.in有二行,分别是一颗二叉树的先序遍历序列和中序遍历序列。【输出】输出文件bTree1.out只有一行,包含两个整数,分别是该树的高度和叶子数,两个整数之间用一个空格隔开。【输入输出样例1】bTree1.inbTree1.outabdeijfcghdijefbghca63【数据限制】1<=所有序列字串长度<=100#include"stdio.h"#include"string.h"structTr{charda;Tr*lchild,*rchild;};Tr*Renew(char*bch,char*mch,intlen){Tr*root;intl;char*temp;if(len<=0){ root=NULL; returnNULL;}root=newTr;程序设计题型全文共51页,当前为第14页。root->da=*bch;程序设计题型全文共51页,当前为第14页。for(temp=mch;temp<mch+len;temp++){if(*temp==*bch)break;}l=strlen(mch)-strlen(temp);root->lchild=Renew(bch+1,mch,l);root->rchild=Renew(bch+1+l,temp+1,len-1-l);returnroot;}voidfreet(Tr*root){if(root->lchild!=NULL)freet(root->lchild);if(root->rchild!=NULL)freet(root->rchild);deleteroot;return;}intdepth(Tr*root){inth,lh,rh;if(root==NULL) h=0;else{lh=depth(root->lchild);rh=depth(root->rchild);if(lh>rh)h=lh+1;elseh=rh+1;}returnh;}intleaf(Tr*root){intnum=0;if(root!=NULL)if(root->lchild==NULL&&root->rchild==NULL) num++;else num=leaf(root->lchild)+leaf(root->rchild);returnnum;程序设计题型全文共51页,当前为第15页。}程序设计题型全文共51页,当前为第15页。intmain(){intlen;charbch[100],mch[100];Tr*root;freopen("Btree1.in","r",stdin);freopen("Btree1.out","w",stdout);gets(bch);gets(mch);len=strlen(bch);root=Renew(bch,mch,len);printf("%d%d",depth(root),leaf(root));freet(root);return0;}7、哈夫曼树及编码(100分)(huffman.cpp)【题目描述】给定一篇用于通信的英文电文,统计该电文中每个字符出现的频率,按频率左小右大的方法为这些字符建立哈夫曼(Huffamn)树,并编出每个字符的哈夫曼树码,输出该电文的哈夫曼码译文。【输入】输入文件huffman.in是一篇用于通信的英文电文。【输出】输出文件huffman.out输出该电文的哈夫曼码译文。【输入输出样例1】huffman.inhuffman.outaaccdddbacbcddddddd011011000011101001100010001111111【数据限制】2<=英文电文字符数<=10000000#include"stdio.h"#include"string.h"constintN0=256;constintINF=100000;structnode1{ intw,lch,rch,parent;}ht[N0+1];structnode2{ charch; charcode[N0+1];程序设计题型全文共51页,当前为第16页。 intstart;程序设计题型全文共51页,当前为第16页。}hc[N0+1];intn,root;charstr[INF];voidreadData(){ inta[N0]={0},p=0; charch; while(scanf("%c",&ch)==1) { a[ch]++;//ch='a',a[97]=1;ch='b',a[98]=1; //a[97]=3,a[98]=2,a[99]=4,a[100]=10 str[p++]=ch; } str[p]='\0'; n=0; inti; for(i=0;i<256;i++) if(a[i]) { n++; ht[n].w=a[i]; hc[n].ch=i; }}voidselectMin(intt,int*s1,int*s2){ intmin1=INF,min2=INF,i; for(i=1;i<=t;i++) if(ht[i].parent==0) if(ht[i].w<min1) { min2=min1; *s2=*s1; min1=ht[i].w; *s1=i; } elseif(ht[i].w<min2) { min2=ht[i].w; *s2=i; }}voidcreateHtHc(){ ints1,s2,w,child,parent,i; root=2*n-1; for(i=n+1;i<=root;i++) { selectMin(i-1,&s1,&s2); ht[i].w=ht[s1].w+ht[s2].w;程序设计题型全文共51页,当前为第17页。 ht[i].lch=s1;程序设计题型全文共51页,当前为第17页。 ht[i].rch=s2; ht[s1].parent=ht[s2].parent=i; } for(i=1;i<=n;i++) { child=i; parent=ht[child].parent; while(child!=root) { if(child==ht[parent].lch) hc[i].code[hc[i].start++]='0'; else hc[i].code[hc[i].start++]='1'; child=parent; parent=ht[child].parent; } }}voidstr2code(charstr[],charcode[]){ inti,j,k,p=0; for(i=0;str[i];i++) { for(j=0;j<=n;j++) if(str[i]==hc[j].ch) break; for(k=hc[j].start-1;k>=0;k--) code[p++]=hc[j].code[k]; } code[p]=0;}intmain(){ charcode[INF]; freopen("huffman.in","r",stdin); freopen("huffman.out","w",stdout); readData(); createHtHc(); str2code(str,code); puts(code); return0;}8、哈夫曼树、编码及译码(100分)(codeToTxt.cpp)【题目描述】程序设计题型全文共51页,当前为第18页。给定2个输入文件,第1个输入文件是用于通信的英文电文,统计该电文中每个字符出现的频率,按频率左小右大的方法为这些字符建立哈夫曼(Huffamn)树,并编出每个字符的哈夫曼树码;第2个输入文件是已经按第1个输入文件的英文电文编好的哈夫曼码,输出该哈夫曼码的对应的英文电文。程序设计题型全文共51页,当前为第18页。【输入】第1个输入文件为huffman.in是用于通信的英文电文,第2个输入文件codeToTxt.in是已经按第1个输入文件编好的哈夫曼码。【输出】输出文件codeToTxt.out输出codeToTxt.in文件内容的英文电文。【输入输出样例1】huffman.incodeToTxt.incodeToTxt.outaaccdddbacbcddddddd011111011000011101001100010001111adddaccdddbacbcdddd【数据限制】2<=英文电文字符数<=10000000#include"stdio.h"#include"string.h"constintN0=256;constintINF=100000;structnode1{ intw,lch,rch,parent;}ht[N0+1];structnode2{ charch; charcode[N0+1]; intstart;}hc[N0+1];intn,root;charstr[INF];voidreadData(){ inta[N0]={0},p=0; charch; while(scanf("%c",&ch)==1) { a[ch]++;//ch='a',a[97]=1;ch='b',a[98]=1; //a[97]=3,a[98]=2,a[99]=4,a[100]=10 str[p++]=ch; } str[p]='\0'; n=0; inti; for(i=0;i<256;i++) if(a[i]) { n++; ht[n].w=a[i];程序设计题型全文共51页,当前为第19页。 hc[n].ch=i;程序设计题型全文共51页,当前为第19页。 }}voidselectMin(intt,int*s1,int*s2){ intmin1=INF,min2=INF,i; for(i=1;i<=t;i++) if(ht[i].parent==0) if(ht[i].w<min1) { min2=min1; *s2=*s1; min1=ht[i].w; *s1=i; } elseif(ht[i].w<min2) { min2=ht[i].w; *s2=i; }}voidcreateHtHc(){ ints1,s2,w,child,parent,i; root=2*n-1; for(i=n+1;i<=root;i++) { selectMin(i-1,&s1,&s2); ht[i].w=ht[s1].w+ht[s2].w; ht[i].lch=s1; ht[i].rch=s2; ht[s1].parent=ht[s2].parent=i; } for(i=1;i<=n;i++) { child=i; parent=ht[child].parent; while(child!=root) { if(child==ht[parent].lch) hc[i].code[hc[i].start++]='0'; else hc[i].code[hc[i].start++]='1'; child=parent; parent=ht[child].parent; } }}voidcode2str(char*code,char*str){ char*p=code,*q=str; intr=root;程序设计题型全文共51页,当前为第20页。 while(*p)程序设计题型全文共51页,当前为第20页。 { if(*p=='0') r=ht[r].lch; else r=ht[r].rch; if(ht[r].lch==0) { *q++=hc[r].ch; r=root; } p++; } *q='\0';}intmain(){ charcode[INF]; freopen("huffman.in","r",stdin);readData(); freopen("codeToTxt.in","r",stdin); gets(code); freopen("codeToTxt.out","w",stdout); createHtHc(); code2str(code,str); puts(str); return0;}9、判定连通图(100分)(dist.cpp)【题目描述】给你一张描述n个城镇的公路表(n*n的对称矩阵A),请判定这n个城镇是否是连通的。公路表中表示了任意两个城镇的连通情况,矩阵元素a(i,j)=0表示城镇i,j不连通,a(i,j)!=0表示城镇i到城镇j的距离。【输入】输入文件dist.in的第一行为一个自然数n(1<n<=30); 接着n行,每行n个整数,是这n个城镇的公路表(元素的值小于1000)。【输出】输出文件dist.out包括一行,如果n个城镇是连通的输出Yes,否则输出No。程序设计题型全文共51页,当前为第21页。【输入输出样例1】程序设计题型全文共51页,当前为第21页。dist.indist.out6013490109900390068490057906504008740Yes【输入输出样例2】dist.indist.out6010490100900000008490000900000008000No【数据限制】1<n<=30#include"stdio.h"constintN0=100;constintINF=100000;intmap[N0][N0];intn;voidreadData(){ inti,j,t; scanf("%d",&n); for(i=1;i<=n;i++) for(j=1;j<=n;j++) { scanf("%d",&t); if(i==j) map[i][j]=0; elseif(t==0) map[i][j]=INF; elsemap[i][j]=t; }}/*voidDFS(intx){ ints[N0],top=0,mark[N0]={0},p,i; printf("%d",x); mark[x]=1; s[++top]=x;//push while(top) { p=s[top];//peak for(i=1;i<=n;i++) if(i!=p&&mark[i]==0&&map[p][i]!=INF) { printf("%d",i); mark[i]=1;程序设计题型全文共51页,当前为第22页。 s[++top]=i;程序设计题型全文共51页,当前为第22页。 break; } if(i>n) top--;//pop } printf("\n");}voidBFS(intx){ intq[N0],f=0,r=0,mark[N0]={0},p,i; printf("%d",x); mark[x]=1; q[r++]=x; while(r!=f) { p=q[f++]; for(i=1;i<=n;i++) if(i!=p&&mark[i]==0&&map[p][i]!=INF) { printf("%d",i); mark[i]=1; q[r++]=i; } } printf("\n");}*/voidcheck(intx){ ints[N0],top=0,mark[N0]={0},p,i; intnum=0; num++;//printf("%d",x); mark[x]=1; s[++top]=x;//push while(top) { p=s[top];//peak for(i=1;i<=n;i++) if(i!=p&&mark[i]==0&&map[p][i]!=INF) { num++;//printf("%d",i); mark[i]=1; s[++top]=i; break; } if(i>n) top--;//pop } if(num==n)printf("Yes\n"); elseprintf("No\n");程序设计题型全文共51页,当前为第23页。}程序设计题型全文共51页,当前为第23页。intmain(){ freopen("dist.in","r",stdin); freopen("dist.out","w",stdout); readData(); check(1); return0;}10、LeastTime(最短时间,100分)(Least.cpp/c)【Description】Youareaspy,andyouhavestolensometopsecretoftheenemy,nowyouaretofindawaywhichtakesyouleasttimetoescape.Therearesomemanycross-pointsandsomemanyroads,eventwocross-pointstherecanbemultipleroads.Youcanassumethatthecross-pointsarenumberedfrom1ton.Cross-point1isyourstartingpointandyouneedtogotocross-pointn.Allroadsarebidirectional(双向的).【Input】Thefirstlinecontainstwointegersnandm(1≤n≤200,0≤m≤10000),numberofcross-pointsandnumberofroadsrespectively.Nextmlineshasthreeintegersi,j,k(i≠j,1≤k≤10000),indicatingthereisaroadoflengthkconnectingcross-pointitocross-pointj.【Output】Outputonenumber,theshortestdistancefromcross-point1tocorss-pointn.Ifthereisnopathexist,output-1.Noextraspacesareallowed.【SampleInput/SampleOutput1】Least.inLeast.out461251342483491210241113程序设计题型全文共51页,当前为第24页。【SampleInput/SampleOutput2】程序设计题型全文共51页,当前为第24页。Least.inLeast.out67125134248349561024116515-1#include"stdio.h"constintN0=205;constintINF=1000000;intmap[N0][N0];intn,m;voidreadData(){ inti,j,k; scanf("%d%d",&n,&m); for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(i!=j) map[i][j]=INF; while(scanf("%d%d%d",&i,&j,&k)==3) {if(k<map[i][j]) {map[i][j]=k; map[j][i]=k;} }}voiddijkstra(intx){ intdist[N0],mark[N0]={0}; inti,j,k,min; mark[x]=1; for(i=1;i<=n;i++) { dist[i]=map[x][i]; } for(i=1;i<n;i++) { min=INF; for(j=1;j<=n;j++) if(mark[j]==0&&dist[j]<min) { min=dist[j]; k=j; } if(min==INF)break; mark[k]=1; for(j=1;j<=n;j++)程序设计题型全文共51页,当前为第25页。 if(mark[j]==0&&dist[j]>dist[k]+map[k][j])程序设计题型全文共51页,当前为第25页。 { dist[j]=dist[k]+map[k][j]; } } if(dist[n]!=INF)printf("%d",dist[n]); elseprintf("-1");}intmain(){ freopen("Least.in","r",stdin);freopen("Least.out","w",stdout); readData(); dijkstra(1); return0;}11、取序号判定素数(prime.cpp/c)【题目描述】一个数组a[0]到a[n-1]存放有n整数,其中2≤n≤100。求出n整数中最大数a[m1]和次最大数a[m2],并判定m1+m2是否为素数。【输入】输入文件prime.in包含n个整数。【输出】输出文件prime.out包含两行第1行是m1和m2,第2行若m1+m2为素数则输出Yes否则输出No。【输入输出样例1】prime.inprime.out235158-2-152Yes【输入输出样例2】prime.inprime.out12345678933333777543219999904No【限制】10-10≤整数a[i]≤10+10,2≤n≤100#include"stdio.h"constintMAX=100;voidprime(inta[],intl){inti,m1,m2,flag=0;程序设计题型全文共51页,当前为第26页。m1=m2=0;程序设计题型全文共51页,当前为第26页。for(i=1;i<l;i++){if(a[i]>a[m1]) { m1=i; }}if(m1==0)m2=1;for(i=1;i<l;i++){if(i!=m1) { if(a[i]>a[m2]) m2=i; }}printf("%d%d\n",m1,m2);for(i=1;i<=m1+m2;i++){ if((m1+m2)%i==0){flag++;}}if(flag<=2)printf("Yes");elseprintf("No");}intmain(){ freopen("prime.in","r",stdin); freopen("prime.out","w",stdout);inta[MAX],len=0,i=0;while(true){if(scanf("%d",&a[i])!=1)break;i++;len++;}prime(a,len);return0;}12、名次与分数(score.cpp/c)【问题描述】程序设计题型全文共51页,当前为第27页。输入数据是我校ACM集训队参加某次ACM网络联赛的成绩和账号,数据分上下两部分,数据上半部分第1列为名次,第2列为账号,第3列为AC(完成的)题目数。数据下半部分为我校ACM集训队队员的姓名和账号。任务1:将我校ACM集训队队员的成绩排序,即做一个队内排名。任务2:计算每个队员的成绩。成绩计算方法:程序设计题型全文共51页,当前为第27页。①没有参加网赛,成绩=0②有参加网赛,网赛AC0题,成绩=10③网赛AC题数≥1,成绩=101-队内名次*sqrt(队内名次)【注:sqrt为平方根】例如李饶立同学队内名次=1,则其成绩=101-1*sqrt(1)=100.000再如林哲斌同学队内名次=2,则其成绩=101-2*sqrt(2)=98.172。输出结果为两列:姓名和成绩,成绩保留3位小数,第4位四舍五入,按成绩由高到低排列。【输入】输入文件score.in为ACM网络联赛的成绩和帐号。【输出】输出文件score.out结果为按成绩由高到低排序的两列:姓名和成绩,成绩保留3位小数,第4位四舍五入。程序设计题型全文共51页,当前为第28页。程序设计题型全文共51页,当前为第28页。score.in score.out1 SZU2011_FM1_002 42 ZHBIT2011_FM1_001 33 SZU2011_FM1_014 34 FJUT2011_FM1_001 35 SZU2011_FM1_004 36 SZU2011_FM1_013 37 FJAU2011_FM1_002 38 SZU2011_FM1_010 39 FJUT2011_FM1_004 310 FJUT2011_FM1_009 311 FJUT2011_FM1_002 312 ZHBIT2011_FM1_002 313 FJAU2011_FM1_007 214 SZU2011_FM1_008 215 FJAU2011_FM1_018 216 FJAU2011_FM1_005 217 SZU2011_FM1_001 218 SZU2011_FM1_009 219 SZU2011_FM1_007 220 FJAU2011_FM1_022 221 FJAU2011_FM1_011 222 ZHBIT2011_FM1_003 223 FJUT2011_FM1_011 224 FJAU2011_FM1_015 225 FJAU2011_FM1_006 226 FJAU2011_FM1_008 227 FJUT2011_FM1_010 228 SZU2011_FM1_018 229 FJNU2011_FM1_010 230 SZU2011_FM1_015 231 FJAU2011_FM1_014 232 FJAU2011_FM1_020 233 FJAU2011_FM1_009 234 FJUT2011_FM1_006 135 SZU2011_FM1_011 136 SZU2011_FM1_005 137 FJUT2011_FM1_012 138 FJAU2011_FM1_025 139 FJUT2011_FM1_007 140 FJAU2011_FM1_001 141 FJUT2011_FM1_008 142 FJAU2011_FM1_023 143 FJUT2011_FM1_013 144 FJNU2011_FM1_009 145 FJUT2011_FM1_005 146 FJAU2011_FM1_024 147 FJNU2011_FM1_020 048 FJAU2011_FM1_012 049 FJAU2011_FM1_017 050 SZU2011_FM1_016 0 姓名 账号 朱智佳 FJAU2011_FM1_001 李饶立 FJAU2011_FM1_002 彭秦中 FJAU2011_FM1_003 陈竞郴 FJAU2011_FM1_004 林剑辉 FJAU2011_FM1_005 李光泽 FJAU2011_FM1_006 程序设计题型全文共51页,当前为第29页。林哲斌 FJAU2011_FM1_007 程序设计题型全文共51页,当前为第29页。程千兴 FJAU2011_FM1_008 黄艳丽 FJAU2011_FM1_009 吴胜杰 FJAU2011_FM1_010 谢荣祥 FJAU2011_FM1_011 杨少群 FJAU2011_FM1_012 郑志强 FJAU2011_FM1_013 沈炬 FJAU2011_FM1_014 罗雄飞 FJAU2011_FM1_015 邱一潮 FJAU2011_FM1_016 卢丽娜 FJAU2011_FM1_017 李绍江 FJAU2011_FM1_018 林雪勇 FJAU2011_FM1_019 李华均 FJAU2011_FM1_020 吴灿南 FJAU2011_FM1_021 李福彬 FJAU2011_FM1_022 苏桂明 FJAU2011_FM1_023 魏述文 FJAU2011_FM1_024 陈贻劲 FJAU2011_FM1_025 李饶立100.000林哲斌98.172李绍江95.804林剑辉93.000李福彬89.820谢荣祥86.303罗雄飞82.480李光泽78.373程千兴74.000沈炬69.377李华均64.517黄艳丽59.431陈贻劲54.128朱智佳48.617苏桂明42.905魏述文37.000杨少群10.000卢丽娜10.000彭秦中0.000陈竞郴0.000吴胜杰0.000郑志强0.000邱一潮0.000林雪勇0.000吴灿南0.000#include"stdio.h"#include"math.h"#include"string.h"constintN0=1000;structnode{ intmc; charname[15],num[30]; intac; doublescore;}student[N0+1];intn=0,totalNumber=0;voidreadData(){ chars[1000]; booldata1=true; while(gets(s)!=NULL) { if(strcmp(s,"")==0)continue; if(strstr(s,"姓名")!=NULL&&strstr(s,"账号")!=NULL) { data1=false; continue; } if(data1&&strstr(s,"FJAU")!=NULL)程序设计题型全文共51页,当前为第30页。 { intt;程序设计题型全文共51页,当前为第30页。 n++; totalNumber++; student[n].mc=n; sscanf(s,"%d%s%d",&t,student[n].num,&student[n].ac); if(student[n].ac==0) student[n].score=10; else student[n].score=101-n*sqrt(n); } if(!data1) { inti; charname1[15],num[30]; sscanf(s,"%s%s",name1,num); for(i=1;i<=n;i++) if(strcmp(num,student[i].num)==0) { strcpy(student[i].name,name1); break; } if(i>n) { totalNumber++; strcpy(student[totalNumber].name,name1); student[totalNumber].score=0; } } }}voidprintData(){ inti; for(i=1;i<=totalNumber;i++) printf("%s%.3f\n",student[i].name,student[i].score);}intmain(){ freopen("score.in","r",stdin);// freopen("score.out","w",stdout); readData(); printData(); return0;}13、快速排序(100分)(quickSort.cpp)程序设计题型全文共51页,当前为第31页。【题目描述】程序设计题型全文共51页,当前为第31页。 给定n个整数作从小到大快速排序,每次分组以本组的左边第1个数作标准元素,用两个指针向中间移动的分组策略,完成快速排序,输出分组次数。【输入】输入文件quickSort.in的第一行为一个自然数n(1<n≤30000), 接着若干行共有n个整数,每个整数之间用空格隔开。【输出】输出文件quickSort.out包括一个整数,完成快速排序整个过程的分组次数。【输入输出样例1】quickSort.inquickSort.out456122【输入输出样例2】quickSort.inquickSort.out416253【数据限制】1<n≤30000#include"stdio.h"constintN0=30005;intn,a[N0];intnum;intdivider(inta[],ints,intt){ inti,j; intc,temp; i=s;j=n; temp=a[s]; do {while((a[j]>=temp)&&(i<j)) j--; if(i<j) { a[i]=a[j]; i++; } while((a[i]<=temp)&&(i<j)) i++; if(i<j) { a[j]=a[i]; j--; }程序设计题型全文共51页,当前为第32页。 }while(i<j);程序设计题型全文共51页,当前为第32页。 a[i]=temp; returni;}voidQuicksort(inta[],ints,intt){ inti; if(s<t) { i=divider(a,s,t); num++; Quicksort(a,s,i-1); Quicksort(a,i+1,t); }}intmain(){ ints=1,t,i; freopen("quickSort.in","r",stdin); freopen("quickSort.out","w",stdout); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); t=n; Quicksort(a,s,t); printf("%d",num); return0;}14、堆排序(100分)(heapSort.cpp)【题目描述】 给定n个整数作从小到大堆排序,输出第二趟堆排序的结果。【输入】输入文件heapSort.in的第一行为一个自然数n(10≤n≤30000),接着若干行共有n个整数,每个整数之间用空格隔开。【输出】输出文件heapSort.out包括n个整数,是第二趟堆排序完成后的结果,每输出10个整数换行一次,各整数之间用一个空格隔开。【输入输出样例1】heapSort.inheapSort.out10293817158393323336153629338173323839程序设计题型全文共51页,当前为第33页。程序设计题型全文共51页,当前为第33页。10≤n≤30000#include"stdio.h"constintN0=30005;inta[N0];intn;voidheapone(inta[],ints,intt){ inti,j; inttemp; temp=a[s]; i=s; j=2*i; while(j<=t) { if((j<t)&&(a[j]<a[j+1])) j++; if(temp<a[j]) { a[i]=a[j]; i=j; j=2*i; } else j=t+1; } a[i]=temp;}voidHeapsort(inta[],intn){ inti; inttemp; for(i=n/2;i>=1;i--) heapone(a,i,n); for(i=n;i>n-1;i--) { temp=a[1]; a[1]=a[i]; a[i]=temp; heapone(a,1,i-1); } temp=a[1]; a[1]=a[i];程序设计题型全文共51页,当前为第34页。 a[i]=temp;程序设计题型全文共51页,当前为第34页。}intmain(){ inti; freopen("heapSort.in","r",stdin); freopen("heapSort.out","w",stdout); scanf("%d",&n); for(i=1;i<=n;i++) scanf("%d",&a[i]); Heapsort(a,n); for(i=1;i<=n;i++) { printf("%d",a[i]); if(i%10==0)printf("\n"); } return0;}15、归并排序(100分)(mergeSort.cpp)【题目描述】 给定n个整数作从小到大归并排序,输出第

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论