问答题 3.  一个有序数列,序列中的每一个值都能够被2或者3或者5所整除,1是这个序列的第一个元素。求第1500个值是多少。
【正确答案】方法一:蛮力法
   最简单的方法就是用一个计数器来记录满足条件的整数的个数,然后从1开始遍历整数,如果当前遍历的数能被2或者3或者5整除,那么计数器的值加1,当计数器的值为1500时,当前遍历到的值就是所要求的值。根据这个思路实现代码如下:
   def searth(n):
   i=0
   count=0
   i=1
   while True:
   if i%2==0 or i%3==0 or i%5==0:
   count+=1
   if count==n:
   break
   i+=1
   return i
   
   if __name__=="__main__":
   print searth(1500)
   程序的运行结果为:
   2045
   方法二:数字规律法
   首先可以很容易得到2,3和5的最小公倍数为30,此外,1~30这个区间内满足条件的数有22个{2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20, 21, 22, 24, 25, 26, 27,28, 30},由于最小公倍数为30,我们可以猜想,满足条件的数字是否具有周期性(周期为30)昵?通过计算可以发现,31~60这个区间内满足条件的数也恰好有22个{32, 33, 34,35, 36, 38, 39, 40, 42, 44, 45, 46, 48, 50, 51, 52, 54, 55, 56, 57, 58, 60},从而发现这些满足条件的数具有周期性(周期为30)。由于1500/22=68,1500%68=4,从而可以得出第1500个数经过了68个周期,然后在第69个周期中取第四个满足条件的数{2, 3, 4,5}。从而可以得出第1500个数为68*30+5=2045。根据这个思路实现代码如下:
   def searth(n):
   a=[0,2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30]
   ret=(n/22)*30+a[n%22]
   return ret
   算法性能分析:
   方法二的时间复杂度为O(1),此外,方法二使用了22个额外的存储空间。方法二的计算方法可以用来分析方法一的执行效率,从方法二的实现代码可以得出,方法一中循环执行的次数为(N/22)*30+a[N%22],其中a[N%22]的取值范围为2~30,因此方法一的时间复杂度为O(N)。
【答案解析】[考点] 如何求有序数列的第1500个数的值