昆明网站建设一条龙服务,做食品那些网站好,如何提高网站的收录量,宠物电商网站模板C站的小伙伴们#xff0c;大家好呀#x1f61d;#x1f61d;#xff01;我最近在阅读学习刘汝佳老师的《算法竞赛入门经典》#xff0c;今天将整理本书的第三章——数组和字符串的一些习题#xff0c;本章习题较多#xff0c;下选取部分习题进行练习总结#xff0c;在这… C站的小伙伴们大家好呀我最近在阅读学习刘汝佳老师的《算法竞赛入门经典》今天将整理本书的第三章——数组和字符串的一些习题本章习题较多下选取部分习题进行练习总结在这里和大家分享一起进步呀✊✊✊ 数组和字符串 逆序输出开灯问题回文字习题得分(score)分子量(Molar Mass)数数字Digit Counting周期串 (Periodic Strings)DNA序列DNA Consensus String 思考 逆序输出
读入一些整数逆序输出到一行中。已知整数不超过100个。
#include stdio.h
#include string.h
int maxn[105];//若数组较长则将其设为全局变量
int main (void)
{int i0,x,k;memset(maxn,0,sizeof(maxn));//将数组清零while((scanf(%d,x))1) maxn[i]x;//先将x赋值给maxn[i]之后ifor (ki-1;k0;k--)printf(%d ,maxn[k]);return 0; }scanf()函数返回值 scanf()函数返回的是成功输入的变量的个数当输入结束时scanf()函数无法再次读取x将返回0。 如何告诉程序输入结束了呢 是按Enter/空格/TAB键吗我们会发现按Enter/空格/TAB键并没有反应这是因为程序正在等待输入。 在Windows下输入完毕后先按Enter键再按CtrlZ键最后再按Enter键。在Linux下输入完毕后按CtrlD键即可结束输入。 大数组需要定义在函数体外的原因 大数组需要定义在函数体外的原因全局变量在静态存储区内分配内存而局部变量是在栈内分配内存空间的。C语言编写的程序会在运行期间创建一个堆栈段用来保存函数的调用关系和局部变量。而在main函数内部定义大数组相当于在栈内需要一个很大的空间会造成栈的溢出。 因此当我们需要定义一个极大的数组时最好在main 函数外部定义这个大数组。
开灯问题
有n盏灯编号为1n。第1个人把所有灯打开第2个人按下所有编号为2的倍数的开关这些灯将被关掉第3个人按下所有编号为3的倍数的开关其中关掉的灯将被打开开着的灯将被关闭依此类推。一共有k个人问最后有哪些灯开着输入n和k输出开着的灯的编号。k≤n≤1000。 样例输入 7 3 样例输出 1 5 6 7 分析用a[1],a[2],a[3]……a[n]表示编号为123……n的灯是否开着。
#include stdio.h
#include string.h
int a[1000];
int main (void)
{int n,k,i,j;scanf(%d%d,n,k);memset(a,0,sizeof(a));//数组清零//0和1表示开灯和关灯两种状态for(i1;ik;i)//人for (j1;jn;j)//灯if (j%i0){if (a[j]0)a[j]1;elsea[j]0;}for(i1;in;i)if (a[i]1)printf(%d ,i);printf(\n);return 0;
}
0表示灯关的状态1表示灯开的状态。从第一个人开始判断是否是1~n编号的倍数如果是的话改变灯的状态即原来是1变为0原来是0变为1。
回文字
输入一个字符串判断它是否为回文串以及镜像串。输入字符串保证不含数字0。所谓回文串就是反转以后和原串相同如abba和madam。所有镜像串就是左右镜像之后和原串相同如2S和3AIAE。注意并不是每个字符在镜像之后都能得到一个合法字符。在本题中每个字符的镜像如图所示空白项表示该字符镜像后不能得到一个合法字符。
输入的每行包含一个字符串保证只有上述字符。不含空白字符判断它是否为回文 串和镜像串共4种组合。每组数据之后输出一个空行。 样例输入
NOTAPALINDROME ISAPALINILAPASI 2A3MEAS ATOYOTA
样例输出
NOTAPALINDROME – is not a palindrome. ISAPALINILAPASI – is a regular palindrome. 2A3MEAS – is a mirrored string. ATOYOTA – is a mirrored palindrome. 分析过程可以看这篇【C语言】经典题目二 下面是代码实现
#includestdio.h
#includestring.h
int main (void)
{char s[128]{0};int i,j,k,n;int flagH1,flagJ1;const char a[80]AEHIJLMOSTUVWXYZ12358;const char b[80]A3HILJMO2TUVWXY51SEZ8;gets(s);nstrlen(s);//判断是否是回文串for(i0,kn-1;ik;i,k--){if (s[i]!s[k]){flagH0;break;}}//判断是否是镜像串for(i0,kn-1;ik;i,j--){for (j0;s[j]!0;j){if (s[i]a[j]){if (s[k]!b[j]){flagJ0;}}}if (flagJ0) break;}//根据标志量判断if(flagH1 flagJ1)printf(%s -- is a mirrored palindrome.,s);else if (flagH1 flagJ0)printf( %s-- is a regular palindrome.,s);else if (flagH0 flagJ1)printf(%s -- is a mirrored string.,s);else printf(%s-- is not a palindrome.,s);return 0;
}习题
得分(score)
给出一个由O和X组成的串长度为180统计得分。每个O的得分为目前连续出现 的O的个数X的得分为0。例如OOXXOXXOOO的得分为1200100123。 分析对键盘输入的长串的每个字符进行判断。设置总和tot0若是X则tot不累加。若是O则需要判断前面O字符连续出现的个数。
#includestdio.h
int main (void)
{char a[80]{0};int tot0,i,k;gets(a);for(i0;a[i]!\0;i){if (a[i]O){tot1;for (ki-1;k0;k--){if (a[k]!O) break;else tot1;}}}printf(%d\n,tot);return 0;
}分子量(Molar Mass)
给出一种物质的分子式不带括号求分子量。本题中的分子式只包含4种原子分 别为C, H, O, N原子量分别为12.01, 1.008, 16.00, 14.01单位g/mol。例如C6H5OH的 分子量为94.108g/mol。
分析对输入的分子式的每个元素进行循环其中会有数字和’C’,‘H’,‘O’,N’四个字母而我们只对四个字母进行判断。若是的话看其后的一位是否为数字若是需要此原子量×数字若不是只需加它本身就可以了。 这里需要解决的是如果输入的字符数组a中的元素等于’C’或’H’或’O’或’N’如何利用其对应的原子量 这里用结构体解决比较方便。可以将’C‘与其原子量12.01进行“捆绑”将’H‘与其原子量1.008进行“捆绑”将’O‘与其原子量16.00进行“捆绑”将’N‘与其原子量14.01进行捆绑。
#includestdio.h
struct Molar
{char atom;double mass;
};
int main (void)
{char a[30]{0};int i,k;double tot0;gets(a);struct Molar b[4]{C,12.01,H,1.008,O,16.00,N,14.01};for (i0;a[i]!\0;i)//遍历输入的a字符数组{for (k0;k3;k)if(a[i]b[k].atom){if (a[i1]1 a[i1]9)//判断字符其后一位是否为数字totb[k].mass * (a[i1]-0);//注意分子式中的数字都是以字符型存入字符数组的elsetotb[k].mass;}}printf(%lf \n,tot);return 0;
}数数字Digit Counting
把前nn≤10000个整数顺次写在一起123456789101112…数一数09各出现多少次输出10个整数分别是01…9出现的次数。 分析利用sprintf()函数将1~10000输出到字符数组中。存入完毕后对字符数组进行遍历即可。 关于memset()函数 memset()函数初始化是以一个字节为单位的也就是说对字符数组才能初始化为任意值。 memset()函数可以很方便将字符数组全部数组全部初始化为某一个值例如 c char a[20]; memset(a,\0,sizeof(a)) 将字符数组亲空。 #includestdio.h
#includestring.h
char a[100000];
int main (void)
{int k0,i;int b[10]{0};//用于记录1~9出现的次数char x;//记从键盘读入的数字字符memset(a,\0,sizeof(a));//将字符数组清零scanf(%s,a);//对数组a进行遍历for(k0;a[k]!\0;k)b[a[k]-0];//输出数组bfor(k0;k9;k)printf(%d ,b[k]);return 0;
}周期串 (Periodic Strings)
如果一个字符串可以由某个长度为k的字符串重复多次得到则称该串以k为周期。例如abcabcabcabc以3为周期注意它也以6和12为周期。 输入一个长度不超过80的字符串输出其最小周期。 分析对于一个字符串其周期一定是字符串长度的因子因此只对因子判断即可。 如何判断是否是周期呢例如3为一个周期则一定满足a[0]a[03],a[1]a[13],a[2]a[23]; 但是要做判断的话满足的如上条件是仅仅不够的。例如会出现abcabcdddabcabcddd这种情况。所以我们需要对整个字符串进行判断。
#include stdio.h
#include string.h
int main (void)
{int i,k,len,n;int flag; //设置标志量char s[80];gets(s);lenstrlen(s); for(i1;ilen;i){if (len%i0) //判断是否是因子//若是判断能否为周期{flag1;for (k0;ki;k){for (n1;nlen/i-1;n){if (s[k]!s[kn*i]) flag0; }}}if (flag1){printf(%d\n,i);break;}}return 0;
}DNA序列DNA Consensus String
输入m个长度均为n的DNA序列求一个DNA序列到所有序列的总Hamming距离尽量 小。两个等长字符串的Hamming距离等于字符不同的位置个数例如ACGTGCGAHamming距离为2左数第1, 4个字符不同。
输入整数m和n4≤m≤50, 4≤n≤1000以及m个长度为n的DNA序列只包含字母ACGT输出到m个序列的Hamming距离和最小的DNA序列和对应的距离。如有多 解要求为字典序最小的解。例如对于下面5个DNA序列最优解为TAAGATAC。
TATGATAC TAAGCTAC AAAGATCC TGAGATAC TAAGATGT 后来发现的问题都错题了求一个DAN序列这是重点 我的问题是从输入的DAN序列中找DAN序列使得到所有的序列的总Hanming距离最小。 如果把题目改成这样的基础版下面是分析过程。
分析 首先是要处理m个DAN序列的储存我们可以利用二维数组进行存储因为二维数组可以看作是很多个一维数组组成。 其次是如何如何找出最优解。其实就是第一个序列和剩下的所有的序列进行比较然后出现不同的字符……这个和我们熟悉的选择排序是不一样的因为选择排序是和它后面的每一个数字进行比较而这个是和所有的进行比较。 那么如何储存每个序列总Hamming距离呢不妨可以放在一个数组中用来存放。 那么如何输出呢我们需要边存储边记录设置变量min若在每一次的比较中有总HAMMING距离小于min那么将此赋值给min并将此时的DAN序列拷贝到字符数组s中。最终输出s即可。
这里需要注意的是题目要求如有多解要求为字典序最小的解。所以我们可以试着从最后一个DAN序列开始循环。
#includestdio.h
#includestring.h
int main(void)
{char a[50][1000]; //用来存储DAN序列保证长度足够长char s[1000]; //用来存储最优DAN序列int b[50]{0}; //记录每个DAN序列的Hamming距离值int i0,k,j;int m,n;//m行n列scanf(%d%d,m,n);int min(m-1)*n; //min一定小于等于(m-1)*n 完成初始化for (i0;im;i)scanf(%s,a[i]);//输入m个DAN序列for(km-1;k0;k--) //从最后一行开始{for(i0;im;i){for(j0;jn;j){if (a[k][j]!a[i][j])b[k];}}if(b[k]min){minb[k];strcpy(s,a[k]);} }//输出//输出m个序列的Hamming值for (j0;jm;j)printf(%d ,b[j]);printf(\n);//输出最小的DAN序列及对应的值printf(%s\n%d,s,min);return 0;
}运行结构如下
思考
题目1必要的存储量 数组可以用来保存很多数据但在一些情况下并不需要把数据保存下来。下面哪些题目可以不借助数组哪些必须借助数组请编程实现。假设输入只能读一遍。
输入一些数统计个数。输入一些数求最大值、最小值和平均数。输入一些数哪两个数最接近。输入一些数求第二大的值。输入一些数求它们的方差。
1输入一些数统计个数。 显然不需要将数据存入数组中我们只需要设置一个变量作为累加器即可。 如下
#include stdio.h int main (void) {int count0;double x;while (scanf(%lf,x)1)count;printf(%d\n,count); }
2输入一些数求最大值、最小值和平均数。
第二个可以利用数组实现但也可以在循环中实现。
定义变量max和min用来存放最大值和最小值。假设第一个输入的数字既是最大值也是最小值即先完成初始化然后后面每输入一个数都和最大值和最小值比较若比最大值大则将此数赋值给max对于min同理。
那么如何求平均值呢可以定义和变量sum每输入一个数就将此数加到sum中然后最后sum除以输入的数的总数即可。
#includestdio.h
int main (void)
{int count1;double max,min,sum,x,ave;scanf(%lf,x);minmaxx;sumx;while(scanf(%lf,x)1){count1;if (xmax){maxx;}if (xmin){minx;}sumx;}avesum/count;printf(max%.2lf,min%.2lf,average%.2lf\n,max,min,ave);return 0;
} 3,输入一些数哪两个数最接近。假设输入的都是整数
我的想法是将输入的数字从小到大排序然后相邻的两个数之间相减即可将差值放到变量min中。利用循环依次判断两个数的差值若小于min将将此差值 赋值给min。
对于数字的排序可以利用选择排序法和起泡排序法。
#includestdio.h
#includestring.h int maxn[10000];//保证数组足够大 int main (void) {int k0,i,x;//x用来存放每次输入的值int count0;//累加器int tmp;//设置中间变量int min;//存放差值的最小值memset(maxn,0,sizeof(maxn));//数组初始化为0//输入一些数字while(scanf(%d,x)1){maxn[k]x;count;}//输入完毕对输入的数字排序//下采用选择法进行排序for(i0;icount;i){for (ki1;kcount;k){if (maxn[k]maxn[i]) //若后面的小于它则利用中间变量交换{tmpmaxn[i];maxn[i]maxn[k];maxn[k]tmp;}}}minmaxn[1]-maxn[0];//初始化for(i1;icount-1;i){if(maxn[i1]-maxn[i]min)minmaxn[i1]-maxn[i];}printf(%d\n,min);return 0; }
运行结果 4.输入一些数求第二大的值。 对于这个题目可以只借助两个变量来实现。一个变量存放当前输入的整数中的最大值一个变量存放当前输入的整数中的第二大值。
#includestdio.h
int main(void)
{int maxF,maxS,x;scanf(d,x);maxFmaxSx;//初始化while(scanf(%d,x)1){if(xmaxF){maxSmaxF; //易出错maxFx;1}else if(xmaxS xmaxF)maxSx;}printf(%d\n,maxS);return 0;
}5. 输入一些数求它们的方差。 求方差需要先求出来平均值。其次将各项与平均值作差并且平方相加再除以总数。我们需要利用输入的每个数所以需要利用数组将数据保存。
#include stdio.h
#include string.h
int maxn[1000];//定义足够大的数组
int main (void)
{memset(maxn,0,sizeof(maxn));//数组初始化为0int x,sum0,k0,count0,i;double ave,var0;//平均值和方差//输入一些数while(scanf(%d,x)1){maxn[k]x;sumx;count;}//计算平均值ave(double)sum/count;//注意强制转换sum//计算方差for (i0;icount;i){var(maxn[i]-ave)*(maxn[i]-ave);}varvar/count;printf(%.2lf,var);return 0;}
