2006/11/29

第一個 Quine

今天下午的自動機與形式語言,在黑板上畫了三節的 Turing machine programming。我直接往後面讀,Sipser 第六章是 "Advanced Topics in Computability Theory",裡面第一節是 Recursion Theorem。以前就曾看到這裡,但沒完全看懂。這次終於理解並拼出生平第一個 quine 程式(in Standard C++),貼在下面作為紀念 XD(欄寬 80 字元):

#include <iostream>
#include <string>
using namespace std;
int main() {
string s = "string t(s);\nfor (string::size_type i = 0; i < t.size(); ++i) {\nsw
itch (t[i]) {\ncase '\\\\':\nt.replace(t.begin() + i, t.begin() + (i + 1), \"\\\
\\\\\\");\n++i;\nbreak;\ncase '\"':\nt.replace(t.begin() + i, t.begin() + (i + 1
), \"\\\\\\\"\");\n++i;\nbreak;\ncase '\\n':\nt.replace(t.begin() + i, t.begin()
 + (i + 1), \"\\\\n\");\n++i;\nbreak;\n}\n}\ncout << \"#include <iostream>\\n#in
clude <string>\\nusing namespace std;\\nint main() {\\nstring s = \\\"\" << t <<
 \"\\\";\\n\" << s;\n}\n";
string t(s);
for (string::size_type i = 0; i < t.size(); ++i) {
switch (t[i]) {
case '\\':
t.replace(t.begin() + i, t.begin() + (i + 1), "\\\\");
++i;
break;
case '"':
t.replace(t.begin() + i, t.begin() + (i + 1), "\\\"");
++i;
break;
case '\n':
t.replace(t.begin() + i, t.begin() + (i + 1), "\\n");
++i;
break;
}
}
cout << "#include <iostream>\n#include <string>\nusing namespace std;\nint main(
) {\nstring s = \"" << t << "\";\n" << s;
}

Recursion theorem 在 computability theory 上佔有重要地位,指出任何程式執行時都可以取得自己的源碼(讀檔案不算 XD)然後任意處理。Quine 做的只是在取得源碼後單純印出,只是小小應用 XD。

--
先不縮排,才不用辛苦算空格 XD。