无聊的 dram 表示居然写这么无聊的题解。
http://uoj.ac/problem/8 Quine
写一个程序,使其能输出自己的源代码。
先来讲个笑话
$ cat quine.rb
quine.rb:1: syntax error, unexpected tINTEGER, expecting tSTRING_CONTENT or tSTRING_DBEG or tSTRING_DVAR or tSTRING_END
quine.rb:1: syntax error, unexpected tI...
^
$ ruby quine.rb
quine.rb:1: syntax error, unexpected tINTEGER, expecting tSTRING_CONTENT or tSTRING_DBEG or tSTRING_DVAR or tSTRING_END
quine.rb:1: syntax error, unexpected tI...
^
$ cat quine.py
File "quine.py", line 1
File "quine.py", line 1
^
IndentationError: unexpected indent
$ python quine.py
File "quine.py", line 1
File "quine.py", line 1
^
IndentationError: unexpected indent
$ cat quine.hs
[1 of 1] Compiling Main ( quine.hs, quine.o )
quine.hs:1:4: parse error on input ‘of’
$ ghc quine.hs
[1 of 1] Compiling Main ( quine.hs, quine.o )
quine.hs:1:4: parse error on input ‘of’
可惜 CE 是不能算 AC 的
正经内容
所以我们想要输出自己的源代码的话怎么办呢?
思路 1
cout << "cout << \"cout ...
程序需要无限长,失败。
思路 2
我们尝试构造一个字符串是整个程序的源代码
char s[] = "char s[] = ...;\ncout << s;\n";
cout << s;
程序需要无限长,失败。
思路 3
我们尝试构造一个字符串是程序的一部分的源代码
char s[] = "cout << s;";
cout << s;
输出不对,失败。
思路 4
思路 3 好像已经很接近了啊,如果这样行不行?
1. s = 2 3 两步的代码
2. 输出第 1 步的代码
3. 输出 s
等等,第 1 步的代码从哪里来呢?
咱不是有 s 么?
s='print "s="+repr(s)\nprint s'
print "s="+repr(s)
print s
什么?不会 python?See this C++
#include <stdio.h>
char s[] = {59,10,105,110,116,32,109,97,105,110,40,41,32,123,10,9,112,114,105,110,116,102,40,34,35,105,110,99,108,117,100,101,32,60,115,116,100,105,111,46,104,62,92,110,99,104,97,114,32,115,91,93,32,61,32,123,34,41,59,10,9,102,111,114,32,40,105,110,116,32,105,32,61,32,48,59,32,105,32,60,32,115,105,122,101,111,102,40,115,41,59,32,105,32,43,43,41,10,9,9,112,114,105,110,116,102,40,34,37,100,37,99,34,44,10,9,9,9,40,105,110,116,41,32,115,91,105,93,44,10,9,9,9,105,32,61,61,32,115,105,122,101,111,102,40,115,41,32,45,32,49,32,63,32,39,125,39,32,58,32,39,44,39,41,59,10,9,112,117,116,115,40,115,41,59,10,9,114,101,116,117,114,110,32,48,59,10,125,0};
// 上面那行是第一步
//(实现细节:第二行结尾的分号放在 s 里面了,就是那个 `59`)
int main() {
printf("#include <stdio.h>\nchar s[] = {"); // --+
for (int i = 0; i < sizeof(s); i ++) // |
printf("%d%c", // +-- 这部分大概相当于是第二步
(int) s[i], // |
i == sizeof(s) - 1 ? '}' : ','); // --+
puts(s); // ------ 第三步
return 0;
}
当然这段代码是跑不过的,因为被我加了注释。请删除注释后提交。
哦不对,请将这段代码的输出提交
哦不对,你们怎么能提交我的代码呢?
交互版
void submit(const char *str); // 交互库提供
void quine(); // 选手实现
要求:调用 submit
一次,参数是选手提交的源代码作为字符串。
多题合并版
可以修改一个程序,使得里面多出一个字符串是程序自己的源代码。
So?
编写一个程序,输出本身源代码的后缀数组。
除此之外为了进一步证明你确实有给 Quine 的后缀排序的超能力,请另外输出 n−1 个整数分别表示排序后相邻后缀的最长公共前缀的长度。
话说大家有什么好的方法么?比如不需要构造字符串之类的做法?
倒是有一个并卵的思路:写一个字符递增的或者增减性简单的代码
参考资料
主要是 http://www.madore.org/~david/computers/quine.html 一位 Quine 大神写的