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

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中算逻部件所进行的加减乘除等运算都是通过加法器和移位器实现的，用位操作更底层，更快。当然，如果大家有更高效的方法，也欢迎一起拿来一起分享。

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

hanyeguxing

第二题是否是从1到n的正整数列？是否可以直接建立数学模型？是否每次必须给出筛选的结果？

[ 本帖最后由 hanyeguxing 于 2010-4-29 20:51 编辑 ]

lhjoanna

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

hanyeguxing

第二题：

@echo off
set n=100
:hanye
set/a a+=1,b=1^<^<a
set/p=第%a%次筛选后:<nul
for /l %%i in (%b%,%b%,%n%) do set/p= %%i<nul&set d=%a%
echo.
if %a%==%d% goto:hanye
set/a c=1^<^<d
echo.%d%次筛选.值为%c%
pause
复制代码

不知道这样算不算，嘿嘿

@echo off
set n=100
:hanye
set/a a+=1,b=1^<^<a
if %b% leq %n% goto:hanye
set/a a-=1,b=1^<^<a
echo.%a%次筛选.值为%b%
pause
复制代码

[ 本帖最后由 hanyeguxing 于 2010-4-29 21:26 编辑 ]

lhjoanna

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

Seter

[1]看不懂跳过
[2]嘛,LS也说了是2的最大幂[貌似小学里的益智题做过]...如果C的话我宁愿先log再pow...如果批的话则将1依次左移1位...如果高精的话我想先把最大的那个数转成二进再降位后全变成1,然后再转成十进...完毕

sgaizxt001

第2题我以为是约瑟夫环的类型，不过如果按照我的想法来，结果是28。所以不对，继续思考

[ 本帖最后由 sgaizxt001 于 2010-4-30 00:00 编辑 ]

523066680

昨天我也没看出来    ，还有1楼的两张图分 M  N，并不能体现m n 的作用区别
只能看出来  一个加起来3位 ， 一个加起来4位。
既然是最终采用加起来的表示位数，为什么不用同一个和来表示呢？ 这个把我弄的晕晕的。

点入了百度百科 ， 按位异或是这句：
异或:异或则是按位“异或”，【相同为“0”，相异为“1”。】

[ 本帖最后由 523066680 于 2010-4-30 09:06 编辑 ]

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的矩阵

qzwqzw

比如3位格雷码就是000 001 011 010 100 101 111 110，按这个顺序遍历，每两种状态间只改变一位

010 101也是只改变一位吗？
是不是改这样
000 001 011 010 110 111 101 100
000 100 110 111 101 001 011 010
000 010 110 111 101 001 011 010
……

Spring

::按照定义描述编码
@echo off
set /p m=请输入m:
set /p n=请输入n:
set /a l=m+n
rem echo 位数: %m%+%n%=%l%
title %l%位的格雷码
set /a sup=1^<^<%l%
set /a sup-=1
set /a l-=1
rem echo 最大值: %sup%
setlocal enabledelayedexpansion
rem 一行输出信息
set "Spring="
set /a Bother=1^<^<n
for /l %%z in (0,1,%sup%) do (
  rem 获取二进制代码
  rem 不知道批处理怎么取二进制，我只能一位一位地凑
  set "BinCode="
  for /l %%i in (0,1,%l%) do (
		set /a y=1^<^<%%i
    set /a x=%%z^&!y!
    if !x! gtr 0 (
      set "BinCode=1!BinCode!"
    ) else (
      set "BinCode=0!BinCode!"
    )
  )
  rem echo %%z 的二进制代码 !BinCode!
  rem 二进制转换格雷码
  set /a n1=!BinCode:~0,1!
  rem 根据定义，第一位不变
  set "GrayCode=!n1!"
  rem 后面的每位分别是这位的值与前以为的异或XOR
  for /l %%i in (1,1,%l%) do (
    set /a n2=!BinCode:~%%i,1!
    set /a x=!n2!^^^^!n1!
    set "GrayCode=!GrayCode!!x!"
    set /a n1=!n2!
  )
  rem echo %%z 的格雷码 !GrayCode!
  rem 下面是输出信息控制
  set "Spring=!Spring! !GrayCode!"
  set /a flag=%%z
  set /a flag+=1
  rem 按题中样式%Bother%个一行
  set /a flag=!flag!%%%Bother%
  if !flag! equ 0  (
    echo !Spring!
    set "Spring="
  )
)
endlocal
pause>nul
复制代码

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

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