C++小型竞赛题目.doc

一、统计数字问题（1）题目描述一本书的页码从自然数1 开始顺序编码直到自然数n。书的页码按照通常的习惯编排，每个页码都不含多余的前导数字0。例如，第6 页用数字6 表示，而不是06 或006 等。数字计数问题要求对给定书的总页码n，计算出书的全部页码中分别用到多少次数字0，1，2，9。现在给定书的总页码十进制整数n (1n109) 。编程计算书的全部页码中分别用到多少次数字0，1，2，9。（2）输入要求输入只有1 行，给出表示书的总页码的整数n。（3）输出要求输出共有10行，在第k行输出页码中用到的数字k-1及其出现的次数。（4）样例输入11（5）样例输出0 11 42 13 14 15 16 17 18 19 1#includeusing namespace std;int main()int a10 = 0,0,0,0,0,0,0,0,0,0 ;int i, j, k;int n;cout 输入页数 n;for (i = 1; i = n; i+)for (j = i; j / 10 != 0 | j % 10 != 0; j = j / 10)for (k = 0; k = 9; k+)if (j % 10 = k)ak = ak + 1;for (i = 0; i = 9; i+)cout i ai n;return 0;没有问题。二、叙拉古猜想（1）题目描述有这样一个游戏：从一个正整数开始，两人轮流进行如下运算：若是奇数，就把这个数乘以3再加1；若是偶数，就把这个数除以2。这样演算下去，直到第一次得到1才算结束，首先得到1的获胜。比如，要是从1开始，就可以得到1421；要是从17开始，则可以得到175226134020105168421。这个问题就是叙拉古猜想，也叫科拉兹猜想或角谷猜想。现在，你和你的朋友一起玩这个游戏，由你先开始，请问谁获胜？（2）输入要求要求可有多组数据。第一行N（N=500），接下来有N行，每行一个整数M（M=10,000,000），表示你拿到的数字是M。（3）输出要求输出N行，如果是你获胜，输出“I win!”,否则输出“I lost!”。（4）样例输入2117（5）样例输出I win!I lost!#includeusing namespace std;int hanshu(int a)int n=0;for(;a!=1;n+)if(a%2=1)a=3*a+1;if(a%2=0)a=a/2;return n;int xiegula(int a)int n;n=hanshu(a);if(n%2=0)return 1;elsereturn 0;int main()int a500,i,n;cout输入数据组数n;cout输入正整数（从我开始）endl;for(i=0;iai;for(i=0;in;i+)if(xiegula(ai)=1)coutI win!endl;if(xiegula(ai)=0)coutI lost!endl;return 0;没有问题。三、全排列（1）题目描述给定n个整数，现请编程求它们所有的全排列。例如整数集1,2,3,较小的数字较先,这样按字典序生成的全排列是：1 2 31 3 22 1 32 3 13 1 23 2 1（2）输入要求输入包括两行，第一行给出正整数n(0n=8)，第二行是n个整数（大小范围：-10000, 10000）。（3）输出要求按字典序输出这n个整数的全排列，每一行给出一个排列。（4）样例输入31 23 88（5）样例输出1 23 881 88 2323 1 8823 88 188 1 2388 23 1#includeusing namespace std;int n;void swap(int *a,int *b)int t;t=*a;*a=*b;*b=t;void shuchu(int a)int i;for(i=0;in;i+)coutai ;coutendl;void digui(int a,int n)int i;if(n=1)shuchu(a);elsefor(i=0;in;i+)swap(ai,an-1);digui(a,n-1);swap(ai,an-1);int main()int i,a8;cout输入正整数个数(on=8)n;cout输入整数endl;for(i=0;iai;coutendl;digui(a,n);return 0; 然而一开始我忘记了从小到大。#include#includeusing namespace std;void paixu(int* a,int n) int temp; int i; int j;for(i=0;in-1;i+) for(j=0;j=aj+1) temp=aj+1; aj+1=aj; aj=temp;int kebukeyishuchu(int shu,int n)int a8,i,j,sum=0;bool kebukeyi=true;for(i=0;in;i+)an-i-1=shu%10;shu=shu/10;sum=sum+an-i-1;for(i=0;in;i+)if(ai=0)kebukeyi=false;if(sum!=n*(n+1)/2)kebukeyi=false;for(i=0;in&kebukeyi=true;i+)for(j=i+1;jn;j+)if(ai=aj)kebukeyi=false;if(kebukeyi=true)return 0;elsereturn 1;void shuchu(int shu,int a,int n)int i,b8;for(i=0;in;i+)bn-i-1=shu%10;shu=shu/10;for(i=0;in;i+)coutabi-1 ;coutendl;int main()int i,a8,b8,min=0,max=0,n;cout输入正整数个数(on=8)n;cout输入整数endl;for(i=0;iai;paixu(a,n);coutendl;for(i=0;in;i+)bi=i+1;min=min+bi*pow(10,n-i-1);max=max+bi*pow(10,i);for(i=min;i=max;i+)if(kebukeyishuchu(i,n)=1)continue;if(kebukeyishuchu(i,n)=0)shuchu(i,a,n);return 0; 四、C阶乘问题（1）题目描述也许你早就知道阶乘的含义，N阶乘是由1到N相乘而产生，如：12! = 123456789101112 = 479,001,60012的阶乘最右边的非零位为6。写一个程序，计算N(1=N=50,000,000)阶乘的最右边的非零位的值。注意:10,000,000！有2499999个零。（2）输入要求仅一行，包含一个正整数N。（3）输出要求单独一行，包含一个整数表示最右边的非零位的值。（4）样例输入12（5）样例输出6#includeusing namespace std;int main()int i,t,n;cout输入需要计算的阶乘数n;t=1;for(i=1;i=n;i+)t=t*i;for(;t%10=0;t=t/10);t=t%10;cout整数最右边非零位的值tendl;return 0; 这个题会在15,35这几种5尾数的结果后面出现bug，然后我已经想不到了。五、Yushi难题（1）题目描述有一位著名的数学家叫Yushi，他提出了一个世纪难题：给定一个正整数N，由1，2，N组成的集合 S0=1，2，3，N对于任意给定的集合，定义集合的和为集合中所有元素的和。集合S0可以被划分为两个不相交的子集合S1，S2。分别对这两个集合求和，如果两个集合的和相差恰好为K，则记为一种合法的划分方法。考虑N=7，K=0，则合法划分方法一种有4种：1,2,4,7,3,5,6；1,2,5,6,3,4,7；1,6,7,2,3,4,5；1,3,4,6,2,5,7对于给定的N和K，求出集合的划分方法总数。（2）输入要求仅含一行，两个整数N(1N32)和K(0=K=100000000)。（3）输出要求仅含一个数，表示划分集合的合法方案数。（4）样例输入7 0（5）样例输出4六、搬寝室（1）题目描述在大学的寝室里面，大家可根据自己的学号选择床号。如果某同学的学号是a，并且有0.k-1一共k张床，那么他就会选择a%k号床作为他的床位。显然，两个人不能睡在一张床上。那么给出所有同学的学号，请你为他们准备一间卧室，使得里面的床的数量最少。（2）输入要求第一行是人数n(1=n=5,000)；第2到第n+1行是每个同学的学号Si(1=Si=1,000,000)。（3）输出要求仅一行，是最少的床的数目。（4）样例输入54691013（5）样例输出8#includeusing namespace std;int main()int a100,b100;int n,i,j,k;cinn;bool chuangzuishao=true;for(i=0;iai;for(k=2;k+)chuangzuishao=true;for(i=0;in;i+)bi=(ai)%k;for(i=0;in;i+)for(j=i+1;jn;j+)if(bi=bj)chuangzuishao=false;if(chuangzuishao=true)break;coutkendl;return 0;这个应该也是没有问题的。七、确定进制（1）题目描述6+9 = 12 对于十进制来说是错误的，但是对于13进制来说是正确的。即, 6(13) + 9(13) = 12(13)， 而 12(13) = 1131 + 2130 = 15(10)。你的任务是写一段程序读入三个整数p、q和 r，然后确定一个进制 B(2=B=16) 使得 p + q = r。如果B有很多选择, 则输出最大的一个。如果没有合适的进制，则输出 0。（2）输入要求要求输入可有 T组测试样例。T在第一行给出。每一组测试样例占一行，包含三个整数p、q、r。 p、q、r的所有位都是数字，并且1 = p、q、r = 1,000,000。（3）输出要求对于每组测试样例输出一行，且包含一个整数：即使得p + q = r成立的最大的B。如果没有合适的B，则输出 0。（4）样例输入311 11 169 8 116 9 12（5）样例输出01613#include#includeusing namespace std;int shuzhi(int a,int b)int i,t=0;for(i=0;a/10!=0|a%10!=0;a=a/10,i+)t=t+a%10*pow(b,i);return t;int ceshi(int p,int q,int r)int B,t=0,a,b,c;for(B=2;B=16;B+)a=shuzhi(p,B);b=shuzhi(q,B);c=shuzhi(r,B);if(a+b=c)t=B;return t;int main()int a5003;int i,j,n,jieguo;cout测试样的组数n;for(i=0;in;i+)for(j=0;jaij;for(i=0;in;i+)jieguo=ceshi(ai0,ai1,ai2);coutjieguoendl;return 0; 这个题应该也是没有问题的。八、相似基因（1）题目描述众所周知，人类基因可以看作一个碱基对序列，它包含了4种核苷酸，简记为A,C,G,T。让我们观察这样一段基因序列 “ACCAGGTT”，这段序列共由8个核苷酸构成，其中第1位和第4位是碱基A，第2位和第3位是碱基C，第5位和第6位是碱基G，第7位和第8位是碱基T。Tom构造了这样一个0,1矩阵：1, 0, 0, 1, 0, 0, 0, 00, 1, 1, 0, 0, 0, 0, 00, 1, 1, 0, 0, 0, 0, 01, 0, 0, 1, 0, 0, 0, 00, 0, 0, 0, 1, 1, 0, 00, 0, 0, 0, 1, 1, 0, 00, 0, 0, 0, 0, 0, 1, 10, 0, 0, 0, 0, 0, 1, 1如果第i位的碱基与第j位的碱基一样，那么0,1矩阵的i行j列为1，否则为0。如果基因序列X与基因序列Y等长且具有相同的0,1矩阵，Tom就会认为X与Y是相似的基因序列。现在的问题是：给你两段长度为N的基因序列，请你帮助Tom判断它们是否相似。（1）输入要求可以有多组测试数据，每组数据第1行输入一个正整数N（1N1000000），第2行和第3行分别输入两段长度为N的基因序列（只由A,C,G,T四种字符构成）。输入直至N=0为结尾。（2）输出要求每组数据输出仅一行，如果相似则输出 “YES”,否则输出 “NO”,注意双引号不需要输出。（3）样例输入2AATG6ACCGTTGAATCC0（3）样例输出NOYES#includeusing namespace std;int main()int N,i,j,k;char a2100;int b100100;int c100100;cinN;for(;N!=0;)bool xiangshi=true;for(i=0;i2;i+)for(j=0;jaij;for(i=0;i2;i+)for(j=0;jN;j+)for(k=0;kN;k+)if(a0j=a0k)bjk=1;if(a1j=a1k)cjk=1;for(j=0;jN;j+)for(k=0;kN;k+)if(bjk)!=cjk)xiangshi=false;break;if(xiangshi=true)coutYESendl;elsecoutNON;return 0;这个题是没有问题的。九、团伙（1）题目描述在某城市里住着N个人，任何两个认识的人不是朋友就是敌人，而且满足：1、我朋友的朋友是我的朋友；2、我敌人的敌人是我的朋友；所有是朋友的人组成一个团伙。告诉你关于这N个人的M条信息，即某两个人是朋友，或者某两个人是敌人，请你编写一个程序，计算出这个城市最多可能有多少个团伙？（2）输入要求第一行包含一个整数N，第二行包含一个整数M，1N=1000，1=M=5000；接下来M行描述M条信息，内容为以下两者之一：“F X Y”表示X与Y是朋友；“E X Y”表示X与Y是敌人。其中1=X,Y=N。（3）输出要求包含一个整数，即可能的最大团伙数。（4）样例输入64E 1 4F 3 5F 4 6E 1 2（5）样例输出3然而这道题我已经醉了。#includeusing namespace std;int main()int i,N,j,M,k,b100,tuanhuoshu=0,h;int min,max;char a100;int c1002;cinNM;for(i=0;iN;i+)bi=1;for(i=0;iai;for(j=0;jcij;for(i=0;iM;i+)if(ai=F)min=ci0ci1?ci0:ci1;bmin-1=bmin-1+bmax-1;bmax-1=0;for(i=0;iN;i+)coutbi ;coutendl;for(i=0;iM;i+)for(j=i+1;jM;j+)if(ai=E&aj=E)for(k=0;k2;k+)for(h=0;hcj1-h)bcj1-h-1+=bci1-k-1;bci1-k-1=0;if(ci1-kcj1-h)bci1-k-1+=bcj1-h-1;bcj1-h-1=0;for(i=0;iN;i+)coutbi ;coutendl;for(i=0;iN;i+)if(bi!=0)tuanhuoshu+;couttuanhuoshuendl;return 0;这个应该是可以的。十、选课（1）题目描述学校实行学分制。每门的必修课都有固定的学分，同时还必须获得相应的选修课程学分。学校开设了N门的选修课程，学生有M天的时间学习。学生花一定量的天数选修一门课并考核通过就能获得相应的学分。在选修课程中，有一门课程可以直接选修，其它课程则需要一定的基础知识，必须在选了其它的一些课程的基础上才能选修。例如数据结构必须在选修了C+程序设计之后才能选修。我们称C+程序设计是数据结构的先修课。每门课的直接先修课最多只有一门。两门课也可能存在相同的先修课。每门课都有一个课号，依次为1，2，3，。你的任务是为自己确定一个选课方案，使得你能得到的学分最多，并且必须满足先