hao对《算法竞赛入门经典》的笔记(10)
-
第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; }
-
第49页 数组和字符串
字符数组: 竖式问题: 题目: 找出所有形如abc*de(三位数乘以两位数)的算式,使得在完整的竖式中,所有数字都属于一个特定的数字集合。输入数字集合(相邻数字之间没有空格),输出所有竖式。每个竖式前应有编号,之后应有一个空行。最后输出解的总数。具体格式见样例输出(为了便于观察,竖式中的空格改用小数点显示,但你的程序应该输出空格,而非小数点)。 样例输入:2357 样例输出: <1> ..775 X..33 ----- .2325 2325. ----- 25575 The number of solutions = 1 分析: 尝试所有的abc和de,判断是否满足条件。
#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; }
最长回文子串: 回文串: 描述 输入一个字符串,求出其中最大的回文子串。子串的含义是:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同,如abba和yyxyy。在判断时,应该忽略所有标点符号和空格,且忽略大小写,但输出应保持原样(在回文串的首部和尾部不要输出多余字符)。 输入 输入字符串长度不超过5000,且占据单独的一行。 输出 输出最长的回文串,如果有多个,输出起始位置最靠左的。 样例输入 Confuciuss say: Madam,I?m Adam. 样例输出 Madam, I?m Adam 分析:如果全部都是大写字母,问题就简单了:直接判断每个子串即可。不能用scanf("%s")输入字符串,因为它碰到空格或TAB就会停下来。
思路:枚举回文串的中间位置,相两边扩展(奇偶回文要分开两个循环)
#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; }
-
第68页 函数和递归
孪生素数: 一、如题: 如果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; }
递归:
-
第88页 基础题目选解
基本思考方案:
-
第112页 数据结构基础
-
第137页 暴力求解法
关于子集生成:
无论是排列生成还是子集枚举,都是递归构造和直接遍历,优点是思路简单,但缺点在于无法简便的减少枚举量-----必须生成所有可能的解,然后一一检查。回溯法把生成和检查过程有机的结合起来,减少了不必要的枚举。就解决了这问题。
-
第157页 高效算法设计
-
第175页 动态规划初步
状态转移方程的计算方法: 1.递归计算(时间效率低,原因在于重复计算。) 2.递推计算(递推的关键是边界和计算顺序。在大多数情况下,递推法的时间复杂度为:状态总数*每个状态的决策个数*决策时间。) 3.记忆化搜索(不必事先确定各个状态的计算顺序,但需要记录每个状态“是否已经计算过”。可以用vis数组记录是否计算过,牺牲了一些内存换来可读性,同时减少出错。)
-
第195页 数学概念与方法
-
第215页 图论模型和算法
hao的其他笔记 · · · · · · ( 全部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
- 淘宝技术这十年
- 1
- 高效程序的奥秘
- 1
- 花田半亩
- 1
- 于丹:重温最美古诗词
- 1
- 诛仙8(大结局)
- 1
- 深入理解计算机系统(原书第2版)
- 9
- C和指针
- 9
- 寒江独钓
- 5
- Windows程序设计
- 9
- 数据结构与算法分析
- 11
- 80X86汇编语言程序设计教程
- 3
- 琢石成器
- 30
- 数学分析教程
- 1
- 操作系统概念(第六版)
- 12
- C++反汇编与逆向分析技术揭秘
- 12