教材全解_计算机科学导论

题目	题型
请比较并区分多项式可解问题和非多项式可解问题的复杂度。	问答
请重写算法（Y-X），使得它能保存X的值。算法如下：算法宏Y←X Y←0 while (X) { decr(X) incr(Y) }	问答
请重写算法，使得它在计算Z←X+Y的同时能保存X和Y的值。算法如下：算法宏Y←Y+X while (x) { decr(X) incr(Y) }	问答
请重写算法，使得它在计算Z←Y×X的同时能保存X和Y的值。算法如下：算法宏Y←Y×X TEMP←Y Y←0 while(X) { decr(X) Y←Y+TEMP }	问答
请重写算法，使得它在计算Z←YX的同时能保存X和Y的值。算法如下：算法宏Y←YX TEMP←Y Y←1 while(x) { decr(X) Y←Y×TEMP }	问答
给定一台带有一条指令（A，1，b，R，B）的图灵机和如下的磁带配置： ↓ … b 1 1 1 b … 请显示出磁带的最终配置。	问答
给定一台带有一条指令（A，b，b，R，B）的图灵机和如下的磁带配置： ↓ … b 1 1 1 b … 请显示出磁带的最终配置。	问答
给定一台带有5条指令（A，b，b，R，B），（B，1，#，R，B），（B，b，b，L，C），（C，#，1，L，C），（C，b，b，R，B)的图灵机和如下的磁带配置 ↓ … b 1 1 1 b … 请显示出磁带的最终配置。	问答
请显示给一个二进制中的非负整数加1的图灵机的状态图。例如，磁带的内容为(101)2它将被改成(110)2。	问答
请显示图灵机中对语句incr(X)的模拟，且当X=0时，给出正确的答案。	问答
请显示图灵机中对语句decr(X)的模拟，且当X=0时，给出正确的答案。	问答
请显示图灵机中对循环语句的模拟，当我们允许使用像#这样的其他符号时，该图灵机能改成可以保存X的原始值。	问答
请给出图灵机模拟宏X←0的状态转移图和程序。	问答
请给出图灵机模拟宏Y←X的状态转移图和程序。	问答
一台图灵机使用单个1来表示整数0，请说明整数n在此机器上是如何表示的。	问答
宏X1←0的歌德尔数是什么？	问答
宏X₂←2的歌德尔数是什么？	问答
宏X3←X1+X2的歌德尔数是什么？	问答
使用简单语言编写的宏来模拟下面的宏： Y←Y-X	问答
使用简单语言编写的宏来模拟下面的宏（X只能是0或1）： if (X) then { A1 } else { A2 }	问答

题目

题型

请比较并区分多项式可解问题和非多项式可解问题的复杂度。

问答

请重写算法（Y-X），使得它能保存X的值。算法如下：算法宏Y←X Y←0 while (X) { decr(X) incr(Y) }

问答

请重写算法，使得它在计算Z←X+Y的同时能保存X和Y的值。算法如下：算法宏Y←Y+X while (x) { decr(X) incr(Y) }

问答

请重写算法，使得它在计算Z←Y×X的同时能保存X和Y的值。算法如下：算法宏Y←Y×X TEMP←Y Y←0 while(X) { decr(X) Y←Y+TEMP }

问答

请重写算法，使得它在计算Z←YX的同时能保存X和Y的值。算法如下：算法宏Y←YX TEMP←Y Y←1 while(x) { decr(X) Y←Y×TEMP }

问答