能够输出自己的程序

xiaoee posted @ 2009年3月24日 01:40 in Coding My Mind with tags 代码 quine 程序 趣题 递归 证明 回文 算法 , 5099 阅读

      最近突然冒出一个想法:怎样写一个程序,它可以输出自己的源代码?

      我们都写过这个程序:

#include<stdio.h>
main() { printf("Hello, world");}

      它会输出:

Hello, world

      于是很自然地,要写出一个输出自己的程序,可以尝试这样写:

#include<stdio.h>
main() { printf("#include<stdio.h>\nmain() { printf(\"#include<stdio.h>\n main() { ...\") } ");}

      它会输出:

#include<stdio.h>
main() { printf("#include<stdio.h>
main() { ..."
) }

      你可以继续这样写下去,但你会发现自己已经陷入死循环了,写到printf那就得返回去加上一段。显然像上面这样是做不到的。是不是说这样的程序就不存在呢?答案是否定的,不仅写得出来,而且各种各样,五花八门的都有。

      一个很容易想到的办法是利用文件操作,像下面这样:

#include <stdio.h>

int main()

{

    FILE *fp;

    char ch;

    fp=fopen("self.c","r");

    ch=getc(fp);

    while(ch!=EOF){

       putchar(ch);

       ch=getc(fp);}

    return 0;

}

      其中self.c中就是本程序的源代码,这显然是可以做到的。

      还有一种方法就是调用操作系统本身的功能,在Windows下可以这样:

#include <stdio.h>

int main()

{

    char path[255];

    sprintf(path,"cmd.exe /c type \"%s\"",__FILE__);

    system(path);

    return 0;

}

      如果是在Unix或者Linux下,你可以调用终端,把type换成cat就行了。

      如果我们只有可执行的程序而没有源文件,上面的方法就不行了(当然后面一种方法还是可以的,但利用了typecat等外部程序)。那么怎样写出一个这样的程序,它不依赖外部文件或程序,而可以输出自己呢?

      在网上找了一下,才发现其实有很多这样的程序。

      原来我想得到的这种程序有个正式名称:Quine,这是由于logician Willard van Orman Quine这位老兄最先提出了这个概念。想想看,其实只要是一个完整的程序设计语言都可以实现这样的功能,因为任何图灵机都可以实现复制自我,程序设计语言也是一种图灵机,当然可以了。但我怎么也想不出,开始甚至觉得是否是不可能的。

      即使在刚看到最开始那样的实现方式的时候我就感到很惊讶了,当我看到各种各样只用程序本身实现输出自己的程序时,我简直是激动不已,太神奇了。
但经过仔细分析这些程序,可以发现它们的构造也是有规律可循的,构造它们需要的是逻辑而不是神奇。

      第一种方法是把代码当作字符串处理

      我觉得最简单清楚又能说明问题的代码是下面这样的:

char x[]="main() { int j; putchar(99); putchar(104); putchar(97);putchar(114); putchar(32);putchar(120); putchar(91); putchar(93);putchar(61); putchar(34); for(j=0; j<strlen(x); ++j)putchar(x[j]);putchar(34); putchar(59); putchar(10); for(j=0; j<strlen(x); ++j) putchar(x[j]);putchar(10); }";

main() { int j; putchar(99); putchar(104); putchar(97); putchar(114); putchar(32); putchar(120);putchar(91); putchar(93); putchar(61); putchar(34); for(j=0; j<strlen(x); ++j) putchar(x[j]);putchar(34); putchar(59); putchar(10); for(j=0 ; j<strlen(x); ++j) putchar(x[j]); putchar(10); }

但是上面的代码要求你只用两行写出来,第一行是对x的定义,第二行是mainx包含了下面main的代码。程序是这样执行的:

首先开始的10putchar输出:

char x[]=”

第一个循环输出字符串的内容:

main() { int j; putchar(99); putchar(104); putchar(97); putchar(114); putchar(32); putchar(120);putchar(91); putchar(93); putchar(61); putchar(34); for(j=0; j<strlen(x); ++j) putchar(x[j]);putchar(34); putchar(59); putchar(10); for(j=0 ; j<strlen(x); ++j) putchar(x[j]); putchar(10); }

接下来的3putchar输出:

“;

并换行。到这里程序就把x的定义部分输出完成了,接下来就是输出main了,别忘了字符串x的内容可就是main啊,所以通过后面一个循环就输出了main。最后输出换行,这样就成功地完成了输出自己。

      写这种程序的关键就是“用来保存后面代码的字符串也要被输出“。

      在C语言中,我们知道,用字符串表示完整的格式是很麻烦的,而且如果有换行字符串就不能保持原型了。这样为了避免上面程序必须写在两行的问题。

      于是又有下面这种方法:

#include <stdio.h>
char c[] = {0x7d,0x3b,0xa,0x69,0x6e,0x74,0x20,0x6d,0x61,0x69,0x6e,0x28,0x29,0xa,0x7b,0xa,0x20,0x20,0x20,0x20,0x70,0x72,0x69,0x6e,0x74,0x66,0x28,0x22,0x23,0x69,0x6e,0x63,0x6c,0x75,0x64,0x65,0x20,0x3c,0x73,0x74,0x64,0x69,0x6f,0x2e,0x68,0x3e,0x5c,0x6e,0x63,0x68,0x61,0x72,0x20,0x63,0x5b,0x5d,0x20,0x3d,0x20,0x7b,0x22,0x29,0x3b,0xa,0x20,0x20,0x20,0x20,0x66,0x6f,0x72,0x28,0x69,0x6e,0x74,0x20,0x69,0x3d,0x30,0x3b,0x69,0x3c,0x73,0x69,0x7a,0x65,0x6f,0x66,0x28,0x63,0x29,0x3b,0x2b,0x2b,0x69,0x29,0xa,0x20,0x20,0x20,0x20,0x7b,0xa,0x20,0x20,0x20,0x20,0x20,0x20,0x20,0x20,0x70,0x72,0x69,0x6e,0x74,0x66,0x28,0x22,0x30,0x78,0x25,0x78,0x2c,0x22,0x2c,0x63,0x5b,0x69,0x5d,0x29,0x3b,0xa,0x20,0x20,0x20,0x20,0x7d,0xa,0x20,0x20,0x20,0x20,0x70,0x72,0x69,0x6e,0x74,0x66,0x28,0x22,0x25,0x73,0x22,0x2c,0x63,0x29,0x3b,0xa,0x20,0x20,0x20,0x20,0x72,0x65,0x74,0x75,0x72,0x6e,0x20,0x30,0x3b,0xa,0x7d,};
int main()
{
    printf("#include <stdio.h>\nchar c[] = {");
    for(int i=0;i<sizeof(c);++i)
    {
        printf("0x%x,",c[i]);
    }
    printf("%s",c);
    return 0;
}

      看出来了吗?其实这个程序中把从数组结束时的};开始到最后都转换成16进制的ASCII码(用一般的文本编辑器就可以了)保存在c中,然后先以16进制方式输出一遍,又以字符串方式输出一篇,也可以完成输出自己;而且这样做可以保持一个比较好看点的格式了。

      总结一下,上面的程序有下面这种形式:

C=”Print(C=”);Print(C);Print(“)

Print(C)”

Print(C=”);Print(C);Print(“)

Print(C)

 

其实用的比较多的还有利用printf的格式输出:

main(){char *a="main(){char *a=%c%s%c;printf(a,34,a,34,10);}%c";printf(a,34,a,34,10);}

      把上面的代码写在一行上;其中3410分别是”(双引号)和换行符的ASCII码。看到它是怎样巧妙地把a这个字符串输出的吧。由于a中有%s,利用printf(a,a)这种格式输出a

    下面这个程序和上面一样,但是更简洁:

main(a){printf(a,34,a="main(a){printf(a,34,a=%c%s%c,34);}",34);}

 

      下面是一种利用宏的方法:

main(a){printf(a,34,a="main(a){printf(a,34,a=%c%s%c,34);}",34);}

      把宏代进去,可以发现其实和上面利用格式输出并没有本质的区别。


      最后来欣赏一位牛人写的程序吧。

      下面这个程序不仅可以输出自己,而且它代码本身还是回文的:

/**/char q='"',*a="*//**/char q='%c',*a=%c%s%c*/};)b(stup;]d[b=]d-852[b)--d(elihw;)q,a,q,q,2+a,b(ftnirps{)(niam;031=d tni;]952[b,",b[259];int d=130;main(){sprintf(b,a+2,q,q,a,q);while(d--)b[258-d]=b[d];puts(b);}/*c%s%c%=a*,'c%'=q rahc/**//*"=a*,'"'=q rahc/**/

     
上面的代码充分利用了/**/的作用。牛人还是很多的,即使像上面这样的代码也是很多的,你可以在这里:http://www.nyx.net/~gthompso/quine.htm

见到许多能输出自己的各种语言的代码。

 

 

bay__gulf618 说:
2009年4月10日 08:34

这个也可以
#include <stdio.h>
int main() { char self[] = "#include <stdio.h> %cint main() { char self[] = %c%s%c; printf(self, 10, 34, self, 34); return 0;}"; printf(self, 10, 34, self, 34); return 0;}

Avatar_small
xiaoee 说:
2009年4月10日 11:37

@bay__gulf618: 是的,上面也讲到了这种方法。

Head_small
皮贝贝 说:
2009年12月13日 01:57

我还是倾向于那个 通过os 打印当前文件的方式

Avatar_small
xiaoee 说:
2009年12月13日 11:54

@皮贝贝: 但是好像不够通用。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter