Euler-Project(IV)

发表于 | 分类于 | | 热度: ℃
字数统计: 3,493 | 阅读时长 ≈ 19

31. Coin sums

Problem Description

In the United Kingdom the currency is made up of pound (£) and pence (p). There are eight coins in general circulation:

1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), and £2 (200p).

It is possible to make £2 in the following way:

1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p

How many different ways can £2 be made using any number of coins?

Solution

题目本质为经典的找零问题，可以通过动态规划的方法解决。

以本题给出的条件为例进行详细说明。题目给出1，2，5，10，20，50，100，200这八种面额的便士类型，要求通过组合获得200便士并求出所有组合的数量。首先将问题进行分解，结果为200便士的组合可分为以下三种：

  • 不引入100便士而是使用其他便士进行组合（单体最多为200便士）
  • 引入一个100便士，剩余的100便士由其他便士组合（单体最多为100便士）
  • 引入两个100便士完成组合

故可得以下递推公式：

31_problem1.PNG-20.5kB\1.PNG)

各字符含义如下：

  • t表示目标量；
  • c表示最大可用的硬币面值；
  • s(c)表示除c外更小的硬币面值；
  • w(t, c)表示使用面值为c或更小的硬币组成目标量的所有方法数。

根据以上递推公式采用动态规划的方法，将大问题分割成多个小问题并进行分类讨论处理，该方法为第一类动态规划，遵循自顶向下的问题划分原则。同时引入二维数组记录不同(t, c)组对应的方法数，以提高程序运行效率。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# How many different ways can 2 pound be made using any number of coins?
# 2 pound equals to 200p
# There are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p

def countWays(target, avc):
    if avc <= 1:
        return 1
    t = target
    if memoset[t-1][avc-1] > 0:
        return memoset[t-1][avc-1]
    result = 0
    while target >= 0:
        result += countWays(target, avc-1)
        target = target - coins[avc-1]
    memoset[t-1][avc-1] = result
    return result

if __name__ == '__main__':
    coins = [1, 2, 5, 10, 20, 50, 100, 200]
    amount_result = 200
    memoset = [[0 for col in range(9)] for row in range(amount_result+1)]
    print countWays(amount_result, 8)

以上算法还可以进一步优化。首先我们观察(t, c)取值不同时w(t, c)的运算结果，对应如下表：

31_solution1.PNG-44.5kB\2.PNG)

根据以上对应关系归纳递推公式如下：

31_formula.PNG-25.2kB\3.PNG)

经过深入分析，我们可以得出w’(t, c)函数不同参数对应结果之间的关系图如下所示：

31_solution2.PNG-44kB\4.PNG)

可以看出第一行和第一列的数值1达到最终目的地需要较长的加和路径。除此之外其他所有元素都可由最多另外两个元素相加得到。从而每个w’(t, c)的值最多决定于另外两个数值，即：

  • 同列c的前一个元素；
  • 同行t，前一列c-1对应的元素；

该方法为第二种动态规划方法，遵循自底向上的问题划分原则，从较小的问题开始解决，逐步解决更大的子问题。此类方法在处理以下问题时具有更高的效率：

  • 每个元素可以通过至多两个其他元素相加获得；
  • 要求较低的时间复杂度及空间复杂度；
  • 使用循环而非函数调用解决问题；

结合以上分析，对应代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# How many different ways can 2 pound be made using any number of coins?
# 2 pound equals to 200p
# There are eight coins in general circulation: 1p, 2p, 5p, 10p, 20p, 50p, 100p, 200p

def countWays(upper_bound, coins, aim_amount, final_ways):
    for i in range(upper_bound):
        j = coins[i]
        print final_ways
        for k in range(j, aim_amount+1):
            final_ways[k] += final_ways[k-j]
    return final_ways

if __name__ == '__main__':
    coins = [1, 2, 5, 10, 20, 50, 100, 200]
    amount_result = 200
    answer = [1] + [0]*amount_result
    final_result = countWays(8, coins, amount_result, answer)
    print final_result[amount_result]

找零问题参考资料

Euler-Project-Problem31-Overview：https://projecteuler.net/overview=031

动态规划2：https://www.jianshu.com/p/e515efee2310

硬币找零问题：https://www.cnblogs.com/anzhengyu/p/11176134.html

32. Pandigital products

Problem Description

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, the 5-digit number, 15234, is 1 through 5 pandigital.

The product 7254 is unusual, as the identity, 39 × 186 = 7254, containing multiplicand, multiplier, and product is 1 through 9 pandigital.

Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.

HINT: Some products can be obtained in more than one way so be sure to only include it once in your sum.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital.
# Example: 39 x 186 = 7254,
def isPandigital(result_string):
    if len(result_string) == 9 and "123456789".strip(result_string) == "":
        return True
    else:
        return False

if __name__ == '__main__':
    result_set = set()
    for multiplicand in range(1, 100):
        for multiplier in range(123, 9880):
            if isPandigital(str(multiplicand)+str(multiplier)+str(multiplicand*multiplier)):
                result_set.add(multiplicand*multiplier)
    print sum(result_set)

33. Digit cancelling fractions

Problem Description

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

# The mean of sign '/' equals to '//' in Python2, so if we wanna get the deimal, we could import such sentence:
# from __future__ import division
from __future__ import division
def isCuriousFraction(numerator, denominator):
    if numerator%10 == denominator//10 and (numerator//10)/(denominator%10) == numerator/denominator:
        return True
    else:
        return False
def reductionFraction(numerator, denominator):
    certain_range = denominator
    for item in range(2, certain_range):
        if numerator == 1:
            break
        if numerator % item == 0 and denominator % item == 0:
            numerator /= item
            denominator /= item
    return denominator

if __name__ == '__main__':
    final_numerator = 1
    final_denominator = 1
    for numerator in range(10, 100):
        if numerator % 10 == 0:
            continue
        for denominator in range(numerator+1, 100):
            if denominator % 10 == 0:
                continue
            if isCuriousFraction(numerator, denominator):
                final_numerator *= numerator//10
                final_denominator *= denominator%10
    final_result = reductionFraction(final_numerator, final_denominator)
    print final_result

34. Digit factorials

Problem Description

145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

Find the sum of all numbers which are equal to the sum of the factorial of their digits.

Note: As 1! = 1 and 2! = 2 are not sums they are not included.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# Find the sum of all numbers which are equal to the sum of the factorial of their digits
from functools import reduce

def getFactorial(input_number):
    if input_number == 0: return 1
    else:
        return reduce(lambda x,y: x*y, range(1, input_number+1))

def getSum(input_number):
    sum_result = 0
    while input_number != 0:
        sum_result += getFactorial(input_number%10)
        input_number /= 10
    return sum_result
if __name__ == '__main__':
    final_sum = 0
    for item in range(3, 100000):
        if getSum(item) == item:
            final_sum += item
    print final_sum

35. Circular primes

Problem Description

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

There are thirteen such primes below 100: 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, and 97.

How many circular primes are there below one million?

Solution

首先引入python的sympy库筛选出10到1000000之间的所有素数，随后对其进行第二次筛选操作。由于需要对每个素数进行顺序位移，故第一批剔除任意数位为偶数的素数。第三次筛选题目要求进行顺序位移并判断结果是否在第一步获得的素数池内。最后计算长度并作差即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# How many circular primes are there below one million
import sympy
# First we should get all the prime numbers
def getAllPrimes(lower_bound ,upper_bound):
    return list(sympy.sieve.primerange(lower_bound, upper_bound))
def sieveEvenElements(prime_set):
    PossiblePrime_set = []
    for item in prime_set:
        item_string = str(item)
        if '0' not in item_string and '2' not in item_string and '4' not in item_string and '6' not in item_string and '8' not in item_string:
            PossiblePrime_set.append(item)
    return PossiblePrime_set
def testRotationResult(SetAfterSieve):
    SetAfterSecondSieve = []
    for item in SetAfterSieve:
        item_string = str(item)
        for index_number in range(len(item_string)):
            if int(item_string[index_number:] + item_string[:index_number]) not in  SetAfterSieve:
                SetAfterSecondSieve.append(item)
                break
    return SetAfterSecondSieve
if __name__ == '__main__':
    original_primeset = getAllPrimes(10, 1000000)
    FirstSieveSet = sieveEvenElements(original_primeset)
    SecondSieveSet = testRotationResult(FirstSieveSet)
    final_circular_prime_number = 4 + len(FirstSieveSet) - len(SecondSieveSet)
    print final_circular_prime_number

36. Double-base palindromes

Problem Description

The decimal number, $ 585 = 1001001001_{2}$ (binary), is palindromic in both bases.

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2.

(Please note that the palindromic number, in either base, may not include leading zeros.)

Solution1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2
def isPalindromes(input_string):
    if input_string == input_string[::-1]:
        return True
    else:
        return False

if __name__ == '__main__':
    sum_result = 0
    for item in range(1, 1000000):
        if isPalindromes(str(item)) and isPalindromes(bin(item)[2:]):
            print item
            sum_result += item
    print sum_result

Solution2

除借助python特有的字符串逆序特性方便地解决问题外，我们设计任意进制下判定某个数字是否为回文数字的函数isPalindromes()如下：

1
2
3
4
5
6
7
def isPalindrome(input_number, base):
    reverse_result = 0
    k = input_number
    while k != 0:
        reverse_result = base*reverse_result + k % base
        k /= base
    return input_number == reverse_result

注意在二进制运算中，可以使用&1代替模运算，使用<<1代替乘法运算。

由于题目需要在二进制下保持回文状态且不考虑前导零的存在，故排除所有的偶数，即循环过程中以奇数起始，步长选择为2：

1
2
3
4
5
6
if __name__ == '__main__':
    sum_result = 0
    for item in range(1, 1000000, 2):
        if isPalindrome(item, 10) and isPalindrome(item, 2):
            sum_result += item
    print sum_result

Solution3

在题目给出的限制范围内，解法二可保持较高的效率，但随着数字上限的扩大，程序运行时间会大大增长。故考虑”生成+判定”的方法：假设在b进制下存在回文数字xyzzyx，取前三个数字xyz为回文结，则该六位数字由三位回文结xyz定义。同时xyz亦可定义五位回文数字xyzyx。故我们可得出如下结论：

对于任意b进制，任意小于$b^{n}$的整数可作为回文结生成两个小于$b^{2n}$的回文数字，这两个回文数字的位数一奇一偶。

应用以上结论，我们选择在二进制下生成两个回文数字并检验十进制下该数字是否为回文数字。如果需要得到奇数位数的回文数字，则设置标志位为true，并进行运算生成元n/进制b，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2

def isPalindrome(input_number, base):
    reverse_result = 0
    k = input_number
    while k > 0:
        reverse_result = base*reverse_result + k % base
        k /= base
    return input_number == reverse_result

def makePalindromeBase2(n, oddflag):
    result = n
    if oddflag:
        n = n >> 1
    while n > 0:
        result = (result << 1) + (n & 1)
        n = n >> 1
    return result

if __name__ == '__main__':
    upper_bound = 1000000
    sum_result = 0
    i = 1
    generated_result = makePalindromeBase2(i, True)
    while generated_result < upper_bound:
        if isPalindrome(generated_result, 10):
            sum_result += generated_result
        i += 1
        generated_result = makePalindromeBase2(i, True)
    j = 1
    generated_result2 = makePalindromeBase2(j, False)
    while generated_result2 < upper_bound:
        if isPalindrome(generated_result2, 10):
            sum_result += generated_result2
        j += 1
        generated_result2 = makePalindromeBase2(j, False)
    print sum_result

37. Truncatable primes

Problem Description

The number 3797 has an interesting property. Being prime itself, it is possible to continuously remove digits from left to right, and remain prime at each stage: 3797, 797, 97, and 7. Similarly we can work from right to left: 3797, 379, 37, and 3.

Find the sum of the only eleven primes that are both truncatable from left to right and right to left.

NOTE: 2, 3, 5, and 7 are not considered to be truncatable primes.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Find the sum of the only eleven primes that are both truncatable from left to right and right to left
import sympy
def rightToLeft(given_prime, primeSet):
    while given_prime != 0:
        if given_prime not in primeSet:
            return False
        given_prime /= 10
    return True
def leftToRight(given_prime, primeSet):
    given_prime_string = str(given_prime)
    for index_number in range(len(given_prime_string)):
        if int(given_prime_string[index_number:]) not in primeSet:
            return False
    return True
def isTruncatablePrimes(given_prime, primeSet):
    if given_prime == 2 or given_prime == 3 or given_prime == 5 or given_prime == 7:
        return False
    return rightToLeft(given_prime, primeSet) and leftToRight(given_prime, primeSet)

if __name__ == '__main__':
    sum_result = 0
    final_result = []
    primeSet = list(sympy.sieve.primerange(2, 1000000))
    for item in primeSet:
        if isTruncatablePrimes(item, primeSet):
            final_result.append(item)
            sum_result += item
    print sum_result

38. Pandigital multiples

Problem Description

Take the number 192 and multiply it by each of 1, 2, and 3:

192 × 1 = 192
192 × 2 = 384
192 × 3 = 576

By concatenating each product we get the 1 to 9 pandigital, 192384576. We will call 192384576 the concatenated product of 192 and (1,2,3)

The same can be achieved by starting with 9 and multiplying by 1, 2, 3, 4, and 5, giving the pandigital, 918273645, which is the concatenated product of 9 and (1,2,3,4,5).

What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, … , n) where n > 1?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
# What is the largest 1 to 9 pandigital 9-digit number that can be formed as the concatenated product of an integer with (1,2, ... , n) where n > 1?

def getConcatenatedResult(multiple_time, max_result, final_item):
    upper_bound = 6 - multiple_time
    lower_bound = 5 - multiple_time
    for item in range(10**lower_bound, 10**upper_bound):
        concatenated_result = ''
        for time in range(1, multiple_time+1):
            concatenated_result += str(item*time)
        tmp_result = comparisonFunction(concatenated_result, max_result, item)
        max_result = tmp_result[0]
        if tmp_result[1] != 0:
            final_item = tmp_result[1]
    return (max_result, final_item)

def comparisonFunction(concatenated_result, max_result, item):
    if judgePandigitalNumber(concatenated_result) and int(concatenated_result) > max_result:
        return (int(concatenated_result), item)
    else:
        return (max_result, 0)

def judgePandigitalNumber(input_number_string):
    if len(input_number_string) == 9 and len(set(input_number_string)) == 9 and '0' not in input_number_string:
        return True

if __name__ == '__main__':
    final_item, max_result = 0, 0
    for multiply_factor in range(2, 6):
        concatenated_result = getConcatenatedResult(multiply_factor, max_result, final_item)
        max_result = concatenated_result[0]
        final_item = concatenated_result[1]
    print max_result

39. Integer right triangles

Problem Description

If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.

{20,48,52}, {24,45,51}, {30,40,50}

For which value of p ≤ 1000, is the number of solutions maximised?

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# For which value of p <= 1000, is the numnber of solutions maximised?
import math

def judgeTriangle(a, b, c):
    if a**2 + b**2 == c**2:
        return True
    else:
        return False

def getSolutions(p):
    solution_number = 0
    for a in range(2, int(p/2)+1):
        for b in range(1, a+1):
            c = p - a - b
            if judgeTriangle(a, b, c):
                solution_number += 1
    return solution_number

if __name__ == '__main__':
    maximum_count = 0
    for p in range(12, 1001):
        count_result = getSolutions(p)
        if count_result > maximum_count:
            maximum_count = count_result
            maximum_count_p = p
    print maximum_count_p

40. Champernowne’s constant

Probelm Description

An irrational decimal fraction is created by concatenating the positive integers:

0.123456789101112131415161718192021…

It can be seen that the $12^{th}$ digit of the fractional part is 1.

If $d_{n}$ represents the $n^{th}$ digit of the fractional part, find the value of the following expression.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# Find the value of the following expression
# d1 x d10 x d100 x d1000 x d10000 x d100000 x d1000000

def getDecimalFraction():
    positive_integer = 1
    decimalfraction_string = ''
    while len(decimalfraction_string) < 1000000:
        decimalfraction_string += str(positive_integer)
        positive_integer += 1
    return decimalfraction_string

if __name__ == '__main__':
    final_fraction = getDecimalFraction()
    result = int(final_fraction[0])*int(final_fraction[9])*int(final_fraction[99])*int(final_fraction[999])*int(final_fraction[9999])*int(final_fraction[99999])*int(final_fraction[999999])
    print result
请作者吃个小鱼饼干吧
分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多