-
1推荐
有序列表和集合插入操作的耗时差距
有个需求，需要插入不重复的数，忽略重复的数。下面插入10000个数。 1.用集合 import bisect as bi import time as tm set_a=set() sortlst_a=[] def ins_set(n): for i in range(…...
-
python对象的内存占用
集合竟然是列表的4倍 import sys as sys a = [x for x in range(1000)] print (sys.getsizeof(a)) 4516 a = [x for x in range(1000000)] print (sys.getsiz…...
-
欧拉计划696:麻将
字数太多,上图 ![Mahjong][1] 麻将的游戏是玩s种花色的牌.每张牌也有一个在范围1..n内的数字，对于每个花色/数字组合，正好有四张相同花色和数字的牌。（真正的麻将游戏也包含其他奖赏牌，但这些在此问题中不考虑。） 糊牌的一手是3t+2张牌（其中t是固定整数），它…...
-
欧拉计划547:带洞正方形内任意点间距离
译文来自 http://pe-cn.github.io/547/ 在长方形中（均匀地）随机选择两个点，可以算出两点间距离的期望值。 例如，在单位正方形中任意两点间距离的期望约为0.521405，而在宽为2长为3的长方形中任意两点间距离的期望约为1.317067。 从边长为…...
-
欧拉计划695：随机长方形
单位正方形内3个点，P1P2P3,作为对角的顶点，形成P1P2 P2P3 P1P3 3个长方形，求面积第二大的矩形面积的平均值。 ![enter image description here][1] 没找到数学公式,先用程序模拟一下 from random import r…...
评论了
利用三角数的性质判定,减少一次查找,但速度更慢 def test(n): a=n*8+1 if int(math.sqrt(a))**2==a: return 1 else: return 0 def f6(n): t=[i*(i+1)//2 for i in range(1+int(math.sqrt(n*8+1)/2-1/2))] le=len(t) c=0 for i in range(le): for j in range(i,le): if t[i]+t[j]+t[j]>n:break tj,tk=t[j],n-t[i]-t[j] if test(tk)==1: if i ==j: if tj==tk: c+=1 else: c+=3 else: if tj==tk: c+=3 else: c+=6 return c
N乘以（N+1）除以2的商是N三角数。 一个奇平方数减1是除以8是一个三角数。 [(2K+1)^2-1]/8=T （T三角数）。 通项公式 {[（2K+1）2^n]^2-(2^N)^2)}/8(2^n)^2=T 三角数乘以9加上1仍是三角数。 三角数二倍平方根取整是这个三角数的序数。 三角数的位数和只有1，3，6，9四种。 位数和是1的三角数，它的序数位数和只有1，4，7三种。 序数位数和是1的三角数减1除以9仍是三角数，它的序数位数和是全面的。 序数位数和是4三角数减1除以9，仍是位数和1的三角数。 序数位数和是7的三角数，减1除以9，位数和是3，6，9的三角数。 位数和是3的三角数,序数位数和只有2与6二种。 序数位数和是2的三角数，加上6 除以9，减去序数除以9的满入数（上取整，下同），仍是位数和3，6，9的三角数。 序数位数和是6的三角数，减去3除以9，加上序数除以9的满入数，仍是位数和3，6，9的三角数。 位数和是6的三角数，序数位数和只有3与5二种。 序数位数和是3的三角数，减去6除以9，加上序数除以9的满入数，仍是位数和1的三角数。 序数位数和是5的三角数，加上3除以9，减去序数除以9的满入数，仍是位数和1的三角数。
https://baike.baidu.com/item/%E8%B4%B9%E9%A9%AC%E5%A4%9A%E8%BE%B9%E5%BD%A2%E6%95%B0%E5%AE%9A%E7%90%86/9459912 费马多边形数定理是一个定律，定义为每一个正整数都可以表示为最多n个n边形数的和。也就是说，每一个正整数一定可以表示为不超过三个的三角形数之和、不超过四个的平方数之和、不超过五个的五边形数之和，依此类推。
去重复的版本,节省1半时间 def f3(n): t=[i*(i+1)//2 for i in range(1+int(math.sqrt(n*8+1)/2-1/2))] le=len(t) c=0 for i in range(le): for j in range(i,le): if t[i]+t[j]>=n:break lft=bisect.bisect_left(t,n-t[i]-t[j],j ) if lft>=0 and bisect.bisect_right(t,n-t[i]-t[j] )==lft+1: if i ==j: if j==lft: c+=1 else: c+=3 else: if j==lft: c+=3 else: c+=6 return c >>> t=time.time();f3(1000000);print(time.time()-t) 2106 2.3600032329559326
不使用推导式的更快的版本,二分查找 import bisect def f2(n): t=[i*(i+1)//2 for i in range(1+int(math.sqrt(n*8+1)/2-1/2))] le=len(t) c=0 for i in range(le): for j in range(le): #print(i,j,t[i],t[j]) if t[i]+t[j]>n:break lft=bisect.bisect_left(t,n-t[i]-t[j] ) if lft>=0 and bisect.bisect_right(t,n-t[i]-t[j] )==lft+1: c+=1 #if n-t[i]-t[j] in t:c+=1 return c >>> t=time.time();f1(100000);print(time.time()-t) 834 2.2152040004730225 >>> t=time.time();f2(100000);print(time.time()-t) 834 0.45240068435668945 >>> t=time.time();f2(1000000);print(time.time()-t) 2106 4.617608070373535