Euler Project解题汇总 031 ~ 040 博客分类: 数学&编程 ScalaPHPCC++C#
程序员文章站
2024-02-16 21:05:28
...
考虑到以后的题目难度会越来越大,某些题目我会加上题目分析,对解题方法进行简单的提示。
问题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
问题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
问题33:Discover all the fractions with an unorthodox cancelling method.
题目简介: 49/98 = 4/8
上面的分数化简是正确的,但一个没有学过数学的人可能会误以为是将分子与分母中的9同时消去得到的。这样的理解是错误的,但这儿确实有一些分数ab/bc,它的值与a/c相等。现在要求所有这样的分数(小于1)的积化成最简形式后分母的值。
题目分析:略
答 案:100
问题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
问题35:
How many circular primes are there below one million?
题目简介:197被称为环形素数(circular prime),这是因为它所有的轮换:197, 971, 719都是素数。求1,000,000以内环形素数的个数。
题目分析:略
答 案:55
问题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
问题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
问题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
问题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
问题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
问题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
推荐阅读
-
Euler Project解题汇总 031 ~ 040 博客分类: 数学&编程 ScalaPHPCC++C#
-
Project Euler解题汇总 051 ~ 060 博客分类: 数学&编程 PHPScala.netCC++
-
Euler Project解题汇总 031 ~ 040 博客分类: 数学&编程 ScalaPHPCC++C#
-
Project Euler解题汇总 023 ~ 030 博客分类: 数学&编程 ScalaPHP.netF#C
-
Project Euler解题汇总 001 ~ 012 博客分类: 数学&编程 ScalaHaskellPHPMatlab.net
-
Project Euler解题汇总 013 ~ 022 博客分类: 数学&编程 ScalaPHP.net编程算法
-
Project Euler解题汇总 023 ~ 030 博客分类: 数学&编程 ScalaPHP.netF#C
-
Project Euler解题汇总 041 ~ 050 博客分类: 数学&编程 PHPScala.netF#J#
-
Project Euler解题汇总 051 ~ 060 博客分类: 数学&编程 PHPScala.netCC++