Python3 欧拉计划问题96-100

作者: AiFany | 来源:发表于2018-02-07 14:13 被阅读62次

EulerProject.png
问题91-95参见：https://www.jianshu.com/p/eaf1075ac5e9

96、数独详细解法参见

数独是一种热门的谜题。它的起源已不可考，但它与欧拉发明的一种类似的谜题拉丁方阵之间有着千丝万缕的联系。数独是利用1~9的数字替换掉9*9网格中的空白位置，使得每行、每列以及每个九宫格中恰好都包含数字1~9。如下是一个典型的数独谜题以及它的解答：

Sudoku.png

一个构造精良的数独谜题应该包含有唯一解，且能够通过逻辑推断来解决，尽管有时可能必须通过“猜测并检验”来排除一些选项。寻找答案的复杂度决定了题目的难度；上面这个谜题被认为是一个比较简单的谜题，因为可以通过逻辑推断来解决它。
在文件sudoku.txt中包含有50个不同难度的数独谜题，它们都只有唯一解。上面给出的示例就是文件中的第一个谜题。解开这50个谜题，找出每个谜题解答左上角的三个数字并连接起来，给出这些数的和。例如：上述示例解答左上角的三个数字连接起来构成的数是483。

Python3解答

import numpy as np
fan=open(r'C:\Users\GWT9\Desktop\p096_sudoku.txt')#数据文件
an =[]
listfan = []
while 1:
    x = fan.readline()
    if len(x) == 0:
        break
    try:
        int(x)
        fanlist = []
        for jj in x:
            if jj != '\n':
                if jj == '0':
                    fanlist.append(np.nan)
                else:
                    fanlist.append(int(jj))
        listfan.append(fanlist)
    except ValueError:
        pass
    if len(listfan) == 9:
        an.append(listfan)
        listfan = []
fan.close()
#all problem data
an = np.array(an)

#sudoku
# 计算可能性
def ProbNumber(hang, lie, data):
    # 行数据
    H = list(data[hang])
    # 列数据
    L = list(data[:, lie])
    # 宫数据
    G = []
    sfang = int(len(data) ** 0.5)
    hh = hang // sfang
    ll = lie // sfang
    # 宫数据添加
    for ig in range(sfang):
        for gi in range(sfang):
            G.append(data[hh * sfang + ig, ll * sfang + gi])
    # 该点的可能性
    lal = list(H) + list(L) + G
    prob = [ip for ip in list(range(1, len(data) + 1)) if ip not \
            in lal]
    return prob

# 为数据中的空元素选择可能性字典
def ForK(data):
    Kdict = {}
    for ik in range(len(data)):
        for ki in range(len(data)):
            if np.isnan(data[ik, ki]):
                # 转换，便于字典的最下值是唯一的
                trans = ProbNumber(ik, ki, data)
                jieti = len(trans) * 10000000 + ik * 10000 + ki * 10
                Kdict['%s-%s' % (ik, ki)] = [jieti, len(trans), trans]
    return Kdict

# 选择可能性最小的位置
def SeleM(ddict):
    Small = min(ddict.items(), key=lambda x: (x[1][0]))[0]
    # 位置
    weizhi = Small.split('-')
    # hang
    Ha = int(weizhi[0])
    # lie
    Li = int(weizhi[1])
    # 集合
    SE = ddict[Small][2]
    return Ha, Li, SE

ss = 0
global NU
VAR_NAME = locals()
for ifrfr in range(len(an)):
    # 初始状态
    InitialState = {}
    InitialState[0] = an[ifrfr]
    # 取值字典
    NumDict = {}
    NU = 1
    # 状态转移
    # 记录栈中调用函数的次数
    minzhai = 0
    def TransFer(insta, numdi, n=0, c=minzhai):
        # 判断是否满足条件
        if len(ForK(insta[n])) == 0:
            global NU
            NU = 0
            return insta, numdi, n
        # 选择最小的
        mmi = SeleM(ForK(insta[n]))
        if c > 900:
            return insta, numdi, n

        if len(mmi[2]) == 0:
            del insta[n]
            c += 1
            return TransFer(insta, numdi, n - 1, c)
        else:
            middle = insta[n].copy()
            if n in numdi:
                if numdi[n] + 1 < len(mmi[2]):
                    numdi[n] += 1
                    middle[mmi[0], mmi[1]] = mmi[2][numdi[n]]
                    n += 1
                    insta[n] = middle.copy()
                    c += 1
                    return TransFer(insta, numdi, n, c)
                else:
                    del numdi[n]
                    del insta[n]
                    c += 1
                    return TransFer(insta, numdi, n - 1, c)
            else:
                numdi[n] = 0
                middle[mmi[0], mmi[1]] = mmi[2][0]
                n += 1
                insta[n] = middle.copy()
                c += 1
                return TransFer(insta, numdi, n, c)
    c_0 = TransFer(InitialState, NumDict)
    # 最终的函数
    def Sudoku():
        count = 1
        while NU != 0:
            VAR_NAME['c_%s' % count] = TransFer(eval('c_%s' % (count - 1))[0], eval('c_%s' % (count - 1))[1],
                                                eval('c_%s' % (count - 1))[2])
            count += 1
        dd = eval('c_%s' % (count - 1))[0][eval('c_%s' % (count - 1))[2]][0][:3]
        return dd
    ss += np.sum(Sudoku() * np.array([100, 10, 1]))#左上角三个数字连接起来
print(int(ss))
答案：24702

97、非梅森素数

1999年人们发现了第一个超过100万位的素数，这是一个梅森素数，可以表示为2^6972593−1，包含2,098,960位数字。在此之后，更多形如2^p−1的梅森素数被发现，其位数也越来越多。
在2004年，发现了一个巨大的非梅森素数：28433×2^7830457+1，包含2,357,207位数字。找出这个素数的最后十位数字。

Python3解答

#这就是python的魔力
print((28433 * (2 ** 7830457) + 1) % (10 ** 10))
答案：8739992577

98、平方数重排

如果单词CARE中的四个字母依次对应为1、2、9、6四个数字，我们得到了一个平方数：1296 = 36²。神奇的是，使用同样的数字字母对应规则，重排后的单词RACE同样也构成了一个平方数：9216 = 96²。我们称CARE和RACE为重排平方单词对，同时规定这样的单词对不允许第一个字母对应数字0或是不同的字母对应相同的数字。
在文件words.txt中包含了将近2000个常见英文单词，找出其中所有的重排平方单词对，一个回文单词不视为它自己的重排。重排平方单词对所给出的最大平方数是多少。注意：所有的重排单词必须出现在给定的文本文件中。

Python3解答

fan=open(r'C:\Users\GWT9\Desktop\p098_words.txt')#数据文件
#存储words的list
cclist =[]
fu = []
for i in fan:
    for j in i:
        if j != ',':
            if j != '"':
                fu.append(j)
        else:
            if len(fu) == 1:
                cclist.append(fu[0])
            else:
                cclist.append(('').join(fu))
            fu =[]
cclist.append(('').join(fu))

#获得重排字母对
pair = []
leng = len(cclist)
for iw in range(leng - 1):
    for jw in range(iw, leng):
        iwc, jwc= cclist[iw], cclist[jw]
        if len(iwc) == len(jwc) and sorted(iwc) == sorted(jwc) and iwc != jwc:
            pair.append([iwc, jwc])

#根据字母长度获得该长度范围内的完全平方数
def Squre(length):
    if length == 1:
        return [1, 4, 9]
    gu = [ji ** 2 for ji in range(int((10 ** (length - 1)) ** 0.5), int((10 ** length) ** 0.5))]
    return gu

#根据字母和数字的对应关系获得数字
def Getdigit(exdict, word):
    num = ''
    for hh in word:
        num += exdict[hh]
    return int(num)

print('WORDS PAIR：', pair)
#判断数字和word是否对应
def Judge(number, word):
    accdict = {}
    leng = len(word)
    for jj in range(leng):
        if jj not in accdict:
            accdict[word[jj]] = str(number)[jj]
    #根据字典反写数字与原来数字是否一样
    if Getdigit(accdict, word) == number:
        return accdict
    else:
        return  False

#根据word和数字，求pair word的对应数字
def Getnum(words1, digitset, words):
    fu = []
    for digit in digitset:
        if len(words1) == len(str(digit)) and len(set(words1)) == len(set(str(digit))):#初步判断数字和word是否匹配。
            cdict = Judge(digit, words1)#判断是否匹配
            if cdict:#如果匹配，输出字母和数字的对应字典
                gunum = Getdigit(cdict, words)
                if gunum in digitset:#如果这个数也是完全平方数
                    fu.append([digit, gunum])#输出结果
                    print('%s ==> %s' %([words1, words], fu[0]))
                    return fu
    return False

result = []
for kk in pair:
    setdi = Squre(len(kk[0]))
    number = Getnum(kk[0], setdi, kk[1])
    if number:
        result.append(max(number[0]))
print('最大的平方数：', max(result))
#答案：
WORDS PAIR： [['ACT', 'CAT'], ['ARISE', 'RAISE'], ['BOARD', 'BROAD'], ['CARE', 'RACE'], ['CENTRE', 'RECENT'], ['COURSE', 'SOURCE'], ['CREATION', 'REACTION'], ['CREDIT', 'DIRECT'], ['DANGER', 'GARDEN'], ['DEAL', 'LEAD'], ['DOG', 'GOD'], ['EARN', 'NEAR'], ['EARTH', 'HEART'], ['EAST', 'SEAT'], ['EAT', 'TEA'], ['EXCEPT', 'EXPECT'], ['FILE', 'LIFE'], ['FORM', 'FROM'], ['FORMER', 'REFORM'], ['HATE', 'HEAT'], ['HOW', 'WHO'], ['IGNORE', 'REGION'], ['INTRODUCE', 'REDUCTION'], ['ITEM', 'TIME'], ['ITS', 'SIT'], ['LEAST', 'STEAL'], ['MALE', 'MEAL'], ['MEAN', 'NAME'], ['NIGHT', 'THING'], ['NO', 'ON'], ['NOTE', 'TONE'], ['NOW', 'OWN'], ['PHASE', 'SHAPE'], ['POST', 'SPOT'], ['POST', 'STOP'], ['QUIET', 'QUITE'], ['RATE', 'TEAR'], ['SHEET', 'THESE'], ['SHOUT', 'SOUTH'], ['SHUT', 'THUS'], ['SIGN', 'SING'], ['SPOT', 'STOP'], ['SURE', 'USER'], ['THROW', 'WORTH']]
['BOARD', 'BROAD'] ==> [17689, 18769]
['CARE', 'RACE'] ==> [1296, 9216]
['DEAL', 'LEAD'] ==> [1764, 4761]
['EAST', 'SEAT'] ==> [2916, 1296]
['EAT', 'TEA'] ==> [256, 625]
['FILE', 'LIFE'] ==> [1296, 9216]
['HATE', 'HEAT'] ==> [1369, 1936]
['HOW', 'WHO'] ==> [256, 625]
['ITS', 'SIT'] ==> [256, 625]
['MALE', 'MEAL'] ==> [1369, 1936]
['MEAN', 'NAME'] ==> [2401, 1024]
['NOTE', 'TONE'] ==> [1296, 9216]
['NOW', 'OWN'] ==> [625, 256]
['POST', 'SPOT'] ==> [2916, 1296]
['POST', 'STOP'] ==> [1024, 2401]
['RATE', 'TEAR'] ==> [1024, 2401]
['SHUT', 'THUS'] ==> [1764, 4761]
最大的平方数： 18769

99、幂值比较

比较两个如2¹¹和3⁷这样的幂值大小并不困难，任何计算器都能验证2¹¹ = 2048 < 3⁷ = 2187。
然而，想要验证632382⁵¹⁸⁰⁶¹ > 519432⁵²⁵⁸⁰⁶就会变得非常困难，因为这两个数都包含有超过300万位数字。
在文件base_exp.txt有一千行，每一行有一对底数和指数，找出哪一行给出的幂值最大。文件的前两行就是上面给出的两个例子。

Python3解答

import math
fan=open(r'C:\Users\GWT9\Desktop\p099_base_exp.txt')#数据文件
#存储words的list
explist =[]
for i in fan:
    com = []
    for hh in i.split(','):
        com.append(int(hh))
    explist.append(com)
#转化为对数比较
sinum = 0
hang = 0
for num in explist:
    dlog = math.log(num[0]) * num[1]
    hang += 1
    if sinum < dlog:
        dnum = hang
        sinum = dlog
print(dnum)
答案：709

100、概率反推

一个盒子中装有21个彩色碟子，其中15个是蓝的，6个是红的。如果随机地从盒子中取出两个碟子，取出两个蓝色碟子的概率是:
P(BB) = (15/21)×((15-1)/(21-1)) =(15/21)×(14/20) = 1/2
下一组使得取出两个蓝色盘子的概率恰好为50%的安排，是在盒子中装有85个蓝色碟子和35个红色碟子。
P(BB) = (85/120)×((85-1)/(120-1)) =(85/120)×(84/119) = 1/2
当盒子中装有超过10¹² 个碟子时，找出第一组满足上述要求的安排，并求此时盒子中蓝色碟子的数量。

Python3解答

#blue:b, total:t
#2b(b-1)=t(t-1)==>8b^2-8b+1=(2t-1)^2
#pell's Equation2u^2-1=d^2==>2(2b-1)^2-1=(2t-1)^2
#d=2t-1,u=2b-1. t=(d+1)/2, b=(1+u)/2
#pell's Equation==>d^2-2u^2=-1
#初始解
d = 1
u = 1
minnumber = 1e12

while 1:
    if (d + 1) / 2 > minnumber:
        print(int((u + 1) / 2))
        break
    d, u = 3 * d + 4 * u, 2 * d + 3 * u
    print('Total:%d, blue:%d'%((d + 1) / 2, (u + 1) / 2))
#运行结果
Total:4, blue:3
Total:21, blue:15
Total:120, blue:85
Total:697, blue:493
Total:4060, blue:2871
Total:23661, blue:16731
Total:137904, blue:97513
Total:803761, blue:568345
Total:4684660, blue:3312555
Total:27304197, blue:19306983
Total:159140520, blue:112529341
Total:927538921, blue:655869061
Total:5406093004, blue:3822685023
Total:31509019101, blue:22280241075
Total:183648021600, blue:129858761425
Total:1070379110497, blue:756872327473
答案：756872327473

持续更新，欢迎讨论，敬请关注！！！

Python3 欧拉计划问题96-100

96、数独详细解法参见

Python3解答

97、非梅森素数

Python3解答

98、平方数重排

Python3解答

99、幂值比较

Python3解答

100、概率反推

Python3解答

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

程序员

程序猿阵线联盟-汇总各类技术干货

数据结构和算法分析

Python3 欧拉计划 问题96-100

96、数独 详细解法参见

Python3解答

97、非梅森素数

Python3解答

98、平方数重排

Python3解答

99、幂值比较

Python3解答

100、概率反推

Python3解答

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

程序员

程序猿阵线联盟-汇总各类技术干货

数据结构和算法分析

Python3 欧拉计划问题96-100

96、数独详细解法参见