devbox
秋刀鱼在做梦
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法竞赛入门经典（第二版）第三章习题_dna consensus string 卜东波

作者：秋刀鱼在做梦 | 2024-08-18 06:55:14

赞

踩

dna consensus string 卜东波

声明：作者水平有限，只是会基础C语言的小菜，C++还未入门。作者仅根据算法竞赛入门经典（第二版）书上第三章习题所述题意而编写，并未严格按照原题的输入输出编写，代码仅经过个人测试（OJ网站太慢了）。代码、文章排版及书写如有错误，欢迎指正！

目录

声明：作者水平有限，只是会C语言的小菜，C++还未入门。作者仅根据算法竞赛入门经典（第二版）书上第三章习题所述题意而编写，并未严格按照原题的输入输出编写，程序仅经过个人测试，如有错误，欢迎指正！

习题3-1 得分（Score，ACM/ICPC Seoul 2005，UVa1585）

习题3-2 分子量（Molar Mass，ACM/ICPC Seoul 2007，UVa1586）

习题3-3 数数字（Digit Counting，ACM/ICPC Danang 2007，UVa1225）

习题3-4 周期串（Periodic Strings，UVa455）

习题3-5 谜题（Puzzle，ACM/ICPC World Finals 1993，UVa227）

习题3-6 纵横字谜的答案（Crossword Answers，ACM/ICPC World Finals 1994，UVa232）

习题3-7 DNA序列（DNA Consensus String，ACM/ICPC Seoul 2006，UVa1368）

习题3-8 循环小数（Repeating Decimals，ACM/ICPC World Finals 1990，UVa202）

习题3-9 子序列（All in All，UVa10340） 

习题3-10 盒子（Box，ACM/ICPC NEERC 2004，UVa1587）

习题3-11 换抵挡装置（Kickdown，ACM/ICPC NEERC 2006，UVa1588）

习题3-12  浮点数（Floating-Point Numbers，UVa11809）  

习题3-1 得分（Score，ACM/ICPC Seoul 2005，UVa1585）

        给出一个由O和X组成的串（长度为1~80），统计得分。每个O的得分为目前连续出现的O的个数，X的得分为0。例如，OOXXOXXOOO的得分为1+2+0+0+1+0+0+1+2+3。

  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. int main() 
  5. {
  6. 	char ox[100];
  7. 	while(scanf("%s", ox) == 1)
  8. 	{
  9. 		int sum = 0, t = 0;
  10. 		for(int i = 0; i < strlen(ox); i++)
  11. 		{
  12. 			if(ox[i] == 'O')
  13. 				t++;
  14. 			else if(ox[i] == 'X')
  15. 				t = 0;
  16. 			sum += t;
  17. 		}
  18. 		printf("%d\n", sum);
  19. 	}
  20. 	return 0;
  21. }

习题3-2 分子量（Molar Mass，ACM/ICPC Seoul 2007，UVa1586）

        给出一种物质的分子式（不带括号），求分子量。本题中的分子式只包含4种原子，分别为C，H，O，N，原子量分贝为12.01，1.008，16.00，14.01（单位：g/mol）。例如，C6H5OH的分子量为94.108g/mol。

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <ctype.h>
  4. #include <math.h>
  5.  
  6. #define c 12.01
  7. #define h 1.008
  8. #define o 16.00
  9. #define n 14.01
  10.  
  11. int i;	//全局变量 
  12.  
  13. //判断元素数字下标 
  14. int subscript(char *a)
  15. {
  16. 	int t = 0, s = 0;
  17. 	while(isdigit(a[++i]))	//判断元素符号后面的数字个数 
  18. 		t++;
  19. 	if(t == 0)
  20. 		return 1;
  21. 	for(; t > 0; t--)
  22. 		s += (a[i-t] - '0')*pow(10,t-1);	//转化 
  23. 	return s;
  24. } 
  25.  
  26. int main() 
  27. {
  28. 	char mf[100];
  29. 	while(scanf("%s", mf) == 1)
  30. 	{
  31. 		float sum = 0;
  32. 		for(i = 0; i < strlen(mf);)
  33. 		{
  34. 			switch(mf[i])
  35.            		{
  36.                		case 'C':sum += c*subscript(mf);
  37.                     	break;
  38.                 	case 'H':sum += h*subscript(mf);
  39.                     	break;
  40.                 	case 'O':sum += o*subscript(mf);
  41.                     	break;
  42.                 	case 'N':sum += n*subscript(mf);
  43.                     	break;
  44.             	}
  45. 		}
  46. 		printf("%.3fg/mol\n", sum);	//保留三位小数 
  47. 	}
  48. 	return 0;
  49. }

注意：个人认为分子式中元素符号后有多位数的情况不能忽略。

习题3-3 数数字（Digit Counting，ACM/ICPC Danang 2007，UVa1225）

        把前n（n≤10000）个整数顺次写在一起：123456789101112...数一数0~9各出现多少次（输出10个整数，分别是0，1， ... ，9出现的次数）。

  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. int main() 
  5. {
  6. 	char a[10000];
  7. 	while(scanf("%s", a) == 1)
  8. 	{
  9. 		int num[10] = {};	//数组初始化 
  10. 		for(int i = 0; i < strlen(a); i++)
  11. 			num[a[i] - '0']++;	//对应数组项计数 
  12. 		for(int i = 0; i < 10; i++)
  13. 			printf("%5d", num[i]);
  14. 		printf("\n");
  15. 	}
  16. 	return 0;
  17. }

习题3-4 周期串（Periodic Strings，UVa455）

        如果一个字符串可以由某个长度为k的字符串重复多次得到，则称该串以k为周期。例如，abcabcabcabc以3为周期（注意，它也以6和12为周期）。

        输入一个长度不超过80的字符串，输出其最小周期。

  1. #include <stdio.h> 
  2. #include <string.h> 
  3.  
  4. int main() 
  5. { 
  6. 	char string1[100]; 
  7. 	while(scanf("%s", string1) == 1)
  8. 	{
  9.    		char string2[85]; 		
  10. 		for(int k = 1; k <= strlen(string1); k++)
  11. 		{
  12.    			strncpy(string2,string1,k); 	//从首部开始截取字符串，长度为k
  13. 			int i = 0;
  14. 			for(; i < strlen(string1); i++)
  15. 				if(string1[i] != string2[i % k])	//遍历字符串判断是否周期循环 
  16. 					break;	
  17. 			if(i >= strlen(string1) && strlen(string1) % k == 0)
  18. 			{
  19. 				//printf("%s\n", string2);
  20. 				printf("%d\n",k);
  21. 				break;
  22. 			}
  23. 		}
  24.    	}
  25.    return 0; 
  26. }

注：C 库函数 char *strncpy(char *dest, const char *src, size_t n) 把 src 所指向的字符串复制到 dest，最多复制 n 个字符。当 src 的长度小于 n 时，dest 的剩余部分将用空字节填充。

习题3-5 谜题（Puzzle，ACM/ICPC World Finals 1993，UVa227）

        有一个5*5的网格，其中恰好有一个格子是空的，其他格子各有一个字母。一共有4种指令：A，B，L，R，分别表示把空格上、下、左右的相邻字母移到空格种。输入初始网格和指令序列（以数字0结束），输出指令执行完毕后的网格。如果有非法指令，应输出“This puzzle has no final configuration.”，例如，图3-5种执行ARRBBL0后，效果如图3-6所示。

  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. int main()
  5. {
  6. 	char a[30];
  7. 	scanf("%[^\n]", a);	//读取除回车以外的字符 
  8. 	fflush(stdin);	//清空输入缓冲区，确保不影响后面的数据读取 
  9. 	char grid[5][5];
  10. 	for(int i = 0, k = 0; i < 5; i++)
  11. 		for(int j = 0; j < 5; j++)	
  12. 			grid[i][j] = a[k++];
  13. 	/*for(int i = 0; i < 5; i++)	//打印输入网格 
  14. 	{
  15. 		for(int j = 0; j < 5; j++)	
  16. 			printf("%c", grid[i][j]);
  17. 		printf("\n");
  18. 	}*/
  19. 	char *ptr;
  20. 	int x, y;
  21. 	ptr = strchr(a, ' ');	//寻找空格位置
  22. 	x = (ptr - a) / 5, y = (ptr - a) % 5;	
  23. 	//printf("空格的坐标为(%d,%d)\n", x, y);
  24. 	char cmd[100];
  25. 	scanf("%[^0]", cmd);	//读取除'0'以外的字符 
  26. 	//printf("%s\n", cmd);
  27. 	for(int i = 0; i < strlen(cmd); i++)
  28. 	{
  29. 		switch(cmd[i])
  30. 		{
  31. 			case 'A':
  32. 				grid[x][y] = grid[x - 1][y];
  33. 				grid[x - 1][y] = ' ';
  34. 				x = x - 1;
  35. 				break;
  36. 			case 'B':
  37. 				grid[x][y] = grid[x + 1][y];
  38. 				grid[x + 1][y] = ' ';
  39. 				x = x + 1;
  40. 				break;
  41. 			case 'L':
  42. 				grid[x][y] = grid[x][y - 1];
  43. 				grid[x][y - 1] = ' ';
  44. 				y = y - 1;
  45. 				break;	
  46. 			case 'R':
  47. 				grid[x][y] = grid[x][y + 1];
  48. 				grid[x][y + 1] = ' ';
  49. 				y = y + 1;
  50. 				break;
  51. 			default:
  52. 				printf("This puzzle has no final configuration.\n");
  53. 				return 0;
  54. 		}
  55. 	}
  56. 	for(int i = 0; i < 5; i++)
  57. 	{
  58. 		for(int j = 0; j < 5; j++)	
  59. 			printf("%c", grid[i][j]);
  60. 		printf("\n");
  61. 	}		
  62. 	return 0;
  63. }

习题3-6 纵横字谜的答案（Crossword Answers，ACM/ICPC World Finals 1994，UVa232）

       输入一个r行c列（1≤r，c≤10）的网格，黑格用“*”表示，每个白格都填有一个字母。如果一个白格的左边相邻位置或者上边相邻位置没有白格（可能是黑格，也可能出了网格边界），则称这个白格是一个起始格。

        首先把所有起始格按照从上到下、从左到右的顺序编号为1, 2, 3,…，如图3-7所示。

         接下来要找出所有横向单词（Across）。这些单词必须从一个起始格开始，向右延伸到一个黑格的左边或者整个网格的最右列。最后找出所有竖向单词（Down）。这些单词必须从一个起始格开始，向下延伸到一个黑格的上边或者整个网格的最下行。输入输出格式和样例请参考原题。

 （哈哈，题目没怎么看懂，也不想看懂，找了个其他作者写的代码）请参考：

  1. #include<stdio.h>
  2. #include<string.h>
  3. #define m 105
  4. char s[m][m];
  5. int sta[m][m];
  6. int main(){
  7. 	int r,c,kase=0;
  8. 	while(scanf("%d%d\n",&r,&c)==2&&r){
  9. 		memset(sta,0,sizeof(sta));
  10. 		int pos=1;
  11. 		for(int i=0;i<r;i++){
  12. 			for(int j=0;j<c;j++){
  13. 				scanf("%c",&s[i][j]);
  14. 				if(s[i][j]=='*')continue;
  15. 				if(j<1||s[i][j-1]=='*'||i<1||s[i-1][j]=='*'){
  16. 					sta[i][j]=pos;
  17. 					pos++;
  18. 				}
  19. 			}
  20. 			getchar();
  21. 		}
  22. 		kase++;
  23. 		if(kase>1)printf("\n");
  24. 		printf("puzzle #%d:\n",kase);
  25. 		printf("Across\n");
  26. 		for(int i=0;i<r;i++){
  27. 			int j=0;
  28. 			while(j<c){
  29. 				if(s[i][j]=='*'||sta[i][j]==0){
  30. 					j++;
  31. 					continue;
  32. 					
  33. 				}
  34. 				printf("%3d.%c",sta[i][j],s[i][j]);
  35. 				j++;
  36. 				while(s[i][j]!='*'&&j<c){
  37. 					printf("%c",s[i][j]);
  38. 					j++;
  39. 				}
  40. 				printf("\n");
  41. 			}
  42. 		}
  43. 		printf("Down\n");
  44. 		for(int i=0;i<r;i++){
  45. 			for(int j=0;j<c;j++){
  46. 					if(s[i][j]=='*'||sta[i][j]==0)continue;
  47. 					printf("%3d.%c",sta[i][j],s[i][j]);
  48. 					sta[i][j]=0;
  49. 					int k=i+1;
  50. 					while(k<r&&s[k][j]!='*'){
  51. 						printf("%c",s[k][j]);
  52. 						sta[k][j]=0;
  53. 						k++;
  54. 					}
  55. 					printf("\n");	
  56. 				}
  57. 			}	
  58. 	}
  59. 	return 0;
  60. }

注：原文链接：算法竞赛入门经典（第二版）习题答案——第三章3.1-3.6_qq_45911039的博客-CSDN博客

习题3-7 DNA序列（DNA Consensus String，ACM/ICPC Seoul 2006，UVa1368）

         输入m个长度均为n的DNA序列，求一个DNA序列，到所有序列的总Hamming距离尽量小。两个等长祖父穿的Hamming距离等于字符不同的位置个数，例如，ACGT和GCGA的Hamming距离为2（左数第1，4个字符不同）。

        输入整数m和n（4≤m≤50，4≤n≤1000），以及m个长度为n的DNA序列（只包含字母A，C，G，T），输出到m个序列的Hamming距离和最小的DNA序列和对应的距离。如有多解，要求为字典序最小的解。例如，对于下面5个DNA序列，最优解为TAAGATAC。

TATGATAC

TAAGCTAC

AAAGATCC

TGAGATAC

TAAGATGT 

  1. #include <stdio.h>
  2.  
  3. int main()
  4. {
  5. 	int T;
  6. 	scanf("%d", &T);
  7. 	while(T--)
  8. 	{
  9. 		int m, n;
  10. 		scanf("%d%d", &m, &n);
  11. 		char DNA[m][n + 1];
  12. 		for(int i = 0; i < m; i++)
  13. 			scanf("%s", DNA[i]);
  14. 		int a[n] = {0}, c[n] = {0}, g[n] = {0}, t[n] = {0},	//用于计数 
  15. 			max[n] = {0}, distance[n] = {0}, distance_sum = 0;
  16. 		char solution[n + 1];
  17. 		for(int j = 0; j < n; j++)	//每一列字符计数，众数即为最优解所在列的字符 
  18. 		{
  19. 			for(int i = 0; i < m; i++)
  20. 				switch(DNA[i][j])
  21. 				{
  22. 					case 'A':
  23. 						a[j]++; break;
  24. 					case 'C':
  25. 						c[j]++; break;
  26. 					case 'G':
  27. 						g[j]++; break;
  28. 					case 'T':
  29. 						t[j]++; break;
  30. 				}
  31. 			
  32. 			max[j] = a[j], solution[j] = 'A', distance[j] = c[j] + g[j] + t[j]; 		 
  33. 			if(c[j] > max[j])	//比较中隐藏了按字典序比较，顺序比较即可 
  34. 				max[j] = c[j], solution[j] = 'C', distance[j] = a[j] + g[j] + t[j];
  35. 			if(g[j] > max[j]) 	//按列除最优解字符外相加即为距离
  36. 				max[j] = g[j], solution[j] = 'G', distance[j] = a[j] + c[j] + t[j];
  37. 			if(t[j] > max[j])
  38. 				max[j] = t[j], solution[j] = 'T', distance[j] = a[j] + c[j] + g[j];
  39. 		}
  40. 		solution[n] = '\0';	//添加字符串末尾结束标志 
  41. 		printf("到m个序列的Hamming距离和最小的DNA序列：%s\n", solution);
  42. 		for(int j = 0; j < n; j++)
  43. 			distance_sum += distance[j];	//距离和 
  44. 		printf("对应的距离：%d\n", distance_sum); 
  45. 	}
  46. 	return 0;
  47. }

 注：一开始审题错了，产生歧义，以为从m个序列之中寻找最优解，其实是从m个序列之外寻找最优解。

附（从m个序列之中寻找最优解）：

  1. //审题产生歧义，以为从m个序列之中寻找最优解 
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. int main()
  6. {
  7. 	int m, n;
  8. 	scanf("%d%d", &m, &n);
  9. 	char DNA[m][n + 1];
  10. 	for(int i = 0; i < m; i++)
  11. 		scanf("%s", DNA[i]);
  12. 	int a[m][m];
  13. 	memset(a, 0, sizeof(a));	//确保初始化为0 
  14. 	for(int i = 0; i < m; i++) 
  15. 		for(int j = 0; j < m; j++)
  16. 		{
  17. 			if(i == j)
  18. 				continue;
  19. 			for(int k = 0; k < n; k++)
  20. 				if(DNA[i][k] != DNA[j][k])
  21. 					a[i][j]++;
  22. 		}
  23. 	/*for(int i = 0; i < m; i++)
  24. 		for(int j = 0; j < m; j++)
  25. 			printf("a[%d][%d] = %d\n", i, j, a[i][j]);*/
  26. 	int sum[m] = {0}, min = 100, t;
  27. 	for(int i = 0; i < m; i++)
  28. 	{
  29. 		for(int j = 0; j < m; j++)
  30. 			sum[i] += a[i][j];
  31. 		if(sum[i] < min)
  32. 		{
  33. 			t = i;
  34. 			min = sum[i];
  35. 		}
  36. 		else if(sum[i] == min)
  37. 			if(strcmp(DNA[t], DNA[i]) > 0)
  38. 			{
  39. 				t = i;
  40. 				min = sum[i];
  41. 			}
  42. 			else
  43. 				continue;
  44. 	}
  45. 	printf("到m个序列的Hamming距离和最小的DNA序列：%s\n", DNA[t]);
  46. 	for(int i = 0; i < m; i++)
  47. 		printf("它对应到第%d个序列的距离：%d\n", i, a[t][i]);
  48. 	return 0;
  49. }

习题3-8 循环小数（Repeating Decimals，ACM/ICPC World Finals 1990，UVa202）

         输入整数a和b（0≤a≤3000，1≤b≤3000），输出a/b的循环小数表示以及循环解长度。例如a=5，b=43，小数表示为0.(116279069767441860465)，循环节长度为21。

这道题主要就是小数部分的处理，想转化为字符串处理，发现还是有点复杂，还是直接参考其他作者的代码，这个是我认为写的比较清晰简洁的，请参考：

  1. #include<stdio.h>
  2.  
  3. int res[3005], mod[3005];	//res数组记录每一次的商,mod数组记录每一次的余数 
  4. int main()
  5. {
  6.  	int a, b;
  7.  	while(scanf("%d%d", &a, &b) != EOF)
  8.  	{
  9.   		int i = 0, j;
  10.   		int flag = 0;	//标记是否找到了循环节 
  11.   		printf("%d/%d = %d.", a, b, a/b);	//先输出整数部分 
  12.   		while(true)
  13. 		{
  14.    			res[i]= a / b;
  15.     		mod[i]= a % b;
  16.       		a=(a % b) * 10; //将这次的余数乘以十作为下一次的被除数 
  17.       		for(j = 1; j < i; j++)	//与前面出现的商和余数进行比较;注意是从j=1，即小数点后进行比较 
  18.        			if(res[j] == res[i] && mod[j] == mod[i])
  19. 				{	//若余数和商的组合在前面出现过，则表示出现循环节 
  20.         			flag = 1;	//此时的i为第二次出现循环节的开头第一个数字的位置 
  21.         			break;
  22.     			}
  23.    			if(flag)
  24.     			break;
  25.    			i++;
  26.   		}
  27.   		for(int k = 1; k < j; k++)	//注意到res[0]中存储的是整数部分 
  28.    			printf("%d", res[k]);	//输出小数点后非循环节部分 
  29.   		printf("(");
  30.   		if(i > 50)
  31. 		{	//如果要输出的小数部分位数大于50，就只输出前50个 
  32.    			for(int k = j; k <= 50; k++)
  33.     			printf("%d", res[k]);
  34.    			printf("...)\n");
  35.   		}
  36. 		else
  37. 		{
  38.    			for(int k = j; k < i; k++)
  39.     			printf("%d", res[k]);
  40.    			printf(")\n");
  41.   		}
  42.  		printf("   %d = number of digits in repeating cycle\n\n", i-j); //注意输出格式，循环节长度前有三个空格，末尾两个换行符 
  43. 	}
  44.  	return 0;
  45. }

 注：原文链接：【算法竞赛入门经典】习题3-8循环小数（Uva202）_GUANYX的博客-CSDN博客

习题3-9 子序列（All in All，UVa10340） 

         输入两个字符串s和t，判断是否可以从t中删除0个或多个字符（其他字符顺序不变），得到字符串s。例如，abcde可以得到bce，但无法得到dc。

粗看题目，似乎略复杂，其实不然，我们用不着删除字符，只需顺序遍历两个序列即可。

  1. #include <stdio.h> 
  2. #include <string.h> 
  3.  
  4. int main() 
  5. { 
  6.     char s[10000], t[10000];
  7. 	while(scanf("%s%s", s, t) != EOF)
  8. 	{
  9. 		int i, j = 0;
  10. 		for(i = 0 ; i < strlen(t); i++)
  11. 			if(t[i] == s[j])	//顺序寻找字符串t中是否含有字符串s中的字符即可 
  12. 				j++;
  13. 		if(j >= strlen(s))	//字符串s遍历完全即符合 
  14. 			printf("Yes\n");
  15. 		else
  16. 			printf("No\n");
  17. 	}
  18.     return 0; 
  19. }

 刚开始，注意力集中在字符串t其内寻找的s字符串中的字符顺序一定要越来越后，便想到用strchr函数和strncpy函数结合，找到就截取后面的字符串再找。后来想到，这不就是顺序遍历两个字符串嘛，自加就可以了哈哈。

字符串处理函数版：

  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. int main()
  5. {
  6. 	char s[10000], t[10000];
  7. 	while(scanf("%s%s", s, t) != EOF)
  8. 	{
  9. 		char *ptr = 0, c, a[10000];
  10. 		strcpy(a, t);	//考虑到字符串t需要截取，拷贝字符串t给字符串a 
  11. 		int i;
  12. 		for(i = 0; i < strlen(s); i++)
  13. 		{
  14. 			c = s[i];
  15. 			ptr = strchr(a, c);	//顺序寻找字符串s中字符c在字符串a（t）第一次出现的位置 
  16. 			if (ptr) 
  17. 				strncpy(a, ptr + 1, strlen(a) - (ptr - a));	//截取字符串a中字符c后面的字符串 
  18.     		else
  19. 			{
  20.        			printf("No\n");
  21.        			break;
  22. 			}
  23. 		}
  24. 		if(i >= strlen(s))
  25. 			printf("Yes\n");
  26. 	}
  27. 	return 0;
  28. }

注：C 库函数 char *strchr(const char *str, int c) 在参数 str 所指向的字符串中搜索第一次出现字符 c（一个无符号字符）的位置。C 库函数 char *strncpy(char *dest, const char *src, size_t n) 把 src 所指向的字符串复制到 dest，最多复制 n 个字符。当 src 的长度小于 n 时，dest 的剩余部分将用空字节填充。

习题3-10 盒子（Box，ACM/ICPC NEERC 2004，UVa1587）

        给定6个矩形的长和宽wi和hi(1≤wi，hi≤10000)，判断它们能否构成长方体的6个面。

 思路：

第一种：正方体（aa=6），只出现一条边a
第二种：侧面相等的长方体（ab == 4 && aa == 2），只出现两条边a，b
第三种：一般长方体（ab == 2 && ac == 2 & bc == 2），只出现三条边a，b，c

注意：按构成长方体的矩形面划分只有这三种情况

（这种思路好像不太灵活，但是我觉得是比较容易理解的，暂时没有其他思路）

  1. #include <stdio.h>
  2.  
  3. struct Rectangle		
  4. {
  5. 	int h;
  6. 	int w;	
  7. }rect[6];	//定义矩形结构体数组 
  8.  
  9. int main()
  10. {
  11. 	int T;				 	
  12. 	scanf("%d", &T);	 
  13. 	while(T--)
  14. 	{
  15. 		for(int i = 0; i < 6; i++)
  16. 			scanf("%d%d", &rect[i].h, &rect[i].w);
  17. 		int aa = 0, bb = 0, ab = 0, ac = 0, bc = 0;
  18. 		int a = rect[0].h, b = rect[0].w, c, flag = 0;	//将第一组数据设为a和b，flag用于判断c是否出现过 
  19. 		for(int i = 0; i < 6; i++)
  20. 		{		//下面的判断语句就是边长a,b,c的组合问题，稍微比划两下就很明了 
  21. 			if(rect[i].h == a && rect[i].w == a)	
  22. 				aa++;
  23. 			else if(rect[i].h == b && rect[i].w == b)
  24. 				bb++;
  25. 			else if(rect[i].h == a && rect[i].w == b || 
  26. 						rect[i].h == b && rect[i].w == a)
  27. 				ab++;
  28. 			else if(rect[i].h == a && rect[i].w != b && !flag)
  29. 			{
  30. 				c = rect[i].w;
  31. 				flag = 1; 
  32. 				ac++;
  33. 			}
  34. 			else if(rect[i].h == b && rect[i].w != a && !flag)
  35. 			{
  36. 				c = rect[i].w;
  37. 				flag = 1;
  38. 				bc++;
  39. 			}
  40. 			else if(rect[i].w == a && rect[i].h != b && !flag)
  41. 			{
  42. 				c = rect[i].h;
  43. 				flag = 1;
  44. 				ac++;	
  45. 			}
  46. 			else if(rect[i].w == b && rect[i].h != a && !flag)
  47. 			{
  48. 				c = rect[i].h;
  49. 				flag = 1;
  50. 				bc++;	
  51. 			}
  52. 			else if(rect[i].h == a && rect[i].w == c || 
  53. 						rect[i].h == c && rect[i].w == a)
  54. 				ac++;
  55. 			else if(rect[i].h == b && rect[i].w == c || 
  56. 						rect[i].h == c && rect[i].w == b)
  57. 				bc++;
  58. 			else
  59. 				break;	//其他情况说明出现第四条边，直接退出		
  60. 		}
  61. 		//printf("aa=%d,bb=%d,ab=%d,ac=%d,bc=%d\n", aa, bb, ab, ac, bc);
  62.         if(aa == 6 || (ab == 4 && aa == 2) || (ab == 4 && bb == 2) || (ab == 2 && ac == 2 & bc == 2)) 
  63.         	printf("POSSIBLE\n");	 //符合以上条件的6组数据则可以构成长方体 
  64.    		else
  65.         	printf("IMPOSSIBLE\n"); 
  66. 	}
  67. 	return 0;	
  68. }

习题3-11 换抵挡装置（Kickdown，ACM/ICPC NEERC 2006，UVa1588）

        给出两个长度分别为n1， n2（n1，n2≤100）且每列高度只为1或2的长条。需要将它们放入一个高度为3的容器（如图3-8所示），问能够容纳它们的最短容器长度。 

（书上没有写输入输出格式，网上找的）

Sample Input                    
2112112112

2212112

12121212

21212121

2211221122

21212

Sample Output

10

8

5

思路：一开始没有输入输出有点懵，想了一下可以将长条数字化 ，果然是这样的。思路就是固定一个长条，先得清楚哪个长条更长，哪个更短，两个长条完全接触的时候长的便是最短容器长度；移动一个长条，计算每一个接触的地方累加的高度是否符合题意。需要注意的是，长条需要完全在固定长条的左端开始移动，否则会漏掉符合的长条移动位置。

  1. #include <stdio.h>
  2. #include <string.h>
  3.  
  4. int main()
  5. { 
  6. 	char s1[105], s2[105], a[105], b[105];
  7. 	while(scanf("%s%s", s1, s2) != EOF)
  8. 	{
  9. 		int n1 , n2 ;
  10. 		if(strlen(s1) <= strlen(s2))	//固定长度最小的长条为a,长度为n1,拷贝给a 
  11. 			strcpy(a, s1), strcpy(b, s2), n1 = strlen(s1), n2 = strlen(s2);
  12. 		else
  13. 			strcpy(a, s2), strcpy(b, s1), n1 = strlen(s2), n2 = strlen(s1);
  14. 		int n, min = n1 + n2;	 //b从a左端开始移动，每次移动一个单位长度，n为移动次数，设置min初始值为两长条长度之和 
  15. 		for(n = 0; n < n1 + n2; n++)
  16. 		{
  17. 			int i = 0;
  18. 			if(n <= n1)	//b最右端未超出a 
  19. 			{
  20. 				for(i = 0; i < n; i++)
  21. 					if((a[i] - '0' + b[n2 - n + i] - '0') > 3)
  22. 						break;
  23. 				if(i >= n && n1 + n2 -n < min)
  24. 					min = n1 + n2 -n;	//最短容器长度等于长条a和b的总长减去接触部分（b的移动次数n） 
  25. 			}
  26. 			else if(n > n1 && n <= n2)	//b最左端未超出a 
  27. 			{
  28. 				for(i = 0; i < n1; i++)
  29. 					if((a[i] - '0' + b[n2 - n + i] - '0') > 3)
  30. 						break;
  31. 				if(i >= n1 && n2 < min)
  32. 					min = n2;	//最短容器长度等于较长的那根长条（b）长度 （n2） 
  33. 			}
  34. 			else	//b最左端超出a 
  35. 			{
  36. 				for(i = n - n2; i < n1; i++)
  37. 					if((a[i] - '0' + b[n2 - n + i] - '0') > 3)
  38. 						break;
  39. 				if(i >= n1 && n < min)
  40. 					min = n;	//最短容器长度等于b的移动次数 
  41. 			}
  42. 		}
  43. 		printf("%d\n", min);
  44. 	}
  45. 	return 0;
  46. }

这个方法偏暴力，网上有位大佬利用对称性简化了繁琐过程，请参考：

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <stdio.h>
  4. #include <string.h>
  5. using namespace std;
  6.  
  7. bool test(int k,char s1[],char s2[]){
  8.     for(int i = 0; s1[k+i] && s2[i]; i++)//这里的循环终止条件很值得学习！
  9.         if(s1[k+i]+s2[i]-2*'0' > 3)return false;
  10.     return true;
  11. }
  12.  
  13. int fun(char s1[],char s2[]){
  14.     int k = 0;
  15.     while(!test(k,s1,s2))k++;//s1固定，向右移动s2
  16.     return max(strlen(s1),strlen(s2)+k);
  17. }
  18.  
  19. int main(){
  20.     char bottom[105],top[105];
  21.     while(scanf("%s%s",bottom,top) != EOF)//对称性
  22.         cout<<min(fun(bottom,top),fun(top,bottom))<<endl;
  23.     return 0;
  24. }

注：原文链接：习题3-11 换低挡装置 UVa1588_Skyline-CSDN博客

习题3-12  浮点数（Floating-Point Numbers，UVa11809）  

        计算机常用阶码-尾数的方法保存浮点数。如图3-9所示，如果阶码有6位，尾数有8位， 可以

表达的最大浮点数为0.1111111112×211111120.1111111112×21111112。注意小数点后第一位必须为

1，所以一共有9 位小数。

图3-9　阶码-尾数保存浮点数

        这个数换算成十进制之后就是0.998046875*2^63=9.205357638345294*10^18。你的任务是

根据这个最大浮点数，求出阶码的位数E和尾数的位数M。输入格式为AeB，表示最大浮点数为

A*10^B。0<A<10，并且恰好包含15位有效数字。输入结束标志为0e0。对于每组数据，输出M和

E。输入保证有唯一解，且0≤M≤9，1≤E≤30。在本题中，M+E+2不必为8的整数倍。

 （这道题设计到了作者不太擅长的数据存储知识，题目都没怎么整懂，看了其他作者的分析，略微明白了其思路），在这里选取了一位大佬的题解，请参考：

上面的图就给出了一个例子，前面的0表示是正数。后面8位表示尾数m，这里是0.111111111（注意后面是9个1，因为头一个省略了）。之后那个0表示分割，最后面6位表示e的二进制为111111。所以这个数就是，用十进制表示就是。

　　在计算机中用二进制表示M和E的时候如果位数不同，那么它们所能表示的最大值也不同。现在给你所能够表示的最大的浮点数的值，让你倒回去求M和E分别有多少位。输入格式为AeB，表示最大浮点数为，并且0 < A < 10，并且保证输出的结果中0 ≤ M ≤ 9且1 ≤ E ≤ 30。输入以0e0表示结束，0e0本身不计算。


　　这个如果直接去算的话相当麻烦，当E很大的时候数会直接超出上限。这个时候可以反过来想，最大的时候M和E的每一位肯定都是1，并且又有0 ≤ M ≤ 9且1 ≤ E ≤ 30的限定，所以一共只有300种情况，自然就想到了打表，先用二重循环枚举M和E可能出现位数的所有情况打一张表，然后输入的时候倒回去找即可。


　　假设当前一层M和E的值为m和e，它们的位数分别为i和j。

　　首先计算m的值，用二进制表示的话，m的值为0.11…，也就是m = 2^(-1) + 2^(-2) + … + 2^(-1 - i)（i比实际1的个数少1个），也就是m = 1 - 2^(-1 - i)。

　　接下来就是计算e的值，不难得出，e = 2^j - 1。

　　那么也就有m * 2^e = A * 10^B，似乎可以直接计算了。然而，直接这样算的话是不行的，因为当e太大的话（e最大可以是1073741823，注意这还只是2的指数），等号左边的数就会超出上限，所以要想继续算下去，就得自己去想办法再写出满足要求的类来，这显然太麻烦了。所以，这个时候我们对等式两边同时取对数，这个时候就有 log10(m) + e × log10(2) = log10(A) + B。因为此时m和e的值都是确定的，所以不妨令等式左边为t，也就有t = log10(A) + B。

　　这个时候就有问题了，A和B怎么算。

　　写题解的时候突然意识到了这个问题，读题的时候很多人，包括我，都把AeB默认为了科学记数法，在ACM协会群里面讨论的时候很多人也都说这是科学计数法。先来看如果是科学记数法的时候应该怎么办。

　　如果是科学记数法的话，那么对于A，就有1 ≤ A < 10。那么0 < log10(A) < 1。所以t的小数部分就是log10(A)，整数部分就是B，即B = ⌊t⌋，A = 10^(t - B)。那么接下来，我们只需要开出两个二维数组来，分别记录对应i和j下A和B的大小，之后从输入里提取出A和B的大小，去二维数组里面查找对应的i和j即可。

　　这种办法在UVA上面是可以直接AC的，但是我却感觉这题这样A了有点数据太水的感觉，秉着处女座+强迫症死磕到底的精神，我们看下哪里有问题。

　　其实回头读下题，我们发现科学记数法1 ≤ A < 10的条件是我们脑补出来的，题目里面根本没有提及，只是简单交待0 < A < 10。也就是说，对于确定的M和E的位数，十进制的表示可以有多种，例如样例中的5.699141892149156e76，下面的数据应当也是完全可能的，而且结果应当与样例的结果是相同的（当然是在保证精度可以计算出结果的前提下）：


0.569914189214915e77
0.056991418921491e78
0.005699141892149e79
0.000569914189214e80
　　带着这个想法我分别拿着上面的数据去UVA toolkit和uDebug上试了试， UVA toolkit依旧能够输出“5 8”的结果来，但是uDebug告诉我我的输入不合法……果真是我想多了么……
　　不过这个问题也好办，还是看上面的数据，忽略掉后面几位精度丢失的问题的话，上面的几个数完全可以通过“A *= 10, B -= 1”或者“A /= 10, B += 1”的操作来相互转化。那么对于0 < A < 1的A的值，我们就可以通过“A *= 10, B -= 1”的操作来使其满足科学记数法的条件。

　　另外，在查表的时候还应该注意精度的问题，15位有效数字对于double来说精度似乎也不够，而且计算出所需要的整数值其实需要的精度也没有那么高，所以这里的精度就只用到了1e-4的程度。

————————————————
版权声明：本文为CSDN博主「crazysillynerd」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：UVA 11809 - Floating-Point Numbers______-CSDN博客

  1. #include <iostream>
  2. #include <sstream>
  3. #include <string>
  4. #include <cmath>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     double M[20][40];
  10.     long long E[20][40];
  11.  
  12.     // 打表
  13.     for(int i = 0; i <= 9; ++i) for(int j = 1; j <= 30; ++j) {
  14.         double m = 1 - pow(2, -1 - i), e = pow(2, j) - 1;
  15.         double t = log10(m) + e * log10(2);
  16.         E[i][j] = t, M[i][j] = pow(10, t - E[i][j]);
  17.     }
  18.  
  19.     // 输入并输出结果
  20.     string in;
  21.     while(cin >> in && in != "0e0") {
  22.         // 处理输入
  23.         for(string::iterator i = in.begin(); i != in.end(); ++i) if(*i == 'e') *i = ' ';
  24.         istringstream ss(in);
  25.         double A; int B;
  26.         ss >> A >> B;
  27.         while(A < 1) A *= 10, B -= 1;
  28.         // 在打好的表中寻找答案
  29.         for(int i = 0; i <= 9; ++i) for(int j = 1; j <= 30; ++j) {
  30.             if(B == E[i][j] && (fabs(A - M[i][j]) < 1e-4 || fabs(A / 10 - M[i][j]) < 1e-4)) {
  31.                 cout << i << ' ' << j << endl;
  32.                 break;
  33.             }
  34.         }
  35.     }
  36. }

根据原作者代码转化为C语言版（由于C++没有入门，根据自己的理解和编写习惯，通过浏览相关语句用法来转化为C语言表述）：

  1. #include <stdio.h>
  2. #include <string.h>
  3. #include <stdlib.h>
  4. #include <math.h>
  5.  
  6. int main() 
  7. {
  8.     double M[20][40];
  9.     long long E[20][40];
  10.     // 打表
  11.     for(int i = 0; i <= 9; ++i) 
  12. 		for(int j = 1; j <= 30; ++j)
  13. 		{
  14.         	double m = 1 - pow(2, -1 - i), e = pow(2, j) - 1;
  15.         	double t = log10(m) + e * log10(2);
  16.         	E[i][j] = t, M[i][j] = pow(10, t - E[i][j]);
  17.     	}
  18.     // 输入并输出结果
  19.     char in[25];
  20.     while(scanf("%s", in) == 1) 
  21. 	{
  22. 		if(strcmp("0e0",in) == 0)
  23.             break;
  24.         // 处理输入
  25.         for(char *i = in; i < in + strlen(in); ++i) 
  26. 			if(*i == 'e') 
  27. 				*i = ' ';
  28.         char * p;
  29.         p = strtok(in, " ");
  30.         double A = atof(p);
  31.         p = strtok(NULL,"\0");
  32.         int B = atoi(p);
  33.         while(A < 1) 
  34. 			A *= 10, B -= 1;
  35.         // 在打好的表中寻找答案
  36.         for(int i = 0; i <= 9; ++i) 
  37. 			for(int j = 1; j <= 30; ++j) 
  38. 			{
  39.             	if(B == E[i][j] && (fabs(A - M[i][j]) < 1e-4 || fabs(A / 10 - M[i][j]) < 1e-4)) 
  40. 				{
  41.                 	printf("%d %d\n", i, j);
  42.                 	break;
  43.             }
  44.         }
  45.     }
  46. }

至此，算法竞赛入门经典（第二版）的所有习题完结，发现大部分题目都涉及到了字符串，拓展了相关方面的知识，但还发现自己还欠缺许多方面的知识，希望能够好好学完这本书，感谢！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/996465
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号