1.定义:枚举法也称为穷举法,是利用计算机运算速度快、精确度高的特点,对要解决问题的所有可能情况,一个不漏地进行检验,从中找出符合要求的答案,因此枚举法是通过牺牲时间来换取答案的全面性。因此,使用枚举法解决问题时,需要考虑优化算法,选择恰当的枚举对象,尽量分析出问题中的隐含条件,缩小枚举范围,以提高解决问题的效率。
2.一般结构:循环(穷举范围)+判断(检验条件)。
例题1:请输出所有的两位偶数。
分析:
穷举范围:两位数范围是10-99。利用range(10,100)可生成10-99的列表
判断条件:偶数满足除以二的余数为0。i%2==0 此条件满足则i为偶数
代码如下:
for i in range(10,100):
if i%2==0:
print(i)
例题2:输入一个数,判断该数是否为质数
分析:
穷举范围:n为素数,需要满足n%2!=0,n%3!=0 ... n%n-1!=0,n的除数范围应该为2-n-1。
判断条件:n%i==0 则代表i是n的因数,n不是素数,当穷尽所有的i,该条件都不满足,则n为素数
代码如下:
n=int(input())
for i in range(2,n-1):
if n%i==0:
break
else:
print(n,是素数)
例题3:请输出所有的两位质数
分析:
穷举范围:两位数范围是10-99。利用range(10,100)可生成10-99的列表
判断条件:判断每一个n是否为素数,利用例题2中相关代码
代码如下:
for n in range(10,100):
for i in range(2,n-1):
if n%i==0:
break
else:
print(n,"是素数")
另一种做法:
t=0
for n in range(10,100):
for i in range(2,int(2,int(n**0.5)+1)):
if n%i==0:
t=1
break
if t==1:
print(n."不是素数")
else:
print(n,“是素数”)
例题4:这个问题,是我国古代著名趣题之一。 大约在1500年前,《孙子算经》中就记载了这个有趣的问题。 书中是这样叙述的:“今有雉兔同笼,上有三十五头,下有九十四足, 问雉兔各几何?这四句话的意思是: 有若干只鸡兔同在一个笼子里,从上面数,有35个头 ;从下面数,有94只脚。求笼中各有几只鸡和兔?
分析:
穷举范围:兔的只数范围为1~34,对应的鸡的只数为35-tu
判断条件:根据每组可能解判断兔的只数*4+鸡的只数*2==94是否成立,如果成立,则代表这组可能解成立
代码如下:
for tu in range(1,35):
ji=35-tu
if tu*4+ji*2==94:
print(“兔的只数为”,tu,“鸡的只数为”,ji)
例题5:一个三位数如果满足该数本身=百位上的数字**3+十位数字**3+个位上的数字**3,则该数被称为三位自幂数,也叫作水仙花数。请输出所有的水仙花数。
穷举范围:三位数的范围是100-999。利用range(100,1000)可以生成该列表。
判断条件:该数本身=百位上的数字**3+十位数字**3+个位上的数字**3
代码如下:
for i in range(100,1000):
bai=i//100
shi=i//10%10
ge=i%10
if bai**3+shi**3+ge**3==i:
print(i,“是水仙花数”)
例题6:公鸡5元一只,母鸡3元一只,小鸡3只一元, 用100元买一百只鸡。其中公鸡,母鸡,小鸡都必须要有。问公鸡,母鸡,小鸡要买多少只刚好凑足100元
穷举范围:公鸡只数范围是1~20,母鸡只数1~33,小鸡只数1~100
判断条件:公鸡只数+母鸡只数+小鸡只数==100 且 公鸡的钱数+母鸡的钱数+小鸡的钱数==100
代码如下:
for cock_num in range(1,21): #公鸡只数可能为1-20
for hen_num in range(1,34): #母鸡只数可能为1-33
for chick_num in range(1,101): #(3小鸡)只数可能为1-100
money1=cock_num*cock_price+hen_num*hen_price+chick_num*threechick_price
num1=cock_num+hen_num+chick_num*3
if money1==100 and num1==100:
print (cock_num,hen_num,chick_num*3) #(③小鸡数)
例题7:输入两个数,求出这两个数的最大公约数
穷举范围:最大公约数可能是1-两个数中较小的那个
判断条件:这两个数除以最大公约数的余数都为0
代码如下:
m=int(input())
n=int(input())
for i in range(min(m,n),0,-1):
if m%i==0 and n%i==0:
print(m,"和",n,"的最大公约数是",i)
例题8:孪生素数(质数对)
所谓孪生素数指的是间隔为2的两个相邻素数,因为它们之间的距离已经近得不能再近了,如同孪生兄弟一样,故将这一对素数称为孪生素数。显然,最小的一对孪生素数是(1,3)。我们可以写出3~100以内的孪生素数,一共有8对,分别是(3,5),(5,7),(11,13),(17,19),(29,31),(41,43)(59,61)和(71,73)。随着数字的增大,孪生素数的分布也越来越稀疏,人工寻找孪生素数变得非常困难。关于孪生素数还存在着一个著名的猜想——孪生素数猜想,即孪生素数是否有无穷多对,这是数论中还有待解决的一个重要问题。此处我们只讨论在有限范围内的孪生素数求解问题。
问题:编程求出3~1000以内的所有孪生素数。
分析:
在判断孪生素数之前首先需要判断这个数字是否为素数,如果连素数都不是的话也就没有必要再继续去判断了。函数定义如下:
def isprime(n):
for i in range(2,n-1):
if n%i==0:
return False
else:
return True
穷举范围:第一个数的范围是2—998,另一个数的范围则是4—1000
判断条件:第一个数和另一个数调用isprime()函数的返回值均为True
def isprime(n):
for i in range(2,n-1):
if n%i==0:
return False
else:
return True
#主程序
for i in range(2,999):
if isprime(i) and isprime(i+2):
print(i,"和",i+2,"是孪生素数")
例题9:完全数(Perfect number),又称完美数或完备数,是一些特殊的自然数。它所有的真因子(即除了自身以外的约数)的和(即因子函数),恰好等于它本身。
如果一个数恰好等于它的因子之和,则称该数为“完全数”。第一个完全数是6,第二个完全数是28,第三个完全数是496,后面的完全数还有8128、33550336等等。
编程1:输入一个数,判断这个数是否是完数。
分析:
利用for循环找到该数的所有因子,求出因子之和。若因子和与该数相等则该数为完数。
n=int(input())
s=0
for i in range(2,n):
if n%i==0:
s=s+i
if s==n:
print(n,"是完数")
编程2:输出1-1000以内所有的完数
分析:
利用编程1自定义一个可以判断该数是否为完数的函数
穷举范围:1-1000文章来源:https://www.toymoban.com/news/detail-574307.html
判断条件:该数为完数,则输出文章来源地址https://www.toymoban.com/news/detail-574307.html
def ws(n):
s=1
for i in range(2,n):
if n%i==0:
s=s+i
if s==n:
return True
#主程序
for i in range(1,1001):
if ws(i):
print(i)
到了这里,关于python算法一:枚举法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!