【出题】批处理输出n阶幻方

lhjoanna

所谓n阶幻方：1-n^2个数排为n行n列，横、竖、对角线相加和相同。
  输入：幻方阶数n (暂限制为奇数阶)
  输出：n行n列的方阵，横、竖、对角线相加和相同。
  举例：5阶幻方，横、竖、对角线相加和为65

17 24  1  8 15
23  5  7 14 16
4  6 13 20 22
10 12 19 21  3
11 18 25  2  9

lhjoanna

恩，幻方生成规则知道了，代码也就不难了。^_^

lhjoanna

是不是太难了，怎么没人贴代码来？可以先到网上搜索一下奇次幻方的构造规律，然后再转化为代码就相对容易些了！

lhjoanna

哦？我刚搜了下没搜到啊。slore兄不妨把那帖子链接贴来，看能不能激发些灵感想出些不同的方法。

lhjoanna

呵，我发现什么帖子都逃不过batcher的眼睛啊~此链接中楼主所说的九宫格就是三阶幻方，又看到了namejm的精彩代码~~不过此题要求是n阶幻方(暂定为奇数阶)，下面11楼 pengfei所上传的附件sigil.exe符合此题题意。虽然没提供代码，但是提供了算法。大家尝试着看谁能写出代码？

lhjoanna

Re:more
      结果符合幻方的要求，代码也不错，在此基础上提些小建议(供参考)：
   1、对于大于3的要求我觉得不必，因为1阶幻方也是幻方，只不过所含的元素只有一个而已，可以统一起来考虑；
   2、对于输入的限制，兄所用的方法是判断最后一位是否奇数，对于要求不高的情况可以满足，但如果要求苛刻些，比如输入a3、12a5等情况，可能会出错。最好还是用完全匹配来限制输入；
   3、对于算法的实现，我没有仔细的验证，应该没问题，毕竟结果正确，并且也符合了行++，列- -，到边的话首尾相接，元素已存在的话放到正下方 等规则；
   4、输出结果正确，再加上对齐就完美了。^_^

Re：tyc
      不知兄用的什么语言，我还真没用过，不过我基本看懂了，一些语法的问题我就无从知晓了，不过算法是正确的。其实对于输出幻方来说，实现起来这样的高级语言比批处理容易些，因为数组类型是内置的，而批处理则需要自己构建一个类似的二维数组来方便操作；此题要求是用批处理来实现，所以希望兄闲暇时也考虑下用批处理来实现~不管怎么说，毕竟动了一番脑子，加分鼓励^_^

lhjoanna

Re:more
      呵，结果是可以对齐了，只是代码是不是繁了点。不需要在赋值的过程中多次调用duiqi，可以在赋值完毕后统一调整格式(包括1)。
   在兄11楼代码基础上修改：

@echo off&setlocal enabledelayedexpansion
:bgn
echo.&set input=&set /p input=请输入一个单数(回车退出):
if not defined input goto :eof
cls
echo %time%&echo.
echo.%input%|findstr /v "^[0-9]*$" >nul&&(echo.请输入纯数字!!!&goto :bgn)
echo.%input:~-1%|findstr "[^13579]" >nul&&(echo.请输入单数...&goto :bgn)
set /a num1=(%input%*%input%+1)*%input%/2,num2=%input%*%input%
echo.%input%阶幻方各行,列以及对角线相加的和为:%num1%
set /a lie=%input%/2+1,hang=1,all=1
set h1l%lie%=1
:agn
set /a hang-=1,lie+=1,all+=1
if %hang% lss 1 set hang=%input%
if %lie% gtr %input% set lie=1
if defined h%hang%l%lie% (set /a hang+=2,lie-=1)
set h%hang%l%lie%=%all%
if "%hang%"=="1" (
   if "%lie%"=="%input%" (
     set /a hang+=1,all+=1
     call set h%%hang%%l%lie%=%%all%%
   )
)
if %all% geq %num2% goto :show
goto :agn
 
:show
call :duiqi
echo.
for /l %%a in (1 1 %input%) do (
  for /l %%b in (1 1 %input%) do (
    call set/p=%%h%%al%%b%% <nul
    set "h%%al%%b="
  )
  echo.
)
echo %time%&echo.
goto :bgn
 
:duiqi
for /l %%a in (1 1 !input!) do (
  for /l %%b in (1 1 !input!) do (
   if !h%%al%%b! lss 10 set "h%%al%%b= !h%%al%%b!"
   if !input! gtr 10  (
        if !h%%al%%b! lss 100 ( set "h%%al%%b= !h%%al%%b!")
   )
  )
)COPY

附：一点改进的建议
   1、可以考虑不用二维变量来实现，直接用一维变量即可。即h%hang%l%lie%可以用类似h%var%来实现；这样做的好处有：1>精简代码，方便调试；2>提高效率，使用二维变量，在输出时就要2个for嵌套，时间复杂度会达到平方级，且变量的设立与空间分配也要多出一倍。
    2、我用19阶幻方输出做为测试。二维变量的情况下运行时间为1.3~1.4s，而一维变量的情况下只需要0.4~0.5s。虽然不同机子上时间不相同，但同一台机子上，同种情况下的对比结果还是能说明一些问题的。

[ 本帖最后由 lhjoanna 于 2009-4-2 20:44 编辑 ]

lhjoanna

Re：随风
     从兄的代码中又学了不少，变量清空操作只需要endlocal就可以代替几行语句；并且输出时赋值给变量，按行输出确实比按个输出节省了不少时间(特别是阶数很高的情况下)；兄能否考虑下用一维的变量来实现，这应该也是提升效率的一个方法。

lhjoanna

呵，指点谈不上，说讨论更贴切些~~说实话，一维变量是我编出来的，官方没有这样的说法,举个例子，类似.%%a%%b我称它为二维的，而对比下 .%%a就是一维了。感觉这样说简炼些^_^
        我的算法也就是兄所说的楼梯法，更确切些叫罗伯法。这是目前比较容易的构造方法了。我也一直在思考效率的提高问题，在目前的这个算法下，我也只想到把变量改为一维(暂称)的可以提高一些效率，我的代码在下面，还请兄帮忙测试或者改进下！

@echo off
:begin
 setlocal enabledelayedexpansion
 color 0c
 cls
 echo.&echo  本程序功能为输出n阶幻方！
 echo.&echo  所谓n阶幻方：1-n^^2个数排为n行n列；
 echo.&echo  要求：横、竖、对角线相加和相同。
 echo.&echo  算法：loubere法
 echo.&set /p "n= 请输入方阵阶数(奇数):"
 echo !n!|findstr "^[1-9]*$">nul || (echo.& echo  Non-Numberic & pause>nul & goto begin)
 set /a a=n%%2
 if !a! equ 0 echo.&echo  Non-Odd & pause>nul & goto begin
 cls
 echo.&echo %time%
 set /a "sum=(1+n*n)*n/2"
 echo.&echo  !n!阶幻方横、竖、对角线相加和为 !sum!
 echo.
 set /a square=n*n,i=1,j=(n+1)/2,loc=j
 set ".!loc!=1"
 for /l %%i in (2 1 !square!) do (
     set /a "i=(i-1)%%n,j=(j+1)%%n"
     if !i! equ 0 set /a i=n
     if !j! equ 0 set /a j=n
     set /a "loc=n*(i-1)+j"
     if defined .!loc! ( 
         set /a "i=(i+2)%%!n!,j=(j-1)%%n"  
         if !i! equ 0 set /a i=n
         if !j! equ 0 set /a j=n
         set /a "loc=n*(i-1)+j"
     )
     set .!loc!=%%i
  rem echo  i:!i!,j:!j!,loc:!loc!,.loc:%%i
 )
 
 call :unify
 
 for /l %%i in (1 1 !square!) do (
     set /a "c=%%i%%n"
     set "result=!result! !.%%i!"
     if !c! equ 0 echo !result!&set "result="
 )
echo.&echo %time%&echo.
 pause>nul&endlocal&goto begin
 
:unify
 for /l %%i in (1 1 !square!) do (
     if !.%%i! lss 10 set ".%%i= !.%%i!"
     if !n! gtr 10  (
        if !.%%i! lss 100 ( set ".%%i= !.%%i!")
     )
 )
 goto :eofCOPY

lhjoanna

要存储n^2个数，就要建立n^2个变量，我是用.1-.n^2来表示这n^2个数的，所以set /a "loc=n*(i-1)+j这句也就是计算当前的数在幻方整个n^2个数中的位置。这样也就代替了用.%%a%%b构建行、列的情况。
     兄说到的那个问题，我想这种情况是不可能出现的，目标数的下一行对应的数不可能被占用。我想数学家罗伯在构思这种幻方构造法时如果发现目标数下一行对应的数会出现被占用的可能，那么在构造规则中就会声明这种情况的处理办法了。我仔细观察了19阶幻方，用此法构建确实不会出现上述情况，可能数学能力有限，我很难用数学语言严谨的表达出来。不过设想下19阶幻方第一行与最后一行相接，第一列与最后一列相接，会出现一个球，那么从1开始连线，你会发现1-19的连线划过的区域是此球最大的圆周，并且假设单位为1，则此圆的周长就是19单位，而此连线只经过了18单位，因为在继续到第19单位时，此位置已经有1占了。所以转到第二个圆周，此第二个圆周与第一个圆周之间的夹角为(360/19)°，这样连续转19次，也就满了360°，即画了19个最大圆，并且每个圆都是不封闭的，每个圆都不相交(因为每将要到相交的地方，就会跳到下一个圆周)，这样看来下一个圆周的第一个位置是永远不会被占的。拿19阶幻方为例，从1-361相连，你会发现是一条不间断的空间曲线，并且361的下一个就是1。361与1衔接，成功的构造了一个球体。只是这个球体的表面是不光滑的，有间隔的凹陷。在此构造过程中，幻方的各个元素在逆时针旋转，而构成的圆周(纵向来看)是顺时针转动的。由此猜想：抛开球体看，只看1-n^2的连线，阶数越高，此连线也接近球体。既然如此接近球体，那么此曲线的方程(坐标由幻方的各个元素构成)和球体的方程(x-a)²+(y-b)²+(z-c)²=R²有千丝万缕的联系。又一猜想：说不定幻方的方程(猜测：f(x,y,z)=n²)当n(阶数)趋于无穷时，幻方的方程也就等于球的方程(或类球方程)。
     呵，大晚上的容易乱想，想了一堆，还没有在网上找到类似支持的理论，只做一种猜测吧！

lhjoanna

呵，我上面写的一些也只是自己的猜测而已，没有一些理论的支持。说实话，我之前对兄的那段loop循环也是一知半解，不过现在明白了，这样修改以后效率提高很多啊，比我的效率也要高一点。这也就说明了我对于一维变量提高效率的说法是不准确的。看来还要自己多研究，不能仅凭想法臆断！多谢兄~

lhjoanna

下午偶然从MATLAB上找到了构造幻方的源代码，是用MATLAB程序设计语言实现的(基于C语言设计)，可以生成阶数不限的幻方。下午把此算法用批处理实现了。下面附上批版代码以及magic(n)函数源代码。

@echo off
:begin
 setlocal enabledelayedexpansion
 set rank=
 echo.&set /p "rank=请输入幻方阶数:"
 set /a remainder=rank%%2
 if !remainder! equ 1 (
    call :odd !rank!
 ) else (
     set /a remainder=rank%%4
     if !remainder! equ 0 ( 
        call :even_4
     ) else call :even_2
   )
rem --------------奇数阶幻方------------------
 
:odd
 set rank=%1
 call :create
 for /l %%i in (1 1 !rank!) do (
     for /l %%j in (1 1 !rank!) do (
         set /a $%%i%%j="(.%%i%%j+.%%j%%i-(rank+3)/2+rank)%%rank"
         set /a #%%i%%j="(.%%i%%j+.%%j%%i*2-2+rank)%%rank"
         set /a _%%i%%j="rank*$%%i%%j+#%%i%%j+1"
     )
  )
 if not "%~2" equ "" goto :eof
 call :output
 endlocal&goto :begin
rem -------------偶数阶幻方(4整除)---------------
 
:even_4
 call :create
 set num=0
 for /l %%i in (1 1 !rank!) do (
     for /l %%j in (1 1 !rank!) do (
         set /a "a=(.%%i%%j%%4)/2,b=(.%%j%%i%%4)/2"
         if !a! equ !b! ( set "_%%i%%j=1" ) else set "_%%i%%j=0"
         set /a "num+=1,n=rank*rank+1"
         set /a #%%i%%j=!num!
         if !_%%i%%j! equ 1 (set /a _%%i%%j=n-#%%i%%j) else set _%%i%%j=!#%%i%%j!
     )
 )
 call :output
 endlocal&goto :begin
rem --------------偶数阶幻方(2整除)--------------
 
:even_2
 set /a p=rank/2,q=rank,p1=p+1
 call :odd !p! OK
 set rank=!q!
 call :rearrange 1 !p! !p1! !rank! 2
 call :rearrange !p1! !rank! 1 !p! 3
 call :rearrange !p1! !rank! !p1! !rank! 1
 call :transpos !p!
 if !rank! equ 2 (
   call :output
   endlocal&goto :begin
 )
 for /l %%i in (1 1 !p!) do set "var_i=!var_i! %%i" 
 set /a k=(rank-2)/4,m=rank-k+2
 for /l %%i in (1 1 !k!) do set "var_j=!var_j! %%i"
 for /l %%i in (!m! 1 !rank!) do set "var_j=!var_j! %%i"
 call :exchange "!var_i!" "!var_j!"
 set /a i=k+1
 set "j=1 !i!"
 call :exchange "!i!" "!j!"
 call :output
 set i=
 set j=
 set var_i=
 set var_j=
 endlocal&goto :begin
 
rem -------------以下为子函数-----------------
 
:create
 set /a rank_2=rank*rank,i=1,j=1
 for /l %%i in (1 1 !rank_2!) do (
       set .!i!!j!=!j!
       set /a j+=1
       if !j! gtr !rank! set j=1&set /a i+=1
 )
 goto :eof
 
:output
  call :append !rank!
  for /l %%i in (1 1 !rank!) do (
     for /l %%j in (1 1 !rank!) do set result=!result! !_%%i%%j:~-3!
     echo.!result!&set result=
  )
  goto :eof
 
:rearrange
 set /a p2=%5*p*p,i=1,j=1
 for /l %%i in (%1 1 %2) do (
     for /l %%j in (%3 1 %4) do (
         set /a _%%i%%j=_!j!!i!+p2
         set /a j+=1
     )
     set /a "i+=1,j=1"
 )
 goto :eof
 
:exchange
 for %%i in (%~1) do (
     for %%j in (%~2) do (
         set /a i=%%i+p
         set tmp=!_%%i%%j!
         call set _%%i%%j=%%_!i!%%j%%
         set _!i!%%j=!tmp!
     )
 )
 goto :eof
 
:transpos
 for /l %%i in (1 1 %1) do (
     for /l %%j in (%%i 1 %1) do (
         if not %%i equ %%j (
            set tmp=!_%%i%%j!
            set _%%i%%j=!_%%j%%i!
            set _%%j%%i=!tmp!
         )
     )
 )
 goto :eof
 
:append
  for /l %%i in (1 1 %1) do (
     for /l %%j in (1 1 %1) do (
         set "_%%i%%j=   !_%%i%%j!"
     )
  )
  goto :eofCOPY

函数magic(n);

function M = magic(n)
%MAGIC  Magic square.
%   MAGIC(N) is an N-by-N matrix constructed from the integers
%   1 through N^2 with equal row, column, and diagonal sums.
%   Produces valid magic squares for all N > 0 except N = 2.

%   Copyright 1984-2002 The MathWorks, Inc.
%   $Revision: 5.15 $  $Date: 2002/04/15 03:44:23 $

% Historically, MATLAB's magic was a built-in function.
% This M-file uses a new algorithm to generate the same matrices.

n = floor(real(double(n(1))));

% Odd order.
if mod(n,2) == 1
   [J,I] = meshgrid(1:n);
   A = mod(I+J-(n+3)/2,n);
   B = mod(I+2*J-2,n);
   M = n*A + B + 1;

% Doubly even order.
elseif mod(n,4) == 0
   [J,I] = meshgrid(1:n);
   K = fix(mod(I,4)/2) == fix(mod(J,4)/2);
   M = reshape(1:n*n,n,n)';
   M(K) = n*n+1 - M(K);

% Singly even order.
else
   p = n/2;
   M = magic(p);
   M = [M M+2*p^2; M+3*p^2 M+p^2];
   if n == 2, return, end
   i = (1:p)';
   k = (n-2)/4;
   j = [1:k (n-k+2):n];
   M([i; i+p],j) = M([i+p; i],j);
   i = k+1;
   j = [1 i];
   M([i; i+p],j) = M([i+p; i],j);
end

分三种情况，奇数、偶数、双偶数。MATLAB源代码中调用了一些函数，可以在帮助文档中找到。
附：
    在MATLAB软件环境下用命令调用magic(n)，效率很高，上千阶的幻方也只需要2-3秒；可用批实现的代码效率却不尽如人意，比上面几楼各位的代码还要低些，可能是大量的变量赋值运算影响了效率吧；大家再来优化下代码，看哪里还有提升的空间。

lhjoanna

按照兄的建议修改了下，感觉效率还有待提高。批代码中大量操作都用于矩阵的赋值与运算，而高级语言中数组则作为内嵌类型，而MATLAB更是以矩阵作为基本的操作单元，所以对矩阵进行线性运算耗费时间很低，可能这也就是其效率高的原因吧。
    MATLAB中有很多经典算法，并且许多用于数值分析的算法都是世界一流的算法，效率自然很高，许多的源代码都是可以自己修改的，也很值得学习借鉴。我现在也就只能看懂整个程序的流程，至于为什么如此构造可以实现(以幻方为例)我还想不明白，这确实需要很强的数学背景了！