Q:
A Pythagorean triplet is a set of three natural numbers, a < b < c, for which,
a2 + b2 = c2
For example, 32 + 42 = 9 + 16 = 25 = 52.
There exists exactly one Pythagorean triplet for which a + b + c = 1000.
Find the product abc.
A:
#! /usr/bin/env python
#coding=utf-8
import math
import time
''' method 1
a,b,c 的范围。abc之间必然存在a<b<c这样类似的关系,假设大小按照这样
显然a<333 & 333<b<500。a+b>c(三角形),所以c < 500
'''
t1 = time.time()
l = []
s = 0
for i in range(334,500):
l.append(i ** 2)
for a in range(1,333):
for b in range(a,500):
s = a ** 2 + b ** 2
if s in l:
c = math.sqrt(s)
if (a + b + c) == 1000:
print "a*b*c = %d*%d*%d = %d" %(a,b,c,a*b*c)
break
t2 = time.time()
print "time used %s" %str(t2-t1)
''' method 2
逻辑有一点难理解,把c^2 - b^2 的值作为key,这个值的开方作为value
(b,b^2) = (c,c^2)
c++
这样key的值如果存在的话,就是满足a^2+b^2=C^2
再判断是否是符合a+b+c=1000
faster than method 1
'''
def squares():
i = 1
while i < 1000:
yield (i,i**2)
i += 1
prev = []
seen = {}
found = False
for (i,isq) in squares():
for (j, jsq) in prev:
k = seen.get(isq-jsq)
if not k: continue
if i + j + k == 1000:
print "a*b*c = %d*%d*%d = %d" %(j,k,i,j*k*i)
found = True
break
if found:break
prev.append((i,isq))
seen[isq] = i
t3 = time.time()
print "time used: %s" %(t3-t2)
分享到:
相关推荐
•Find the lowest, across all departments, of the per-department max- imum salary computed by the preceding query. Answer: •SQL query: select name from student natural join takes natural join course ...
解决 Can not find the main class. Program will exit. 难题
07_driver.page_source.find示例.py07_driver.page_source.find示例.py07_driver.page_source.find示例.py07_driver.page_source.find示例.py07_driver.page_source.find示例.py07_driver.page_source.find示例.py07...
08_driver.find查找元素示例.py08_driver.find查找元素示例.py08_driver.find查找元素示例.py08_driver.find查找元素示例.py08_driver.find查找元素示例.py08_driver.find查找元素示例.py08_driver.find查找元素示例...
Find the shortest path from 0 to 15 for the following graph. A multistage graph is a graph (1) G=(V,E) with V partitioned into K >= 2 disjoint subsets such that if (a,b) is in E, then a is in Vi , ...
Eclipse 编译时遇到错误could not find the main class,program will exit的解决方法
By bringing together crucial information that was previously scattered or difficult to find, Perkins has created an incredible resource that enables professionals to leverage RTP's benefits in a wide ...
slow to download, and difficult to maintain, but like the badly taught driver who insists on flouting the rules because it。ッs worked for him so far, many developers find those outdated habits ...
用richTextBox1.Find实现查找功能,C#源代码 用VisualStudio2008创建 http://download.csdn.net/user/gouyue
Find all employees in the database who live in the same cities and on the same streets as do their managers. d. Find all employees who earn more than the average salary of all employees of their ...
The target audience is developers somewhat familiar with Perl and the Unix-based Web server environment, but you'll find the book illustrative even if your knowledge is sketchy. After showing how to...
5.7.4 Find the Data Structures that Consume Memory . . . 57 6 Solving Performance Problems . . . . . . . . . . 63 6.1 Finding Performance Bugs – A Step-by-Step Approach . . . . . 63 6.1.1 Do an ...
The average person consumes approximately 30 gigabytes of data every single day, but has no idea how to interpret it correctly. EVERYDATA explains, through the eyes of an expert economist and ...
find_java.zip find_java.zip find_java.zip find_java.zip
错误提示:Abc.java:9: variable i might not have been initialized System.out.println(i); 中文说明:变量i可能没有赋值就使用了。 例子说明: int i; System.out.println(i); 2.变量重复定义 错误提示:Abc....
Leveraging visual tools, The Startup Equation leads you step by step through the decisions you need to make to find your perfect startup model. You'll learn things such as identifying your unique ...
find the the set point in which triangle in the mesh
This will find the peaks in spectrum
有的时候在开发jsp时,需要使用jstl时,在jsp上面引用jstl却出现错误:Can not find the tag library descriptor for "http://java.sun.com/jsp/jstl/core,这是由于缺少两个jar包导致的。
- cvc-complex-type.2.4.c: The matching wildcard is strict, but no declaration can be found for element 'dubbo:application'. - schema_reference.4: Failed to read schema document '...