1 # -*- coding: utf-8 -*-
   2 # 有这样一道题目：100匹马，100担货物，大马一次可以拉3担货物，中马一次可以拉2担货物，小马2匹才能拉1担货物。
   3 import time
   4 start = time.time()
   5 # 方法一:
   6 for x in range(1,100):
   7         for y in range(1,100):
   8                 for z in range(1,100):
   9                         if x+y+z==100 and x*3+y*2+z*0.5==100:
  10                                 print x ,y ,z
  11 print time.time()-start
  12 start = time.time()
  13 # 方法一需要执行100万次循环.
  14 # 方法二:根据马总数为100,那么第三层循环其实可以舍去.
  15 for x in range(1,100):
  16         for y in range(1,100):
  17                 if x*3+y*2+(100-x-y)*0.5 == 100:
  18                         print x,y,100-x-y
  19 print time.time()-start
  20 start = time.time()
  21 # 方法二需要执行1万次循环
  22 # 方法三:在二的基础上,再对上下界进行优化
  23 # 大马最多只能有33匹,所以最外层循环可以只到上界33；中马类推
  24 for x in xrange(100/3+1):
  25         for y in range( 51):        #(100-x*3)/2+1 ):
  26                 if x*3+y*2+(100-x-y)*0.5 == 100:
  27                         print x,y,100-x-y
  28 print time.time()-start
  29 start = time.time()
  30 # 方法三需要执行33*50=1650次循环
  31 # 方法四:我们回头看这个问题,根据上述的那个公式,发现这其实是个二元一次方法而已.那么,理论上,只需要用一个循环来解决问题.
  32 # x*6 + y*4 + 100 - x - y = 200
  33 # x*5 + y*3 = 100
  34 # y = (100-x*5)/3        # 此处还发现x上界可进一步优化到100-x*5>0
  35 for x in xrange(100/5+1):
  36         y = (100-x*5)/3
  37         if x*3+y*2+(100-x-y)*0.5 == 100:
  38                 print x,y,100-x-y
  39 print time.time()-start
  40 start = time.time()
  41 # OK,方法四只执行了21次循环.比起方法一的100万次循环,你觉得如何?

   1 # 方法五:
   2 # 好吧,我承认,最BT的来了,这个循环只运行7次,每次都找出一个解.
   3 # 从方法四中我们看出来,x必须满足条件使100-x*5能被3整除,第一个x是2,以后x步进3,直到21.
   4 for x in xrange(2,100/5+1,3):
   5         print x,(100-x*5)/3,100-x-(100-x*5)/3