XQuery/Project Euler
< XQuery
Project Euler 是一个数学问题的集合。目前有 166 个问题，所以可能需要一些时间才能解决所有问题 :-).
将所有小于 1000 的自然数中是 3 或 5 的倍数的数加起来。
sum ((1 to 999)[. mod 3 = 0 or . mod 5 = 0])
求所有不超过一百万的斐波那契数列中的偶数项之和。
declare function local:fib($fibs,$max) {
let $next := $fibs[1] + $fibs[2]
return
if ($next > $max)
then $fibs
else local:fib(($next,$fibs),$max)
};
sum( local:fib((2,1),1000000)[. mod 2 = 0])
这种暴力破解方法递归地（反向）构建斐波那契数列到最大值，然后过滤并求和结果。
数字 317584931803 的最大素数因子是多少？
首先我们需要得到一个素数列表。被称为埃拉托斯特尼筛法的算法可以在 XQuery 中直接表达
declare function local:sieve($primes as xs:integer*,$nums as xs:integer* ) as xs:integer* {
if (exists($nums))
then
let $prime := $nums[1]
return local:sieve(($primes,$prime), $nums[. mod $prime != 0])
else $primes
};
<result>
{ local:sieve( (), 2 to 1000 ) }
</result>
素数列表从空开始，数字列表从整数开始。local:sieve 的每个递归调用都将剩余整数中的第一个作为新的素数，并将整数列表缩减为那些不能被素数整除的整数。当整数列表耗尽时，返回素数列表。
数字 N 的因式分解也可以很容易地表示为 N 的素数子集
declare function local:factor($n as xs:integer ,$primes as xs:integer*) as xs:integer* {
$primes[ $n mod . = 0]
};
因此
let $n:= xs:integer(request:get-parameter("n",100))
let $max := xs:integer(ceiling($n div 2))
let $primes := local:sieve((),2 to $max)
return
<result>
{ local:factor($n,$primes) }
</result>
最大的是
max (local:factor($n,$primes))
不幸的是，这种优雅的方法对于像问题中那样大的整数来说，会耗尽空间和时间。
求由两个三位数的乘积组成的最大回文数。
declare function local:palindromic($n as xs:integer) as xs:boolean {
let $s := xs:string($n)
let $sc := string-to-codepoints($s)
let $sr := reverse ($sc)
let $r := codepoints-to-string($sr)
return $s = $r
};
max(
(for $i in (100 to 999)
for $j in (100 to 999)
return $i * $j)
[local:palindromic(.)]
)
运行 [ 耗时 20 秒 ]
从 1 到 100 的整数中，平方和与和的平方之间的差是多少？
declare function local:diff-sum($n as xs:integer) as xs:integer) {
sum (1 to $n) * sum(1 to $n)
- sum( for $i in 1 to $n return $i * $i )
};
local:diff-sum(100)
这种糟糕的暴力破解方法可以用一个使用熟悉公式的显式表达式来代替
declare function local:diff-sum($n as xs:integer) as xs:integer {
let $sum := $n * ($n + 1) div 2
let $sumsq :=( $n * ($n+1) * (2 * $n +1) ) div 6
return $sum * $sum - $sumsq
};
local:diff-sum(100)