2011山大免试研究生机试题 - webdancer's Blog

2011山大免试研究生机试题

webdancer posted @ 2011年9月26日 16:31 in 算法 with tags 算法 , 1598 阅读

----------------以下仅提供了解体的思路,代码未完善,上机时有些题可以直接算出来的------------------------------

1.求两个正整数的最大公约数.

def gcd(a,b):
    while b:
        a,b=b,a%b
    return a

2.令S=s1s2s3...s2n是一个符合规范的括号字符串。可以采用两种方式对S编码:
(1)一个整数序列P=p1p2...pn,其中pi是字符串S中第i个右括号前左括号的个数(记为P序列);
(2)一个整数序列W=w1w2...wn,其中wi是字符串S中第i个右括号往左数遇到和它相匹配的左括号时经过的左括号个数(记为W序列).
要求:对于一个符合规范的括号字符串,将其P序列转化为W序列.

def translate( a ):
    #stack
    s=[]
    b=[]
    for i in range(len(a)):
        if i==0:
            for j in range(a[i]):
                s.append('(')
                b.append(1)
            s.append(')')
            b.append(1)
        else:
            for j in range(a[i]-a[i-1]):
                s.append('(')
                b.append(1)
            s.append(')')
            b.append(1)
    c=[]
    for m,v in enumerate(s):
        count=0
        if v==')':
            for n in range(m-1,-1,-1):
                if s[n]=='(':
                    count+=1
                if s[n]=='(' and b[n]==1:
                    b[n]=0
                    break;
            c.append(count)

    for e in c:
        print e ,
    print '\n-----------'

3.有n个半圆形金属条c1,c2,c3...cn,半圆直径分别为l1,l2,l3...ln.(如图)问可否将这些金属环首尾相接形成一个大环.
要求:输入3组直径数据(组内数据之间已用逗号隔开,每组数据间已用分号隔开),判断这3组金属条各自是否可以首尾相接.针对每组数据,如果可以,输出Y,否则输出N.

def isconnect(a):
    m=max(a)
    s=0
    first=True
    for e in a:
        if e!=m:
            s+=e
        if e==m and first:
            first=False
        elif e==m and not first:
            s+=e
    if m>s:
        return False
    else:
        return True

4.设有一个由0和1组成的字符串b1b2……bn(bi为0或1).由该字符串可以生成一个旋转矩阵B如下:
b1     b2 …  bN−1  bN (第一行为原字符串,以下n-1行均由其前一行的串循环左移一位构成)
b2     b3 …  bN      b1  

bN−1 bN …  bN−3  bN−2
bN     b1 …  bN−2  bN−1
矩阵B的每一行可视为一个二进制数.对这n个二进制数由小到大排序形成矩阵C.
比如有一个二进制串00110,生成的旋转矩阵为
00110
01100
11000
10001
00011
对其排序得
00011(第一行的00011<第二行的00110<第三行的01100<......)
00110
01100
10001
11000
现在设有一个二进制串r经以上变换及排序后生成矩阵C1.
要求:输入一个二进制串,如果将其视为C1的最后一列,推测并输出C1的第一行数据.
例:输入10010       程序需要输出00011

def bwt(s):
    assert '\0' not in s, "s CAN NOT contains ('\0')"
    s+='\0'
    table=sorted(s[i:]+s[:i] for i in range(len(s)))
    r=[row[-1] for row in table]
    return ''.join(r)

def ibwt(r):
    table=['']*len(r)
    for i in range(len(r)):
        table=sorted(r[i]+table[i] for i in range(len(r)))
    s=[row for row in table if row.endswith('\0')][0]
    return s.rstrip('\0')

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee