小练习：20160815 找出所有能写成 pandigital 数字乘积的数字之和

冬雪雪冬 · 发表于 2016-8-14 21:00:04

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由冬雪雪冬于 2016-8-22 10:07 编辑

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

登录/注册后可看大图

好了言归正传，我们开始做小练习。

题目要求：
以python语言完成，如果是python2请注明。
程序以代码文字格式发帖。
题目比较简单，注重程序效率和创意。
答题在一周内完成，即8.22 10：00之前，其后将公开大家的答案，并评比成绩。
另程序和答案可以在网上搜到，希望大家独立完成。

----除列出程序外，请给出输出的结果。----

题目：

如果一个 n 位数使用了 1 到 n 中每个数字且只使用了一次，我们称其为 pandigital。例如，15234 这个五位数，是 1 到 5 pandigital 的。

7254 是一个不寻常的数，因为：39 × 186 = 7254 这个算式的乘数，被乘数和乘积组成了一个1到 9 的 pandigital 组合。

找出所有能够组合成 1 到 9 pandigital 的乘法算式中乘积的和。

提示: 有的乘积数字能够被多个乘法算式得到，所以在计算时要记得只计算它们一次。

冬雪雪冬 · 发表于 2016-8-14 21:07:30

本帖最后由冬雪雪冬于 2016-8-14 22:16 编辑

答案是：45228
我的思路是：
利用排列函数将1~9的排列列出，做循环。
下一步就是乘号放在哪里？
考虑了一下只有几个可能：
1位*4位=4位
2位*3位=4位
3位*3位=3位（犯了个低级错误，这个怎么能成立呢！，应该去掉！，程序先不改了，好在没影响最终的结果。）
（反过来的4位*1位，因排列时会出现与1位*4位相同的结果，故忽略，其他类似）
相同的乘积只计一次，所以用set来存放。

from time import time
from itertools import permutations
start = time()
data = permutations('123456789')
set1 = set()
for i in data:
    product = int(i[5] + i[6] + i[7] + i[8])
    if int(i[0]) * int(i[1] + i[2] + i[3] + i[4]) == product:
        set1.add(product)
    product = int(i[5] + i[6] + i[7] + i[8])
    if int(i[0] + i[1]) * int(i[2] + i[3] + i[4]) == product:
        set1.add(product)
    product = int(i[6] + i[7] + i[8])
    if int(i[0] + i[1] + i[2]) * int(i[3] + i[4] + i[5])== product:
        set1.add(product)
print(sum(set1))
print(time() - start)

wangzhenas · 发表于 2016-8-14 21:56:36

答案： 45228
思路：要求1-9的数字各出现一次，那么符合形式的乘法如下：
x * xxxx = xxxx
xx * xxx = xxxx
而xx * xx 不可能得到5位数，xxx * xxx 不可能得到3位数，因此缩小了迭代法的范围

import time
t,num_s = time.time(),set()

for i in range(1,99):
    for j in range(1000//i,10000//i):
        s = str(i)+str(j)+str(i*j)
        if len(s)==9:
            s = set(s)
            if len(s)==9 and '0' not in s:
                num_s.add(i*j)
                print(i,j,i*j)
                
print(sum(num_s),time.time()-t)

yanghua · 发表于 2016-8-15 14:00:35

好有意思的样子

飘飞的白杨 · 发表于 2016-8-15 14:28:14

import itertools
list0 = []
def a(l):
    x1 = l[0]
    x2 = l[0]*10+l[1]
    y1 = l[1]*1000+l[2]*100+l[3]*10+l[4]
    y2 = l[2]*100+l[3]*10+l[4]
    z = l[5]*1000+l[6]*100+l[7]*10+l[8]
    if x1*y1 == z or x2*y2 == z:
        return z
    else:
        return False
for l in itertools.permutations([1,2,3,4,5,6,7,8,9],9):
    n =a(l)
    if n != False and n not in list0:
        list0.append(n)
print(sum(list0))

答案：45228

bacon6581 · 发表于 2016-8-15 16:20:57

本帖最后由 bacon6581 于 2016-8-19 12:06 编辑

from time import time
start=time()

a=set()
result=0
#用的是穷举法，即先获取每一个9位数，再去判断是否属于pandigital 组合
#P9取9 即9！=362880种取法
#第一位数字有9种取法（1-9）
#取出来的数字放在列表‘c’里（这时c里只有刚放进来的一个数字）
for i1 in range(0,9):
    b=[1,2,3,4,5,6,7,8,9]
    c=[]
    c.append(b.pop(i1))
    b1=b[:]
    c1=c[:]
#第二位数字有8种取法(第一位数字已取走的那个数字，就不能再取了)
#取出来的数字放在列表‘c’里（这时c里有两个数字了）
    for i2 in range(0,8):
        b=b1[:]
        c=c1[:]
        c.append(b.pop(i2))        
        b2=b[:]
        c2=c[:]
#第三位数字有7种取法(第一、二位数字已取走的那个数字，就不能再取了)
#取出来的数字放在列表‘c’里（这时c里有三个数字了）
#下同
        for i3 in range(0,7):
            b=b2[:]
            c=c2[:]
            c.append(b.pop(i3))
            b3=b[:]
            c3=c[:]
            for i4 in range(0,6):
                b=b3[:]
                c=c3[:]
                c.append(b.pop(i4))
                b4=b[:]
                c4=c[:]
                for i5 in range(0,5):
                    b=b4[:]
                    c=c4[:]
                    c.append(b.pop(i5))
                    b5=b[:]
                    c5=c[:]
                    for i6 in range(0,4):
                        b=b5[:]
                        c=c5[:]
                        c.append(b.pop(i6))
                        b6=b[:]
                        c6=c[:]
                        for i7 in range(0,3):
                            b=b6[:]
                            c=c6[:]
                            c.append(b.pop(i7))
                            b7=b[:]
                            c7=c[:]
                            for i8 in range(0,2):
                                b=b7[:]
                                c=c7[:]
                                c.append(b.pop(i8))
#前面8个数字都确定了，那最后一位只有一种取法了：P1取1=1
#直接把剩余的一个数字，放入列表‘c’里边
                                c.append(b[0])
#产生pandigital 组合的只可能会是以下4种情况：
#1位数 * 4位数 = 5位数
#2位数 * 3位数 = 5位数
#4位数 * 1位数 = 5位数
#3位数 * 2位数 = 5位数
#如果有123456789组合，则必有234516789组合
#即1*2345==5678（第一个组合的第一种判断） 与2345*1==5678（第二个组合的第3种判断）属重复判断
#故注释掉后两种判断
#判断成立，即该数值属pandigital 组合，并将结果放入集合'a'中（不用操心会有重复值）
                                if(((c[0]*(c[1]*1000+c[2]*100+c[3]*10+c[4]))==c[5]*1000+c[6]*100+c[7]*10+c[8])
                                   or ((c[0]*10+c[1])*(c[2]*100+c[3]*10+c[4])==c[5]*1000+c[6]*100+c[7]*10+c[8])):
                                   #or ((c[0]*100+c[1]*10+c[2])*(c[3]*10+c[4])==c[5]*1000+c[6]*100+c[7]*10+c[8])
                                   #or ((c[0]*1000+c[1]*100+c[2]*10+c[3])*(c[4])==c[5]*1000+c[6]*100+c[7]*10+c[8])):
                                    a.add(c[5]*1000+c[6]*100+c[7]*10+c[8])
#将集合a里的所有数值累加一遍，即所求之结果！
for k in a:
    result+=k
print(result)
print(time()-start)

>>> ================================ RESTART ================================
>>> 
45228
22.254349946975708
>>> ================================ RESTART ================================
>>> 
45228
15.573134183883667
>>>

中文注释后加的，要是注释有报错，麻烦版主删掉再试！
注释掉两行，速度快了7秒

无下限HENTAI · 发表于 2016-8-17 16:17:07

#12*798为4位数，79*123为4位数
#范围为（12~79），（798~123）
import itertools as it
count = 0
a = list(it.permutations(range(1,10),3))
b = list(it.permutations(range(1,10),2))
for i in a:
    for j in b:
        if set(i) & set(j) == set():
            c = int(str(i[0])+str(i[1])+str(i[2]))
            d = int(str(j[0])+str(j[1]))
            if c <798 and d <79:
                mult = c * d
                if mult < 10000:
                    mult_str = str(mult)
                    mult_set = {int(mult_str[0]),int(mult_str[1]),int(mult_str[2]),int(mult_str[3])}
                    if 0 not in mult_set and len(mult_set) == 4:
                        union = set(i).union(set(j))
                        if union & mult_set == set():
                            count += 1
                            print('%d x %d = %d'%(c,d,mult))
            else:
                continue
print('共有%d个这样的结果'%count)

结果：
138 x 42 = 5796
157 x 28 = 4396
159 x 48 = 7632
186 x 39 = 7254
198 x 27 = 5346
297 x 18 = 5346
483 x 12 = 5796
共有7个这样的结果

无下限HENTAI · 发表于 2016-8-17 16:24:10

看错了，原来是求和的

import itertools as it
total = []
a = list(it.permutations(range(1,10),3))
b = list(it.permutations(range(1,10),2))
for i in a:
    for j in b:
        if set(i) & set(j) == set():
            c = int(str(i[0])+str(i[1])+str(i[2]))
            d = int(str(j[0])+str(j[1]))
            if c <798 and d <79:
                mult = c * d
                if mult < 10000:
                    mult_str = str(mult)
                    mult_set = {int(mult_str[0]),int(mult_str[1]),int(mult_str[2]),int(mult_str[3])}
                    if 0 not in mult_set and len(mult_set) == 4:
                        union = set(i).union(set(j))
                        if union & mult_set == set():
                            total.append(mult)
total_set = set(total)        
print('所有乘积的和是：%d'%sum(total_set))

结果：
所有乘积的和是：30424

yyongl · 发表于 2016-8-17 20:24:12

有时候就盲目了，可能就标点错了也看不出来

老忘 · 发表于 2016-8-18 11:14:20

本帖最后由老忘于 2016-8-18 11:34 编辑

思路：
1、要能够组合成 1 到 9 pandigital 的乘法算式，也就是说乘数、被乘数、积的位数之和必须要是9，要满足这一点，则只有1位数乘4位数、2位数乘3位数（重复的不考虑）二种情况。
2、分别从1-9中，按1-4位取出其pandigital数，存入对应列表，再按条件1进行判断。

开始采用从1到9999全部循环处理，36秒左右出结果，后改成用itertools模块取出1-4位的pandigital数再全部循环处理，14左右秒出结果，最后改成提交的这个版本，仅0.2秒左右出结果。所以在此不得不再次感叹一下，编程时的思路会影响程序效率，思路真的十分重要，要多想想啊！

# -*- coding:Utf-8 -*-
import itertools
import time
start = time.clock()

def check_pd(x):#检测是否为仅含1 到 9 的pandigital数，是返回1，否返回0
    for eachone in x:
        if  x.count(eachone)>1 or eachone=='0':
            return 0
    return 1

list_rel=[]
for i in range(1,5):
    locals()['list_'+str(i)]=[] #动态生成list_1、list_2、list_3、list_4的空列表，存放1 到 9 的分别取1-4位的pandigital数
    for each in list(itertools.permutations([1,2,3,4,5,6,7,8,9],i)):
        s=''
        for eachone in each:
            s=s+str(eachone)
        locals()['list_'+str(i)].append(int(s))
#要使乘数和积满足9位的pandigital数，只能是1位数乘4位数或者2位数乘3位数二种情况
for i in range(1,3):
    for each in locals()['list_'+str(i)]:
        for eachone in locals()['list_'+str(5-i)]:
            if len(str(each)+str(eachone)+str(each*eachone))==9 and  check_pd(str(each)+str(eachone)+str(each*eachone)) and (each*eachone not in list_rel):
                list_rel.append(each*eachone)

print(sum(list_rel))

end = time.clock()
print ("read: %f s" % (end - start))

计算结果：

mather · 发表于 2016-8-20 08:28:13

s = [1,2,3,4,5,6,7,8,9]

def be_nums(j):#定义一个可以将组合变换为数字的函数
    res = 0
    for ji in j:
        res = res*10 + ji
    return res
#可能的情况是1位乘4位等于4位
#或者2位乘3位等于4位的情况
product = set()
import itertools
#先求1位乘4位的，再求2位乘4位的
for i in range(2,10):
    #不可能是1乘的所以只计算2以上的乘
    for j in itertools.permutations([x for x in s if x!=i],4):
        temp = be_nums(j)
        may_product = i*temp
        if (may_product)//10000>0:
            break#直接跳出内层循环？不知道有没有问题
        sets = set(j)
        sets.add(i)
        is_break = False
        while may_product>0:
            te = may_product%10
            if  te==0 or te in sets:
                is_break = True
                break
            else:
                sets.add(te)
                may_product = may_product//10
        if (not is_break) and (len(sets)==9):
            product.add(i*temp)
for i in itertools.permutations(s,2):
    #2位乘3位的
    temp1 = be_nums(i)
    for j in itertools.permutations([x for x in s if x not in i],3):
        temp2 = be_nums(j)
        may_product = temp1*temp2
        if (may_product)//10000>0:
            break
        sets = set(list(i)+list(j))
        is_break = False
        while may_product>0:
            te = may_product%10
            if te==0 or te in sets:
                is_break = True
                break
            else:
                sets.add(te)
                may_product = may_product//10
        if (not is_break) and (len(sets)==9):
            product.add(temp1*temp2)
print(product)
print(sum(product))

结果：{5346, 5796, 6952, 7852, 4396, 7632, 7254}
45228

过河的小卒 · 发表于 2016-8-21 17:40:30

def func():
    l1 = []
    k = 0
    for i in range(1000,10000):
        if len(set(str(i))) == 4 and '0' not in str(i):
            for j in range(1,100):
                if i%j == 0:
                    if len(set(str(i)+str(j)+str(i//j))) == 9:
                        l1.append(i)
                        break
    return l1
list1 = func()
print(list1,'\n',sum(list1))

输出：
[3876, 4396, 4827, 5278, 5346, 5427, 5724, 5796, 6158, 6174, 6372, 6952, 7236, 7254, 7362, 7452, 7632, 7638, 7852, 7854, 8156, 8316, 8463]
151541
所以结果为151541

过河的小卒 · 发表于 2016-8-22 10:20:15

过河的小卒发表于 2016-8-21 17:40
输出：
[3876, 4396, 4827, 5278, 5346, 5427, 5724, 5796, 6158, 6174, 6372, 6952, 7236, 7254, 7362, ...

哎，没考虑i//j得到的数中是否包含0
改进后：

def func():
    l1 = []
    k = 0
    for i in range(1000,10000):
        if len(set(str(i))) == 4 and '0' not in str(i):
            for j in range(1,100):
                if i%j == 0:
                    if len(set(str(i)+str(j)+str(i//j))) == 9:
                        if '0' not in str(i//j):
                            l1.append(i)
                            print(i,j,i//j)
                            break
    return l1
list1 = func()
print(list1,'\n',sum(list1))

输出：
4396 28 157
5346 18 297
5796 12 483
6952 4 1738
7254 39 186
7632 48 159
7852 4 1963
[4396, 5346, 5796, 6952, 7254, 7632, 7852]
45228
这下对了
貌似我的代码行数最少

账号		自动登录	找回密码
密码			立即注册

[技术交流] 小练习：20160815 找出所有能写成 pandigital 数字乘积的数字之和

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

评分

评分

评分

评分

评分

评分

评分