用 Project Euler 學習 D

D 是一種系統程式語言。它的重點是將 C 和 C++ 的強大功能和高效能與 Ruby 和 Python 等現代語言的程式設計師生產力相結合。特別關注質量保證、文件、管理、可移植性和可靠性的需求。^[1]

Project Euler 是一個致力於一系列數學問題的網站，這些問題旨在透過計算機程式解決。每個問題都是根據“一分鐘規則”設計的，這意味著有效的實現將允許在效能適中的計算機上在一分鐘內獲得解決方案。^[2]

在這篇文章中，我選擇了一些問題，並向您展示如何用 D 語言解決它們。

• 我只選擇最簡單的，因為已釋出的解決方案可能會破壞問題。
  
• 目的是展示 D 語言的功能和強大之處，因此下面的程式碼可能不是解決這些問題的最佳方式。

開始之前

首先，我們需要一個 D 編譯器。
下面所有的例子都使用 dmd 2.0.32，您可以從官方網站下載它。
從 zip 檔案中解壓編譯器並嘗試編譯“Hello World”程式

//helloworld.d import std.stdio; void main() { writeln("Hello, world!"); }

如果您使用的是 Windows，只需執行類似以下內容

C:\dmd2\windows\bin\dmd.exe helloworld.d
helloworld.exe

問題 1

讓我們從問題 1開始

If we list all the natural numbers below 10 that are multiples of 3 or 5,
we get 3, 5, 6 and 9. The sum of these multiples is 23.

Find the sum of all the multiples of 3 or 5 below 1000.

這非常容易，答案是

$\sum _{i=1}^{\left\lfloor {\frac {999}{3}}\right\rfloor }3i+\sum _{i=1}^{\left\lfloor {\frac {999}{5}}\right\rfloor }5i-\sum _{i=1}^{\left\lfloor {\frac {999}{15}}\right\rfloor }15i$

這個方程可以用鉛筆和紙來解決。呃……等等。我們在討論程式語言，對吧？
也許從每個人在第一次嘗試時使用的常見方法開始會更好

//problem1_a.d import std.stdio; void main() { int sum = 0; for (int i = 1; i < 1000; ++i) { if (i % 3 == 0 || i % 5 == 0){ sum += i; } } writeln(sum); }

是的，當我解決第一個問題時，我就是這樣做的。
如果我當時對 D 語言更熟悉，它看起來會像這樣

//problem1_b.d import std.stdio; void main() { int sum; foreach (i; 1..1000) { if (i % 3 == 0 || i % 5 == 0){ sum += i; } } writeln(sum); }

與第一個版本有兩個區別

1. foreach 語句不僅更簡潔，而且更快。

   這裡速度可以忽略不計，但是您會發現當用 1×10⁸ 代替 1000 進行測試時，它可以節省大約 10% 的時間

2. 在 D 語言中，int sum 預設情況下被初始化為 0。

   如果您真的、真的不想初始化它，請使用 int sum = void;

D2 的標準庫 Probos 還提供了一個強大的演算法模組，可以讓你用一行程式碼來實現它。

//problem1_c.d import std.stdio, std.algorithm, std.range; void main() { writeln( reduce!("a + b")(0, filter!("a % 3 == 0 || a % 5 == 0")(iota(1, 1000, 1))) ); }

它不如第二個版本（problem1_b.d）快，但它比用其他語言（如python 或haskell）編寫的相應程式快。
如果您不知道這些函式是什麼意思，這裡有一個簡要的解釋

• !( ... )

  模板引數用 !(...) 而不是 <...> 括起來。Foo!(int) 在 D 語言中等於 C++ 中的 Foo<int>。

• reduce!("a + b")(0, range);

  對 range 中的元素進行求和並返回一個數字。

• filter!("a % 3 == 0 || a % 5 == 0")(range);

  找到 range 中滿足要求的所有元素並返回一個新的 range。

• iota(begin, end, step);

  構造一個 range，它遍歷 begin、begin + step、begin + 2 * step、...，直到但不包括 end。

給這些函式起別名會使程式碼更易讀。

auto numbers = iota(1, 1000, 1); alias filter!("a % 3 == 0 || a % 5 == 0", typeof(numbers)) filter1; alias reduce!("a + b") sum; writeln( sum(0, filter1(numbers)) );

請檢視官方網站上的這些頁面以獲取更多資訊。
演算法，模板，D 語言和 C++ 之間的模板比較

問題 2

問題 2:

Each new term in the Fibonacci sequence is generated by adding the previous two terms.
By starting with 1 and 2, the first 10 terms will be:
    1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
Find the sum of all the even-valued terms in the sequence which do not exceed four million.

這個單行函式式解決方案被拆分為多行，以便我可以在其中新增一些註釋

//problem2_a.d import std.stdio; import std.algorithm; import std.range; void main() { writeln( reduce!("a + b")( // the sum of all filter!("(a&1) == 0")( // the even-valued terms until!("a >= 4000000")( // which do not exceed four million recurrence!("a[n-1] + a[n-2]")(1, 2) // a Fibonacci sequence starting with 1 and 2 ) ) ) ); }

用直接遞迴來計算斐波那契數列是一個不好的做法^[3]，而當遞迴也被用來對數列求和時，情況就更糟了。

//problem2_b.d import std.stdio; int fib(int n) { if (n < 3) { return n; } else { return fib(n - 2) + fib(n - 1); } } int sumFib(int bound, int n = 1) { if (fib(n) > bound) { return 0; } else if (fib(n) & 1) { return sumFib(bound, n + 1); } else { return sumFib(bound, n + 1) + fib(n); } } void main() { writeln(sumFib(4_000_000)); }

如果您執行此程式，fib() 將在得到結果之前被呼叫 35563510 次。
這個數字是完全不可接受的，因為在 4,000,000 以下的數列中只有 32 個元素。

但令人驚訝的是，當改為模板遞迴時，程式可以得到極大的改進。

//problem2_c.d import std.stdio; import std.metastrings; template fib(int n) { static if (n < 3) { const fib = n; } else { const fib = fib!(n - 2) + fib!(n - 1); } } template sumFib(int bound, int n = 1) { static if (fib!(n) > bound) { const sumFib = 0; } else static if (fib!(n) & 1) { const sumFib = sumFib!(bound, n + 1); } else { const sumFib = sumFib!(bound, n + 1) + fib!(n); } } pragma (msg, ToString!( sumFib!(4_000_000) )); void main(){}

演算法完全相同。但是這些更改使所有內容都在編譯時完成。

• if -> static if
• return -> const
• writeln(...) -> pragma (msg, ...)

它比原始版本好得多，因為編譯器只編譯一次每個 fib!(n)（1 ≤ n ≤ 33）。
編譯器直接輸出結果，根本不需要執行程式。

問題 22

問題 22 被選中是因為它是第一個需要檔案和字串操作的問題

Using names.txt, a 46K text file containing over five-thousand first names, 
begin by sorting it into alphabetical order. Then working out the alphabetical 
value for each name, multiply this value by its alphabetical position in the 
list to obtain a name score.

For example, when the list is sorted into alphabetical order, COLIN, which is 
worth 3 + 15 + 12 + 9 + 14 = 53, is the 938th name in the list.
So, COLIN would obtain a score of 938 × 53 = 49714.

What is the total of all the name scores in the file?

import std.stdio, std.string, std.algorithm; void main() { string input = cast(string)std.file.read("names.txt"); auto words = split(input, ","); sort(words); int score(string s) { // a nested function return reduce!("a + b - 64")(0, s[1..length-1]); // remove quotation marks and calculate the alphabetical value } long sum; foreach (i; 0..words.length) { sum += (i + 1) * score(words[i]); } writeln(sum); }