`
Eastsun
  • 浏览: 308228 次
  • 性别: Icon_minigender_1
  • 来自: 天津
社区版块
存档分类
最新评论

Project Euler解题汇总 051 ~ 060

阅读更多
  :本文代码中会使用按字典顺序生成所有的排列筛法求素数中介绍的函数。

问题51Find the smallest prime which, by changing the same part of the number, can form eight different primes.
题目简介:对于数字56**3(其中*表示占位符),将其中的两个*换成0~9中的数字,产生的10个数字中为素数的有:56003, 56113, 56333, 56443, 56663, 56773, 56993。56003是这一系列素数中最小的那个。
  现在要求满足下列条件最小的那个素数:该数是由将某个数中的几位(不一定相邻)替换为相同数字而产生的8个素数中的一个。(注意:如果被替换的位置中有首位,则不能用0来替换)
答  案:121313
import java.util.Arrays.fill
import eastsun.math.Util._

object Euler051 extends Application {
    
    var pa = getPrimes(1000000).filter{ _ > 100000 }
    var bf = new Array[Int](64)
    var res = 0
    var i = 0
    while(res == 0 && i < pa.length){
        fill(bf,1)
        var j = i + 1
        while(res == 0 && j < pa.length){
            var pi = pa(i)
            var pj = pa(j)
            var id = 0
            var tg = true
            var pie = -1
            var pje = -1
            do{
                id = id<<1
                if(pi%10 == pj%10) id = id|1
                else if(pie != -1 && (pj%10 != pje || pi%10 != pie)) tg =false
                else{ 
                    pje = pj%10
                    pie = pi%10
                }
                pi = pi/10
                pj = pj/10
            }while(pi != 0 && tg )
            if(tg){
                bf(id) += 1
                if(bf(id) >= 8 ) res = pa(i)
            }
            j += 1
        }
        i += 1
    } 
    println(res)   
}



问题52Find the smallest positive integer, x, such that 2x, 3x, 4x, 5x, and 6x, contain the same digits in some order.
题目简介:求最小的x,使得x的2倍,3倍,4倍,5倍,6倍都是由相同的数字组成
答  案:142857
PS:对1/7的循环节印象比较深刻,直接就写出来了,果然是对的:-)


问题53How many values of C(n,r), for 1 ≤ n ≤ 100, exceed one-million?
题目简介:求组合数C(n,r) (1 ≤ n ≤ 100)中超过1000000的有多少个。
答  案:4075
object Euler053 extends Application {
    var buf =new Array[BigInt](101)
    var res =0
    for(row <- 0 to 100){
        var pre =buf(0)
        for(col <- 1 to row-1){
            var tmp =pre
            pre =buf(col)
            buf(col) += tmp
            if(buf(col)>1000000) res += 1
        }
        buf(row) =1
    }
    println(res)
}



问题54How many hands did player one win in the game of poker?
题目简介:一个扑克牌游戏,判断提供的数据中玩家1赢的盘数有多少次
答  案:376
import scala.io.Source._
object Euler054 extends Application {
    val src = fromFile("poker.txt").getLines
    var cnt = 0
    src.foreach{ hand =>
        val lst = hand.split("\\s").toList
        val aPlayer = new CardHand(lst.take(5))
        val bPlayer = new CardHand(lst.drop(5))
        if(aPlayer > bPlayer) cnt += 1
    }
    println(cnt)
}

class CardHand(cards:List[String]) extends Ordered[CardHand] {
    val map = Map('2'->2,'3'->3,'4'->4,'5'->5,'6'->6,'7'->7,
                  '8'->8,'9'->9,'T'->10,'J'->11,'Q'->12,'K'->13,'A'->14)
    val values = cards.map{c => map(c.first)}.sort{ _ > _ }
    
    def rank :List[Int] = {
        val isFlush = cards.forall{ _.last == cards.first.last }
        val isStraight = values.zipWithIndex.forall{ case(x,y) => x + y == values.first }
        if(isFlush && isStraight) return 9::values
        if(isFlush) return 6::values
        if(isStraight) return 5::values
        
        val lst = values.map{ v =>(values.filter{ _==v }.size,v) }.removeDuplicates.sort{ _ > _ }
        val vst = lst.map{ _._2 }
        if(lst.first._1 == 4) return 8::vst
        if(lst.first._1 == 3) return if(lst(1)._1 == 2) 7::vst else 4::vst
        if(lst.first._1 == 2) return if(lst(1)._1 == 2) 3::vst else 2::vst
        1::values
    }
    
    def compare(that:CardHand):Int = rank compare that.rank
}



问题55
How many Lychrel numbers are there below ten-thousand?

题目简介:首先介绍一个数学名词:利克瑞尔数(Lychrel Number):指的是将该数与将该数各数位逆序翻转后形成的新数相加、并将此过程反复迭代后,结果永远无法是一个回文数的自然数。
  现在已知对于10000以内的自然数,要么能够在50步(指将这个数与其逆序后的数相加的过程)内得到一个回文数;要么该数是一个利克瑞尔数。
  求:10000以内利克瑞尔数的个数
答  案:249
import java.math.BigInteger
object Euler055 extends Application {
    var res = 0
    for(n <- 1 until 10000){
        var b:BigInt = n
        var s = b.toString
        var r = s.reverse
        var k = 0
        do{
            b = b + BigInt(r)
            s = b.toString
            r = s.reverse
            k += 1
        }while(!s.sameElements(r) && k <= 50)
        if(k > 50) res += 1
    }
    println(res)
}



问题56Considering natural numbers of the form, a^b, finding the maximum digital sum.
题目简介:记f(x)表示自然数x的各位数字之和,a^b表示a的b次方。对1≤a,b <100,求f(a^b)的最大值。
答  案:972
//Scala
    val nums = for(a <- 1 to 100;b <- 1 to 100) yield (a:BigInt).pow(b)
    nums.map{ _.toString.foldLeft(0){ _+_-'0' } }.foldLeft(0){ _ max _ }



问题57Investigate the expansion of the continued fraction for the square root of two.
题目简介:2的平方根有连分数的表示:√2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...
  展开其中的前四项为:
1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

  接下来的三项依次为:99/70, 239/169,577/408
  而第八项是1393/985,注意,这是第一个出现分子位数超过分母位数的项(分子是4位数,而分母是3位数)
  现在要求前1000项中,分子位数比分母位数多的个数。
答  案:153
object Euler057 extends Application {
    var res = 0
    var a = BigInt(1)
    var b = BigInt(1)
    for(n <- 1 to 1000){
        a = a + b + b
        b = a - b
        if(a.toString.length > b.toString.length) res += 1
    }
    println(res)
}



问题58
Investigate the number of primes that lie on the diagonals of the spiral grid.

题目简介:将自然数按如下方式逆时针排列:
      37 36 35 34 33 32 31
      38 17 16 15 14 13 30
      39 18 05 04 03 12 29
      40 19 06 01 02 11 28
      41 20 07 08 09 10 27
      42 21 22 23 24 25 26
      43 44 45 46 47 48 49
  其中标红色的表示出现在对角线上且为素数的自然数,注意对角线上一共有13个自然数,其中8个为素数。也就是说素数所占的比例为 8/13 ≈ 62%.
  将上述方阵继续排列下去,求使得对角线上素数比例小于10%的方阵的最小边长。
答  案:26241
object Euler058 extends Application {
    var ps:Stream[Int] = Stream.cons(2,
                             Stream.from(3).filter{ n =>
                                 ps.takeWhile(p => p*p <= n).forall(n%_ !=0)
                             })
    def isPrime(n:Int) = ps.takeWhile{ p => p*p<=n }.forall{ n%_ !=0 }
    
    val rate = 0.1
    var count = 1
    var primes = 0
    var size = 1
    var diag = 1
    do{
        size += 2
        for(loop <- 1 to 4){
            diag = diag + size -1
            if(isPrime(diag)) primes += 1
        }
        count += 4
    }while(primes >= count*rate)
    println(size)
}



问题59
Using a brute force attack, can you decrypt the cipher using XOR encryption?

题目简介:使用暴力破解一段使用异或方式加密的英文文本。
答  案:107359
import scala.io.Source._
object Euler059 extends Application {
    def isLetter(c:Int):Boolean = 
        " !\"'(),-.0123456789:;?ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz".indexOf(c) >= 0 
        
    var src = fromFile("cipher1.txt").getLine(1).split(",").map{ _.trim.toInt.toChar }.zipWithIndex
    var pw = for(idx <- 0 until 3)
                 yield 'a'.to('z').find{ c => src.filter{ _._2%3 == idx }.forall{ s => isLetter(s._1^c) } }.get
    var sum = src.foldLeft(0){ (n,s) => n + (s._1^pw(s._2%3)) }
    println(sum)
}



问题60Find a set of five primes for which any two primes concatenate to produce another prime.
题目简介:自然数3, 7, 109, 673有着非常奇特的性质:
   1.它们都是素数
   2.它们任意两个连接而成的数也是素数。比如7与3相连得到73是素数
   3.它们是满足上面两个性质并且使得和最小的一组数
  现在要求5个素数使得其中任意两个连接得到的数也是素数,并且使这5个数之和最小。
  输出这5个数之和
答  案:26033
import eastsun.math.Util._
import java.util.Arrays.binarySearch

object Euler060 extends Application {   
    //get primes below 100000000
    val primes = getPrimes(100000000)
    
    def isPrime(n:Int) = binarySearch(primes,n) >= 0
    
    //get intersection of la and lb,store in order
    def intersect(la:List[Int],lb:List[Int]):List[Int] = {
        var lx = la
        var ly = lb
        var ls:List[Int] = Nil
        while(!(lx.isEmpty || ly.isEmpty)){
            var ix = lx.head
            var iy = ly.head
            if(ix >= iy) ly = ly.tail
            if(ix <= iy) lx = lx.tail
            if(ix == iy) ls = ix::ls
        }
        ls.reverse
    }
    
    def find(ls:List[Int]):Int = {
        var min = Integer.MAX_VALUE
        def find0(lx:List[Int],sum:Int,depth:Int){
            if(lx.size < 4 - depth) return
            if(depth == 3) min = primes(lx.first)+ sum
            else lx.foreach{ x =>
                    find0(intersect(lx,items(x)),sum+primes(x),depth+1)
                 }
        }
        find0(ls,0,0)
        min
    }
    
    val size = primes.findIndexOf{ _ >= 10000 }
    val items = new Array[List[Int]](size)
    
    for(i <- 0 until size){
        var item = List[Int]()
        for(j <- i+1 until size){
            var a = primes(i)
            var b = primes(j)
            if(isPrime((a+""+b).toInt) &&
               isPrime((b+""+a).toInt) ) item = j::item
        }
        items(i) = item.reverse
    }
    
    var res = Integer.MAX_VALUE
    items.zipWithIndex.foreach{ iti =>
        var f = find(iti._1)
        if(f < Integer.MAX_VALUE && f + primes(iti._2) < res) res = f + primes(iti._2)
    }   
    println(res)    
}
分享到:
评论

相关推荐

    ProjectEuler 解题表格

    在提供的压缩文件“project_euler解题表格.docx”中,很可能是博主Linuke分享了他的Project Euler解题过程和经验。这个表格可能包含了他对各个问题的思考、代码实现以及解决问题所花费的时间,对于其他学习者来说是...

    下载Project Euler题目

    标题 "下载Project Euler题目" 暗示了这个压缩包可能包含了与解决Project Euler问题相关的Java源代码。Project Euler是一个在线平台,提供了大量的数学和计算机科学问题,旨在提高编程技能和数学理解。这些问题通常...

    ProjectEuler1-16代码

    【标题】"ProjectEuler1-16代码"所涉及的知识点主要集中在计算机编程和算法设计上,尤其针对初学者和编程爱好者。Project Euler是一个在线平台,它提供了一系列的数学和计算机科学问题,旨在通过解决这些问题来提升...

    Project Euler 第22题

    【标题】"Project Euler 第22题"是一个著名的编程挑战,源自Project Euler网站,这是一个鼓励人们通过编程解决数学和计算问题的在线平台。这道题目通常涉及到字符串处理、排序以及数学计算,旨在锻炼编程者的问题...

    project euler problem 5

    题目:Project Euler问题5——寻找最小公倍数 在Project Euler的问题集中,问题5要求我们找到能被1至20所有数字整除的最小正整数。这个问题实际上是在寻找这组数字的最小公倍数(LCM)。对于较小的参数值,如本例中...

    project euler1.rar_ACM_project_project euler

    【项目欧拉(Project Euler)】是一个非常受欢迎的在线数学和计算机编程挑战平台,它吸引着全球的程序员和数学爱好者参与。项目欧拉的问题通常涉及数学、算法和计算机科学,鼓励解决问题并学习新技能。本压缩包...

    project euler5.rar_ACM_project

    【标题】"project euler5.rar_ACM_project" 涉及的是ACM竞赛相关的编程项目,特别是Project Euler的第五部分。Project Euler是一个在线数学和计算机科学的挑战项目,旨在提高编程技能并解决复杂的数学问题。这个...

    project euler2.rar_ACM_project

    《ACM项目:Project Euler问题集解码》 在编程竞赛和算法研究领域,ACM(International Collegiate Programming Contest)项目具有极高的地位,而Project Euler则是其中一道独特的风景线。这个项目旨在挑战参赛者的...

    project euler3.rar_ACM_project

    《ACM项目:Project Euler第三部分解题代码详解》 Project Euler是一个著名的在线数学与计算机科学问题集,旨在挑战编程者的思维能力和算法技巧。在这个压缩包"project euler3.rar_ACM_project"中,包含了10个已经...

    Project Euler_Eulerproject_fasmg_x86_windows_math_

    《使用汇编语言解决Project Euler问题的探索》 在IT领域,编程挑战是提升技能、锻炼思维的重要方式,其中Project Euler以其独特的数学与计算机科学相结合的特性,深受程序员喜爱。本项目聚焦于"Project Euler",它...

    projecteuler.net:我对 Project Euler 问题的一些解决方案

    Project Euler 是一个在线平台,提供了一系列数学和计算机科学的挑战问题,旨在提高解题技巧,同时也为编程爱好者提供了练习和学习的机会。这个项目通常涉及到算法、数学和编程的结合,鼓励用户通过编写高效的代码来...

    matlab用不同编程语言实现的各种Project Euler问题的解决方案.zip

    《MATLAB实现Project Euler问题详解》 Project Euler是一个著名的在线数学和计算机科学挑战平台,它提供了许多具有挑战性的问题,旨在提升编程技能和数学理解。本资料包“matlab用不同编程语言实现的各种Project ...

    project euler欧拉工程1-50题代码golang版

    全部在linux下运行通过并得到结果,因为是个人所做,所以不保证是最优结果,仅供交流学习 因为是个人联系所做,所以代码中没有注释,不过我相信只要你真的有去思考题目也是能知道我为什么这样做 ...

    ProjectEuler:Project Euler 问题的解决方案

    "Project Euler: Project Euler 问题的解决方案"是一个与编程挑战相关的项目,主要集中在使用JavaScript解决数学和计算问题。Project Euler是一个著名的在线平台,它提供了一系列的数学和计算机科学问题,旨在提升...

    project-euler:多种语言的projecteuler.net问题解决方案

    《项目欧拉:多语言实现的ProjectEuler.net问题解决方案》 Project Euler是一个深受程序员喜爱的在线挑战平台,它提供了一系列涉及数学、计算机科学和算法的难题,旨在提高编程技能和解决问题的能力。这个名为...

    ProjectEuler:projecteuler.net

    欧拉计划(Project Euler)是一个在线平台,旨在通过一系列具有挑战性的数学和计算机科学问题来提升编程技巧。这些问题设计巧妙,通常需要运用到数学、算法和编程知识来解决。参与欧拉计划,不仅可以锻炼编程能力,...

    project-euler-solutions:我在 Project Euler 中所有问题的答案

    项目欧拉解决方案该存储库包含我对 Project Euler (projecteuler.net) 上发现的编程问题的所有答案。 每个解决方案都是用 Java 编写的,旨在从命令行运行。 解决方案文件中将提供指向相关欧拉问题的链接。 某些解决...

    Project-Euler:projecteuler.net 上问题的解决方案

    在编程世界中,Project Euler 是一个著名的在线平台,它提供了大量的数学和计算机科学问题,旨在通过挑战参与者解决这些问题来提高其编程和问题解决能力。这个压缩包“Project-Euler:projecteuler.net 上问题的解决...

    projecteuler-solutions:所有700多个Euler项目问题​​的数值答案

    顾名思义,projecteuler-solutions是站点Project Euler的解决方案的集合。 该站点旨在为Euler项目提供完整而准确的解决方案清单。这个网站的目的是什么? 在一个棘手的问题上奋斗了数小时或数天之后,您最终可能会...

    project-euler:我对projecteuler.net上问题的解决方案

    在这个压缩包“project-euler-master”中,很显然包含了作者对Project Euler问题的Python解决方案。 在Python编程语言中解决Project Euler问题,我们可以学习到许多关键的编程概念和技术。以下是一些可能涵盖的知识...

Global site tag (gtag.js) - Google Analytics