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)