1.问题描述 求100以内的所有勾股数。 所谓勾股数,是指能够构成直角三角形三条边的三个正整数(a,b,c)。 2.问题分析 根据“勾股数”定义,所求三角形三边应满足条件a 2 +b 2 =c 2 。可以在所求范 围内利用穷举法找出满足条件的数。 3.算法分析 采用穷举法求解时最容易想到的一种方法是利用三个循环语句分别控制变量 a、b、c的取值范围,第一层控制变量a,取值范围是1~100;在a值确定的情况 下再确定b值,即第二层控制变量b,为了避免结果有重复现象,b的取值范围是 (a+1)~100;a、b的值已确定,利用穷举法在(b+1)~100范围内一个一个地去比 较,看当前c值是否满足条件a 2 +b 2 =c 2 ,若满足,则输出当前a、b、c的值,否 则继续寻找。主要代码如下:
…
for a in range(1,101): # 确定a的取值
for b in range(a+1, 101): # 确定b的取值
for c in range(b+1, 101): # 确定c的取值
if a*a + b*b == c*c: # 判断三个变量是否满足勾股数条件
print("%4d %4d %4d\t |" %(a, b, c), end="")
…
但是上述算法的效率比较低,根据a 2 +b 2 =c 2 这一条件,在a、b值确定的情 况下没必要再利用循环一个一个去寻找c值。若a、b、c是一组勾股数,则a 2 +b 2 的平方根一定等于c,c的平方应该等于a、b的平方和,故可将a 2 +b 2 的平方根赋 给c,再判断c的平方是否等于a 2 +b 2 。根据“勾股数”定义将变量定义为整型,a 2 +b 2 的平方根不一定为整数,但变量c的类型为整型,将一个实数赋给一个整型 变量时可将实数强制转换为整型(舍弃小数点之后的部分),然后再赋值,这种 情况下得到的c的平方与原来的a 2 +b 2 的值肯定不相等。故可利用这一条件进行 判断。 4.完整的程序
#!/usr/bin/python3
# -*- coding: utf-8 -*-
# @author : liuhefei
# @Time : 2019/6/12 0:37
# @desc: 勾股数 a**2+b**2=c**2
import math
if __name__ == "__main__":
count = 0
print("100以内的勾股数有:")
# a、b、c分别表示三角形的三条边
# 满足勾股数的三个数组成的三角形一定是直角三角形
print(" a\tb\t c \t\t a \t b \t c \t\t a \t b\t c \t\t a\t b\t c");
# 求100以内的勾股数
for a in range(1,101):
for b in range(a+1, 101): # 邻边不能相等,否则就是等边三角形了
c = int(math.sqrt(a*a + b*b)) # 求c值,并转换为整型
# 判断c的平方是否等于a*a + b*b,且两边之和大于第三边
if c*c == (a*a + b*b) and (a + b > c) and (a + c > b) and (b + c > a) and c = 3 and a % 2 == 1:
n = (a - 1) // 2
b = 2 * n**2 + 2*n
c = 2 * n**2 + 2*n + 1
print("%d %d %d\n" %(a,b,c))
else:
# 输入的a为偶数,则a = 2n,b=n**2-1,c=n**2+1
if a >= 3 and a % 2 == 0:
n = a // 2
b = n**2 - 1
c = n**2 + 1
print("%d %d %d\n" % (a, b, c))
else:
print("error")
|