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

Project Euler解题汇总 061 ~ 070

程序员文章站 2022-03-13 19:16:05
...
问题61Find the sum of the only set of six 4-digit figurate numbers with a cyclic property.
object Euler061 extends Application {
    val fun = Array( (n:Int) => n*(n+1)/2,
                     (n:Int) => n*n,
                     (n:Int) => n*(3*n-1)/2,
                     (n:Int) => n*(2*n-1),
                     (n:Int) => n*(5*n-3)/2,
                     (n:Int) => n*(3*n-2)
                   )
    def getNum(i:Int):Seq[(Int,Int)] = {
        val st = Stream.from(1).map{ n => (fun(i)(n),i) }
        st.dropWhile{ _._1 < 1000 }.takeWhile{ _._1 < 10000 }
    }
     
    val num = (0 until 6).flatMap(getNum).toArray
    val lst = new Array[List[Int]](num.size)
    for(i <- 0 until num.size){
        val tail = num(i)._1%100
        val idx  = num(i)._2
        var xs:List[Int] = Nil
        for(j <- 0 until num.size){
            val it = num(j)
            if(idx != it._2 && tail == it._1/100) xs = j::xs
        }
        lst(i) = xs
    }
    
    def sum(n:Int):Int = {
        def sum0(t:Int,d:Int,xs:List[Int]):Int = {
            if(d == 6) return if(t==n) 0 else -1
            else{
                if(xs.contains(num(t)._2)) return -1
                val ys = num(t)._2::xs
                if(lst(t).exists{ sum0(_,d+1,ys) >=0 }){
                    num(t)._1 + lst(t).map{ sum0(_,d+1,ys) }.find{ _ >=0 }.get
                }
                else -1
            }
        }
        sum0(n,0,Nil)
    }
    
    println(Stream.from(0).map(sum).find{ _>=0 }.get)
}



问题62Find the smallest cube for which exactly five permutations of its digits are cube.
import java.util.Arrays.sort
import java.lang.Math.cbrt

object Euler062 extends Application {
    val MAX = 5
    var res = 345L
    var cnt = 0
    do{
        res += 1
        val cube = res*res*res
        val list = cube.toString.toArray
        sort(list)
        val uper = cbrt(list.foldRight(0L){ (c,s) => 10*s+c-'0' }).toLong
        cnt = 1
        var n = res + 1
        while(n <= uper){
            val array = (n*n*n).toString.toArray
            sort(array)
            if(list sameElements array) cnt += 1
            n += 1
        }
    }while(cnt != MAX)
    println(res*res*res)
}



问题63How many n-digit positive integers exist which are also an nth power?
import scala.Math._

object Euler063 extends Application {
    val MAX = (log(10)/(log(10)-log(9))).intValue
    var cnt = 0
    for(p <- 1 to MAX;n <- 1 to 9){
        val b = n:BigInt
        if(b.pow(p).toString.size == p) cnt += 1
    }
    println(cnt)
}



问题64How many continued fractions for N ≤ 10000 have an odd period?
import eastsun.math.Util._
object Euler064 extends Application {

    val res = 1.to(10000).filter{ continuedFractionOfSqrt(_,null) % 2 ==1 }.length
    println(res)
}



问题65
Find the sum of digits in the numerator of the 100th convergent of the continued fraction for e.

object Euler065 extends Application {
    def a(n:Int) = 
        if(n == 1) 2
        else if(n%3 == 0) 2*n/3
        else 1
    
    def b(n:Int):(BigInt,BigInt) = {
        var num:BigInt = a(n)
        var den:BigInt = 1
        for(i <- 1 until n){
            var t = num*a(n-i) + den
            den = num
            num = t
        }
        (num,den)
    }
     
    var (x,y) = b(100)
    var res = x.toString.map{ _-'0' }.foldLeft(0){ _+_ }
    println(res)
}



问题66
Investigate the Diophantine equation x^2 − D*y^2 = 1.

import eastsun.math.Util._
object Euler066 extends Application {
    val buf = new Array[Int](1000)
    var (res,max,d) = (2,3:BigInt,1)
    while(d <= 1000){
        val pd = continuedFractionOfSqrt(d,buf)
        if(pd > 0){
            val sq = Math.sqrt(d)
            var (x0,y0) = (sq:BigInt,1:BigInt)
            var (x1,y1) = ((buf(0)*sq+1):BigInt,buf(0):BigInt)
            val cnt = if(pd%2 == 1) 2*pd-1 else pd-1
            var idx = 1
            while(idx < cnt){
                var t = x1
                var a = buf(idx%pd)
                x1 = x1*a + x0
                x0 = t
                t  = y1
                y1 = y1*a + y0
                y0 = t
                idx += 1
            }
            if(x1 > max){
                max = x1
                res = d
            }
        }
        d += 1
    }
    println(res)
}



问题67
Using an efficient algorithm find the maximal sum in the triangle?

import scala.io.Source._

object Euler067 extends Application {
    val num = fromFile("triangle.txt").getLines.map{ line =>
                   line.split("\\s+").map{ _.toInt }
              }.toList.toArray
    val path = new Array[Array[Int]](num.length)
    
    for(i <- 0 until path.length) path(i) = new Array[Int](i+1)
    
    for(i <- 0 until path.length) path(num.length-1)(i) = num(num.length-1)(i)
    
    for{row <- (path.length - 2) to 0 by -1;
        col <- 0 to row 
    } path(row)(col) = num(row)(col) +path(row+1)(col).max(path(row+1)(col+1))
    
    println(path(0)(0))
}



问题68What is the maximum 16-digit string for a "magic" 5-gon ring?
import eastsun.math.Util._

object Euler068 extends Application {
    val its = Array.range(1,10)
    val buf = new Array[Int](10)
    buf(0) = 10
    do{
        Array.copy(its,0,buf,1,9)
        val sum = buf(8)+buf(9)+buf(1)
        val tag = 0.until(8,2).forall{i => buf(i)+buf(i+1)+buf(i+3) == sum}
        if(tag){
            val idx = 0.until(10,2).foldLeft(0){ (i,j) => if(buf(i)<buf(j)) i else j }
            val num = idx.until(idx+10,2).map{ i =>
                          buf(i%10)+""+buf((i+1)%10)+""+buf((i+3)%10)
                      }.mkString("")
            println(num)
        }
    }while(nextPermutation(its))
}




问题69Find the value of n ≤ 1,000,000 for which n/φ(n) is a maximum.
import eastsun.math.Util._
object Euler069 extends Application {
    var res = getPrimes(1000).foldLeft(1){(s,p) => if(s*p <= 1000000) s*p else s}
    println(res)
}




问题70Investigate values of n for which φ(n) is a permutation of n.
import eastsun.math.Util._
import java.util.Arrays.binarySearch
import scala.util.Sorting._

object Euler070 extends Application {
    val MAX = 10000000
    val primes = getPrimes(MAX)
    def isPrime(n:Int) = binarySearch(primes,n) >= 0
    val phi = new Array[Int](MAX)
    phi(1) = 1
    var n = 2
    var rate = 0.0
    var res = 0
    while(n < MAX){
        if(isPrime(n)) phi(n) = n - 1
        else{
            var idx = 0
            while(n%primes(idx) != 0) idx += 1
            val p = primes(idx)
            val s = n/p
            phi(n) = if(s%p == 0) phi(s)*p else phi(s)*(p-1)
        }
        if(phi(n) > n*rate){
            val pa = phi(n).toString.toArray
            val pn = n.toString.toArray
            quickSort(pa)
            quickSort(pn)
            if(pa sameElements pn){
                rate = phi(n).floatValue/n
                res = n
            }
        }
        n += 1
    }
    println(res)
}