Python （NUDT&&educoder特别关心版）

· · 学习·文化课

Python （NUDT&&educoder特别关心版）

主题：浅谈程序设计与算法基础

（一份融合Io Wiki与educoder实训作业的整理笔记报告）

报告人：4p11b彭轩昂(这个不重要)

欢迎食用

总述与回顾（Overview and Review）

学习Python的优势

Python 的优点

For us :

模拟

本块将简要介绍模拟算法。

简介

模拟就是用计算机来模拟题目中要求的操作。

模拟题目通常具有码量大、操作多、思路繁复的特点。由于它码量大，经常会出现难以查错的情况，如果在考试中写错是相当浪费时间的。

技巧

写模拟题时，遵循以下的建议有可能会提升做题速度：

from myCoding import *
N = 8             #位数为8
########## Begin ##########
def ZhenToFu(z):
    if(z[0]=='0' or z[0]=='1'): z='+'+z
    ans1,idx,ok1,ok2='',0,0,0
    for i in range (len(z)):
        if(z[i]!='+' and z[i]!='-' ):
            if z[i]=='1' and ok1==0:    ok1=1 
            if z[i]=='.' and ok1==0:    ok1=-1
            if z[i]=='1' and ok1==-1:    ok2=1
            if z[i]=='.' and ok1==1:    ok2=1
            if z[i]!='.' and (ok1==1 or ok2==1):   ans1+=z[i] ## 确定尾数
            if z[i]!='.' and ok1!=0 and ok2!=1:   idx+=ok1 ## 确定阶码
    jz=2 if idx>0 else 3
    jz2='+' if idx>0 else '-'
    ans=YuanToBu(ZhenToDing_int(jz2+bin(idx)[jz:]))+' '
    ans+=YuanToBu(ZhenToDing_point(z[0]+'0.'+ans1)) ## 合并
    return ans

########## End ##########
z = input()            #真实值
f = ZhenToFu(z)        #转换成浮点数
print('%s -> %s' % (z, f))

例题2 冯·诺依曼体系结构模拟 (一个浪费寿命的题目)

　　本关任务是将前面关卡的功能结合起来，模拟一个程序在 CPU 中的完整执行过程。

编程要求

　　仔细阅读右侧编辑器给出的代码框架及注释，在指定的 Begin-End 区间编写程序，将使用 TOY 计算机指令集编写的.toy文件，根据给定的主存地址address加载到主存mem指定区域（连续存放），并控制 CPU 执行.toy文件中的程序代码，得到执行结果。 　　你需要补充完整 5 个函数：

  1. 函数loadProgram(file, mem, address)实现程序加载功能：从主存mem的address地址开始存放file文件，无返回值。
  2. 函数fetch(mem, pReg)实现取指令功能：根据程序计数器给出的地址取出主存对应的指令放入指令寄存器，程序计数器自增 1，函数返回pReg和iReg的值。
  3. 函数decode(iReg)实现指令译码功能：解析指令寄存器中的指令，不存在的操作数置为None，函数返回操作码opcode,和 2 个操作数op1,op2。
  4. 函数execute(opcode, op1, op2, reg, mem, address)实现执行和写结果功能：根据指令解析的操作码执行对应的操作，若为停机指令返回False，其余指令返回 True。特别说明： 1）执行跳转指令jmp和jz时，需要考虑程序中代码的逻辑地址（.toy 文件中指令前面的编号）和放入主存后的物理地址的不一致之处，两个地址间存在固定的偏移量差值（address）； 2）指令mov1和mov2读写的是主存中存放的数据（不是指令），这里直接使用指令中给出的物理地址实现读写访问。
  5. 函数run(file, addr)实现完整过程模拟功能：程序加载、取指令、指令译码、指令执行和写结果，无返回值。注意，在执行程序前，需要将第一条指令代码在主存中的地址（即addr）放入程序计数器pReg中，为第一次取指令做好准备。 
    #add.toy
000 mov3 1 12
001 mov3 2 13
002 add  1 2
003 out  1
004 halt

    开始你的任务吧，祝你成功！

    模拟 CPU 执行完整程序代码的全部过程

    初始化主存、通用寄存器、指令寄存器和程序计数器

mem = ['']*1000 #主存

reg = [0]*10 #通用寄存器

pReg = 0 #程序计数器

iReg = '' #指令寄存器

def loadProgram(file,  mem, address):
    txt = open(file,'r')
    line = txt.read()
    line = line.replace('\n',' \n ')
    line = line.split(' ')
    f=False
    for i in range(len(line)):
        if (line[i]!='' and line[i]!='\n'):
            if mem[address] == '' and 1-f: f=True
            elif f and mem[address] == '': mem[address] = line[i]
            elif f: mem[address] = mem[address] + ' ' + line[i]
        elif (line[i]=='\n'): address+=1;f=False
    txt.close()

def decode(iReg):
    tmp=iReg.split(' ')
    if (len(tmp)==1):    ans=(tmp[0],None,None)
    if (len(tmp)==2):    ans=(tmp[0],int(tmp[1]),None)
    if (len(tmp)==3):    ans=(tmp[0],int(tmp[1]),int(tmp[2]))
    return ans

def execute(opcode, op1, op2, reg, mem, address):
    global pReg
    if opcode=='mov1': reg[op1] = mem[op2]
    elif opcode=='mov2': mem[op1] = reg[op2]
    elif opcode=='mov3': reg[op1] = op2
    elif opcode=='add': reg[op1] = reg[op1]+reg[op2]
    elif opcode=='sub': reg[op1] = reg[op1]-reg[op2]
    elif opcode=='mul': reg[op1] = reg[op1]*reg[op2]
    elif opcode=='div': reg[op1] = reg[op1]//reg[op2]
    elif opcode=='jmp': pReg = op1
    elif opcode=='jz' and reg[op1]==0: pReg = op2
    elif opcode=='in': reg[op1] = int(input())
    elif opcode=='out': print(reg[op1])
    elif opcode=='halt': return False
    return True

def run(file, addr):
    global pReg, iReg
    loadProgram(file,mem,addr)
    iReg=mem[addr];pReg=+1
    opcode,op1,op2=decode(iReg)
    while execute(opcode,op1,op2, reg, mem, addr):
        # print(opcode,op1,op2,reg)
        iReg=mem[pReg+addr];pReg+=1
        opcode,op1,op2=decode(iReg)

# run('a1.txt', 20)

file = input()
address = int(input())
run(file, address)

枚举

本块将简要介绍枚举算法。

简介

要点

1.给出解空间
2.减少枚举的空间
3.选择合适的枚举顺序

根据题目判断。比如例题中要求的是最大的符合条件的素数，那自然是从大到小枚举比较合适。

例题3 哥德巴赫猜想

背景

　　1742 年，哥德巴赫在给欧拉的信中提出了一个猜想：任一大于 2 的整数都可写成三个素数之和，希望欧拉能给出证明。实际上，哥德巴赫猜想的证明难度远远超过了人们的想象，从欧拉到 200 多年后的今天一直未被破解，成为了世界三大数学猜想中剩下的唯一一个未被解决的问题。 　　但是，在哥德巴赫猜想的证明过程中，涌现出一系列杰出的数学家，比如我国著名数学家陈景润，同时也催生了许多先进的数学理论与方法，推动了数学领域的发展，这其实也是哥德巴赫猜想的重要意义。

任务

　　哥德巴赫猜想现在普遍采用的表述是：任一大于 2 的偶数都可写成两个素数之和。本关任务就是试着验证一下这个说法。 　　具体来说，本关任务是实现Goldbach函数，该函数的功能是将一个大于 2 的偶数 N 分解为满足以下条件的 N1 和 N2： 　　1）N1 和 N2 都是素数，即除了 1 和本身外再没有其他约数的数，规定 1 不是素数； 　　2）N1+N2=N； 　　3）N1 要尽可能小。 　　此外，你可以利用本关程序尝试不同的 N，如果某个 N 不能按要求分解成 N1 和 N2，那你就解决了困扰人们 200 多年的哥德巴赫猜想，但是，目前还没人发现这样的 N。 　　 在每个测试集中，系统会给定一个大于 2 的偶数 N（用变量N表示）， 例如，测试集 1 的输入是：

10

程序的功能是将其分解为两个素数之和，例如，测试集 1 的运行结果为：

10 = 3 + 7

开始你的任务吧，祝你成功！


########## Begin ##########
Prime = []

def initPrime(n):
    for i in range(2,n):
        if num[i]:
            Prime.append(i)
            for j in range(i+i,n,i):
                num[j] = False

def Goldbach(N):
    initPrime(N)
    for i in Prime:
        if(num[N-i]):
            return (i,N-i)

# def Goldbach(N):
#     for i in range(int(N/2)):
#         if Prime(i) and Prime(N-i):
#             return (i,N-i)

########## End ##########
N=int(input(''))
num = [True for i in range(N)]
N1,N2 = Goldbach(N)
print('%d = %d + %d' % (N, N1, N2))

例题4 打印素数表

  • 打印 1 - n内的素数表

方案 1

def prime(n):## 根据素数定义模拟素数判断过程
    # flag = True ## 事先不知道是否为素数，那就假定不是
    for i in range(2,n):
        if n%i==0:## 可以枚举从小到大的每个数看是否能整除
            # flag = False  ## 这就说明不是素数
            # break  ## 时间优化点，省略后续判断
            return False  ## 代码优化点，不需要用变量Flag
    # return Flag
    return True

n=10000
primes=[]
for i in range(2,n+1):
    if (prime(i)):## 枚举每一个整数，判断是否为素数
        primes.append(i)
# primes = [i for i in range(2, n + 1) if prime(n)] ## 代码优化点，利用列表推导式
print(primes)

这样做是十分稳妥了，但是真的有必要每个数都去判断吗？

很容易发现这样一个事实：如果 x 是 a 的约数，那么\frac{a} {x}也是 a的约数。

这个结论告诉我们，对于每一对 (x, \frac{a} {x} )，只需要检验其中的一个就好了。为了方便起见，我们之考察每一对里面小的那个数。不难发现，所有这些较小数就是 [1, \sqrt{a}] 这个区间里的数

由于 1 肯定是约数，所以不检验它。

偶数肯定是约数，设步长为 2 。

方案 2


def prime(n):## 根据素数定义模拟素数判断过程
    for i in range(2,int(n**0.5)+1,2):  ## 时间优化点 + 1
        if n%i==0:  return False
    return True

n=100000
primes = [i for i in range(2, n + 1) if prime(i)] ## 代码优化点，利用列表推导式
print(primes)

难道就到此为止了？？？（显然是）

一个思路：

举个例子，比如我们要筛选出100以内的所有素数，我们知道2是最小的素数，我们先用2可以筛掉所有的偶数。

然后往后遍历到3，3是被2筛剩下的第一个数，也是素数，我们再用3去筛除所有能被3整除的数。

筛完之后我们继续往后遍历，第一个遇到的数是7，所以7也是素数，我们再重复以上的过程，直到遍历结束为止。

结束的时候，我们就获得了100以内的所有素数。

(这就是埃拉托斯特尼算法，即eratosthenes发明的用来筛选素数的方法，为了方便我们一般简称为埃式筛法或者筛法)

方案 3

def eratosthenes(n):
    for i in range(2, n+1):
        if is_prime[i]:
            primes.append(i) ## 用当前素数i去筛掉所有能被它整除的数
            for j in range(i * 2, n+1, i):
                is_prime[j] = False ## 素数的倍数标记为False 

n=1000000
primes = []
is_prime = [True] * (n + 1)
eratosthenes(n)
print(primes)

当然我们还可以进一步优化，达到极致优化效果，有兴趣可以进一步了解

不过利用filter和functools提供的reduce可以极大优化代码复杂度，使这个优秀的算法只需一行完成

方案 4

from functools import reduce
n = 1000001 ## 一行版
primes = reduce(lambda r, x: list(filter(lambda a: a % x != 0 or a == x, r)) if x in r else r, range(2, int(n**0.5) + 1), list(range(2, n+1)))
print(primes)

递归 & 分治

本块将介绍递归与分治算法的区别与结合运用。

递归

定义

递归（英语：Recursion），在数学和计算机科学中是指在函数的定义中使用函数自身的方法，在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。

引入

要理解递归，就得先理解什么是递归。

以下是一些有助于理解递归的例子：

什么是递归？

递归代码最重要的两个特征：结束条件和自我调用。自我调用是在解决子问题，而结束条件定义了最简子问题的答案（边界条件）。


def fac(n):
  if n==1: return 1
  return n*fac(n-1)

def fac(n): return 1 if n==1 else n*fac(n-1) ## 一行版
## 求阶乘
print(fac(10)) 

def mycos(x,n=30): 
  if n==0: return 0
  return mycos(x,n-1)+(-1)**n*x**(2*n)/fac(2*n)

def mycos(x,n=30): return 1 if n==0 else mycos(x,n-1)+(-1)**n*x**(2*n)/fac(2*n) ## 一行版
##  用泰勒级数求余弦值
print(mycos(3.1415926535/3))

def gcd (m,n):
  if n==0: return m
  return gcd(n,m%n)

def gcd (m,n): return m if n==0 else gcd(n,m%n) ## 一行版
## 辗转相除法求最大公约数
print(gcd(36,24))

# 总结：
# def func(传入数值):
#   if 终止条件: return 最小子问题解
#   return func(缩小规模)

为什么要写递归

练习分析问题的结构。当发现问题可以被分解成相同结构的小问题时，递归写多了就能敏锐发现这个特点，进而高效解决问题。

递归的缺点

在程序执行中，递归是利用堆栈来实现的。每当进入一个函数调用，栈就会增加一层栈帧，每次函数返回，栈就会减少一层栈帧。而栈不是无限大的，当递归层数过多时，就会造成 栈溢出 的后果。

递归的优化

搜索优化 和 记忆化搜索

比较初级的递归实现可能递归次数太多，容易超时。这时需要对递归进行优化。

例题 三个数的最大公约数、快乐数

例5 快乐数

编写一个算法来判断一个数 n 是不是快乐数。 快乐数定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。
  • 如果 n 是快乐数就返回 True ；不是，则返回 False 。

H={}

def isHappy(n):
    print('%d\n%d'%(n,n),end='->')
    if n==1: return True
    if n in H: return H[n] ## 记忆化，如果记录过这种情况，直接返回
    tmp,m= n,0
    while tmp>0:  
        m+=(tmp%10)**2
        tmp=tmp//10 ## 解决问题
    H[n]=False ## 标记状态
    H[n]=isHappy(m) ## 缩小规模并更新
    return H[n]

# n = int(input())
n=20

def solve(n):
    print()
    if isHappy(n):   return n
    return solve(n+1)

print('%d 后的第一个开心数是 %d' % (n, solve(n)));

分治

定义

分治（英语：Divide and Conquer），字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

过程

分治算法的核心思想就是「分而治之」。

大概的流程可以分为三步：分解 -> 解决 -> 合并。

分解原问题为结构相同的子问题。 分解到某个容易求解的边界之后，进行递归求解。 将子问题的解合并成原问题的解。 分治法能解决的问题一般有如下特征：

该问题的规模缩小到一定的程度就可以容易地解决。 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 注意 如果各子问题是不独立的，则分治法要重复地解公共的子问题，也就做了许多不必要的工作。此时虽然也可用分治法，但一般用 动态规划 较好。

要点

写递归的要点 明白一个函数的作用并相信它能完成这个任务，千万不要跳进这个函数里面企图探究更多细节， 否则就会陷入无穷的细节无法自拔，人脑能压几个栈啊。

区别

递归与枚举的区别

递归和枚举的区别在于：枚举是横向地把问题划分，然后依次求解子问题；而递归是把问题逐级分解，是纵向的拆分。

递归与分治的区别

递归是一种编程技巧，一种解决问题的思维方式；分治算法很大程度上是基于递归的，解决更具体问题的算法思想。

例 6 13队查人

13队有4个p，总共13个b，求总人数

  • 思路 1 分治
  • 把所有人分成2个部分查人后汇总
  • 把部分再分成2个部分查人后汇总
  • 分到不可分为止
  • 思路 2 递归
  • 各b查人
  • 我们b有x人，那么总人数为我们b人数加上剩余班人数
  • 如果没有其它b了，总人数就是我们b人数
People=[0,12,11,11,12,11,11,12,12,13,12,12,12,7]

def check_people1(l,r): ## 分治查人法
    if l==r: return People[l]
    total=0
    total+=check_people1(l,(l+r)//2)
    total+=check_people1((l+r)//2+1,r) ##分成两部分
    return total ## 汇总

def check_people2(n): ## 递归查人法
    if n==1: return People[n]
    return People[n]+check_people2(n-1) ## 我们b加剩余b人数

print(check_people1(1,13))
print(check_people2(13))

Part 3 题外话（Let's have fun）