python常用算法

【题目】下面的代码用来计算小于100的最大素数，注意break语句和else子句的用法。

for n in range(100,1,-1):

    for i in range(2,n):

        if n%i == 0:
            break

    else:

        print(n)

        break    

 【题目】使用列表推导式生成100以内的所有素数

一个数若可以进行因数分解，那么分解时得到的两个数一定是一个小于等于sqrt(n)，一个大于等于sqrt(n)，据此，上述代码中并不需要遍历到n-1，遍历到sqrt(n)即可。

>>> [p for p in range(2, 100) if 0 not in [p%d for d in range(2, int(p**0.5)+1)]]
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

for i in range(100, 1000):
    #这里是序列解包的用法
    bai, shi, ge = map(int, str(i))
    if ge**3 + shi**3 + bai**3 == i:
        print(i)

for ji in range(0, 31):
    if 2*ji + (30-ji)*4 == 90:
        print('ji:', ji, ' tu:', 30-ji)

#另一种计算方法
>>> def demo(tui, jitu):
       tu = (tui - jitu*2)/2
       if int(tu)==tu:
              return (int(tu), int(jitu-tu))
       else:
              return 'Data Error'

【题目】编写程序，输出由1、2、3、4这四个数字组成的每位数都不相同的所有三位数。

digits = (1, 2, 3, 4)
for i in digits:
    for j in digits:
        for k in digits:
            if i!=j and j!=k and i!=k:
                print(i*100+j*10+k)

【优化后】

digits = (1, 2, 3, 4)
for i in digits:
    for j in digits:
        if j==i:
            continue
        for k in digits:
            if k==i or k==j:
                continue
            print(i*100+j*10+k)

 【题目】编写程序，计算组合数C(n,i)，即从n个元素中任选i个，有多少种选法。

根据组合数定义，需要计算3个数的阶乘，在很多编程语言中都很难直接使用整型变量表示大数的阶乘结果，虽然Python并不存在这个问题，但是计算大数的阶乘仍需要相当多的时间。本例提供另一种计算方法：以Cni(8,3)为例，按定义式展开为Cni(8,3)=8!/3!/(8-3)!=(8*7*6*5*4*3*2*1) /(3*2*1)/ (5*4*3*2*1)，对于(5,8]区间的数，分子上出现一次而分母上没出现；(3,5]区间的数在分子、分母上各出现一次；[1,3]区间的数分子上出现一次而分母上出现两次。

def Cni1(n,i):
    if not (isinstance(n,int) and isinstance(i,int) and n>=i):
        print('n and i must be integers and n must be larger than or equal to i.')
        return
    result = 1
    Min, Max = sorted((i,n-i))
    for i in range(n,0,-1):
        if i>Max:
            result *= i
        elif i<=Min:
            result /= i
    return result

#也可以使用math库中的阶乘函数直接按组合数定义实现。

>>> def Cni2(n, i):
	import math
	return int(math.factorial(n)/math.factorial(i)/math.factorial(n-i))
>>> Cni2(6,2)
15

#还可以直接使用Python标准库itertools提供的函数。

>>> import itertools
>>> len(tuple(itertools.combinations(range(60),2)))
1770

#itertools还提供了排列函数permutations()。

>>> import itertools
>>> for item in itertools.permutations(range(1,4),2):
	print(item)

def main(n):
    for i in range(n):
        print((' * '*i).center(n*3))
    for i in range(n, 0, -1):
        print((' * '*i).center(n*3))

def int2base(n, base):
    '''把十进制整数n转换成base进制'''
    result = []
    div = n
    #除基取余，逆序排列
    while div != 0:
        div, mod = divmod(div, base)
        result.append(mod)
    result.reverse()    
    result = ''.join(map(str, result))
    #变成数字，返回
    return eval(result)