Python常规算法

Python常规算法

完全数

如果一个数恰好等于它的因子之和，则称该数为“完全数” 。例如：第一个完全数是6，它有约数1、2、3、6，除去它本身6外，其余3个数相加，1+2+3=6。第二个完全数是28，它有约数1、2、4、7、14、28，除去它本身28外，其余5个数相加，1+2+4+7+14=28。

求出1000以内所有的完全数:

for i in range(1,1000):
	s=0
    for k in range(1,i):
        if i%k==0:
            s+=k
    if i==s:
        print i

亲密数

对于两个不同的整数A和B，如果整数A的全部因子（包括1，不包括A本身）之和等于B；且整数B的全部因子（包括1，不包括B本身）之和等于A，则将A和B称为亲密数

求3000内的亲密数有哪些

#求出循环中的因数集
def judge(z):
    for a in range(1,z):
        b=yshuhe(a)
        if a==yshuhe(a) and a<b:
            print("%d和%d是亲密数"%(a,b))
#求出一个数的因数集
def yshuhe(n):
    sum=0
    for i in range(1,n):
        if(n%i==0):
            sum+=i
    return sum
judge(3000)

平分七筐鱼

甲、乙、丙三位鱼夫出海打鱼，他们随船带了21只箩筐。当晚返航时，他们发现有七筐装满了鱼，还有七筐装了半筐鱼，另外七筐则是空的，由于他们没有秤，只好通过目测认为七个满筐鱼的重量是相等的，7个半筐鱼的重量是相等的。在不将鱼倒出来的前提下，怎样将鱼和筐平分为三份？

resultlist=[]
for i in range(7):
    for j in range(7-i):
        z=7-i-j
        if(i+j/2==3.5):
            print(i,j,z)
            resultlist.append([i,j,z])
print(resultlist)
#将各种情况展示出来
for i in resultlist:
    for j in resultlist:
        for z in resultlist:
            if i[0]+j[0]+z[0]==7 & i[1]+j[1]+z[1]==7 & i[2]+j[2]+z[2]==7:
                print([i,j,z])

井深与绳子长度

五家人共用一口井，甲家的绳子用两条不够，还要用乙家的绳子一条才能打到井水；乙家的绳子用三条不够，还要用丙家的绳子一条才能打到井水；丙家的绳子用四条不够，还要再用丁家的绳子一条才能打到井水；丁家的绳子用五条不够，还需要再用戊家的绳子一条才能打到井水；戊家的绳子六条不够，还要再用甲家的绳子一条才能打到井水。

最后问：井有多深？每家的绳子各有多长？

def fun():
	e=0
	while True:
        e+=4
        a=0
        while True:
            a+=5
            d=e+a/5
            c=d+e/4
            if c%2 != 0 or d%3 != 0:
                continue
            b = c + d/3
            if b+c/2 <a:
                break
            if b+c/2 ==a:
                deep = 2*a+b
                print('a-->%d,b-->%d,c-->%d,d-->%d,e-->%d,deep-->%d'%(a,b,c,d,e,deep))
                return a,b,c,d,e,deep
fun()

答案解析：

设甲乙丙丁戊家绳子的长度分别为a,b,c,d,e。井深为deep

则有：

2a+b=deep;

3b+c=deep;

4c+d=deep;

5d+e=deep;

6e+a=deep;

则进行处理得到：

a=b+c/2;

b=c+d/3;

c=d+e/4;

d=e+a/5;

因为绳子是整条的，所以推出c是2的倍数、d是3的倍数、e是4的倍数、a是5的倍数。这里假设e和a是已知的去推出其它数。

等差素数数列

素数等差数列是等差数列的一种。在等差数列中，任何相邻两项的差相等。该差值称为公差。类似“7、37、67、97、127、157”这样完全由素数组成的等差数列叫做素数等差数列。除去1以外，有的数除了1和它本身以外，不能再被别的整数整除，如2、3、5、7、11、13、17、…等，这种数称作素数(也称质数)。

求100以内的等差素数数列

n=int(input('请输入查找范围：'))
def primeNumber(n):
    pt=[True]*n
    s=[]
    for p in range(2,n):
        if not pt[p]:
            continue
        s.append(p)
        for i in range(p*p,n,p):
            pt[i]=False
    return pt,s
pt,s=primeNumber(n)

for i in range(len(s)):
    for j in range(i+1,len(s)):
        a0,a1=s[i],s[j]
        an=a1+a1-a0	#公差相等，前后项相加，等于中间项的两倍
        k=[]
        while an < n and pt[an]: #判断an项是否为素数，如果是则添加到k，打印出来
            k.append(an)
            an += a1-a0
        if k:
            print([a0,a1]+k)

贪心算法

贪心算法的基本思路是从问题的某一个人初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化地条件。若下一个数据和部分最优价连在一起不再是可行解时，就不该把数据添加到部分解中，知道把所有数据枚举完，或者不能再添加算法停止。

题目：已知一些孩子和一些糖果，每个孩子有需求因子g，每个糖果有大小s，当某个糖果的大小s>某个孩子的需求因子g时，代表该糖果可以满足该孩子，求使用这些糖果，最多能满足多少孩子（注意，某个孩子最多只能用1个糖果满足）

class Solution:
    def findContentChild(self,g,s):
        g = sorted(g)
        s = sorted(s)
        child = 0
        cookie = 0
        while child < len(g) and cookie < len(s):
            if g[child] <= s[cokkie]:
                child +=1
            cookie+=1
        return child
if __name__=="__main__":
    g = [5,10,2,9,15,9]
    s = [6,1,20,3,8]
    S = Solution()
    result = S. findContentChild(g,s)
    print(result)

答案解析：

(1)对需求因子数组g和糖果大小数组s进行从小到大的排序
(2)按照从小到大的顺序使用各糖果尝试是否可满足某个孩子，每个糖果只尝试1次，只有尝试成功时，换下一个孩子尝试，直到发现没更多的孩子或者没有更多的糖果，循环结束。

汉诺塔

有三个立柱A、B、C。A柱上穿有大小不等的圆盘N个，较大的圆盘在下，较小的圆盘在上。要求把A柱上的圆盘全部移到C柱上，保持大盘在下、小盘在上的规律（可借助B柱）。每次移动只能把一个柱子最上面的圆盘移到另一个柱子的最上面。请输出移动过程。

def move(a,b,c,n):#a原柱子，b目的柱子，c辅助柱子，n个盘子
    if(n==1):#递归出口，当只剩一个盘子时，我们不需要再递归了，只需要将这个盘子移到目的柱子上
        b.append(a.pop())
    move(a,c,b,n-1)#先移动n-1个到c上，只留最下面最大的那个
    b.append(a.pop())#把a最大的盘子移动到b
    move(c,b,a,n-1)#这时把c中所有的盘在移到b目的柱子上去
x=['x',3,2,1]
y=['y']
z=['z']
move(x,y,z,3)
print(x,y,z)

自守数

自守数是指一个数的平方的尾数等于该数自身的自然数。例如：5x5=25 6x6=36 25x25=625 76x76=5776

for n in range(1,1000):
    k=len(str(n))#求数的长度
    t=(n*n)%(10**k)#计算数的后几位
    if t==n:
        print(n)

金蝉素数

这些数字是由1，3，5，7，9这5个奇数排列组成的5位素数，且同时去掉它的最高位与最低位数字后的3位数还是素数，同时去掉它的高二位与低二位数字后的三位数还是素数。因此，人们把这些神秘的素数成为金蝉素数，喻意金蝉脱壳之后仍然为美丽的金蝉。

from itertools import permutations
from functools import reduce
import math
#判断一个数是否是素数
def isprime(n):
    for i in range(2,int(math.sqrt(n))+1):
        if n%i==0:
            return False
        return True
def showprime():
    for p in permutations([1,3,5,7,9]):#可以得到13579的所有排列情况
        for i in(p[1:-1],p[::2],p):		#p即原数去掉最高位和最低位数字后的3位，原数去掉高二位与低二位数字后的三位数和原数所组成的元组
            prime = reduce(lambda x,y:x*10+y,i)
            if not isprime(prime):
                break:
        else:
            if(p[2]==9):
                continue
            print("%d是金蝉素数"%prime)
showprime()

可逆素数

可逆素数是将一个素数的各个位置的数字顺序倒置过来构成的反序数仍是素数。

import math
def isPrimeNum(n):
    for k in range(2,int(math.sqrt(n)+1)):
        if n%k==0:
            return False
    return True
for i in res:
    if not p[int(str(i)[::-1])]:
        continue
    else:
        print("%d是可逆素数")

埃及分数式

分子是1的分数叫做单位分数。古代埃及人在进行分数运算时，只使用分子是1的分数，因此这种分数也叫做埃及分数。要求输入一个分数，将该分数分解为埃及分数，例如，输入3/7，将分解为1/3+1/11+1/231

import math
a=int(input('分子：'))
b=int(input('分母：'))
f=a/b
s='%d/%d='%(a,b)
while f>le-8:#科学计数法，即1乘10的-8次方
    c=math.ceil(round(1/f,8))
    s+='1/%d+'%(c)
    f=f-1/c
s=s[:-1]
print(s)

正整数分解质因数

将一个正整数分解质因数。例如：输入90，打印出90=2 * 3 * 3 * 5

value=int(input("请输入一个值"))
print("%s="%value,end="")
def fun(n):
    for i in range(2,n):
        if n%i==0:
            print("%s*"%i,end="*")
            return(fun(n//i))
        print("{}".format(i))
fun(5767)

试探算法

试探算法也叫回溯法，试探算法的处事方式比较委婉，他先暂时放弃关于问题规模大小的限制，并将问题的候选解按照某种顺序逐一枚举和检验。当发现当前候选解一定不是正确的解时，就选择下一个候选解。如果当前候选解除不满足问题规模要求外，其余都满足，则扩大当前候选解的范围，并继续试探。如果当前候选解满足包括问题规模在内的所有要求时，该候选解就是问题的一个解。

题目：给定一个迷宫，入口已知。问是否有路径从入口到出口，若有·，则输出一条这样的路径。
**注意：**移动可以从上、下、左、右、上左、上右、下左、下右八个方向。输入0表示可以走，输入1表示墙。

maze = [[1,1,1,1,1,1,1,1,1,1],
    [0,0,1,0,1,1,1,1,0,1],
    [1,1,0,1,0,1,1,0,1,1],
    [1,0,1,1,1,0,0,1,1,1],
    [1,1,1,0,0,1,1,0,1,1],
    [1,1,0,1,1,1,1,1,0,1],
    [1,0,1,0,0,1,1,1,1,0],
    [1,1,1,1,1,0,1,1,1,1]]
m, n = 8, 10  # 8行，10列
entry = (1,0) # 迷宫入口
path = [entry] # 一个解（路径）
paths = []   # 一组解
# 移动的方向
directions = [(0,1),(1,1),(1,-1),(0,-1),(-1,0),(-1,1),(-1,-1)]
# 冲突检测
def conflict(nx, ny):
    global m,n,maze
  # 是否在迷宫中，以及是否可通行
    if 0 <= nx < m and 0 <= ny < n and maze[nx][ny]==0:
        return False
    return True
# 套用子集树模板
def walk(x, y): # 初始入口
    global entry,m,n,maze,path,paths,directions
    if (x,y) != entry and (x,y)==(7,5): # 出口
        paths.append(path[:]) # 直接保存，未做最优化
    else:
        for d in directions: # 遍历8个方向(亦即8个状态)
            nx, ny = x+d[0], y+d[1]
            path.append((nx,ny))   # 保存，新坐标入栈
            print(path)
            if not conflict(nx, ny): # 剪枝
                maze[nx][ny] = 2     # 标记，已访问（奇怪，此两句只能放在if区块内！）
                walk(nx, ny)
                maze[nx][ny] = 0     # 回溯，恢复
            path.pop()        # 回溯，出栈
# 解的可视化（根据一个解x，复原迷宫路径，'2'表示通路）
def show(path):
    global maze
    import pprint, copy
    maze2 = copy.deepcopy(maze)
    for p in path:
        maze2[p[0]][p[1]] = 2 # 通路
        pprint.pprint(maze2) # 带通路的迷宫
        print()
# 测试
walk(1,0)
print(path)
print(paths)

凯撒密码

凯撒密码是古罗马凯撒大帝用来对军事情报进行加解密的算法，它采用了替换方法对信息中的每一个英文字符循环替换为字母表序列中该字符后面的第三个字符，即，字母表的对应关系如下：
原文：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
密文：D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
对于原文字符P，其密文字符C满足如下条件：C=(P+3) mod 26
上述是凯撒密码的加密方法，解密方法反之，即：P=(C-3) mod 26

import string
letters=[]
key=12
miwens=[]
jiewens=[]
jiewen=''
miwen=''
value=input("请输入加密前的明文:")
value=value.upper()
for i in string.ascii_uppercase:
    letters.append(i)
print(len(letters))    
for i in value:
    if i in letters:
        num=letters.index(i)
        if num+key>=len(letters):
            num=num+key-len(letters)
            miwen=letters[num]
        else:
            miwen=letters[num+key]
        miwens.append(miwen)
print("加密后为：%s"%str(miwens))
for j in miwens:
    if j in letters:
        num=letters.index(j)
        if num-key<0:
            num=num+(len(letters)-key)
            jiewen=letters[num]
            jiewen = jiewen.lower()
        else:
            jiewen=letters[num-key]
            jiewen = jiewen.lower()
        jiewens.append(jiewen)
print("密文%s 解密后为：%s"%(str(miwens),str(jiewens)))