【出题】批处理中的位运算应用和提高

lhjoanna

最近刚到学校，这学期又不能上网了，只能抽空来网吧上会儿，这几天正好在看位的一些东西，感觉位用的好的话真的可以省不少时间。给大家出两道题练习一下吧。一道是关于Gray码的构造，在网上看到的。另一道是前段时间去复试时候的逻辑题，感觉蛮有意思，拿来给大家用批实现下。闲话不多说，看题：
【1】格雷码的构造(Gray码)
输入：m和n两个整数，这里限定这两个和加起来不能超过32(出于机器上能表示的最大二进制位数考虑)。
输出：m+n位格雷码，使得位置相邻两数的二进制表示只有一位之差。
格式：0到2^(n+m)-1的数输出为2^n * 2^m的矩阵。


举例：比如输入2和3，则就是生成5位格雷码。
资料：简单说格雷码是指一种遍历顺序，比如3位格雷码，3位二进制数有000-111八种状态，格雷码是构造一种遍历顺序，使得每两个相邻的状态只差一位，比如3位格雷码就是000 001 011 010 110 111 101 100，按这个顺序遍历，每两种状态间只改变一位。如果看不大明白，那大家到网上搜索相关资源吧。我刚搜了一下，百度百科中有(http://baike.baidu.com/view/358724.htm)，其中也介绍了二进制与格雷码的转换方法。
结果输出示例(附图):空间问题，我只截了3位和4位格雷码
注意：附件中的图像按照弯曲的S型看，第一行从头到尾，第二行从尾到头，第三行从头到尾...马上再过2个小时要到外地去一趟，没时间修改代码了，大家知道这个意思就好

【2】1-100共100个整数，第一遍时从1开始数，凡是奇数位都丢弃，偶数位剩下。如1、3、5...99丢弃，第一遍后剩下的是2、4、6...100。然后第二遍开始，同样是处于奇数位置的数丢弃，偶数位置的数留下。如2、6、10...丢弃，4、8、12...留下。这样每一轮都是把处于奇数位置的数丢弃，偶数位置的数留下。请大家用批处理编程来解出这样进行几轮会只剩一个数，剩下的那个是什么数？

附：做为纯数学逻辑题来算并不难算，但用批的话就考虑的多了，因为要进行很多轮，效率肯定是个问题。如果这个数不是100，而是更大呢。用位是个不错的方法，拿100个整数来说，用一位表示一种状态，1表示丢弃，0表示留下(或相反)，那么100个数就只需要100位，32位的系统上，100位也只需要4个整数变量，这要比定义100个变量节省很多时间。更重要的是，CPU中算逻部件所进行的加减乘除等运算都是通过加法器和移位器实现的，用位操作更底层，更快。当然，如果大家有更高效的方法，也欢迎一起拿来一起分享。

不知道题干说清楚了没有，哪里描述不太清楚的就跟帖说下。

lhjoanna

恩，是的，从1到给定数(这里假定100)的正整数序列，可以构建模型，不一定要写出筛选序列，我是方便大家看题目写出的。如果给定数太大，每一轮都写筛选结果看起来会很繁。当然，效率是考虑的问题！

lhjoanna

呵，当然算。思路很好啊，题干分析提炼后，直接找最接近给定数的2的最大次方就OK。
看来直接解结果的话，用位表示状态我是绕远了(考场上我要能想这么透彻就好了)
加分鼓励  嘿嘿~

lhjoanna

呵，是我没写清楚，输出格式为：0到2^(n+m)-1的数写成2^n * 2^m的矩阵，使得位置相邻两数的二进制表示只有一位之差。已经在顶楼修改，不过实质还是m+n位格雷码。
百度百科中有关于二进制和格雷码转换的介绍

lhjoanna

和它有点类似，不过约瑟夫环的出列序列可以提前设定，本题理论上肯定也可以设定复杂的丢弃方案，只是要保证能循环结束。

lhjoanna

第一题哪里不明白？
2位二进制的话，共四个数，00 01 10 11，但这个序列并不是格雷码，因为01到10变了2位，按格雷码的话，序列应该是00 01 11 10，这样就保证每两个相邻数之间二进制只改变一位。输出格式是2^m*2^n的矩阵

lhjoanna

汗，不好意思，应该是000 001 011 010 110 111 101 100，附件中的图像应该这样看，第一行从左向右，然后第二行从尾向前看，然后第三行再从左到右  这样按照弯曲的S型
三位格雷码的话，你可以把000 001 011 010 110 111 101 100 首尾相接，想象成循环队列一样，任何一个数开始循环一遍都可以。

010 到 101 这是三位都改变了
兄下面列出的三个序列，第三个不对，010重复了，没有100
正确的序列有：
000 001 011 010 110 111 101 100
001 011 010 110 111 101 100 000
011 010 110 111 101 100 000 001
010 110 111 101 100 000 001 011
110 111 101 100 000 001 011 010
111 101 100 000 001 011 010 110
101 100 000 001 011 010 110 111
100 000 001 011 010 110 111 101
......
当然，逆时针循环也可以，可以当成个首尾相接的循环队列

[ 本帖最后由 lhjoanna 于 2010-4-30 10:13 编辑 ]

lhjoanna

不好意思，马上要到外地去趟，没时间仔细看细节了，我运行了一下结果是正确的，先加分~嘿嘿