QQ登录

只需一步,快速开始

搜索
查看: 372|回复: 8

[活动专区] 小练习:20170807 squarefree的二项式系数

[复制链接]
最佳答案
465 
累计签到:683 天
连续签到:1 天
发表于 2017-8-6 22:34:27 | 显示全部楼层 |阅读模式

马上注册加入鱼C,享用更多服务吧^_^

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 冬雪雪冬 于 2017-8-15 07:45 编辑

从现在开始我们要开展一批欧拉计划的习题练习。
其实在我们论坛中已有欧拉计划的板块,可能有些鱼油还没注意到。
什么是欧拉计划:http://bbs.fishc.com/thread-60405-1-1.html
我们欧拉板块现已给出了200余题,这批练习将从欧拉计划中选题。其实用python语言完成有很多的优势,可以更简洁更方便的实现。
如果大家有兴趣也可浏览欧拉的英文网站:https://projecteuler.net/archives
这里已经有了500余题。


                               
登录/注册后可看大图


题目要求:
以python语言完成,如果是python2请注明。
程序以代码文字格式发帖。
注重程序效率和创意。
答题在一周内完成,即8.14 10:00之前,其后将公开大家的答案,并评比成绩。

另程序和答案可以在网上搜到,希望大家独立完成。题目不难,大家看看谁的效率高。

----回帖需写明解题思路,鼓励在程序中加上注释


一些鱼油反映题目有些过难,为此略过一部分偏难的题目。



题目:

二项式系数 nCk 可以排成帕斯卡三角的形式,如下图:


                               
登录/注册后可看大图


可知,前 8 行中,总共有 12 个不同的数字 1, 2, 3, 4, 5, 6, 7, 10, 15, 20, 21 和 35。对于正整数 n,如果没有任何一个质数的平方可以整除 n,则 n 被叫做 squarefree 。
那么。帕斯卡三角的前 8 行得到的那 12 个不同的数字中,除了 4 和 20,其余都是 squarefree 的。所有 squarefree 数之和是 105。

请给出帕斯卡三角前 51 行中不同的 squarefree 数之和。

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
50 
累计签到:327 天
连续签到:5 天
发表于 2017-8-7 11:36:19 | 显示全部楼层
这题计算逻辑应该挺简单的,完整按照题目要求写程序就行了,暴力解法速度也挺快。
C(n,k)有2种算法,一种是用阶乘n!//k!//(n-k)!,另一种就是利用杨辉三角形,上一行的2项之和,递归算法。
  1. import time
  2. st=time.time()

  3. from math import factorial as f
  4. def C(n,k):
  5.         return f(n)//f(k)//f(n-k)

  6. # from functools import lru_cache
  7. # @lru_cache(maxsize=None)
  8. # def C(n,k):
  9. #         if k==0 or k==n: return 1
  10. #         return C(n-1,k-1)+C(n-1,k)

  11. def gen_prime_sqr(n):
  12.         primes = [True]*n
  13.         primes[:2] = [False]*2
  14.         for i, prime in enumerate(primes):
  15.                 if prime:
  16.                         for j in range(i*i, n, i):
  17.                                 primes[j] = False
  18.         return [k*k for k, trueprime in enumerate(primes) if trueprime]

  19. prime_sqr = gen_prime_sqr(int(C(50,25)**0.25)+1)

  20. def is_sqrfree(n, prime_sqr=prime_sqr):
  21.         for p in prime_sqr:
  22.                 if n % p == 0:
  23.                         return False
  24.         return True

  25. sqrfreelist = set()
  26. for n in range(0, 51):
  27.         for k in range(0, (n+1)//2+1):
  28.                 if is_sqrfree(C(n,k)):
  29.                         sqrfreelist.add(C(n,k))
  30. print(sum(sqrfreelist))
  31. print(time.time()-st)
复制代码


34029210557338
0.015608787536621094
[Finished in 0.1s]

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
5 
累计签到:37 天
连续签到:1 天
发表于 2017-8-7 11:49:07 | 显示全部楼层
思路见注释。。。
  1. # 得到三角图里的所有的数(去重)
  2. def test1(n):
  3.     a = [1,1]  # 第二列
  4.     result = [1]  # 前两列都只有1
  5.     for i in range(3,n+1):  # 从第三列开始计算
  6.         b = []
  7.         for j in range(len(a)-1):
  8.             b.append(a[j]+a[j+1])  # 每个数字跟后面的数字相加
  9.         result += b
  10.         a = [1]+b+[1]  # 在新列两边各加1
  11.     return list(sorted(set(result)))
  12.    
  13. # 质数清单
  14. def zhishu(n):  #  求的小于n的所有质数
  15.     a = [True]*(n+1)
  16.     a[0],a[1]=False,False
  17.     for index in range(2, len(a)):
  18.         if a[index]==True:
  19.             for i in range(index+index,len(a),index):
  20.                 a[i]=False
  21.     return [i for i, j in enumerate(a) if j==True]
  22.    
  23. # 结果
  24. def test2(n):
  25.     a = test1(n)  # 得到三角图里数字
  26.     b = []  # 非squarefree数字
  27.     m = int(max(a)**0.25)+1  # 能否为质数的平方整除,所以只需得到最大数的开4次方的质数序列
  28.     z = [i**2 for i in zhishu(m)]
  29.     for i in a:
  30.         for j in z:
  31.             if i%j==0:
  32.                 b.append(i)
  33.                 break
  34.     return sum(set(a)-set(b))
  35.             
复制代码

time test2(51)
Wall time: 15.6 ms
Out[16]: 34029210557338

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:47 天
连续签到:1 天
发表于 2017-8-7 21:27:35 | 显示全部楼层
本帖最后由 plus 于 2017-8-8 12:44 编辑

求杨辉三角的代码是百度找的,就凑个热闹
看看结果对不
input a number:51
34029210557338
import time

def YangHui (num):  #先要找到这个列表,来源百度杨辉三角
    LL = [[1]]
    for i in range(1,num):
        LL.append([(0 if j== 0 else LL[i-1][j-1])+ (0 if j ==len(LL[i-1]) else LL[i-1][j]) for j in range(i+1)])
    return LL

primes = [2,3]
nextp = 5

def is_prime(nextp, primes):
    for x in primes:
        if x > nextp**0.5:
            return True
        if nextp % x == 0:
            return False

num = 51 #int(input('input a number:')) #输入层数

tt=time.time()

m = {1}
for i in YangHui(num):m = m|set(i)
psk = list(m)
list.sort(psk) #生成对应层数杨辉三角并处理列表psk为三角中不重复的数字

while primes[-1] <= psk[-1]**0.25+1:
    if is_prime(nextp, primes):
        primes.append(nextp)
    nextp += 2

square=[]
for i in psk:
    for j in primes:
        if i % j**2==0:
            square.append(i)
            break

squarefree=list(set(psk)-set(square))

sum1 = 0
for i in squarefree:sum1 += i

print(sum1)
print(time.time()-tt)

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
2 
累计签到:4 天
连续签到:1 天
发表于 2017-8-7 21:41:32 From FishC Mobile | 显示全部楼层
自己都感觉过程复杂  
num=51
a=[[1,1]]
for i in range(1,num-1):
    a.insert(i,[1])
   
    for j in range(i):
        
        a[i].append((a[i-1][j]+a[i-1][j+1]))
        
    a[i].append(1)
#print(a)
dd=[]
for i in range(num-1):
    for each in a[i]:
        if each not in dd:
            dd.append(each)
#print (dd)
#print(max(dd))
def zhishu_list(number):
    a = [True]*(number+1)
    a[0], a[1] = False, False
    for i in range(2,len(a)):
        if a[i] == True:
            for j in range(i*i,len(a),i):
                a[j]=False
    b = [i for i,j in enumerate(a) if j==True]
    return b
ss=int(max(dd)**0.5)

zhi=zhishu_list(ss)
#print(zhi)
zhi1=[]
for i in zhi:
    zhi1.append(i*i)
#print(zhi1)
total=0
for i in dd:
    for j in zhi1:
        if j>i :
            break
        else:
            if i%j ==0:
                print(i)
                total+=1
                break
print(total)
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
2 
累计签到:275 天
连续签到:1 天
发表于 2017-8-10 20:25:44 | 显示全部楼层
  1. import math
  2. import time
  3. def denum(num):
  4.     rawnum=num
  5.     dlist=[]
  6.     for i in range(2,int(math.sqrt(num))+1):
  7.         if not num%i:
  8.             while not num%i:
  9.                 num//=i
  10.                 dlist.append(i)
  11.         if num==1:
  12.             return dlist
  13.     if rawnum!=num:
  14.         dlist.append(num)
  15.         return dlist
  16.     else :
  17.         return [rawnum]
  18. dnum={}
  19. squarefree_nums=[1,2,3,5,6,7,10,15,21,35]
  20. binomials=[[[3,7],[],21],[[5,7],[],35]]
  21. n=7
  22. while n<51:
  23.     dlist=denum(n+1)
  24.     if  n&1:
  25.         temp=[]
  26.         temp.append(binomials[-1][0][:])
  27.         temp.append(binomials[-1][1][:])
  28.         temp.append(binomials[-1][2])
  29.     for i in range(len(binomials)):
  30.         for j in dlist:
  31.             if j in binomials[i][0]:
  32.                 binomials[i][0].remove(j)
  33.                 binomials[i][1].append(j)
  34.             else:
  35.                 binomials[i][0].append(j)
  36.         if n-i-1 in dnum:
  37.             templist=dnum[n-i-1]
  38.         else:
  39.             templist=denum(n-i-1)
  40.             dnum[n-i-1]=templist
  41.         for j in templist:
  42.             if j in binomials[i][0]:
  43.                 binomials[i][0].remove(j)
  44.             else:
  45.                 binomials[i][1].remove(j)
  46.                 binomials[i][0].append(j)
  47.         binomials[i][2]=(binomials[i][2]*(n+1))//(n-i-1)
  48.         if not binomials[i][1] and binomials[i][2] not in squarefree_nums:
  49.             squarefree_nums.append(binomials[i][2])
  50.     if  n&1:
  51.         temp[2]*=2
  52.         if 2 in temp[0]:
  53.             temp[0].remove(2)
  54.             temp[1].append(2)
  55.         else :
  56.             temp[0].append(2)
  57.             if not temp[1] and temp[2] not in squarefree_nums:
  58.                 squarefree_nums.append(temp[2])
  59.         binomials.append(temp)
  60.     if n in dnum:
  61.         temp=dnum[n]
  62.     else:
  63.         temp=denum(n)
  64.         dnum[n]=temp
  65.     if len(set(temp))==len(temp):
  66.         squarefree_nums.append(n)
  67.     n+=1
  68. print(sum(squarefree_nums))
  69. print(time.process_time())
复制代码


34029210557426
0.156001

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:8 天
连续签到:1 天
发表于 2017-8-11 15:28:52 | 显示全部楼层
本帖最后由 hhhhhq 于 2017-8-11 15:31 编辑

def combination(m,n):
    a, b= 1, 1
    for i in range(n):
        a = a*(i+1)
        b = b*(m-i)
    C = b/a
    return C



def find(number):
    j = 2
    while True:
        if j*j > number:
            d = number
            return d
            break
        elif number % (j*j) == 0:
            d = 0
            return d
            break
        j += 1



def squarefree():
    Sum = 0
    list = []
    for m in range(1,51):
        for n in range(1,26):
            if n > m/2:
                break
            C = combination(m,n)
            if C in list:
                continue
            number = C
            d = find(number)
            if d != 0:
                list.append(C)

    Sum = sum(list) + 1
#    list.sort()
#    print(list)
#    print(len(list))
    print(Sum)
   
squarefree()
#想不出来更好的算法了,结果是34029210557338#

评分

参与人数 1荣誉 +10 鱼币 +10 收起 理由
冬雪雪冬 + 10 + 10

查看全部评分

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 
累计签到:27 天
连续签到:2 天
发表于 2017-8-12 12:38:57 | 显示全部楼层
本帖最后由 达锅 于 2017-8-13 14:42 编辑

解题越来越需要灵感了,一开始被大数误导,求除数被除数,发现数好大,算不下去……就耗了一周

答案是:34029210557338
  1. def cc(r,n):
  2.     n,r=zs[n][:],zs[r][:]+zs[n-r][:]#获得分子分母的质数列表
  3.    
  4.     for i in r:#去掉分母
  5.         n.remove(i)
  6.     #print(n)
  7.     for i in set(n):
  8.         if n.count(i)>=2:return 0#存在2个以上的相同质数,能整除,返回0
  9.     temp=1#返回乘积
  10.     for i in n:
  11.         temp*=i
  12.     return temp

  13. c=1+51
  14. lb=[i for i in range(c)]#生成质数列表
  15. zs=[[] for i in range(c)]
  16. lb[0],lb[1]=[],[]
  17. for i in range(2,c):
  18.     if lb[i]>1:
  19.         for j in range(i+1,c):
  20.             if lb[j]%lb[i]==0 :
  21.                 zs[j].append(lb[i])
  22.                 lb[j]//=lb[i]
  23.         zs[i].append(lb[i])
  24.         lb[i]=1
  25.     zs[i]+=zs[i-1]#加上前一项,即生成在c范围内所有阶乘由质数构成的列表


  26. summ=0
  27. all=set()
  28. for n in range(1,c-1):
  29.     for r in range(n//2+1):
  30.         temp=cc(r,n)#是,返回数,不是,返回0
  31.         if temp and temp not in all:
  32.             all.add(temp)
  33.             summ+=temp

  34. print(summ)
复制代码

评分

参与人数 1荣誉 +10 鱼币 +10 贡献 +10 收起 理由
冬雪雪冬 + 10 + 10 + 10

查看全部评分

1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
最佳答案
0 

尚未签到

发表于 2017-8-13 16:36:00 | 显示全部楼层
      想破头也没想出什么巧妙的算法,想从满足条件的数所在的位置下手,因为这个三角数阵每一行的值都是从前一行继承而来的,不过想了半天还是无功而返,只能硬着头皮直接算,居然算出来了!!!!不知道答案对不对。
      最后的结果是628775518183470
  1. # 给出卡帕斯三角中前n行中所有不同的数
  2. def crt_list(n = 3):
  3.     list_nums = [[1 for i in range(n)]]
  4.     list_kap = [1]
  5.     if n%2 :
  6.         temp = n//2
  7.     else:
  8.         temp = n//2 - 1
  9.     for i in range(temp):
  10.         list_deff = list_nums[i]
  11.         list_column = [1]
  12.         for j in range(1, n-i-1):
  13.             num = list_column[-1] + list_deff[j]
  14.             list_column.append(num)
  15.             if num not in list_kap:
  16.                 list_kap.append(num)
  17.         list_nums.append(list_column)
  18.     return list_kap

  19. # 给出i_end以内的素数表            
  20. def crt_pri(i_end):
  21.     mark_pri = [True for i in range(i_end + 1)]
  22.     mark_pri[0], mark_pri[1] = False, False
  23.     for i in range(2, i_end + 1):
  24.         if mark_pri[i] == True:
  25.             for j in range(i + i, i_end + 1, i):
  26.                 mark_pri[j] = False
  27.     nums_pri = [i for i,j in enumerate(mark_pri) if j == True]
  28.     return nums_pri

  29. # 将所给列表中的数进行平方
  30. def list_square(list_og):
  31.     list_aim = []
  32.     for each in list_og:
  33.         list_aim.append(each*each)
  34.     return list_aim

  35. # 将所给列表中不满足squarefree条件的数移除
  36. def judge(list_og):
  37.     list_pri = list_square(crt_pri(int(list_og[-1]**0.25) + 1))
  38.     for each in list_og:
  39.         for i in list_pri:
  40.             if each%i:
  41.                 continue
  42.             else:
  43.                 list_og.remove(each)
  44.                 break
  45.     return list_og

  46. # 将满足条件的数加起来
  47. def sqarefree_kap(n):
  48.     t_start = t.time()
  49.     sum_sqf = 0
  50.     list_kap = judge(crt_list(n))
  51.     for each in list_kap:
  52.         sum_sqf += each
  53.     t_end = t.time()
  54.     print(t_end - t_start)
  55.     return sum_sqf
复制代码
1. 如果您的提问得到满意的答案,请务必选择【最佳答案】;2. 如果想鼓励一下楼主或帮助到您的朋友,可以给他们【评分】作为奖励;
3. 善用【论坛搜索】功能,那里可能有您想要的答案;4. 粘贴代码请点击编辑框上的 <> 按钮,否则您的代码可能会被“吃掉”!
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关闭

小甲鱼强烈推荐上一条 /1 下一条

小黑屋手机版Archiver( 粤公网安备 44051102000370号 | 粤ICP备11014136号

© 2010-2017 FishC.com GMT+8, 2017-10-22 01:49 Powered by Discuz! X2.5 Theme by dreambred

快速回复 返回顶部 返回列表