【python】之哥德巴赫猜想（递归法）和教室排课（枚举法）
14天阅读挑战赛 努力是为了不平庸~ 算法学习有些时候是枯燥的，这一次，让我们先人一步，趣学算法！欢迎记录下你的那些努力时刻（算法学习知识点/算法题解/遇到的算法bug/等等），在分享的同时加深对于算法的理解，同时吸收他人的奇思妙想，一起见证技术er的成长~
目录
算法知识点
递归
程序调用自身的编程技巧称为递归。它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解，递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算，大大地减少了程序的代码量。
枚举
将所有可能的情况一一列举出来筛选出满足条件的。得到的结果肯定是正确的，但是可能做了很多的无用功，浪费了宝贵的时间，所以需要人脑先排除一些不必要的情况，减少时间复杂度
算法题目来源
算法题目描述
哥德巴赫猜想
众所周知，哥德巴赫猜想被称作数字王冠上的明珠--每个不小于6的偶数都是两个奇素数之和，你被要求编写一个程序来验证1000以内的情况。
题目描述
输入格式
一个大于6小于1000的偶数n
输出格式
一行，为一个表达式，形式为a+b,a和b分别是两个奇素数，其中a小于b，使得a+b=n(如果有多组解，输出a最小的一组)
输入例子
10
输出例子
10=3+7
做题思路
题意要把一个大于6小于1000的偶数分为两个奇素数，所以要建个判断素数（素数又叫质数。素数，指的是“大于1的整数中，只能被1和这个数本身整除的数”）的函数，在创建一个验证猜想的函数，因为是要把一个大于6小于1000的偶数分为两个奇素数，所以传三个值过去，a要小于那个大于6小于1000的偶数，b要大于0，在用判断素数函数来判断a，b是否为素数，如果是则输出那个小于那个大于6小于1000的偶数等于a加b表达式如果素数条件不满足则用递归，将a加2，b加2，因为a和b的起始值为奇数那么加上一个偶数还是奇数，2是最小的偶数，接着执行验证猜想函数直到找到为止。
代码实现
def zhishu(num):
q = True
if num==1:
q = False
for i in range(2, num):
if num % i == 0:
q= False
return q
def guess(a,b,num):
if a<num and b>0:
if zhishu(a) == True and zhishu(b) == True:
print('%d=%d+%d' % (num,a,b))
else:
return guess(a+2,b-2,num)
num = int(input())
a = 1
b=num-1
guess(a,b,num)执行结果
教室排课
题目描述
信息学院有四个专业A、B、C、D，各专业入学新生人数分别是Na, Nb, Nc，Nd人。新学期开始有一门公共课，按专业划分成四个教学班，四个班在某个相同的时间段上课。已知该时间段还剩余8间教室可用，编号从1到8，每个教室能容纳的人数分别为120，40，85，50，100，140，70，100。 试编一个程序，为上述四个教学班分配教室。找出所有可行的分配方案，对于每个方案依次输出为专业A、B、C、D分配的教室编号，输出所有方案。 输入格式 一行，包含4个整数Na, Nb, Nc，Nd (20≤Na, Nb, Nc，Nd≤120)，每2个整数之间用一个空格隔开。
输出格式 如果存在分配方案，输出若干行，每行表示一种教室分配方案，包含4个整数，依次表示A、B、C、D四个专业分配的教室编号。 如果不存在分配方案，输出-1。 样例输入： 109 87 120 81 样例输出： 1 5 6 3 1 5 6 8 1 8 6 3 1 8 6 5 6 5 1 3 6 5 1 8 6 8 1 3 6 8 1 5
样例输入：
100 101 102 103 样例输出：
-1
解题思路
写一个列表用来装120，40，85，50，100，140，70，100。再定义一个flag来判断是否存在分派方案，如果不存在分配方案，输出-1。下面就用for语句和if语句嵌套，如果与前面重复或者房间比上课人数少，那么用continue跳出本次循环，执行到第四次循环就是满足条件的排序，有满足排序条件的把flag赋值为1，输出的时候要注意我们是用列表装的房间，下标是从0开始的，而房间号是从1开始的所以所有输出的索引要加1才是房间号，最后判断flag是否为-1，如果为-1也就是没有排序方案，则输出-1。
代码实现
js=[120,40,85,50,100,140,70,100]
flag=-1
Na, Nb, Nc ,Nd= map(int, input('Na, Nb, Nc ,Nd:').split())
for i in range(len(js)):
if Na>js[i]:
continue
for j in range(len(js)):
if(j==i or Nb>js[j]):
continue
for k in range(len(js)):
if(k==i or k==j or Nc>js[k]):
continue
for p in range(len(js)):
if(p==i or p==j or p==k or Nd>js[p]):
continue
print(i + 1,j+1,k+1,p+1)
flag=1
if flag==-1:
print(flag)运行结果
有方案的运行结果：
没方案的运行结果：
相关算法题型题目总结
如果遇到一些被处理的对象之间是有规律的递增或递减，将子问题和原问题为同样的事，且更为简单，那么就可以考虑用递归。
读书笔记
递归主体内容有两类： 一、是有边界，即终止条件。 二、是需要调用自己。 如果使用循环能解决问题，尽量不要使用递归算法，因为在使用递归算法的时候会加大资源的消耗 如果递归算法的深度过于深，可能会造成栈溢出。
腾讯云开发者
