python练习

Python,算法 2016-04-15

其实有很多这样的活动都有一个相同的模式:N 种人物卡片,每次买一包干脆面随机得到一张。当你集齐这 N 种人物时,就会有相应的奖励。 那时候还不懂怎么计算概率,白白给人家送了好多钱,吃了好多干脆面。 现在的任务是,给你一个正整数 N (1 <= N <= 10^4),请你帮我从期望的角度计算平均需要买多少包干脆面才能集齐这 N 种人物。 提醒:由于结果可能不是整数,所以结果只保留到小数点后两位。

概率DP 假设手中现在有x张卡片,那么再买一包得到新卡片的概率为

\frac {N-x}{N}

则期望步数为

\frac {N}{N-x}
def solve(n):
    r = 0.0
    for i in range(0, n):
        r += (1.0 * n) / (n - i)
    return r
print '%.2f' % solve(N)

银行在打印票据的时候,常常需要将阿拉伯数字表示的人民币金额转换为大写表示,现在请你来完成这样一个程序。 在中文大写方式中,0到10以及100、1000、10000被依次表示为: 零壹贰叁肆伍陆柒捌玖拾佰仟万 以下的例子示范了阿拉伯数字到人民币大写的转换规则: 1 壹圆 11 壹拾壹圆 111 壹佰壹拾壹圆 101 壹佰零壹圆 -1000 负壹仟圆 1234567 壹佰贰拾叁万肆仟伍佰陆拾柒圆 现在给你一个整数a(|a|<100000000), 打印出人民币大写表示. 注意:请以Unicode的形式输出答案。你可以通过decode("utf8")来将utf8格式的字符串解码为Unicode,例如你要输出ans = "零圆", print ans.decode("utf8"). Note:数据已于2013-11-19日加强,原来通过的代码可能不能再次通过。

#coding = 'utf-8'
def f(a):
    W = ['万','拾','佰','仟']
    L = ['零','壹','贰','叁','肆','伍','陆','柒','捌','玖']
    flag = ''
    if a < 0:
        flag = '负'
        a = -a
    i = 0
    ans = '圆'
    nonzero = False
    if a == 0:
        ans += L[0]
    while a > 0:
        if a % 10 == 0:
            if nonzero:
                nonzero = False
                ans += L[0]
        else:
            if i > 0:
                ans += W[i % 4]
            ans += L[a % 10]
            nonzero = True

        i += 1
        a /= 10
    return flag.decode('utf8') + ans.decode('utf8')[::-1]
print f(a)

给你一个字符串a和一个正整数n,判断a中是否存在长度为n的回文子串。如果存在,则输出YES,否则输出NO。 回文串的定义:记串str逆序之后的字符串是str1,若str=str1,则称str是回文串,如"abcba".

def manacher(s, n):
r = '#'
for c in s:
r += c + '#'
p = 0
mx = 0
a = [1]
for i in range(1, len(r) - 1):
a.append(0)
if mx > i:
a[i] = min(a[2 * p - i], mx - i)
else:
a[i] = 1
while (i >= a[i]) and (i + a[i] < len(r)) and (r[i - a[i]] == r[i + a[i]]):
a[i] += 1
if a[i] - (i & 1) >= n:
return True
if i + a[i] > mx:
p = i
mx = i + a[i]
return False
if manacher(a, n):
print 'YES'
else:
print 'NO'

本文由 mcginn 创作,采用 知识共享署名 3.0,可自由转载、引用,但需署名作者且注明文章出处。

如果对您有用,您的支持将鼓励我继续创作!