UOJ Logo dram的博客

博客

Quine 题解

2016-08-08 14:06:19 By dram

无聊的 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 大神写的

评论

sunxuehui
前排%
WrongAnswer
%%% 上次研究了一个万能Quine(其实一点也不万能): http://uoj.ac/submission/80061 这个代码交#8和交#100都能AC。
goodqt
http://uoj.ac/submission/73615 第一次山东省队集训,考试的时候看错了题,在考场上写的,题答题最后一个点要求输出意思为“输出本程序”的一行字,结果我把本程序输出了,没分。 我交的时候是最长代码,当时唯一一个除了quine还有其他功能的代码,可惜现在这两点都不是了。
pedrolee
%%% 总感觉和Y combinator有点像
3161906213
这样子后台是怎么进行测评的

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。