首页 > 代码库 > 第三章学习小结—-转

第三章学习小结—-转

【学习目标】

01掌握一维数组的声明和使用方法(OK)

02掌握二维数组的声明和使用方法(OK)

03掌握字符串的声明、赋值、比较和连接方法(连接很少用)

04熟悉字符的ASCII码和ctype.h中的字符函数

05正确认识++、+=等能修改变量的运算符(OK)

06学会用编译选项-Wall获得更多的警告信息(OK)

07了解不同操作系统中换行符的表示方法(嗯)

08掌握fgetc和getchar的使用方法(fgetc基本没用过)

09掌握预处理和迭代开发的技巧(嗯)

 

程序3-1 逆序输出

输入元素个数n,n<100,接着是n个的元素(大小不超过10^9),然后逆序输出

 

view plaincopy
#include <stdio.h>  
  • #define N 110  
  •   
  • int a[N];  
  •   
  • int  
  • main(void)  
  • {  
  •     int n, i;  
  •   
  •     scanf("%d", &n);  
  •     for (i = 0; i != n; i++)  
  •         scanf("%d", &a[i]);  
  •     for (i = n-1; i != -1; i--)  
  •         printf(i != 0 ? "%d " : "%d\n", a[i]);    
  •     return 0;  
  • }  

 

 

附带:数组的复制

输入元素个数n,n<100,接着是n个的元素(大小不超过10^9),复制前m(m <= n)个元素后逆序输出,再复制全部元素后输出

 

view plaincopy
#include <stdio.h>  
  • #include <string.h>  
  • #define N 110  
  •   
  • int a[N];  
  • int b[N];  
  •   
  • int  
  • main(void)  
  • {  
  •     int n, m, i;  
  •   
  •     scanf("%d %d", &n, &m);  
  •     for (i = 0; i != n; i++)  
  •         scanf("%d", &a[i]);  
  •       
  •     memcpy(b, a, sizeof (int)*m);  
  •     for (i = m-1; i != -1; i--)  
  •         printf(i != 0 ? "%d " : "%d\n", b[i]);  
  •       
  •     memcpy(b, a, sizeof (a));  
  •     for (i = n-1; i != -1; i--)  
  •         printf(i != 0 ? "%d " : "%d\n", b[i]);  
  •     return 0;  
  • }  

 

 

例题3-1开灯问题

 

view plaincopy
#include <stdio.h>  
  • #include <string.h>  
  • #define false -1  
  • #define ture 1  
  • #define N 1010  
  •   
  • int a[N];  
  •   
  • int  
  • main(void)  
  • {  
  •     int n, k, i, j;  
  •     int first = 1;  
  •   
  •     scanf("%d%d", &n, &k);  
  •     memset(a, falsesizeof(a));  
  •       
  •     for (i = 1; i != k+1; i++) {  
  •         for (j = i-1; j < n; j += i) {  
  •             a[j] = -a[j];  
  •         }  
  •     }  
  •       
  •     for (i = 0; i != n; i++) {  
  •         if (ture == a[i])  
  •             printf(1 == first ? first = 0, "%d" :" %d", i+1);  
  •     }  
  •     printf("\n");  
  •     return 0;  
  • }  

思路:简单模拟,这里我数组下标还是从0开始,所以最后输出下标时要+1;另外,用first标志变量更具通用性!

 

书上的方法是利用!0 == 1,而且利用(j%i == 0)来判断,就清晰简明来讲比上面的程序要好一点。

 

例题3-2 蛇形填数

 

view plaincopy
#include <stdio.h>  
  • #include <string.h>  
  • #define N 10  
  • #define empty 0  
  •   
  • int a[N][N];  
  •   
  • int  
  • main(void)  
  • {  
  •     int n, i, j, m;  
  •     int count = 1;  
  •   
  •     scanf("%d",&n);  
  •     memset(a, empty, sizeof (a));  
  •     i = 0;  
  •     j = n-1;      
  •     a[i][j] = count++;  
  •     m = n*n;      
  •     while (m--) {                 
  •         while (i+1 != n && a[i+1][j] == empty) a[++i][j] = count++;  
  •         while (j-1 != -1 && a[i][j-1] == empty) a[i][--j] = count++;  
  •         while (i-1 != -1 && a[i-1][j] == empty) a[--i][j] = count++;  
  •         while (j+1 != n && a[i][j+1] == empty) a[i][++j] = count++;  
  •     }  
  •     for (i = 0; i != n; i++) {  
  •         for (j = 0; j != n; j++)  
  •             printf(j != n-1 ? "%d " : "%d\n", a[i][j]);  
  •     }  
  •     return 0;  
  • }  


最后一个问题为什么是++tot而不是tot++;其实应当是针对起点从0开始而问的。我们只需要保证第一个while循环能执行n*n次,里面的第一个循环第一次执行确保count ==  2即可。

 

 

3.2字符数组

竖式问题——

 

view plaincopy
#include <stdio.h>  
  • #include <string.h>  
  •   
  • char base[11];  
  • char tmp[20];  
  •   
  • /* 
  •  *compare tmp[] with instr[] 
  •  *if all the elements of tmp[] belongs to instr[] return 1, else return 0; 
  •  */  
  • int  
  • cmp(char *t)  
  • {  
  •     char *p, *q;  
  •     int count;  
  •     int len = strlen(base);  
  •   
  •     for (p = t; *p != ‘\0‘; p++) {  
  •         count = 0;  
  •         for (q = base; *q != ‘\0‘; q++) {  
  •             if (*p != *q)  
  •                 count++;              
  •         }  
  •         if (count == len)  
  •                 return 0;  
  •     }  
  •     return 1;  
  • }  
  •   
  • int  
  • main(void)  
  • {  
  •     int abc, de;  
  •     int count = 1;  
  •       
  •     scanf("%s", base);    
  •     for (abc = 100; abc != 1000; abc++)  
  •         for (de = 10; de != 100; de++) {  
  •             sprintf(tmp, "%d", abc);  
  •             if (cmp(tmp) == 0)  
  •                 continue;  
  •             sprintf(tmp, "%d", de);  
  •             if (cmp(tmp) == 0)  
  •                 continue;  
  •             sprintf(tmp, "%d", abc*(de%10));  
  •             if (cmp(tmp) == 0)  
  •                 continue;  
  •             sprintf(tmp, "%d", abc*(de/10));  
  •             if (cmp(tmp) == 0)  
  •                 continue;  
  •             sprintf(tmp, "%d", abc*de);  
  •             if (cmp(tmp) == 0)  
  •                 continue;  
  •             printf("<%d>\n", count++);  
  •             printf("  %d\nX  %d\n-----\n", abc, de);  
  •             printf("%5d\n%4d\n-----\n%5d\n\n", abc*(de%10), abc*(de/10), abc*de);             
  •         }  
  •     printf("The number of solutions = %d\n", count-1);            
  •     return 0;  
  • }  



 

显然我写的这个程序简洁性不如书本上的,最大的区别在于书本用了一个我从没用过的函数strchr()

另外我的程序也可以设置一个buf[99],使用一个sprintf()把4个相关数字串存入buf[99],一次性检查。

谷歌一下strchr()的一个BSD版本实现如下

 

view plaincopy
#include <stddef.h>  
  • #include <string.h>  
  •   
  • char *  
  • strchr(const char *p, int ch)  
  • {  
  •     char c;  
  •   
  •     c = ch;  
  •     for (;; ++p) {  
  •         if (*p == c)  
  •             return ((char *)p);  
  •         if (*p == ‘\0‘)  
  •             return (NULL);  
  •     }  
  •     /* NOTREACHED */  
  • }  

这个函数的功能就是返回ch在字符串的位置,如果字符串中没有ch,则返回NULL
因此LRJ老师的版本非常清晰简明~我还是敲一遍吧!

 

 

view plaincopy
#include <stdio.h>  
  • #include <string.h>  
  •   
  • int  
  • main(void)  
  • {  
  •     int i, abc, de, x, y, z, ok, count = 0;  
  •     char s[20], buf[90];  
  •   
  •     scanf("%s", s);  
  •     for (abc = 111; abc <= 999; abc++)  
  •         for (de = 11; de <= 99; de++) {  
  •             x = abc*(de%10);  
  •             y = abc*(de/10);  
  •             z = abc*de;  
  •             sprintf(buf, "%d%d%d%d%d", abc, de, x, y, z);  
  •             ok = 1;  
  •             for (i = 0; i < strlen(buf); i++)  
  •                 if (strchr(s, buf[i]) == NULL)  
  •                     ok = 0;  
  •             if (ok) {  
  •                 printf("<%d>\n", ++count);  
  •                 printf("%5d\nX%4d\n-----\n%5d\n%4d\n-----\n%5d\n\n", abc, de, x, y, z);  
  •             }             
  •         }  
  •     printf("The number of solutions = %d\n", count);  
  •     return 0;     
  • }  

看来用好C标准函数,可以提高不少效率和大大减少错误的可能性。

 

 

3.3最长回文字串

首先阅读了书本前面的分析——

第一步采用比较通用的方案:预处理。就是存入源串,再按约束构造一个新串。这个新串为处理后续问题提供了方便,相当于简化了问题,如果源串有用处则要保存好。

处理字符的函数一般定义在 ctype.h中,包括:

isalpha(),isdigit(),isprint()(判断是不是可打印的字符,回车符就是不可打印的?),toupper(),tolower()

有了仅仅保存大写字母的新串,可以暴力枚举所有子串,假定一般情况:子串不是回文的情况远远多于是回文。

可以得到如下代码——

 

view plaincopy
#include <stdio.h>  
  • #include <string.h>  
  • #include <ctype.h>  
  • #define N 5010  
  •   
  • char input[N];  
  • char new[N];  
  • int srcpt[N];  
  •   
  • int  
  • main(void)  
  • {  
  •     int i, j;  
  •     int len = 0;  
  •     int max = 1;  
  •     int curlen = 0, savei = 0, savej = 0;  
  •     int tmp, p, q, ok;  
  •   
  •     fgets(input, sizeof(input), stdin);  
  •     for (i = 0; i != strlen(input); i++)  
  •         if (1 == isalpha(input[i])) {  
  •             new[len] = toupper(input[i]);  
  •             srcpt[len++] = i;  
  •         }  
  •       
  •     for (i = 0; i != len; i++) {  
  •         for (j = i; j != len; j++) {  
  •             curlen = j-i+1;  
  •             ok = 1;  
  •             p = i + curlen/2-1; /*Notice!!!*/  
  •             if (0 == curlen%2) {  
  •                 q = p+1;  
  •                 tmp = curlen;  
  •             }  
  •             else {  
  •                 q = p+2;  
  •                 tmp = curlen-1;  
  •             }  
  •             while (tmp > 0) {  
  •                 if (new[p--] != new[q++])  
  •                     break;  
  •                 tmp -= 2;  
  •             }  
  •             if (tmp > 0)  
  •                 ok = 0;  
  •             if (1 == ok && curlen > max) {  
  •                 max = curlen;  
  •                 savei = i;  
  •                 savej = j;  
  •             }  
  •         }  
  •     }  
  •           
  •     for (i = srcpt[savei]; i <= srcpt[savej]; i++)  
  •         printf("%c", input[i]);  
  •     printf("\n");  
  •       
  •     return 0;  
  • }  

正如LRJ所言,这个版本处理5000个a时显得非常吃力,上面代码一般情况下效率可能还可以接受,但对于全是a这种极端情况则所有枚举情况都是以最坏的效率进行的!

 

书上的版本——

 

书上的思路是一次遍历新串,设i为新串当前位置

当前位置i对应的单个字符必定已经是回文串,以i为中心,向两边扩展,是回文串则记录信息(此时判断得到的回文串长度大小必定是奇数);

当前位置i对应的字符和i+1对应的字符(两个字符)若是回文串,或者以 i和i+1 为中心,向两边扩展,是回文串则记录信息(此时判断得到的回文串长度大小必定是偶数);

这样子就能充分利用当前已知的回文串,其实这个思想是动态规划的思想!

 

以ababbbb为例,循环过程如下:

i == 0;s[0] == a;a是回文,max更新为1,无法继续扩展;

对于s[0~1],ab不是回文,break;

i == 1;  s[1] == b;b是回文,扩展一步,aba是回文,max更新为3,无法继续扩展;

对于s[1~2],ba不是回文,break;

i == 2;s[2] == a;a是回文,扩展一步,bab是回文,再扩展一步,ababb不是回文,break;

对于s[2~3],ab不是回文,break;

i == 3;s[3] == b;b是回文,扩展一步,abb不是回文,break;

对于s[3~4],bb是回文,扩展一步,abbb不是回文,break;

i == 4;s[4] == b;b是回文,扩展一步,bbb是回文,再扩展一步,abbbb不是回文,break;

对于s[4~5],bb是回文,扩展一步,bbbb是回文,更新max为4,无法继续扩展;

i == 5;s[5] == b;  b是回文,扩展一步,bbb是回文,无法继续扩展(右边会越界);

对于s[5~6],bb是回文,但无法继续扩展(同样右边会越界);

i == 6;s[6] == b;b是回文,无法继续拓展;

不存在s[6~7],i+1 == 7会越界;

结束;

 

代码是相当地清晰有力——

 

view plaincopy
#include <stdio.h>  
  • #include <string.h>  
  • #include <ctype.h>  
  • #define N 5000+10  
  •   
  • char buf[N];  
  • char s[N];  
  • int p[N];  
  •   
  • int  
  • main(void)  
  • {  
  •     int m = 0, max = 0;  
  •     int x, y, i, j;  
  •       
  •     fgets(buf, sizeof (buf), stdin);      
  •     for (i = 0; i < strlen(buf); i++)  
  •         if (isalpha(buf[i])) {  
  •             p[m] = i;  
  •             s[m++] = toupper(buf[i]);  
  •         }  
  •     for (i = 0; i < m; i++) {  
  •         /* 对于当前位置i,以回文s[i]为中心不断扩展,得到奇数长度的最长回文串 */  
  •         for (j = 0; i -j >= 0 && i +j < m; j++) {  
  •             if (s[i -j] != s[i +j])  
  •                 break;  
  •             if (j*2+1 > max) {  
  •                 max = j*2+1;  
  •                 x = p[i -j];  
  •                 y = p[i +j];  
  •             }  
  •         }  
  •         /* 对于当前位置i,若s[i~i+1]是回文,则以其为中心不断扩展,得到偶数长度的最长回文串 */  
  •         for (j = 0; i -j >= 0 && i+1 +j < m; j++) {  
  •             if (s[i -j] != s[i+1 +j])  
  •                 break;  
  •             if (j*2+2 > max) {  
  •                 max = j*2+2;  
  •                 x = p[i -j];  
  •                 y = p[i+1 +j];  
  •             }  
  •         }  
  •     }  
  •     for (i = x; i <= y; i++)  
  •         printf("%c", buf[i]);  
  •     printf("\n");  
  •     return 0;  
  • }  

 

 

总结

这章首先学到了strchr()函数,用于查找一个字符在一个字符串中的位置;

对于求最长子回文,书上给出了动态规划的思想,显得相当优美。对于每一个当前i,充分利用子问题的解(单个字符就是回文,作为奇数串的“最小”解;若s[i~i+1]也是回文则是偶数串的“最小”解,其实也可以把空串理解回文,即偶数串的“最小”解,这样理解甚至更加自然),从而快速地得到当前i对应的最大子回文(设置当前max就微不足道了),碉堡了

 

原博客地址:http://blog.csdn.net/architect19/article/details/8567507