MathxH对《算法竞赛入门经典》的笔记(10)

算法竞赛入门经典
  • 书名: 算法竞赛入门经典
  • 作者: 刘汝佳
  • 页数: 225
  • 出版社: 清华大学出版社
  • 出版年: 2009-11
  • 第37页
    开灯问题:
    题目: 有n盏灯,编号为1~n.第一个人把所有的灯打开,第2个人按下所有编号为2的倍数的开关(这些灯将被关掉),第3个人按下所有编号为3 的倍数的开关(开着的灯关掉,关着的灯被打开),以此类推,一共有k个人,问最后有哪些灯开着?输入:n和k,输出开着的灯的编号。k<=n<=1000
    样列输入: 7 3
    样列输出: 1 5 6 7
    分析:用a[1],a[2],...a[n]表示编码为1,2,3...,n的灯是否开着。模拟这些操作即可。
    #include<stdio.h>
    #include<string.h>
    #define   MAXN 1000 + 10
    
    int a[MAXN];
    
    int main()
    {
         int i, j, n , k, first = 1;
         memset(a, 0, sizeof(a));
    
         scanf("%d%d", &n, &k);
         for(i = 1; i <= k ; ++i)
           for(j = 1; j <= n; ++j)
                if(j % i == 0) a[j] = !a[j];
         for(i = 1; i <= n; i++)
             if(a[i]) { if(first) first = 0; else printf(" "); printf("%d", i)}
         printf("\n");
    
         return 0;
    }
    
    蛇形填数:
    题目:
    在n*n的方阵里填入1,2,...,n*n (n<=8),要求填成蛇形。
    例如n=4时的方阵为:
    10 11 12 1
    9 16 13 2
    8 15 14 3
    7 6 5 4
    分析:用一个二维数组来存储题目中的方阵。
    #include <cstdio>  
    #include <cstring>  
    #define MAXN 10  
    int a[MAXN][MAXN];  
    int main()  
    {  
        int n, x, y, val=0;  
        scanf("%d",&n);  
        memset(a,0,sizeof(a));// clear array  
        val=a[x=0][y=n-1]=1;// set the first element  
        while (val<n*n)  
        {  
            while (x+1<n && !a[x+1][y])   a[++x][y]=++val;  
            while (y-1>=0 && !a[x][y-1])  a[x][--y]=++val;  
            while (x-1>=0 && !a[x-1][y])  a[--x][y]=++val;  
            while (y+1<n && !a[x][y+1])   a[x][++y]=++val;  
        }  
        for (x=0; x<n; ++x)  
        {  
            for (y=0; y<n; ++y)  
            {  
                printf("%3d",a[x][y]);  
            }  
            printf("/n");  
        }  
        return 0;  
    }  
    
    2013-07-16 14:52:04 回应
  • 第49页
    字符数组:
    竖式问题:
    题目:
    找出所有形如abc*de(三位数乘以两位数)的算式,使得在完整的竖式中,所有数字都属于一个特定的数字集合。输入数字集合(相邻数字之间没有空格),输出所有竖式。每个竖式前应有编号,之后应有一个空行。最后输出解的总数。具体格式见样例输出(为了便于观察,竖式中的空格改用小数点显示,但你的程序应该输出空格,而非小数点)。
    样例输入:2357
    样例输出:
    <1>
    ..775
    X..33
    -----
    .2325
    2325.
    -----
    25575
    The number of solutions = 1
    分析:
    尝试所有的abc和de,判断是否满足条件。
    C语言中的字符型用关键字char表示,实际储存的是字符的ASCII码。字符常量可以用单引号法表示。在语法上可以当做int型使用。
    #include <stdio.h>   
    #include <string.h>   
    
    int main()   
    {   
      int abc, de, x, y, z, i, ok, count = 0;   
      char s[20], buff[100];   
      scanf("%s", s);   
    
      for (abc = 100; abc < 999; abc++)   
      {   
      for (de = 10; de < 99; de++)   
      {   
      x = abc * (de % 10);   
      y = abc * (de / 10);   
      z = abc * de;   
      sprintf(buff, "%d%d%d%d%d", abc, de, x, y, z);   
      ok = 1;   
      for (i = 0; i < strlen(buff); i++)   
      if (strchr(s, buff[i]) == NULL)   
      ok = 0;   
      if (ok)   
      {   
      printf("<%d>/n", ++count);   
      printf("%5d/nX%4d/n-----/n%5d/n%4d/n-----/n%5d/n", abc, de, x, y, z);   
      }   
      }   
      }   
      printf("The number of solutions = %d/n", count);   
      return 0;   
    }
    
    可以用sprintf把格式化信息输出到字符串,保证buffer足够大。
    由于字符串的本质是数组,只能用strcpy,strcmp,strcat来执行“赋值”,“比较”,“连接”操作。不能用=,==,<=,+等运算符。它们在string.h中。
    最长回文子串:
    回文串:
    描述
    输入一个字符串,求出其中最大的回文子串。子串的含义是:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同,如abba和yyxyy。在判断时,应该忽略所有标点符号和空格,且忽略大小写,但输出应保持原样(在回文串的首部和尾部不要输出多余字符)。
    输入
    输入字符串长度不超过5000,且占据单独的一行。
    输出
    输出最长的回文串,如果有多个,输出起始位置最靠左的。
    样例输入
    Confuciuss say: Madam,I?m Adam.
    样例输出
    Madam, I?m Adam
    分析:如果全部都是大写字母,问题就简单了:直接判断每个子串即可。不能用scanf("%s")输入字符串,因为它碰到空格或TAB就会停下来。
    使用fgetc可以从打开的文件读取一个字符。一般情况下应当检查不是EOF后再将其转换成char值。getchar等价于fgetc(stdin)。
    fgets会读取完整的一行。就是说,它一旦读取到‘\n’,就会停止读取工作,然后在buffer后加‘\0’结束符。
    头文件ctype.h中定义的isalpha,isdigit,isprint,等可以判断字符的属性,toupper,tolower等用来转换大小写。
    思路:枚举回文串的中间位置,相两边扩展(奇偶回文要分开两个循环)
    
    #include <stdio.h>
     #include <ctype.h>
     #include <string.h>
     #define Z 5000+100
     int main ()
     {
      int x,y,m,n,p[Z],i,j,k,max=0;
      char ch [Z],b[Z];
      fgets (ch,sizeof(b),stdin);
      n=strlen (ch);
      m=0;
      for (i=0;i<n;i++)
      {
       p[m]=i;//记录字符的位置
       if (isalpha (ch[i]))//忽略所有标点符号和空格,且忽略大小写
       b[m++]=tolower (ch[i]);
      }
      for (i=0;i<m;i++)//枚举
      {
       for (j=0;i-j>=0&&i+j<=m;j++)//奇数回文串
       {
        if (b[i-j]!=b[i+j])
         break;
        if (j*2+1>max)
        {
         max=j*2+1;
         x=p[i-j];
         y=p[i+j];
        }
       }
       for (j=1;i-j>=0&&i+j-1<m;j++)//偶数回文串
      {
        if (b[i-j]!=b[i+j-1])
         break;
        if (j*2>max)
        {
         max=j*2;
         x=p[i-j];
         y=p[i+j-1];
        }
       }
      }
      for (;x<=y;x++)
       printf ("%c",ch[x]);
      return 0;
     }
    
    字符还可以直接用ASCII码来表示。如果用八进制\o,十六进制就是\xh(h为16进制数字串)
    2013-07-16 14:52:26 回应
  • 第68页
    为了方便使用,往往用typedef struct {域定义;}类型名;的方式定义一个新类型名。这样,就可以像原生数据类型一样使用这个自定义类型了。
    建议用来判断某事物是否具有某种特殊性质的函数命名成“is_xxx”的形式。返回非0数为真,0为假。
    编写函数时,尽量保证它能对任何合法参数都能得到正确结果,如若不然,应在显著位置标明函数的缺陷,以避免使用。编程时,合理的利用assert宏,将给调试带来很大的方便。(assert.h)
    孪生素数:
    一、如题:
    如果n和n+2都是素数,则称它们是孪生素数。输入m,输出2个均不超过m的最大孪生素数。5<=m<=1000。例如m=20时候,答案为17、19,m=1000的时候,答案等于881、883。
    二、分析:
    首先是要判断素数,判断一个数M是否为素数,只要判断到到根号M就可以确定它是不是素数了。它如果存在因数,那么一定可以写成乘积的形式。比如M = 1 * M。如果它存在两个因数,乘积等于M,这两个因数一定一个小于根号M,一个大于根号M,因为一定存在两个相等的数乘积等于它(当然可能不是整数),这两个数就是根号M,因为M = 根号M * 根号M。如果两个数都在根号M以下,乘起来小于M,如果两个数都在根号M以上,乘起来一定大于M,所以两个数分布于根号M两边,那么我们只要找到其中一半有没有这样一个整数就可以了。如果有,自然对应的另一半也有一个和它对应的数,使它们的乘积为M。其次,如何找出最大的2个孪生素数?可以把所有满足条件的孪生素数找出来再比较大小,但这样过于繁琐,所以,我们只需用一循环,从小于m的数开始倒序查找符合条件的孪生素数,一找到就输出,那输出的便是最大孪生素数了。
    三、代码:
    #include<stdio.h>
     #include<math.h>
     #include<assert.h> //程序使用了assert.h中的assert宏来限制非法的函数调用;
    
    int is_prime(int x) //声明了一个判断素数的函数;
     {
         int i,m;
         assert(x>=0); //当x>=0不成立的时候,程序将异常终止;
         if(x==1) return 0; //特殊的:1不是素数;
         m=floor(sqrt(x)+0.5); //避免了浮点误差,floor函数为向下取整;
         for(i=2;i<=m;i++)
          if(x%i==0) return 0; //素数的判断;
         return 1;
     }
    
    int main() //主函数;
     {
         int i,m;
         while(scanf("%d",&m)!=EOF)
         for(i=m-2;i>=3;i--) //从第m-2个数开始判断,从而实现了输出“最大孪生素数”的目的;
          if(is_prime(i)&&is_prime(i+2)) //调用了is_prime函数;
          {
              printf("%d %d\n",i,i+2);
              break;
          }
         return 0;
     }
    
    
    C语言用调用栈(call stack)来描述函数之间的调用关系。调用栈由栈帧(stack frame)组成,每个栈帧对应着一个未运行完成的函数。
    递归:
    记住为递归函数编写终止条件,否则无限递归,导致栈溢出。
    在运行时,程序会动态创建一个堆栈段,里面存放着栈帧,因此保存着调用关系和局部变量。
    在可执行文件中,文本段储存指令,数据段存储已初始化的全局变量,BSS段存储未赋值的全局变量
    2013-07-16 14:52:41 回应
  • 第88页
    基本思考方案:
    有些题考虑建立常量表,打表的方式可能会更简单。
    用状态变量来辅助字符串读入
    对于大数高精度运算,请考虑数组存储大数,模拟手工计算。考虑万进制提高效率。
    排序的话,数据规模小的话,冒泡排序很管用的,比快排好。快排有时候分割不好,速度很慢。stdlib.h中的qsort速度就很快。
    2013-07-16 14:52:55 回应
  • 第112页
    对比测试,随机生成大规模随机数据量。考虑srand , time,rand rand生成闭区间的[0,RAND_MAX],RAND_MAX至少为32767.
    二叉树的一般三种遍历:先序遍历,中序遍历,后序遍历如下: PreOrder(T)=T的根节点 + PreOrder(T的左子树) + PreOrder(T的右子树) InOrder(T)= InOrder(T的左子树) + T的根节点 + InOrder(T的右子树) PostOrder(T)=PostOrder(T的左子树) + PostOrder(T的右子树)+ T的根节点
    关于图,考虑DFS,BFS,拓扑排序。
    2013-07-16 14:53:17 回应
  • 第137页
    暴力求解,一般用在排列枚举之类的方面。
    如果某问题的解可以由多个步骤得到,而每个步骤可以由若干种选择,且可以使用递归枚举,工作方式可以用解答树来描述。
    关于子集生成:
    子集生成算法:给定一个集合,枚举它所有可能的子集。一般有3种思路:增量构造,位向量法,二进制法。
    用二进制表示子集,其中从右往左第i位(从0开始编号)表示元素i是否在集合中(1表示“在”,0表示“不在”)。当用二进制法表示子集时,位运算中的&, | ,^对应集合的交,并,对称差。
    无论是排列生成还是子集枚举,都是递归构造和直接遍历,优点是思路简单,但缺点在于无法简便的减少枚举量-----必须生成所有可能的解,然后一一检查。回溯法把生成和检查过程有机的结合起来,减少了不必要的枚举。就解决了这问题。
    在编写枚举递归需要深入分析,对模型精雕细琢。如果在回溯法中使用了辅助的全局变量,用完之后,请恢复原状。
    2013-07-16 14:53:33 回应
  • 第157页
    分治: 1.划分问题:把问题划分成子问题 2.递归求解:递归解决子问题 3.合并问题:合并子问题的解得到原问题解 归并排序: 1.划分问题:把序列分成元素个数尽量相等的两半 2.把两半元素分别排序 3.把两个有序表合并成一个 快速排序: 1.划分问题:把数组的各个元素重排后分成左右两部分,使得左边的任意元素都小于或等于右边的任意元素 2.递归求解:把左右两边部分分别排序 3.合并问题:不用合并,因为此时数组已经完全有序。
    逐步缩小范围法师一种常见思维,比如二分查找,二分查找只适用有序序列。其实逐步缩小范围本质上是概率论和猜测的问题,就是按照概率科学的猜,所以设计好了,效率很高。二分查找一般写成非递归形式。
    可以使用C++的STL算法库。
    2013-07-16 14:53:49 回应
  • 第175页
    动态规划需要理解“状态”,“状态转移”,“最优子结构”,“重叠子问题”等概念。
    动态规划是一种思维手段,本身不是什么特定的算法。
    动态规划的核心是状态和状态转移方程。
    状态转移方程的计算方法:
    1.递归计算(时间效率低,原因在于重复计算。)
    2.递推计算(递推的关键是边界和计算顺序。在大多数情况下,递推法的时间复杂度为:状态总数*每个状态的决策个数*决策时间。)
    3.记忆化搜索(不必事先确定各个状态的计算顺序,但需要记录每个状态“是否已经计算过”。可以用vis数组记录是否计算过,牺牲了一些内存换来可读性,同时减少出错。)
    2013-07-16 14:54:00 回应
  • 第195页
    设a,b,c为任意整数。若方程ax+by=c的一组整数解为(x0,y0),则它的任意整数解都可以写成(x0+kb',y0-ka'),其中a'=a/gcd(a,b),b'=b/gcd(a,b),k取任意整数。
    设a,b,c为任意整数,g=gcd(a,b),方程ax+by=g的一组解是(x0,y0),则当c是g的倍数时ax+by=c的一组解是(x0c/g,y0c/g);当c不是g的倍数时无整数解。
    数学归纳法是一种利用递归的思想的证明方法。如果要讨论的对象具有某种递归性质(如正整数),可以考虑用数学归纳法。
    2013-07-16 14:54:09 回应
  • 第215页
    建立表达式树的方法就是每一次找到最后计算的运算符,然后递归建树。“最后计算”的运算符是在括号外的,优先级最低的运算符。如果有多个,根据结合性来选择:左结合(加,减,乘,除),右结合(乘方)。
    并查集的精妙之处在于用树来表示集合。
    最短路径:DIJKSTRA算法,Floyd算法。
    2013-07-16 14:54:17 回应

MathxH的其他笔记  · · · · · ·  ( 全部427条 )

P2P网络技术原理与C++开发案例
5
大话移动通信
1
图解网络硬件
1
写给大家看的C++书
1
Orange'S:一个操作系统的实现
1
虚拟机
1
大规模C++程序设计
10
Linux Shell脚本攻略
3
HTTP权威指南
3
C++ API设计
8
C++语言的设计和演化
5
构建嵌入式LINUX系统
3
七周七语言
15
链接器和加载器
1
Windows网络与通信程序设计
2
Windows核心编程(第5版)
16
C++GUI Qt4编程
3
图解TCP/IP(第5版)
12
Python学习手册
5
编写可读代码的艺术
14
你一定爱读的极简欧洲史
2
短码之美
1
程序员的自我修养
17
美国纽约摄影学院摄影教材(上)
2
Win32多线程程序设计
8
竹林蹊径
4
鸟哥的Linux私房菜
4
Linux/Unix设计思想
6
程序设计语言的形式语义
1
Windows驱动开发技术详解
9
你必须知道的495个C语言问题
5
Windows内核原理与实现
44
PCI Express 体系结构导读
3
程序员的数学
5
深入浅出 MFC 第二版
2
并发的艺术
4
群和它的图象表示
1
C语言接口与实现
1
致命元素
2
深入解析Windows操作系统
51
Linux C编程一站式学习
13
如果沒有耶穌
16
淘宝技术这十年
1
高效程序的奥秘
1
花田半亩
1
于丹:重温最美古诗词
1
诛仙8(大结局)
1
深入理解计算机系统(原书第2版)
9
C和指针
9
寒江独钓
5
Windows程序设计
9
数据结构与算法分析
11
80X86汇编语言程序设计教程
3
琢石成器
30
数学分析教程
1
操作系统概念(第六版)
12
C++反汇编与逆向分析技术揭秘
12