outs:; }
选做题 6.5 等值数列段
如果一个数列中的某一段（至少有两个元素）的各元素值均相同，则称之为等值数列段。等值数列段中元素的个数叫做等值数列段的长度。
输入：由N个元素组成的整数数列A（其中N<=50) 输出：A中长度最大的等值数列段的始末位置，如果没有等值数列段，则输出No equal number list. 说明：始末位置是指数组下标，即0表示第一个元素。
如果有多个同等长度的等值数列，只输出第一个等值数列的起始位置。
当在一个LIST中出现两个等长的连续串的时候，我们的答案应该是第一个等长串。 #include
int a[50]; int f[10]={0};
int n,i,j,k=-1,t,q,s,o,o1,count=1,max=-1; scanf(\ for(i=0;i<=n-1;i++) scanf(\ do{
for(j=0;j<=n-1;j++) {
if(a[j]==a[j+1]) {
count=count+1; k=count;
f[j+1]=f[j+1]+k; }
if(a[j]!=a[j+1]) {
count=1; continue; }
max=k; }
}while(max printf(\ //for(q=0;q<=n-1;q++) //printf(\ //printf(\ else{ o=f[0]; for(s=1;s<=n-1;s++) { if(f[s]>o) { o=f[s]; o1=s; } } //printf(\ //printf(\ printf(\to %d.\\n\ } } 选做6.6 邮票组合 背景：我们寄信都要贴邮票，在邮局有一些小面值的邮票，通过这些小面值邮票中的一张或几张的组合，可以满足不同邮件的不同的邮资。 现在，邮局有4种不同面值的邮票。在每个信封上最多能贴5张邮票，面值可相同，可不同。 输入：四种邮票的面值。 输出：用这四种面值组成的邮资最大的从1开始的一个连续的区间。 说明：如结果为10，则表明使用4张邮票可组合出1、2、3、4、5、6、7、8、9、10这些邮资。 名词解释： 邮资：就是你寄东西需要花多少钱。 邮票面额：是由国家发行的具有固定价格的花纸片，被称为邮票。 如果你寄东西，邮局称了重量，告诉你要240分。这样你就要贴邮票了。如果现在邮局的邮票有面值为80分、50分、20分和10分的四种，你就可以采用不同的组合得到240的邮资，例如：采用3张80分的可以凑出240分；或者24张10分的凑起来240分也可以。显然不同邮票的组合都可以得到同样一种邮资。 #include int neng(int a[],int max) { int i,j,k,m,n; - 31 - int sum; for(i=0;i<5;i++) for(j=0;j<5;j++) for(k=0;k<5;k++) for(m=0;m<5;m++) for(n=0;n<5;n++) { sum=a[i]+a[j]+a[k]+a[m]+a[n]; if (sum==max) return 1; } return 0; } void main() { int a[5],i; int max=0; a[4]=0; scanf(\ while(1) { if(neng(a,max)) { max++; } else break; } printf(\} 选做6.7 十进制数转换为16位二进制数 将任一正整数（<65536）转换为 16 位二进制形式。 输入： 正整数 输出： 正整数的 16 位二进制数 友情提示：定义一个整型数组，数组有16个元素，保存变换后的二进制数。 #include int n,i; int a[16]; scanf(\ if(n>0&&n<65536) { for(i=0;i<=15;i++) { a[i]=n%2; n=n/2; } for(i=15;i>=0;i--) printf(\ printf(\ } else printf(\} 选做6.8 求各位数字组成的最大数 任意输入一个自然数，输出该自然数的各位数字组成的最大数。例如，输入 1593 ，则输出为 9531 。 输入： 自然数 n 输出： 各位数字组成的最大数 #include int n,i,j,max; int a[4]; scanf(\ for(i=0;i<=3;i++) {a[i]=(n); n=n/10;} for(j=0;j<=3;j++) for(i=0;i<3-j;i++) if(a[i+1]>a[i]) { max=a[i]; a[i]=a[i+1]; a[i+1]=max; } for(i=0;i<=3;i++) printf(\ printf(\} 选做题6.9 折半插入排序 排序是程序设计中的重要内容之一，据不完全统计，在一般的数据处理程序中，排序占去了处理机时间的四分之一，而在典型的安装程序中，一半以上的时间用在对表的排序上。 - 32 - 常用的排序算法有：直接插入排序，折半插入排序，希尔排序，起泡排序，快速排序，选择排序，堆排序等。其中直接插入排序的基本操作是将一个记录插入到已排好序的有序表中，从而得到一个新的、记录数增1的有序表。在直接插入排序中，为了找到插入位置，采用了顺序查找的方法。为了提高查找速度，可以采用折半查找，这种排序称折半插入排序。 折半查找法先取有序数组的中间元素与查找值相比较。如相等则查找成功；如查找值大于中间元素，则再取高半部的中间元素与查找值相比较。如查找值小于中间元素，则再取低半部的中间元素与查找值相比较。如此重复直到查找成功或最终未找到该数为止。在折半插入排序算法中，由于进行关键字比较的次数比较少，所以算法的效率就比较高。 例如：有序列10,90,80,30,20,15。我们进行折半插入排序的过程如下： 初始（第1趟）：有序子序列为空。待排序数据为10，则不需要进行关键字比较，直接插入。 第2趟：有序子序列为“10”，待排序数据为90，进行1次比较就可以确定插入位置，得到长度+1的有序子序列“10,90”。此时比较次数为 1 。 第2趟：有序子序列为“10,90”。待排序数据为80，取有序序列中间（取整）的元素10进行第 1 次比较，80大；则应该从“90”这个子序列中进行折半插入80，进行第 2 次比较，定位应该的插入位置，得到有序序列“10,80,90”。此趟比较次数为 2。 第3趟：有序子序列为“10,80,90”。待排序数据为30，取有序序列中间的元素80进行第 1 次比较，30小；则应该从“10”这个子序列中进行折半插入30，进行第 2 次比较，可以定位应该插入的位置，得到新的长度+1的有序子序列。此趟比较次数为 2。 第4趟：有序子序列为“10,30,80,90”。待排序数据为20，取有序序列中间的元素30进行第 1 次比较，20小；则应该从“10”这个子序列中进行折半插入20，进行第 2 次比较，可以确定应该插入的位置。此趟比较次数为 2。 第5趟：有序子序列为“10,20,30,80,90”。待排序数据为15，取有序序列中间的元素30进行第 1 次比较，15小；则应该从“10,20”这个子序列中进行折半插入15，取子序列中间的元素10，进行第 2 次比较，15大，则应该从“20”这个子序列中进行 折半插入排序，再进行 1 次比较就可以确定应该插入的位置。此趟比较次数为 3。 此时，完成排序，得到升序序列“10,15,20,30,80,90”。在整个排序过程中进行关键字比较的总次数 = 0+1+2+2+2+3 = 10。 输入：数列中元素个数（元素数量<=100） 数列 输出：使用折半插入排序后的有序升序数列 在折半插入排序过程中进行关键字比较的次数 说明：输出个数列之间用空格分隔 #include int n,a[100],b[100],i,j,count=0,lengthb=1; scanf(\ for(i=0;i scanf(\ b[0]=a[0]; for(i=1;i int c=0,d=lengthb-1,flag=0; do { if(a[i]>b[(c+d)/2]){ //待插入数字大于中间值 c=(c+d)/2+1; count++; } else { if(a[i] d=(c+d)/2-1; count++; } else { count++; flag=1; break; } } } while(c<=d); //处理最后一个数字 if(flag==0){ for(j=i-1;j>=c;j--){ b[j+1]=b[j]; - 33 - } b[c]=a[i]; lengthb++; } } for(i=0;i if(i!=lengthb-1)printf(\ } printf(\ return 0; } 8.1 合并字符串 输入两个已经按从小到大顺序排列好的字符串，编写一个合并两个字符串的函数，使合并后的字符串，仍然是从小到 大排列。 输入：两个已经排好顺序（升序）的两个字符串 输出：一个合并在一起的有序（升序）的字符串 要求：设计一个效率尽量高的算法，对每个字符串只扫描一遍就可以了。 如果采用先进行串连接，然后再进行排序的算法，则效率太低了。 #include char a[100],b[100],t; int k,i,j; gets(a); gets(b); strcat(a,b); k=strlen(a); for(j=1;j<=k;j++) for(i=0;i t=a[i]; a[i]=a[i+1]; a[i+1]=t; } puts(a); return 0; } 8.3 删除重复字符 背景： 输入一个长度不超过 100 的字符串，删除串中的重复字符。 输入： 输入要检查的字符串，长度不超过100个字符。例如：abacaeedabcdcd。 输出： 删除重复字符后的字符串。例如：abced。 #include char a[100],b[100]; int n,i,j,cnt=1; gets(a); n=strlen(a); b[0]=a[0]; for(i=1;i for(j=0;j if(a[i]==a[j]) break; } if(a[i]==a[j]&&i==j) { b[cnt]=a[i]; cnt++; } } for(i=0;i printf(\ printf(\ return 0; } 8.4 删除字符串中指定字符 输入两个字符串 s1 和 s2 ，在 s1 中删除任何 s2 中有的字符。例如， s1 ：“ abc123ad ”， s2 ：“ a1 ” ，则输出“bc23d ”。 输入： 两个字符串 s1 和 s2 输出： 删除后的字符串 s1 #include - 34 - #include char a[100],b[100],c[100]; int x,y,i,j,cnt; scanf(\ scanf(\ x=strlen(b); y=strlen(a); for(j=0;j cnt=0; for(i=0;i c[cnt]=a[i]; cnt++; } strcpy(a,c); y=cnt; } for(i=0;i 8.5 单词有多少 用空格或换行分开的字符串称为单词。输入多行字符串，直到遇到了单词 \时才停止。最后输出单词的数量。用于分割单词的空格或换行可能多于1个。 输入： 多个字符串 输出： 单词的数量 #include int count=0; char *word ; while(1) { word=(char *) malloc (sizeof(char)*20); scanf(\ ++count; if(0==strcmp(word,\ break; free(word); } printf(\ } 8.6 在指定位置插入字符串 输入两个字符串 s1 、 s2 和 s1 中任意字符 k ，在 s1 中的指定字符 k 第一次出现的位置处插入字符串 s2 并输出。 输入： 两个字符串 s1 、 s2 和 s1 中任意字符 k 输出： 插入后的字符串 s1 #include char s1[100],s2[100],s3[100]; char c; int i,j,n,t,count=-1; gets(s1); gets(s2); n=strlen(s1); t=strlen(s2); scanf(\ for(i=0;i<=n-1;i++) {count=count+1; if(c==s1[i]) break;} for(i=0;i for(i=count;i for(i=count+t;i<=n+t;i++) s3[i]=s1[i-t]; puts(s3); /*for(i=0;i printf(\ } printf(\} 选做T 8.1 拱猪计分 - 35 -