当前位置:首页 >> 学科竞赛 >>

第十一周 枚举(二)


ACM算法与程序设计
第十讲 枚举(二)

完美立方
1、链接地址 http://poj.grids.cn/problem?id=2810 2、问题描述 a^3=b^3+c^3+d^3为完美立方等式。例如 12^3=6^3+8^3+10^3。编写一个程序,对任 给的正整数N (N≤100),寻找所有的四元组(a, b, c, d),使得a

^3=b^3+c^3+d^3,其中a,b,c,d 大于1,小于等于N。

2/32

问题描述
输入格式
正整数N (N≤100)

输出要求
每行输出一个完美立方,按照a的值,从小到大依次输出。 当两个完美立方等式中a的值相同,则依次按照b、c、d 进行非降升序排列输出,即b值小的先输出、然后c值小的 先输出、然后d值小的先输出。

3/32

问题描述
输入样例
24

输出样例
Cube = 6, Triple = (3,4,5) Cube = 12, Triple = (6,8,10) Cube = 18, Triple = (2,12,16) Cube = 18, Triple = (9,12,15) Cube = 19, Triple = (3,10,18) Cube = 20, Triple = (7,14,17) Cube = 24, Triple = (12,16,20)
4/32

3、解题思路
?

此题的思路非常简单:给定4 个整数的四元组(a、b、 c、d),判断它们是否满足完美立方等式a^3 = b^3 + c^3 + d^3。对全部的四元组进行排序,依次进行 判断。如果一个四元组满足完美立方等式,则按照要 求输出。先判断a值小的四元组;两个四元组的a 值相 同,则先判断b值小的;两个四元组的a值和b值分别 相同,则先判断c值小的。关键是解决两个方面的问题:

5/32

3、解题思路
(1) 确定全部需要判断的四元组,并对它们进行排序。稍作分 析不难发现,在这个序列中,任意一个四元组(a、b、c、d): (a) a≥6,因为a 最小必须是5,才能使得b、c、d 分别是3 个 大于1 的不同整数,但(5、2、3、4)不满足完美立方等式的要 求;(b)如果(a、b、c、d)满足完美立方等式,则b、c、d 都 要比a 小。 (2) 避免对一个整数的立方的重复计算。[2, N]中的每个整数i, 在整个需要判断的四元组序列中都反复出现。每出现一次,就 要计算一次它的立方。在开始完美立方等式的判断之前,先用 一个数组保存[2, N]中的每个整数的立方值。在判断四元组(a、 b、c、d)是否满足完美立方等式的要求时,直接使用存储在数 组中的立方值。
6/32

#include <stdio.h> ?#include <math.h> ?int main(void) ?{ ? int i, n, a, b, c, d; ? long cube[101]; ? scanf("%d ", &n ); ? for ( i = 1 ; i <= n ; i++ ) ? cube[i] = i*i*i; ? for ( a = 6 ; a <= n ; a++ ) ? for ( b = 2 ; b < a - 1; b++ ) ? { ? if (cube[a] < cube[b] + cube[b+1] + cube[b+2]) break; ? for ( c = b+1 ; c < a ; c++ ) ? { ? if ( cube[a] < cube[b] + cube[c] + cube[c+1]) break; ? for ( d = c+1; d < a ; d++ ) ? if ( cube[a] == cube[b] + cube[c] + cube[d] ) ? printf( "Cube = %d, Triple = (%d,%d,%d)\n", a, b, c, d); ? } ? } ? return 0; ?}
?

4、参考程序

7/32

熄灯问题
1、链接地址
http://poj.grids.cn/problem?id=2811

2、问题描述 一个由按钮组成的矩阵,其中每行有6个按钮, 共5行。每个按钮的位置上有一盏灯。当按下一个 按钮后,该按钮以及周围位置(上边、下边、左边、 右边)的灯都会改变一次。即,如果灯原来是点亮 的,就会被熄灭;如果灯原来是熄灭的,则会被点 亮。在矩阵角上的按钮改变3盏灯的状态;在矩阵 边上的按钮改变4盏灯的状态;其他的按钮改变5 盏灯的状态。
8/32

问题描述

在上图中,左边矩阵中用X标记的按钮表示被按下, 右边的矩阵表示灯状态的改变。对矩阵中的每盏灯 设置一个初始状态。请你按按钮,直至每一盏等都 熄灭。与一盏灯毗邻的多个按钮被按下时,一个操 作会抵消另一次操作的结果。在下图中,第2行第 3、5列的按钮都被按下,因此第2行、第4列的灯 的状态就不改变。
9/32

问题描述

请你写一个程序,确定需要按下哪些按钮,恰好使得所有的灯都熄灭。 根据上面的规则,我们知道:

(1)第2次按下同一个按钮时,将抵消第1次按下时所产生的结果。因此, 每个按钮最多只需要按下一次;
(2)各个按钮被按下的顺序对最终的结果没有影响;

(3)对第1行中每盏点亮的灯,按下第2行对应的按钮,就可以熄灭第1 行的全部灯。如此重复下去,可以熄灭第1、2、3、4行的全部灯。同 样,按下第1、2、3、4、5列的按钮,可以熄灭前5列的灯。
10/32

问题描述
输入数据
第一行是一个正整数N,表示需要解决的案例数。每个 案例由5行组成,每一行包括6个数字。这些数字以空格 隔开,可以是0或1。0表示灯的初始状态是熄灭的,1表 示灯的初始状态是点亮的。

输出要求
对每个案例,首先输出一行,输出字符串“PUZZLE #m”,其中m是该案例的序号。接着按照该案例的输入 格式输出5行,其中的1表示需要把对应的按钮按下,0 则表示不需要按对应的按钮。每个数字以一个空格隔开。

11/32

问题描述
输入样例 2 011010 100111 001001 100101 011100 001010 101011 001011 101100 010100 输出样例 PUZZLE #1 101001 110101 001011 100100 010000 PUZZLE #2 100111 110000 000100 110101 101101
12/32

3、解题思路
为了叙述方便,按下图所示,为按钮矩阵中的每个位置分 别指定一个坐标。用数组元素puzzle[i][j]表示位置(i, j)上 灯的初始状态:1 表示灯是被点亮的;0 表示灯是熄灭的。 用数组元素press[i][j]表示为了让全部的灯都熄灭,是否要 按下位置(i, j)上的按钮:1 表示要按下;0 表示不用按下。
?

由于第0 行、第0 列和第7 列不属于按钮矩阵的范围,没 有按钮,可以假设这些位置上的灯总是熄灭的、按钮也不用 按下。其它30 个位置上的按钮是否需要按下是未知的。
?

因此数组press 共有2^30种取值。从这么大的一个空间 中直接搜索我们要找的答案,显然代价太大、不合适。要从 熄灯的规则中,发现答案中的元素值之间的规律。不满足这 个规律的数组press,就没有必要进行判断了。
?
13/32

3、解题思路

14/32

?根据熄灯规则,如果矩阵press

是寻找的答案,那么按照press 的 第一行对矩阵中的按钮操作之后,此时在矩阵的第一行上:

3、解题思路

?? ??

如果位置(1, j)上的灯是点亮的,则要按下位置(2, j)上按钮, 即press[2][j]一定取1; 如果位置(1, j)上的灯是熄灭的,则不能按位置(2, j)上按钮, 即press[2][j]一定取0。
?这样依据press

的第一、二行操作矩阵中的按钮,才能保证第一行 的灯全部熄灭。而对矩阵中第三、四、五行的按钮无论进行什么样 的操作,都不影响第一行各灯的状态。依此类推,可以确定press 第三、四、五行的值。
?因此,一旦确定了press

第一行的值之后,为熄灭矩阵中第一至四 行的灯,其他行的值也就随之确定了。press 的第一行共有2^6 种 取值,分别对应唯一的一种press 取值,使得矩阵中前四行的灯都 能熄灭。只要对这2^6 种情况进行判断就可以了:如果按照其中的 某个press对矩阵中的按钮进行操作后,第五行的所有灯也恰好熄灭, 则找到了答案。
15/32

解决方案

3、解题思路 (1)对press 第一行的元素press[1][1]~ press [1][6]的各
种取值情况进行枚举,依次考虑如下情况:
000000 100000 010000 110000 001000 …… 111111

(2) 对press 第一行每一种取值,根据熄灯规则计算出press 的其他行的值。判断这个press 能否使得矩阵第五行的所有灯 也恰好熄灭。 16/32

4、参考程序
#include <stdio.h> ?int puzzle[6][8],press[6][8]; ?bool guess(void) ?{ ? int c,r; ? for (r=1;r<5;r++ ) ? for (c=1;c<7;c++) ? press[r+1][c]=(puzzle[r][c]+press[r][c] ? +press[r-1][c]+press[r][c-1] ? +press[r][c+1])%2; ? for(c=1;c<7;c++) //判断最后一行是否熄灭 ? if ((press[5][c-1]+press[5][c]+press[5][c+1] ? +press[4][c])%2!=puzzle[5][c]) ? return(false); ? return true; ?}
?

17/32

4、参考程序
void enumate(void) ?{ ? int c; ? for (c=1;c<7;c++) ? press[1][c]=0; ? while(guess()==false) ? { ? press[1][1]++; ? c=1; ? while(press[1][c]>1) ? { ? press[1][c]=0; ? c++; ? press[1][c]++; ? } ? } ?}
?

18/32

int main(void) ?{ ? int cases,i,r,c; ? scanf("%d", &cases); ? for (r=0;r<6;r++) ? press[r][0]=press[r][7]=0; ? for (c=1;c<7;c++) ? press[0][c]=0; ? for (i=0;i<cases;i++) ? { ? for (r=1;r<6;r++) ? for (c=1;c<7;c++) ? scanf("%d", &puzzle[r][c]); ? enumate(); ? printf("PUZZLE #%d\n",i+1); ? for (r=1;r<6;r++) ? { ? for (c=1;c<7;c++) ? printf("%d ",press[r][c]); ? printf("\n"); ? } ? } ? return 0; ?}
?

4、参考程序

19/32

讨厌的青蛙
1、链接地址
http://poj.grids.cn/problem?id=2812

2、问题描述
在韩国,有一种小的青蛙。每到晚上,这种青蛙会跳越稻 田,从而踩踏稻子。农民在早上看到被踩踏的稻子,希望 找到造成最大损害的那只青蛙经过的路径。每只青蛙总是 沿着一条直线跳越稻田,而且每次跳跃的距离都相同,如 图1所示。 稻田里的稻子组成一个栅格,每棵稻子位于一 个格点上,如图2所示。而青蛙总是从稻田的一侧跳进稻田, 然后沿着某条直线穿越稻田,从另一侧跳出去,如图3所示。

20/32

问题描述

21/32

问题描述
青蛙的每一跳都恰好踩在一棵水稻上,将这棵水稻拍倒。可能 会有多只青蛙从稻田穿越,有些水稻被多只青蛙踩踏,如图4 所示。当然,农民所见到的是图5中的情形,看不到图4中的 直线。

22/32

问题描述
根据图5,农民能够构造出青蛙穿越稻田时的行走路径,并且 只关心那些在穿越稻田时至少踩踏了3 棵水稻的青蛙。因此, 每条青蛙行走路径上至少包括3 棵被踩踏的水稻。而在一条青 蛙行走路径的直线上,也可能会有些被踩踏的水稻不属于该行 走路径。在图5中,格点(2, 1)、(6, 1)上的水稻可能是同一只 青蛙踩踏的,但这条线上只有两棵被踩踏的水稻,因此不能作 为一条青蛙行走路径;格点(2, 3)、(3, 4)、(6, 6)在同一条 直线上,但它们的间距不等,因此不能作为一条青蛙行走路径; 格点(2, 1)、(2, 3)、(2, 5)、(2, 7)是一条青蛙行走路径,该 路径不包括格点(2, 6)。请你写一个程序,确定在所有的青蛙 行路径中,踩踏水稻棵数最多的路径上有多少棵水稻被踩踏。 例如,图5的答案是7,因为第6 行上全部水稻恰好构成一条青 蛙行走路径。
23/32

问题描述
输入数据
从标准输入设备上读入数据。第一行上两个整数R、C,分别 表示稻田中水稻的行数和列数,1≤R、C≤5000。第二行是一 个整数N,表示被踩踏的水稻数量, 3≤N≤5000。在剩下的 N 行中,每行有两个整数,分别是一颗被踩踏水稻的行号 (1~R)和列号(1~C),两个整数用一个空格隔开。而且,每棵 被踩踏水稻只被列出一次。

输出要求
从标准输出设备上输出一个整数。如果在稻田中存在青蛙行走 路径,则输出包含最多水稻的青蛙行走路径中的水稻数量,否 则输出0。
24/32

问题描述
输入样例
67 ?14 ?2 1 ?6 6 ?4 2 ?2 5 ?2 6 ?2 7 ?3 4 ?6 1 ?6 2 ?2 3 ?6 3 ?6 4 ?6 5 ?6 7
?

输出样例
7

25/32

3、解题思路
这个问题看起来很复杂,其实目的很简单:帮助农民找到 为害最大的青蛙。也就是要找到一条穿越稻田的青蛙路径, 这个路径上被踩踏的水稻不少于其他任何青蛙路径上被踩踏 的水稻数。当然,整个稻田中也可能根本就不存在青蛙路径。 问题的关键是:找到穿越稻田的全部青蛙路径。任何一条穿 越稻田的青蛙路径L,至少包括3 棵被踩踏的水稻。假设其 中前两棵被踩踏的水稻分别是(X1,Y1)、(X2,Y2),那么: 令dx=X2-X1、dy=Y2-Y1;X0=X1-dx、Y0=Y1- dy; X3=X2 + dx、Y3=Y2 + dy
?

(X0,Y0)位于稻田之外,青蛙从该位置经一跳后进入稻田、 踩踏位置(X1,Y1)上的水稻
?
26/32

3、解题思路
Xi=X0 + i×dx、Yi=Y1 + i×dy(i>3),如果(Xi,Yi)位于 稻田之内,则(Xi,Yi)上的水稻必被青蛙踩踏
?

根据上述规则,只要知道一条青蛙路径上的前两棵被踩踏的 水稻,就可以找到该路径上其他的水稻。为了找到全部的青 蛙路径,只要从被踩踏的水稻中,任取两棵水稻(X1,Y1)、 (X2,Y2),判断(X1,Y1)、(X2,Y2)是否能够作为一条青蛙路径 上最先被踩踏的两颗水稻。

解决方案
这个问题的描述中,最基本的元素是被踩踏的水稻。在程序 中要选择一个合适的数据结构,来表达这个基本元素。这个 数据结构是否合适的标准是:在程序中要表达这个元素时, 能否用一个单词或者短语,即用一个变量来表示。
27/32

3、解题思路
struct PLANT //描述一棵被踩踏的水稻 { int x; //水稻的行号 int y; //水稻的列号 } 这个问题的主要计算是:从被踩踏的水稻中选择两棵 (X1,Y1)、(X2,Y2)。判断它们是否能够作为一条青蛙路径上 最先被踩踏的两颗水稻。(X1,Y1)、(X2,Y2)唯一确定了蛙跳 的方向和步长,从(X2,Y2)开始,沿着这个方向和步长在稻 田内走。每走一步,判断所到达位置上(X,Y)的水稻是否被 踩踏,直到走出稻田为止。如果在某一步上,(X,Y)没有被 踩踏,则表明(X1,Y1)、(X2,Y2)是一条青蛙路径上最先被踩 踏的两颗水稻的假设不成立。这个判断的算法在问题求解过 28/32 程中要反复使用,它的效率成为决定整个计算效率的关键。

3、解题思路
用一个PLANT 型的数组plants[5001]表示全部被踩踏的 水稻
? ? ?

将plants 中的元素按照行/列序号的升序(或者降序)排列

采用二分法查找plants 中是否有值为(X,Y)的元素:将 (X,Y)与plants 中间的元素比较,(1)相等,表明找到了元 素;(2)比plants 中间元素的小,继续在plants 的前半部寻 找;(3)比plants 中间元素的大,继续在plants 的后半部寻 找。 采用上述方法判断每走一步所到达位置上(X,Y)的水稻是 否被踩踏,最多只要比较log2N,其中N 是稻田中被踩踏水 稻的总量。
29/32

4、参考程序
#include <stdio.h> ?#include <stdlib.h> ?int r,c,n; ?struct PLANT ?{ ? int x,y; ?}; ?PLANT plants[5001]; ?PLANT plant; ?int myCompare(const void *ele1,const void *ele2); ?int searchPath(PLANT secPlant, int dX, int dY);
?

30/32

4、参考程序
int main(void) ?{ ? int i,j,dX,dY,pX,pY,steps,max=2; ? scanf("%d%d",&r,&c); ? scanf("%d",&n); ? for(i=0;i<n;i++) ? scanf("%d %d",&plants[i].x,&plants[i].y); ? qsort(plants,n,sizeof(PLANT),myCompare); ? //先竖向排列,再横向排列 ? for(i=0;i<n-2;i++) ? for(j=i+1;j<n-1;j++) ? { ? dX=plants[j].x-plants[i].x; ? dY=plants[j].y-plants[i].y; ? pX=plants[i].x-dX; ? pY=plants[i].y-dY;
?

31/32

4、参考程序
? ?

?
? ? ? ?

?
? ? ? ? ? ? ? ? ?

}

} if(max==2) max=0; printf("%d\n",max); return (0);

if(pX<=r&&pX>=1&&pY<=c&&pY>=1) //说明plants[i]不是青蛙进入稻田的起始点 continue; if(plants[i].x+max*dX>r)//说明在该路径上不会出现更多被踩踏的 break;//注意随着j的变化,dX只会增大 pY=plants[i].y+max*dY; if(pY>c||pY<1)//注意行进方向为[-pi/2,pi/2) continue; //随着j的变化,dY可能会减小 //steps表示路径上踩踏的水稻数,如果不成为路径,则为0 steps=searchPath(plants[j],dX,dY); if(steps>max) max=steps;

32/32

4、参考程序
int myCompare(const void *ele1,const void *ele2) ?{ ? PLANT *p1,*p2; ? p1=(PLANT*)ele1; ? p2=(PLANT*)ele2; ? if(p1->x==p2->x) //优先竖向比较 ? return(p1->y-p2->y); ? return (p1->x-p2->x); ?}
?

33/32

int searchPath(PLANT secPlant,int dX,int dY ) ?{ ? PLANT plant; ? int steps; ? plant.x=secPlant.x+dX; ? plant.y=secPlant.y+dY; ? steps=2; ? while(plant.x<=r&&plant.x>=1&&plant.y<=c&&plant.y>=1) //没有 出界 ? { ? if(!bsearch(&plant,plants,n,sizeof(PLANT),myCompare)) //不成为路 径 ? { ? steps=0; ? break; ? } ? plant.x+=dX; ? plant.y+=dY; ? steps++; ? } ? return (steps); ?}
?

4、参考程序

34/32

马的走法
1、问题描述
在一个4×5的棋盘上,马的起始位置坐标(纵,横)位置由键 盘输入,求马能返回初始位置的所有不同走法的总数(马走过 的位置不能重复,马走“日”字)。 输入输出样例:

35/32

2、问题分析
由于4×5的棋盘的问题规模比较小,用回溯法可以较好的解 决问题。 如下图所示,如果从(1,1)出发,那么马首先从(1,1)点走向 (3,2)点,再到(2,4)点,这样过程可以一步一步递推下去,最后 要么找到一条路径,要么进入“死胡同”,这时函数 find(p1,p2)就不能递归调用自己了,因此实现了回溯。 为了避免走重复的位置,可以定义一个数 组chess[5][4]表示棋盘,若chess[i][j]=1, 则表示马已经走过,在递推时就不能走此 位置,应该换一个方向。 对于马走的方向,可以定义数组d[2][8], 每列表示一个马可以走的方向。 36/32

#include <stdio.h> int chess[5][4]; int d[2][8]={{-1,-1,-2,-2,2,2,1,1}, {2,-2,1,-1,1,-1,2,-2}}; int sx,sy,tot; void find(int p1,int p2) { int i,pi,pj; for(i=0;i<8;i++) { pi=p1+d[0][i]; pj=p2+d[1][i]; if((pi==sx) && (pj==sy)) //一定要放在前面 tot++; else if((pi>=0)&&(pi<5)&&(pj>=0)&&(pj<4)&&(chess[pi][pj]==0)) { chess[pi][pj]=1; find(pi,pj); chess[pi][pj]=0; } } }

3、参考代码

37/32

3、参考代码
int main(void) { int i,j; while(scanf("%d %d",&sy,&sx)==2) { for(i=0;i<5;i++) for(j=0;j<4;j++) chess[i][j]=0; tot=0; sx--;sy--; find(sx,sy); printf("%d\n",tot); } return 0; }
38/32


相关文章:
第十九周 简单枚举
第五章 简单的枚举法 12页 5财富值 第十一周 枚举(二) 暂无评价 38页 5财富...我们把小华的不同走法一一列举如下:第第第第第:小① 学学 ④ 文文文文 ...
二年级数学(下)第十一周练习卷
松江众兴小学二年级数学(下)第十一周练习卷 班级 姓名 家长签名 一、计算 1、横式计算 483+237 718-639 98+508 600-234 2、 递等式计算 36÷9×1 56-7...
第十一周教案
第十一周教案_二年级语文_语文_小学教育_教育专区。课时教学设计课 题 语文园地五 2014 年 11 月 10 日 教案序号 课型 10 复习 授课时间 教学目标 1、学习从...
快乐数学上学期社团教材
实验小学快乐数学社团活动安排表:辅导老师:王亚男 周次 第 1、2 周第3周 第...第九周整数的拆分习题 20 第十周 枚举法习题十 21 22 第十一周 找规律法...
二年级第十一周测试卷
二年级第十一周测试卷一、看谁最聪明。 (共 38 分) 看谁最聪明。 共 1、括号里最大能填几: 4 ×()< 30 ( ) × 9 < 62 3 ×( ) < 17 ( ) ...
基础测试第十一周(实词2)学生版 ring
基础测试第十一周(实词2)学生版 ring_高三语文_语文_高中教育_教育专区。高三专项考核——文言实词 2(第十一周) 2014·11·11 每题 3 分,满分 120 分 1.下...
第十一周数学教案
第十一周数学教案_数学_小学教育_教育专区。课时教案设计第 十一周第 1 课时 ...质疑总 2分 结 找最小公倍数 枚举法 板书设计 预习 分数的大小 作业 必做...
二上数学导优作业设计
8. 8 9. 第十一周 1.把 2、3、13、18 分别填入下面( ()-( )里,使...第十八周枚举法 1.一个长方形的周长是22米,如果它的长和宽都是整米数,问:...
三年级作业(第十一周)
三年级作业(第十一周)_其它考试_资格考试/认证_教育专区。三年级作业(第十一周...My … is/are …二、 预习课文 要求:1.听录音,熟读、记本模块核心词汇。 ...
第十一周高二语文23娜塔莎
第十一周高二语文23娜塔莎_高二语文_语文_高中教育_教育专区。编制人 王俊 审核...2、通过文本分析,把握少女娜塔莎的思想感情,分析人物形象。 3、通过娜塔莎形象...
更多相关标签:
十一北京周边二日游 | 写在结婚二十一周年的 | 十一北京周边自驾游 | 十一黄金周 | vogue十一周年盛典 | vogue十一周年庆典 | 传奇十一周年客户端 | 十一北京周边旅游推荐 |