Geek@Paris

MacIdea 3周年·编程大赛——Python版参考答案

2012-09-04

2012年8月1日,MacIdea论坛举办了一次小小的编程比赛。比赛内容是让大家做3个算法题,外加1个MacIdea创始人hdfdisk提供的附加题。

我向来喜欢这种挑战自我的小比赛,第一时间就去凑热闹了,公司的活都不干了……

几年前就想学Python,一直没找到切入点。这次比赛是一个不错的机会,我毅然决然地调动了所有资源开始学习Python,从研究Python开发环境到上网搜索入门教材和范例,废寝忘食了几天,在家都顾不上搭理老婆了…

如今距离比赛结束(2012年8月14日)有2个多星期了,8月初提交完答案后我再也没管过它。现在答案和成绩都出来后,找个时间坐下来再好好看看这3个算法题的解题思路,参考参考别人的答案。

结合各家精华,用依旧生疏的Python知识完善了一下我的一份答案,放在这里以备查阅。

详情请查看正文:

PS:由于试题内容比较长,我把它们放在文章末尾部分了。


开发环境

本来想简单一点,就用Sublime Text 2来写。结果发现这么做的问题有不少,一来Sublime Text 2没有自动补全功能(不知道有没有相关插件);二来其Console居然不接受键盘输入……

于是按照不少教程里提到的过程装了Eclipse及其PyDev插件,但这么用了没多久还是不爽…

最后找到了PyCharm这个IDE,试用下来发现非常好用!不仅支持语法分析和自动补全,还支持各种GUI框架和Django,极力推荐~


第0题

题目要求很简单,去除四则运算表达式中多余的括号即可。

也许不了解逆波兰表达式(或前缀表达式)的同学首先想到的方法是通过堆栈或正则表达式来寻找匹配的括号对,然后根据一定的规律来删除不必要的括号对?据我所知这么做出错的可能性非常高,具体我没有尝试。我发现比赛结果中做对这题的同学只有2位(一共18份答案),不知道另外16位同学中是不是有人尝试了这些方法呢……

下面是我提交完答案后再改良过的版本。由于答案长度也会影响评分,所以我用了非常简短的变量名和函数名。一些名称的解释如下:

  • i2r、r2i:r表示Reverse Polish Notation(逆波兰表达式),i表示Infix Notation(中缀表达式)。2就是英语to,在这里表示转换方向。
  • p、opt、optL、optR:都是operator的缩写,表示运算符。L/R表示左右。
  • e、eL、eR:expression(left/right)的缩写,表示(左/右)表达式。
  • c:character的缩写,表示表达式中的任何一个符号。

下面代码中的算法先根据运算符优先级把中缀表达式转换成后缀表达式(逆波兰表达式)。由于后缀表达式没有括号,所以在这个过程中,所有括号都被去除了。然后再把后缀表达式转换成中缀表达式,按一定的规则补充必要的括号,以保证结果相同。于是题目要求就达成了。

由于这个题目中只有字母,也只有加减乘除,所以代码比较简短,参考答案如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#!/usr/bin/env python
# -*- coding:utf-8 -*-
 
def i2r(e):
    p = {'*':4,'/':4,'+':3,'-':3,'(':2,')':1}
    result=[]
    stack=[]
    for c in e:
        if 'a'<=c<='z':
            result.append(c)
        elif c in '+-*/':
            while len(stack) and p[c] <= p[stack[-1]]:result.append(stack.pop())
            stack.append(c)
        elif c=='(':
            stack.append(c)
        elif c==')':
            while stack[-1]!='(':result.append(stack.pop())
            stack.pop()
    while len(stack):
        if stack[-1]=='(':stack.pop()
        else:result.append(stack.pop())
    return ''.join(result)
 
def r2i(e):
    opt=e[-1]
    e=e[:-1]
    i=c=1
    while c:
        if e[-i] in '+-*/':c+=1
        else:c-=1
        i+=1
    optL = e[-i]
    optR = e[-1]
    eL = e[:-i+1]
    if len(eL) > 1:eL = r2i(eL)
    eR = e[-i+1:]
    if len(eR) > 1:eR = r2i(eR)
    if opt in '*/' and optL in '+-':eL = '('+eL+')'
    if opt in '*-' and optR in '+-' or opt=='/' and optR in '+-*/':eR = '('+eR+')'
    return eL+opt+eR
 
def main():
    print '去除冗余括号之后的表达式是:'+str(r2i(i2r(raw_input('请输入表达式:'))))
 
if __name__ == '__main__':
    main()

第1题

这一题简单讲就是说,一共有X条线路Y个车站,线路都是单向的,从1号车站出发,问到达Y车站最少需要换几次车。

好在不是双向链表,也不是循环线路,算法会简单不少。我不知道有没有更聪明的算法,我的算法就是最直觉的办法,从1号站台开始,把所有可能性都遍历一遍,找出最少的换车次数…

同样,因为变量名和函数名都很简洁,这里解释一下各名称的含义:

  • S、L:Station和Line的缩写,也就是车站和线路的意思。从每个车站出发可以乘众多线路的车,而每条线路都由众多个车站组成。
  • cS、cL:Current Station、Current Line的缩写,当前车站,当前线路。
  • fS:Function for Station的缩写,计算从指定线路的指定站出发,尝试在这条线路后面其他站换车,看前往Y车站最少的换车次数是多少。
  • fL:Function for Line的缩写,计算从指定线路的指定站出发,尝试该站其他所有线路,看前往Y车站最少的换车次数是多少。
  • cnt:count,计数,用来记录换车次数。由于题目限制最多100条线路最多500个车站,所以我设其初值为999。

参考答案如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#!/usr/bin/env python
# -*- coding:utf-8 -*-
 
def fS(cS,cL):
    rest = cL[cL.index(cS)+1:]
    if not len(rest):return -1
    if d in rest:return 0
    cnt = 999
    for cS in rest:
        tmp = fL(cS,cL)
        if tmp != -1:
            tmp+=1
            if tmp < cnt:
                cnt = tmp
    if cnt == 999:return -1
    return cnt
 
def fL(cS,cL):
    cnt = 999
    for aL in Ls:
        if aL != cL and cS in aL:
            tmp = fS(cS,aL)
            if tmp != -1 and tmp < cnt:
                    cnt = tmp
    if cnt == 999:return -1
    return cnt
 
def main():
    global n,d,Ls
    n,d = map(int, raw_input('请输入线路数和车站数(由空格分隔):').split())
    Ls = []
    i = 0
    while i < n:
         Ls.append(map(int,raw_input('请输入第%s条线路所经过的车站(由空格分隔):' % (i+1)).split()))
         i+=1
    print '最少换乘次数是:'+str(fL(1,[]))
 
if __name__ == '__main__':
    main()

第2题

题目请看文章末尾的原题,我不知道如何用更简洁的语言来描述这道题目…

这题最直接的解法就是遍历,两两比较,满足一定条件的话删除其中之一,然后继续遍历……这个算法在最坏的情况下时间复杂度为O(N^2),我不知道有没有更聪明的算法呢……参考答案如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#!/usr/bin/env python
# -*- coding:utf-8 -*-
 
def f(Ps):
    rPs = Ps[:]
    for p in Ps:
        for r in rPs:
            if p[0]<r[0] and p[1]<r[1]:
                rPs.remove(p)
                break
    return len(rPs)
 
def main():
    n = int(raw_input('请输入行数:'))
    Ps = []
    i = 0
    while i<n:
        Ps.append(map(int,raw_input('请输入第%s个帖子的技术分和语言分(由空格分隔):' % (i+1)).split()))
        i+=1
    print '最多容纳%s个技术帖。' % f(Ps)
 
if __name__ == '__main__':
    main()

下面是所有的试题

问题 #0: 括号

提供一个表达式,其中包含若干个变量及六种运算符:+、-、*、/、(、)。在表达式中可能含有多余的括号。你的任务是修改此表达式,去除所有多余的括号,但不能改变变量和/或运算符的位置。

你的答案中的表达式须与原表达式相等。

例如:

输入:a+(b+c)
输出:a+b+c
输入:(a*b)+c/d
输出:a*b+c/d
输入:a*(b+d)
输出:a*(b+d)
输入:a+b/(c-d)
输出:a+b/(c-d)
输入:((a+b)*f)-(i/j)
输出:(a+b)*f-i/j

注意:表达式中所有变量皆为小写字母,且每个变量仅有一个字母。切记你的任务是去除多余的括号,所以不要化简表达式。

输入:
一行,待处理的表达式。

输出:
一行,去除多余括号后的表达式。

输入样例:
a+(b+c)

输出样例:
a+b+c

问题 #1: 巴士

因为小镇里没有地铁站或是电车站,所以何度加巴士株式会社——大雄爸爸工作的那个公司——最近在小镇里新设立了一些新的巴士车站和一些单程的巴士线路。

今天,大雄要去月见台公园(嘛…当然是去和静香约会,你懂的),但如果没有从大雄家直达月见台公园的车的话,他就得先坐某一路巴士,到达 A 车站,然后再在 A 车站换乘另一路巴士。他可能会在换乘若干次后到达公园。

现在我们给小镇里的每一个巴士车站编号:1、2、3…Y。在这里,我们规定大雄家的编号为1,月见台公园的编号为 Y。

你的任务是给大雄规划最佳乘车方案,使他换乘最少次数的巴士。

输入:
X+1 行。
第一行:两个正整数 X 和 Y(1≦X≦100,1<Y≦500),表示小镇里总共有 X 条单程巴士线路,及 Y 个车站。
第二行到第 X+1 行:依顺序给出了从第1条到第 X 条巴士线路的信息(第 X+1 行给出了第 X 条巴士线路的信息)。这一行以从左向右的顺序依次给出了该线路经过的所有车站的编号。(注:相邻两个站之间以空格隔开。)

输出:
一行,换乘巴士所用的最少次数。
在这里,0代表大雄不需要换乘(即,有车从他家直达公园),而-1代表他无法乘巴士。

输入样例:
3 7
6 7
4 7 3 6
2 1 3 5

输出样例:
2

特别注意:巴士是单程的,所以你不能“倒着坐”。(例如,有一条线路是“4 7 3 6”,你不能从3号站坐到7号站,只能“沿着线路的方向”从3号站坐到6号站。)

问题 #2: 论坛

为了改变 MacIdea 里充斥着技术宅而缺少妹纸的窘境,最近 MacIdea 在酝酿改版。

鹳狸猿们认为,妹纸们不愿意来 MacIdea 的一个原因是因为论坛里充满了许多高深且语言晦涩难懂的技术帖。所以鹳狸猿和斑竹们花了好长时间给论坛里的每一个技术帖都做了评估,给每一个帖子评了“技 术含量分”(技术含量高的帖子得分高)和“语言分”(语言浅显易懂的帖子得分高)。

鹳狸猿们打算把“技术含量高且语言浅显易懂”的帖子移动到一个单独的版块,然后用这个版块来吸引妹纸们。但为了避免这个版块帖子泛滥,他们规定:当帖子甲的“技术含量分”比帖子乙的得分低、并且“语言分”也比帖子乙的得分低时,那么帖子甲就不能留在这个版块。

你的任务是计算这个版块最多能容纳多少技术帖。

输入:
X+1 行。
第一行:一个正整数数 X(X≦1000),表示论坛里总共有多少技术帖;
第二行到第 X+1 行:依顺序给出了从第1个到第 X 个技术帖的信息(第 X+1 行给出了第 X 个技术帖的信息)。每行有两个数 A 和 B,分别代表该帖的“技术含量分”和“语言分”。

输出:
一行,一个正整数,这个版块最多能容纳多少技术帖。

输入样例:
5
4 1
4 2
4 3
3 3
2 2

输出样例:
4

附加题: 纸币

(本题由 hdfdisk 友情提供)

MacIdea 最近决定发行论坛专属的纸质货币了,但在如何设计纸币面额的问题上,鹳狸猿们拿不定主意,现在请你设计一个算法,来帮助 MacIdea 解决这个问题。

首先,大家都不喜欢带着太重的钱包出去,所以鹳狸猿们提了个要求,钱包里最多只能放 x 张货币。

过多的面额会导致设计和印刷成本升高,所以你还应该把面额的数量限制在 y。

请你设计一套货币,使得

  • 在钱包里只有 x 张纸币的情况下,钱包里纸币的价值尽可能大,我们设这个数为 a
  • 你能够用你设计的面额组合出从0到 a 的任何一个价值。

(数据范围:2≦x≦8,1≦y≦50)

输入样例:
3 4
即钱包里可以放3张纸币,你可以设计最多4种面额。

输出样例:
1 4 6 9
16

即,面额设计为1、4、6、9;能够组合出的连续最大面额为16。
注:9+9 = 18,但无法组合出17,所以连续的最大面额为16。

如果没有解比这个解更好,则这个算法获得胜利,但:
1 3 6 10
21

是比上面的算法更好的结果,如果这个算法在之后给出,则这个算法获得胜利。

Author:admin | Categories:DevPython | Tags:

Leave a Reply

Your email address will not be published. Required fields are marked *


Clickcha - The One-Click Captcha