首页 > Project Euler > Project Euler个人解答(Problem 41~50)

Project Euler个人解答(Problem 41~50)

2013年12月20日 发表评论 阅读评论

pe_banner_light

哟西~好的,这一P弄完,就把EP上第一页的题目全部搞完了~

这一P开始有个很明显的迹象就是。。。Python完成的任务逐渐增多,而Mathematica慢慢变少。。

其实也不是说Mathematica完成不了,只是确实有些问题用Mma来完成不能体现Mma的魅力!!而且我在想算法的时候,只要想到代码里面会有for语句什么的,我就会本能地打开Python;【C++比较繁琐,Matlab?for语句不是开玩笑的!!】不过如果涉及到字符串比较复杂的操作,或者分解质因数这一类比较数学的题目,不管怎么样,还是Mma走起吧。。话说Mma和Python在Euler Project上语言分数排名上是第二和第三诶。。

毕竟只要复杂度不是太恐怖或者算法太烂,还用不上C++这个最终兵器。。不过估计之后的趋势会变成,C++逐渐比重增加。。。这就当一个预言吧。。

到了这里,发现需要积累一些常用函数了,目前为止这里用个最多的几个就是Python生成器输出全排列,判断是否是质数,生成指定范围内的质数表这几个。

Problem 41:Pandigital prime

We shall say that an n-digit number is pandigital if it makes use of all the digits 1 to n exactly once. For example, 2143 is a 4-digit pandigital and is also prime.

What is the largest n-digit pandigital prime that exists?

翻译:
如果一个数字将1到n的每个数字都使用且只使用了一次,我们将其称其为一个n位的pandigital数。例如,2143是一个4位的pandigital数,并且是一个质数。

最大的n位pandigital质数是多少?

思路:
既然是要查找最大的数,那么就要从上往下扫描,找到第一个质数就是答案了。。。

但是如果你从987654321开始查起,那就杯具了。。最后你会发现还不如从小往大查来得快。。。

因为可以很容易证明,9位数和8位数都是绝对不可能的,因为1加到9等于45,1加到8等于36,所以8,9位数一定可以被3整除!!绝对不可能是质数;

然后就从7654321开始,为了方便从大往小找,只要输出[7,6,5,4,3,2,1]的字典序就可以了~而且,因为判断质数比较慢,所以还可以再加一个判断最后一位是不是1,3,7,如果不是,一定不可能是质数!!

其次,Python的生成器的机制可以很好利用一下,不需要输出所有的全排列再来判断,而是输出一个算一个,算出第一个质数就马上退出。

下面这个程序只要0.002s就可以算完了。。

Code:Python

#输出全排列
def QPL(m_list):
    if len(m_list) == 1:
        yield m_list
    for i in range(len(m_list)):
        restlist = m_list[0:i]+m_list[i+1:]
        for subres in QPL(restlist):
            yield [m_list[i]]+subres;

#判断质数
def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
    
for t in QPL(range(7,0,-1)):
    if t[-1] != 1 and t[-1] != 3 and t[-1] != 7:
        continue;
    k = int(''.join(map(str,t)));
    if isPrime(k):
        print k
        break

Problem 42:Coded triangle numbers

The nth term of the sequence of triangle numbers is given by, tn = ½n(n+1); so the first ten triangle numbers are:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

By converting each letter in a word to a number corresponding to its alphabetical position and adding these values we form a word value. For example, the word value for SKY is 19 + 11 + 25 = 55 = t10. If the word value is a triangle number then we shall call the word a triangle word.

Using words.txt (right click and 'Save Link/Target As...'), a 16K text file containing nearly two-thousand common English words, how many are triangle words?

翻译:
三角形数序列中第 n 项的定义是: tn = ½n(n+1); 因此前十个三角形数是:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

通过将一个单词中每个字母在字母表中的位置值加起来,我们可以将一个单词转换为一个数。例如,单词SKY的值为19 + 11 + 25 = 55 = t10。如果单词的值是一个三角形数,我们称这个单词为三角形单词。

words.txt (右键另存为)是一个16K的文本文件,包含将近两千个常用英语单词。在这个文件中,一共有多少个三角形词?

思路:
主要就是读取文件,分解出单词来吧。。。其余的没什么技巧可言。。

Code:Mathematica

(*读取文件*)
namefile = Import["words.txt"];
(*提取双引号里面的单词*)
namelist = StringCases[namefile, "\"" ~~ (x : LetterCharacter ..) ~~ "\"" -> x];
(* 求每个单词的和*)
k = Plus @@ (Flatten[ToCharacterCode@Characters[#]] - 64) & /@ namelist;
(*统计每个单词出现次数*)
Count[k, #] & /@ Table[(n (n + 1))/2, {n, 1, 20}]
(*求和*)
Total@%

Problem 43:

The number, 1406357289, is a 0 to 9 pandigital number because it is made up of each of the digits 0 to 9 in some order, but it also has a rather interesting sub-string divisibility property.

Let d1 be the 1st digit, d2 be the 2nd digit, and so on. In this way, we note the following:

  • d2d3d4=406 is divisible by 2
  • d3d4d5=063 is divisible by 3
  • d4d5d6=635 is divisible by 5
  • d5d6d7=357 is divisible by 7
  • d6d7d8=572 is divisible by 11
  • d7d8d9=728 is divisible by 13
  • d8d9d10=289 is divisible by 17

Find the sum of all 0 to 9 pandigital numbers with this property.

翻译:
1406357289是一个pandigital数,因为它包含了0到9之间每个数字且只包含了一次。此外它还有一个有趣的子串整除性质。

令d1表示其第一位数字,d2表示第二位,以此类推。这样我们可以得到:

  • d2d3d4=406 能被 2 整除
  • d3d4d5=063 能被 3 整除
  • d4d5d6=635 能被 5 整除
  • d5d6d7=357 能被 7 整除
  • d6d7d8=572 能被 11 整除
  • d7d8d9=728 能被 13 整除
  • d8d9d10=289 能被 17 整除

求所有具有如上性质的0到9pandigital数。

思路:
第一个方法想到的自然就是暴力解决,见法一,我这代码需要78s才可以出结果,超出了EP建议的one-minute-problem

第二个方法,我们首先可以计算出所有可以被2,3,5,7,11,13,17整除的所有三位数,这里注意两点,首先个位数和两位数应该也理解成三位数,也就是15应该是015,另一点,这个三位数必须每个位都不一样;

然后我们可以逐个扫描所有可以被2整除的3位数,假设是106,然后再在可以被3整除的三位数里面找开头是06的,而且最后一位要没出现在过1,0,6里面的,比如说找到063,然后我们就相当于有了1063;

然后再找可以被5整除的数里面,开头是63,而且第三位没有出现在1,0,6,3里面的数,找到635,这样我们就有了10635;

然后在不断这样找下去,知道长度达到9为止就结束;

这个方法可以在0.5s内完成全部的计算!!

Code:Python

#法一
#输出全排列(yield)
def QPL(m_list):
    if len(m_list) == 1:
        yield m_list
    for i in range(len(m_list)):
        restlist = m_list[0:i]+m_list[i+1:]
        for subres in QPL(restlist):
            yield [m_list[i]]+subres;


sum = 0;
divide = [2,3,5,7,11,13,17]
for t in QPL(range(0,10)):
    flag = True
    for i in range(2,9):
        #判断这三位是否能被divide的对应数整除
        if mod(int(''.join(map(str,t[i-1:i-1+3]))),divide[i-2]) != 0:
            flag = False
            break;
    if flag:
        sum += int(''.join(map(str,t)))
print sum
#############################################################
#法二
####首先筛选出可以被各个指定数整除的不重复的三位数
divide = [2,3,5,7,11,13,17]
pool = [[] for i in range(0,7)]
for i in range(0,1000):
    a = i // 100
    b = mod(i//10,10)
    c = mod(i,10)
    if a != b !=c != a:
        for k in range(0,7):
            if mod(i,divide[k])==0:
                pool[k].append([a,b,c])

#迭代计算,采用生成器
def solve(curlist):
    #长度为9,说明全部这是满足条件的一组
    if len(curlist) == 9:
        yield curlist
        return
    next_idx = len(curlist)-2;
    #找出前两位和前面匹配的三位数
    next_pool = filter(\
          lambda x:x[0]==curlist[-2] and \
                   x[1]==curlist[-1],\
          pool[next_idx])
    #找出第三位和之前的数都没重复的三位数
    next_pool = filter(lambda x:x[-1] not in curlist,next_pool)
    for i in range(0,len(next_pool)):
        curlist.append(next_pool[i][-1])
        for temp in solve(curlist):
            yield temp
        curlist[-1:]=[]

sum = 0;
for i in range(0,len(pool[0])):
    for result in solve(pool[0][i]):
        #找出d1
        digist_left = filter(lambda x:x not in result,range(0,10));
        result[0:0] = digist_left
        sum += int(''.join(map(str,result)))

print sum

Problem 44:Pentagon numbers

Pentagonal numbers are generated by the formula, Pn=n(3n-1)/2. The first ten pentagonal numbers are:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

It can be seen that P4 + P7 = 22 + 70 = 92 = P8. However, their difference, 70 - 22 = 48, is not pentagonal.

Find the pair of pentagonal numbers, Pj and Pk, for which their sum and difference are pentagonal and D = |Pk - Pj| is minimised; what is the value of D?

翻译:
五角数通过如下公式定义:Pn=n(3n-1)/2。前十个五角数是:

1, 5, 12, 22, 35, 51, 70, 92, 117, 145, ...

可以看出P4 + P7 = 22 + 70 = 92 = P8. 但是它们的差70 - 22 = 48却不是五角数。

找出最小的五角数对Pj 和 Pk,, 使得它们的和与差都是五角数,并且D = |Pk-Pj| 取到最小。这时D的值是多少?

思路:
这里暴搜的话比较费劲,但是也比较好写;唯一需要用到的就是判断一个数是不是五角数,很容易推导的,就是只要\(\dfrac{1+\sqrt{1+24n}}{6}\)是整数就行了。

但是还有一种方法,虽然不是算法上面的改进,只是比较猥琐,而且理论上不能保证一定可以解决问题的(虽然这里算是解决了。。),就是预先算好一定数量的五角数,然后判断就可以了。。。

这里说一下,如果用python,判断一个数在不在一个集合里面,最好用集合,你可以试一下法二的代码不用set去做,那个速度,简直不能忍受。。

Code:Python

#法一:
def IsPentagonNumber(n):
    k = (1+sqrt(1+24*n))/6;
    if k == int(k):
        return True
    else:
        return False

found = False;
i = 2;
while not found:
    t1 = i*(3*i-1)/2
    for j in range(1,i):
        t2 = j*(3*j-1)/2
        if IsPentagonNumber(t1+t2) and IsPentagonNumber(abs(t1-t2)):
            found = True
            print abs(t1-t2)
            break
    i += 1

#法二:
pre_list = [n*(3*n-1)/2 for n in xrange(1,3000)]
s = set(pre_list)#用集合!!
for i in s:
    for j in s:
        if j > i: continue
        if (i+j) in s and abs(i-j) in s:
            abs(i-j)

Problem 45:Triangular, pentagonal, and hexagonal

Triangle, pentagonal, and hexagonal numbers are generated by the following formulae:

Triangle Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
Pentagonal Pn=n(3n-1)/2 1, 5, 12, 22, 35, ...
Hexagonal Hn=n(2n-1) 1, 6, 15, 28, 45, ...

It can be verified that T285 = P165 = H143 = 40755.

Find the next triangle number that is also pentagonal and hexagonal.

翻译:
三角数,五角数和六角数分别通过以下公式定义:

三角数 Tn=n(n+1)/2 1, 3, 6, 10, 15, ...
五角数 Pn=n(3n-1)/2 1, 5, 12, 22, 35, ...
六角数 Hn=n(2n-1) 1, 6, 15, 28, 45, ...

可以证实 T285 = P165 = H143 = 40755.

找出这之后的下一个既是五角数又是六角数的三角数。

思路:
其实这道题只要扫描H144开始(因为六角数增长最快),然后判断每个数是不是五角数和三角数就行了;

判断五角数见上题,三角数就是判断\(\dfrac{\sqrt{1+8n}-1}{2}\)是不是整数就行了;这么做程序也是一瞬间就找到答案的;

但是事实上这里面还有一个化简,虽然对速度几乎没有影响,就是我们只要判断每个六角数是不是五角数就行了,因为只要是个六角数,可以证明它肯定是一个三角数!证明:

\(H=h(2h-1)=T=\dfrac{t(t+1)}{2}\)
得到:
\(4h^2-2h=t^2+t\)
如果我们将\(t\)\(2k-1\)代替的话:
\(\begin{eqnarray*}t^2+t & = &(2k-1)^2+2k-1 \\& = & 4k^2+1-4k+2k-1\\&=&4k^2-2k\end{eqnarray*}\)
形式与\(4h^2-2h\)相同!

Q.E.D.

Code:Python

def IsPentagonNumber(n):
    k = (1+sqrt(1+24*n))/6;
    if k == int(k):
        return True
    else:
        return False

i = 144
while not IsPentagonNumber(i*(2*i-1)):
    i += 1    
print i*(2*i-1)

Problem 46:Goldbach's other conjecture

It was proposed by Christian Goldbach that every odd composite number can be written as the sum of a prime and twice a square.

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

It turns out that the conjecture was false.

What is the smallest odd composite that cannot be written as the sum of a prime and twice a square?

翻译:
Christian Goldbach 提出每个奇合数都可以写作一个质数与一个平方数的二倍之和:

9 = 7 + 2×12
15 = 7 + 2×22
21 = 3 + 2×32
25 = 7 + 2×32
27 = 19 + 2×22
33 = 31 + 2×12

但是这个推测是错误的。

最小的不能写作一个质数与一个平方数的二倍之和的奇合数是多少?

思路:
也没想到什么比较好的做法,所以就利用一下Mathematica写代码的便利性吧。。

下面的代码的思路就是为了检测一个数是否符合条件,用它减去1到\(\sqrt{\dfrac{n}{2}}\)之间每个数的平方的两倍,然后看看差里面质数个数是否为0;这个是第一行代码的意思;

然后第二行就是从35开始,检测这个数是否符合第一行函数的条件或者是个质数,否则就自增2(奇合数);

Code:Mathematica

Goldbach[n_] := Length@Select[n - 2*Range[1, Sqrt[n/2]]^2, PrimeQ] != 0
NestWhile[# + 2 &, 35, Goldbach[#] || PrimeQ[#] &]

Problem 47:Distinct primes factors

The first two consecutive numbers to have two distinct prime factors are:

14 = 2 × 7

15 = 3 × 5

The first three consecutive numbers to have three distinct prime factors are:

644 = 2² × 7 × 23

645 = 3 × 5 × 43

646 = 2 × 17 × 19.

Find the first four consecutive integers to have four distinct prime factors. What is the first of these numbers?

翻译:
最小的两个具有两个不同质数因子的连续整数是:

14 = 2 × 7

15 = 3 × 5

最小的三个具有三个不同质数因子的连续整数是:

644 = 2² × 7 × 23

645 = 3 × 5 × 43

646 = 2 × 17 × 19.

找出最小的四个具有四个不同质数因子的整数。它们之中的第一个是多少?

思路:
这道题好像也没什么好的解法,因一直的欣慰的是,Mathematica做分解质因数这种事情是非常好用的~

Code:Mathematica

(*惰性编程,计算每个数有多少个不同的质因数*)
GetDistinFactor[n_] := GetDistinFactor[n] = Length@Select[FactorInteger[n], #[[1]] != n &]
(*暴力迭代*)
NestWhile[# + 1 &, 1, 
   GetDistinFactor[#]     != 4 || 
   GetDistinFactor[# + 1] != 4 || 
   GetDistinFactor[# + 2] != 4 || 
   GetDistinFactor[# + 3] != 4 &]

Problem 48:Self powers

The series, 11 + 22 + 33 + ... + 1010 = 10405071317.

Find the last ten digits of the series, 11 + 22 + 33 + ... + 10001000.

翻译:
11 + 22 + 33 + ... + 1010 = 10405071317.

11 + 22 + 33 + ... + 10001000的最后十位是什么?

思路:
一看到这种题,我就忍不住用Mathematica。。。

其实Python也很简洁;

另外,其实这道题也不一定要用的上有大数计算机制的语言,其实想C++这种,只要能得到十进制的11位数,那么也可以计算出来的,就是不断计算,然后不断截断为10位就可以了,见代码!

Code:Mathematica

IntegerDigits[Sum[i^i, {i, 1, 1000}]][[-10 ;;]] // FromDigits

Code:Python

sum = 0
for i in range(1,1001):
    sum += i**i
print mod(sum,10000000000)

Code:C++

for(int i = 1;i <= 1000;i++)
{
	unsigned long long product_t = 1;
	for(int j = 1;j <= i;j++)
	{
		product_t = (product_t*i)%10000000000;
	}
	sum = (sum+product_t)%10000000000;
}
cout<<sum;

Problem 49:Prime permutations

The arithmetic sequence, 1487, 4817, 8147, in which each of the terms increases by 3330, is unusual in two ways: (i) each of the three terms are prime, and, (ii) each of the 4-digit numbers are permutations of one another.

There are no arithmetic sequences made up of three 1-, 2-, or 3-digit primes, exhibiting this property, but there is one other 4-digit increasing sequence.

What 12-digit number do you form by concatenating the three terms in this sequence?

翻译:
1487, 4817, 8147这个序列,每个比前一个递增3330,而且这个序列有两个特点:1. 序列中的每个数都是质数。2. 每个四位数都是其他数字的一种排列。

1,2,3位组成的三个质数的序列中没有具有以上性质的。但是还有另外一个四位的递增序列满足这个性质。

如果将这另外一个序列的三个数连接起来,组成的12位数字是多少?

思路:
我暂时没想到什么好方法,我的算法基本上是:

首先获取一个1000到9999的质数表(事实上这个范围好像可以缩小),然后扫描质数表任意两个数,比如a和b,其中a>b,算出c=a+(a-b),也就是第三个数;

然后判断c是不是四位数,以及是不是质数,再判断a,b,c是不是相同的数组成的;

Code:Python

#判断是不是质数
def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

#获取排好序的列表,比如1542就会返回1,2,4,5
def GetDigist(n):
    return sorted(list(str(n)))

#生成1000-9999的质数表    
primelist = []
for i in range(1000,10000):
    if isPrime(i):
        primelist.append(i)

#计算
for i in range(0,len(primelist)):
    for j in range(0,i):
        a = primelist[i]
        b = primelist[j]
        if GetDigist(a) != GetDigist(b):
            continue
        
        c = a + (a - b)
        if c > 9999 or not isPrime(c):
            continue
        
        if GetDigist(a)==GetDigist(c):
            print a,b,c

Problem 50:Consecutive prime sum

The prime 41, can be written as the sum of six consecutive primes:

41 = 2 + 3 + 5 + 7 + 11 + 13

This is the longest sum of consecutive primes that adds to a prime below one-hundred.

The longest sum of consecutive primes below one-thousand that adds to a prime, contains 21 terms, and is equal to 953.

Which prime, below one-million, can be written as the sum of the most consecutive primes?

翻译:
41这个质数,可以写作6个连续质数之和:

41 = 2 + 3 + 5 + 7 + 11 + 13

这是100以下的最长的和为质数的连续质数序列。

1000以下最长的和为质数的连续质数序列包含21个项,和为953.

找出100万以下的最长的何为质数的连续质数序列之和。

100万以下的哪个质数能够写成最长的连续质数序列?

思路:
首先基本思路就是,先找出从2开始,一直连加到第几个质数,和会超过一百万,这里我们算出来是第547个质数,也就是说我们只要分析前546个质数的连加和是不是个质数就可以了;

显然的,我们编程的思路就是先算1~546个质数连加和是不是质数,然后再计算1~545,2~546,如果还不是,再计算1~544,2~545,3~546...不断下去;

这个大方向我也想不到什么好优化的。。

但是小地方还是可以优化的,如果对Haar特征和Adaboost做人脸识别的算法有了解的人,应该对积分图像法有所了解,运用到我们这里可以很方便的计算出累加和;

是这样子的,我们先建立一张积分表,第i个数就是前n个质数的和,也就是说前n个质数是2,3,5,7,11,13...的话,我们建立的表就是2,5,10,17,28,41...

然后我们要计算中间某段连续的质数的和,比如第3到5,那么只要积分表里面的第六个数减去第二个数就可以了,对吧~

这张积分表可以在一开始计算前多少个质数的和会超过1000000的时候就建立好;

这道题的Python代码很好的展示了Python生成器这个神器在算法中的作用~整个代码只要0.04秒就算完了。

Code:Python

#判断是不是质数
def isPrime(n):
    if n <= 1:
        return False
    for i in range(2, int(sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True
#生成积分表
sum = 0
prime_list = []
for i in xrange(2,1000000):
    if isPrime(i):
        sum += i
        prime_list.append(sum)
    if sum > 1000000:
        break
#去掉最后一个大于1000000的值
prime_list[-1:]=[]

#生成器,只为取第一个值
def GetConsecutivePrimeSum():
    for span in xrange(len(prime_list)-1,0,-1):
        for begin_p in range(0,len(prime_list)-span):
            sum = prime_list[begin_p+span]-prime_list[begin_p];
            if isPrime(sum):
                yield sum
#取生成器的第一个值
answer = GetConsecutivePrimeSum();
print answer.next()

Code:Mathematica

(*maxidx=547*)
maxidx = NestWhile[# + 1 &, 1, Total@Table[Prime[i], {i, 1, #}] < = 1000000 &]
(*建立积分表*)
IntegrateList = FoldList[Plus, 2, Table[Prime[i], {i, 2, maxidx - 1}]];

Flag = False;
span = maxidx - 1;

While[!Flag,
 	For[ori = 1, ori <= maxidx - span - 1, ori++,
        If[PrimeQ[IntegrateList[[ori + span]] - IntegrateList[[ori]]],      
           Print[IntegrateList[[ori + span]] - IntegrateList[[ori]]]; 
            Flag = True]
    	  ]
       span--;
 ]

【完】

本文内容遵从CC版权协议,转载请注明出自http://www.kylen314.com

  • 红薯

    pe43:暴力解决,编译后不到1scf1 = With[{ code = And @@ Thread[ Table[100 A[ ] + 10 A[[i + 1]] + A[[i + 2]], {i, 2, 8}]~ Mod~{2, 3, 5, 7, 11, 13, 17} == 0] // Boole // Quiet }, Compile[{{A, _Integer, 1}}, code, RuntimeAttributes -> Listable, RuntimeOptions -> "Speed", CompilationTarget -> "C" ] ];FromDigits /@ Pick[#, cf1@#, 1] &@Permutations@Range[0, 9] // Tr // AbsoluteTimingp47:Block[{i = 1}, NestWhile[Length@FactorInteger[i++] != 4 &, , Or, 4]; i - 4] // AbsoluteTiming

    • 我感觉我的代码是在“翻译”算法,而大神您的代码是在用Mma实现算法。。。

  • pe49:With[{p = Select[Range[1000, 9999], PrimeQ], tag = Composition[FromDigits, Sort, IntegerDigits]}, Cases[Last@Reap[Sow[#, tag[#]] & /@ p], {___, x_, ___, y_, ___, z_, ___} /; 2 y == x + z -> {x, y, z}]]用到了等价类的思想,把数位同构的数先合并起来,最后提取合适的数列,最终用时0.05s

    • 确实很快;我记得当时一时没想出好方法来就跑去python了。。不过想想,确实应该可以很快算出来的;毕竟四位数质数只有1061个,只要能找到方法根据 tag[#]&把这1061个数归好类就可以了;剩下的在每个分类里面找合适结果都不是很耗时的计算,不过你模板方法体现了Mma匹配上的强大之处!!赞【分类的话,我觉得用Gather的话,可读性应该比Sow-Reap大法好】突然想到Mma中“字典”这个数据结构可以用Sow-Reap/Gather变相实现了。。

      • 分类的确Gather更优,这种情况下完全可以替代Sow/Reap,当时太激动了没想到= =。不过字典那个的确有同感,我觉得Mma内部对Sow/Reap很可能是用hash实现的,这样肯定跑的飞起,缺点是对嵌套的字典就无能为力了,不过现实中应该很少碰到嵌套字典这种东西吧。。

        • Sow-Reap可以用于其他更加奇葩的场合!hash的话应该是的,毕竟想要快速实现tag这个功能的话还是这种数据结构最好;其实嵌套字典很常用。。。至少我python写代码很常用,建立一个字典,字典每个键值是日期,然后value又是一个字典,这个字典键值是用户名,然后又是一个字典什么的。。。反正我印象中我用的很多。。python里面。。以前想简单使用字典,字典的key-value不会怎么修改的话,我比较喜欢dict[key_]:=dict[key]=...这种方法。。

          • dict[key_]:=dict[key]=...感觉很适合动态规划,很方便的就缓存了值。还有在写python的时候,要是遇到嵌套列表的情况,我喜欢把键值堆成一个元组作为键,类似 dict[(key1, key2)] = value 这个样子,而且python还不允许拿列表作为键值。。很伤。。Sow/Reap还能用于什么场合啊。。我现在脑子里除了等价类其它啥也想不出来了(ノ°ο°)ノ

            • 我觉得dict[key1][key2]这个感觉更好。。列表作为键值本身就是一个很不科学的设计!字符串和数值都可以很好地做hash映射,但是列表映射基本不可能,就算勉强实现了,查找的时候也是很低效的!不要执着于tag功能,tag只是一个可选参数,Sow/Reap主要用于回收中间变量的,比如在做某些迭代计算的时候,你最后想分析中间过程or变量变化状况之类的。。

  • PE43为啥我用手算出来的结果不一样?ab = {'14','41'}cdefghij2 = {'90352867','30952867'}cdefghij7 = {'06357289','30657289','36057289','60357289'}result = {1490352867,4190352867,1430952867,4130952867,1406357289,4106357289,1430657289,4130657289,1436057289,4136057289,1460357289,4160357289}sum(result)/2才得到答案。。

    • 你的思路是啥?

      • '''是这样的,abcdefghij 10位数d%2 == 0cde%3 == 0efg%7 == 0def%5 == 0,f 为0或5fgh%11 == 0 ,f为0时g=h,所以f为5'''from functools import reducedef list2Num(L): return reduce(lambda x,y:x*10+y,L[::-1])def num2List(i): return list(map(int, str(i)))g = [1,2,3,4,6,7,8,9,0]fgh = []for i in range(1,91): temp = num2List(i*11) if temp[0] == 5: if temp in g : fgh.append(i*11)'''得fgh = [506, 517, 528, 539, 561, 572, 583, 594]'''gh = [6,17,28,39,61,72,83,94]ghi = []for i in range(13,70): temp = i*13 if (temp - temp%10)//10 in gh: ghi.append(temp)'''得ghi = [286, 390, 728, 832]观察ghi中的数的前两位对比fgh中后两位,得fgh = [528,539,572,583]'''hi = [86,28,32,90]hij = []for i in range(16,53): temp = i*17 if (temp - temp%10)//10 in hi: hij.append(temp)'''hij = [289, 323, 867]去掉323为hij =[289,867]再回头看ghi和fgh得ghi =[286,728],fgh = [528,572]d%2 == 0cde%3 == 0fgh = [528,572]ghi = [286,728]hij = [289,867]g只能为2或7if g = 2,fghij = 52867if g = 7,fghij = 57289剩下的数为:abcde = {13490} or {13460}'''abcde2={1,3,4,9,0}abcde7={1,3,4,6,0}from itertools import permutationsg2 = [i for i in permutations(abcde2,3) if sum(i)%3 == 0 and i %2 ==0]#g = 2g7 = [i for i in permutations(abcde7,3) if sum(i)%3 == 0 and i %2 ==0]#g = 7'''g2 = [(9, 0, 3), (3, 0, 9)]g7 = [(0, 6, 3), (3, 0, 6), (3, 6, 0), (6, 0, 3)]所以ab只能是14或41cdefghij2 = {'90352867','30952867'}cdefghij7 = {'06357289','30657289','36057289','60357289'}result = {1490352867,4190352867,1430952867,4130952867,1406357289,4106357289,1430657289,4130657289,1436057289,4136057289,1460357289,4160357289}'''

      • https://www.dropbox.com/s/ca9j59kcwu54azq/test.py?dl=0 好像留言出了问题?我传到网上来了

        • 所以你的结果里面不是有重复么?

          • lll9p

            咦哪里重复了。。

            • 啊,不对,不好意思。。眼花了。。但是你结果是有问题的啊。。比如说4190352867,352不能被7整除。。

              • 啊啊。。。真是。。

  • james cook

    请教下PE50为何sum>100万就ok了?

    • 因为题目。。。

      • 题目没有说吧。。只是说找一段序列的和是质数并最接近100万如果从1到546个质数之间只从500到546的和是质数,但从500到550的和是质数且小过100万,会不会有这种情况?从结果上来说你是对的,不过有数学上的依据不?

        • 题目不是说要最接近,而是最长哦。。

          • 饿 第一句口误,重点在第二句。