Euler Project解题汇总 031 ~ 040

　　考虑到以后的题目难度会越来越大，某些题目我会加上题目分析，对解题方法进行简单的提示。

问题31：Investigating combinations of English currency denominations.
题目简介：英国的货币有便士(p)与英镑(£)两种，有以下8种常见的面值：
　　　1p, 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
2英镑的总值可能是如下的一种组合方式：
　　1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
现在要求总值为两英镑的所有可能的组合方式数。
题目分析：这是典型的动态规划(DP)题，不过这里数据量很小，直接暴力之。
答    案：73682

// Scala
def ways(c:Int,ls:List[Int]):Int =ls match{
    case Nil   => if(c == 0) 1 else 0
    case x::xs => 0.to(c/x).foldLeft(0){ (s,n) => s+ways(c-x*n,xs) }
}
ways(200,200::100::50::20::10::5::2::1::Nil)

问题32：Find the sum of all numbers that can be written as pandigital products.
题目简介： 数字7254有着特殊的性质：
　　　　　　　39×186 = 7254
可以看到，乘数，被乘数与乘积连起来恰好是数字1到9的一个排列(391867254)。
现在求所有数c的和，其中c满足存在a,b使得a×b=c，且a,b,c连起来为123456789的一个排列。
题目分析：简单的分析后可以知道数c只可能是一个4位数(why?自己想-_-)。然后就可以暴力之~
答    案：45228

// Scala
//a,b,c是否恰为123456789的一个排列
def suit(a:Int,b:Int,c:Int):Boolean ={
    var fs =new Array[Boolean](10)
    def test(n:Int){
        var t =n
        while(t != 0){
            fs(t%10) =true
            t = t/10
        }
    }
    test(a)
    test(b)
    test(c)
    fs.slice(1,10).forall(_==true)
}
1234.to(9876).filter{ n => 
    2.to(Math.sqrt(n)).filter{ n%_==0 }.exists{ k => suit(k,n/k,n) }
}.foldLeft(0){ _+_ }

问题33：Discover all the fractions with an unorthodox cancelling method.
题目简介： 49/98 = 4/8
　　上面的分数化简是正确的，但一个没有学过数学的人可能会误以为是将分子与分母中的9同时消去得到的。这样的理解是错误的，但这儿确实有一些分数ab/bc，它的值与a/c相等。现在要求所有这样的分数(小于1)的积化成最简形式后分母的值。

题目分析：略
答    案：100

// Scala
def gcd(a:Int,b:Int):Int =if(a==0) b else gcd(b%a,a)
var ls = for{ a <- 1 to 9
             b <- 1 to 9
             c <- 1 until b
             if 9*b*c+a*b == 10*a*c
         } yield (c,b)
var (a,b) = ls.foldLeft(Pair(1,1)){(p,v) =>(p._1*v._1,p._2*v._2)}
var res = b/gcd(a,b)

问题34： Find the sum of all numbers which are equal to the sum of the factorial of their digits.
题目简介：求所有能表示为其各位数字的阶乘的和的数。
譬如：145 = 1! + 4! + 5!
注意：虽然1! = 1， 2! = 2 ，但这两个数不包括在内。
题目分析：关键是算出这种数的一个上界。
　　　　PS：比较意外的是，即便包括1，2在内，满足条件的这种数一共才4个
答    案：40730

// Scala
object Euler034 extends Application {
    var fac = Array.range(0,10).map{ n => 1.to(n).foldLeft(1){ _*_ } }
    var res = 0
    for(n <- 10 to 7*fac(9)){
        var sum = n.toString.foldLeft(0){ (s,i) => s+fac(i-'0') }
        if(sum == n) res += n
    }
    println(res)
}

问题35：
How many circular primes are there below one million?
题目简介：197被称为环形素数(circular prime)，这是因为它所有的轮换：197, 971, 719都是素数。求1,000,000以内环形素数的个数。
题目分析：略
答    案：55

// Scala
import java.util.Arrays.{binarySearch => find}
import java.util.BitSet
import scala.collection.jcl.LinkedList

object Euler035 extends Application{
    /**
       得到小于bound的素数从小到大组成的Array
       Sieve of Eratosthenes 
    */
    def takePrime(bound:Int):Array[Int] = {
        if(bound <= 2) return Array()
        var set = new BitSet(bound)
        var idx = 2
        var lst = new LinkedList[Int]
        lst.add(2)
        while(idx < bound){
            var sp = lst.last
            var st = sp*2
            while(st <= bound){
                set.set(st)
                st += sp
            }
            st = sp+1
            while(st < bound && set.get(st)) st += 1
            if(st < bound) lst.add(st)
            idx = st
        }
        lst.toArray
    }
    val pa = takePrime(1000000)
    val po = Array(1000000,100000,10000,1000,100,10,1)
    
    def suit(p:Int):Boolean ={
        var pow = po.find{_<p}.get
        var cpy = p
        do{
            cpy = cpy/10 + cpy%10*pow
            if(find(pa,cpy) < 0) return false
        }while(cpy != p)
        true
    } 
    
    var res = pa.filter{ suit _ }.length
    println(res)
}

问题36：Find the sum of all numbers less than one million, which are palindromic in base 10 and base 2.
题目简介：求1,000,000以内的10进制与2进制表示都为回文数的数之和。
题目分析：略
答    案：872187

// Scala
def isPalin(n:Int):Boolean ={
    var cpy =n
    var inv =0
    while(cpy != 0){
        inv = inv*10 + cpy%10
        cpy = cpy/10
    }
    if(inv != n) return false
    while(inv != 0){
        cpy = cpy<<1
        if((inv&1) != 0) cpy = cpy|1
        inv = inv>>>1
    }
    cpy == n
}

1.until(1000000).filter{ n => isPalin(n) }.foldLeft(0){ _+ _}

问题37：Find the sum of all eleven primes that are both truncatable from left to right and right to left.
题目简介：数3797有个有趣的性质：
　　依次将它左边的数字一个个移去，得到：3797, 797, 97, 7
　　或者从右边进行：3797, 379, 37, 3
得到的这些数都是素数。已经证明这样的数只有11个(不包括2,3,5,7)。求所有这样的数之和。
题目分析：懒得想了，直接把35题的代码改改就行。
答    案：748317

// Scala
import java.util.Arrays.{binarySearch => find}
import java.util.BitSet
import scala.collection.jcl.LinkedList

object Euler037 extends Application{
    /**
       得到小于bound的素数从小到大组成的Array
       Sieve of Eratosthenes 
    */
    def takePrime(bound:Int):Array[Int] = {
        if(bound <= 2) return Array()
        var set = new BitSet(bound)
        var idx = 2
        var lst = new LinkedList[Int]
        lst.add(2)
        while(idx < bound){
            var sp = lst.last
            var st = sp*2
            while(st <= bound){
                set.set(st)
                st += sp
            }
            st = sp+1
            while(st < bound && set.get(st)) st += 1
            if(st < bound) lst.add(st)
            idx = st
        }
        lst.toArray
    }
    val pa = takePrime(1000000)
    val po = Array(1000000,100000,10000,1000,100,10,1)
    
    def suit(p:Int):Boolean ={
        var pow = po.find{_<p}.get
        var cpy = p
        var cpx = p
        do{
            cpy = cpy%pow
            cpx = cpx/10
            pow = pow/10
            if(find(pa,cpx) < 0||find(pa,cpy) < 0) return false
        }while(pow > 1)
        true
    } 
    
    var res = pa.filter{ suit _ }.foldLeft(0){ _+_ }
    println(res)
}

问题38：What is the largest 1 to 9 pandigital that can be formed by multiplying a fixed number by 1, 2, 3, ... ?
题目简介：求满足下列条件的最大的那个数A：
　　存在自然数数a及n(>1)，使得：
　　　　a×1 = m1
　　　　……
　　　　a×n = mn
　　将m1,...,mn依次相连恰好为123456789的一个排列，并且记A为连接成的那个数。
譬如192384576就是满足条件的一个数，因为：
　　192×1 = 192
　　192×2 = 384
　　192×3 = 576
题目分析：暴力是个好东东～
答    案：932718654

// Scala
object Euler038 extends Application {
    var res = "0"
    
    def suit(s:String):Boolean = {
        if(s.length != 9) return false
        var fs =new Array[Boolean](10)
        for(c <- s)
            if(c=='0') return false
            else if(fs(c-'0')) return false
            else  fs(c-'0') =true
        true
    }
    
    for(n <- 1 until 100000){
        var n2s =""
        var mul =1
        do{
            n2s += n*mul
            mul += 1
        }while(n2s.length<9)
        if(suit(n2s) && n2s>res)  res = n2s
    }
    println(res)
}

问题39： If p is the perimeter of a right angle triangle, {a, b, c}, which value, for p ≤ 1000, has the most solutions?
题目简介：1000以内，求数p使得周长为p的直角三角形的种数最多。
譬如周长为120的直角三角形有三种：{20,48,52}, {24,45,51}, {30,40,50}
题目分析：略
答    案：840

// Scala
var res =0
var max =0
for(p <- 1 until 1000){
    var c =0
    for{ a <- 1 until p/2
         b <- 1 to a
         if a*a+b*b==(p-a-b)*(p-a-b)
    } c += 1
    if(c > max){
        max =c
        res =p
    }
}
res

问题40：Finding the nth digit of the fractional part of the irrational number.
题目简介：将所有的自然数依次连起来作为小数部分做成一个无线不循环小数：
　　　　0.123456789101112131415161718192021...
记该小数第n位的数字为d(n)，有d(12) = 1
求： d(1)×d(10)×d(100)×d(1000)×d(10000)×d(100000)×d(1000000)
题目分析：暴力，又见暴力～
事实上这个题有高效的算法，不过此处数据量太小，暴力足已。
答    案：210

// Scala
var sb = new StringBuilder
var n =1
while(sb.length < 1000000){
    sb.append(n)
    n += 1
}
var res = 1
var idx = 1
for(i <- 0 to 6){
    res = res*(sb(idx-1)-'0')
    idx = idx*10
}
res

考研的时候，跑中科院去复试，出了道题和问题31很类似，当时很傻眼，结果被K掉了，郁闷了好久