欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Euler Project解题汇总 031 ~ 040 博客分类: 数学&编程 ScalaPHPCC++C# 

程序员文章站 2024-02-16 21:05:28
...
  考虑到以后的题目难度会越来越大,某些题目我会加上题目分析,对解题方法进行简单的提示。

问题31Investigating 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)




问题32Find 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){ _+_ }



问题33Discover 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)
}



问题36Find 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){ _+ _}




问题37Find 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)
}



问题38What 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



问题40Finding 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