一、亮着电灯的盏数。
题目简介:
一条长廊里依次装有n(1 ≤ n ≤ 65535)盏电灯,从头到尾编号1、2、3、…n-1、n。每盏电灯由一个拉线开关控制。开始,电灯全部关着。
有n个学生从长廊穿过。第一个学生把号码凡是1的倍数的电灯的开关拉一下;接着第二个学生把号码凡是2的倍数的电灯的开关拉一下;接着第三个学生把号码凡是3的倍数的电灯的开关拉一下;如此继续下去,最后第n个学生把号码凡是n的倍数的电灯的开关拉一下。n个学生按此规定走完后,长廊里电灯有几盏亮着。
注:电灯数和学生数一致。
题目解答:
全部写在代码注释里了,无需多言。
完整代码请见http://www.anycodex.com/blog/?p=218
二、划出及格线。
题目简介:
10个学生考完期末考试评卷完成后,A老师需要划出及格线,要求如下:
(1) 及格线是10的倍数;
(2) 保证至少有60%的学生及格;
(3) 如果所有的学生都高于60分,则及格线为60分:
运行时间限制: 无限制
内存限制: 无限制
输入:
输入10个整数,取值0~100
输出:
输出及格线,10的倍数
样例输入:
61 51 49 30 20 10 70 80 90 99
样例输出:
50
题目解答:
我是觉得这道题目出的不怎么好,及格线至少60%是什么意思?就按样例里面给出的数据,我如果把及格线化为10,及格线100%也满足题目里面要求的任何条件吧?但很显然,这不是主考官的出题意思了。分数应该是尽可能的高,同时要满足及格率大于60%。
思路1:将及格线从100开始往下降,直到及格线大于60%,循环break。(测试未通过)但测试是错误的,迄今我也不知道为什么。
思路2:将输入数据从低到高排序,取小于第4个数据的10的倍数作为及格线。(测试通过)
完整代码请见
http://www.anycodex.com/blog/?p=230
三、单词迷宫。
题目简介:
Word Maze 是一个网络小游戏,你需要找到以字母标注的食物,但要求以给定单词字母的顺序吃掉。如上图,假设给定单词if,你必须先吃掉i然后才能吃掉f。
但现在你的任务可没有这么简单,你现在处于一个迷宫Maze(n×m的矩阵)当中,里面到处都是以字母标注的食物,但你只能吃掉能连成给定单词W的食物。
如下图,指定W为“SOLO”,则在地图中红色标注了单词“SOLO”。
注意区分英文字母大小写,你只能上下左右行走。
运行时间限制: 无限制
内存限制: 无限制
输入:
输入第一行包含两个整数n、m(0<n, m<21)分别表示n行m列的矩阵,第二行是长度不超过100的单词W,从第3行到底n+3行是只包含大小写英文字母的长度为m的字符串。
输出:
如果能在地图中连成给定的单词,则输出“YES”,否则输出“NO”。注意:每个字母只能用一次。
样例输入:
5 5
SOLO
CPUCY
EKLQH
CRSOL
EKLQO
PGRBC
样例输出:yes
题目解答:
其实没想象中的那么复杂,就是要考虑的边边角角问题多了些。
主要思路:
1、创建一个字符串数组用于存放n*m的字母;
2、创建一个整型(或bool型)数组,用于标记相应位置处的元素是否被访问过;
3、找到第一个字母(如S)后,进入查找下一个字母(如O)的程序,找到之后,在递归进入查找下一个字母的程序,以此类推。若递归到需要查找的单词进入结尾时(如需要查找的为SOLO,查找顺序为S —> O —–> L ——>O——->’\0′),遇到’\0‘,则证明该单词被找到;
需要处理的边界问题:
为了说明需要注意的细节,我们可以把输入的测试数据改为:
5 5
SQOC
CPUCY
EKLQH
CRSOL
EKSQO
PGRBC
主要差别在于,有两个S,当按照顺序查找S —-> Q ——> O ——> C,从Q查找O时,Q的上方和右方都是O。
这道题里面需要考虑的编编脚脚问题主要有:
1、越界问题。如当一个元素位于最右小脚,那么只能去检查它的上方和左方,而不能检查它的右方和下方,etc.
2、每个元素只能访问一次的问题。用数组标记是否被访问过即可解决。
4、查找S时,有两个S,从第一个S找未成功后,能接着查找是否存在别的S,然后能找到索要查找单词的可能性;
3、当一个方向失败之后,还能接下去尝试其他方案。这就涉及到上下左右四个判断语句不能用if esle if else if….之类的结构,而是if if if if;
完整代码请见
http://www.anycodex.com/blog/?p=222
测试平台:
www.anycodex.com