Board logo

标题: 【出题】批处理输出n阶幻方 [打印本页]

作者: lhjoanna    时间: 2009-4-1 12:50     标题: 【出题】批处理输出n阶幻方

所谓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

作者: pusofalse    时间: 2009-4-1 13:53

这个题目相当难啊~ 以前做过类似的,没做出来~ - -|||
作者: batman    时间: 2009-4-1 15:11

解此题最重要的不是代码,而是思路。。。
作者: lhjoanna    时间: 2009-4-1 16:56

恩,幻方生成规则知道了,代码也就不难了。^_^
作者: lhjoanna    时间: 2009-4-1 20:02

是不是太难了,怎么没人贴代码来?可以先到网上搜索一下奇次幻方的构造规律,然后再转化为代码就相对容易些了!
作者: Lumiere    时间: 2009-4-1 21:08

是想自己摸索出来那个规则吧?
作者: slore    时间: 2009-4-1 22:30

cn-dos不是有么
作者: lhjoanna    时间: 2009-4-1 22:56

哦?我刚搜了下没搜到啊。slore兄不妨把那帖子链接贴来,看能不能激发些灵感想出些不同的方法。
作者: Batcher    时间: 2009-4-1 23:27

不知道slore兄是不是说的这个:
http://www.cn-dos.net/forum/viewthread.php?tid=26647

CN-DOS这次出问题看来丢了十来天的数据,哎~
作者: lhjoanna    时间: 2009-4-2 06:47

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

试试:
  1. @echo off
  2. :bgn
  3. set input=&set /p input=请输入3以上的单数(回车退出):
  4. if not defined input goto :eof
  5. cls
  6. if %input% lss 3 (echo.你输入的也太小了吧...&goto :bgn)
  7. echo.%input:~-1%|findstr "[^13579]" >nul&&(echo.请输入单数...&goto :bgn)
  8. set /a num1=(%input%*%input%+1)*%input%/2,num2=%input%*%input%
  9. echo.%input%阶幻方各行,列以及对角线相加的和为:%num1%
  10. set /a lie=%input%/2+1,hang=1,all=1
  11. set h1l%lie%=1
  12. :agn
  13. set /a hang-=1,lie+=1,all+=1
  14. if %hang% lss 1 set hang=%input%
  15. if %lie% gtr %input% set lie=1
  16. if defined h%hang%l%lie% (set /a hang+=2,lie-=1)
  17. set h%hang%l%lie%=%all%
  18. if "%hang%"=="1" (
  19.   if "%lie%"=="%input%" (
  20.     set /a hang+=1,all+=1
  21.     call set h%%hang%%l%lie%=%%all%%
  22.   )
  23. )
  24. if %all% equ %num2% goto :show
  25. goto :agn
  26. :show
  27. for /l %%a in (1 1 %input%) do (
  28.   for /l %%b in (1 1 %input%) do (
  29.     call set/p=%%h%%al%%b%%  <nul
  30.     set "h%%al%%b="
  31.   )
  32.   echo.
  33. )
  34. goto :bgn
复制代码

作者: tyc    时间: 2009-4-2 16:19     标题: 我试试,化了一节课的时间才做出来的

  1. program aa;
  2. var
  3. i,j,m,n:integer;
  4. a:array [1..100,1..100] of integer;
  5. begin
  6. repeat
  7. readln(n);
  8. m:=n mod 2;
  9. until m<>0;
  10. for i:=1 to n do
  11.   for j:=1 to n do a[i][j]:=0;
  12. i:=2;j:=n div 2;
  13. for m:=1 to n*n do
  14. begin
  15.   i:=i-1;j:=j+1;
  16.   if (i=0) and (j<>n+1) then  i:=n;
  17.   if (j=n+1) and (i<>0) then j:=1;
  18.   if (a[i][j]<>0) or (i=0) and (j=n+1) then
  19.   begin
  20.     i:=i+2;
  21.     j:=j-1;
  22.   end;
  23.   a[i][j]:=m;
  24. end;
  25. for i:=1 to n do
  26.   begin
  27.   for j:=1 to n do
  28.    write(a[i][j]:5);
  29.   writeln;
  30.   end;
  31. end.
复制代码

[ 本帖最后由 tyc 于 2009-4-2 16:20 编辑 ]
作者: lhjoanna    时间: 2009-4-2 18:43

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

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

应版主的要求,再做一些修改吧:
  1. @echo off
  2. :bgn
  3. set input=&set /p input=请输入一个单数(回车退出):&cls
  4. if not defined input goto :eof
  5. echo.%input%|findstr /v "^[0-9]*$" >nul&&(echo.请输入纯数字!!!&goto :bgn)
  6. echo.%input:~-1%|findstr "[^13579]" >nul&&(echo.请输入单数!!!&goto :bgn)
  7. set /a num1=(%input%*%input%+1)*%input%/2,num2=%input%*%input%
  8. echo.%input%阶幻方各行,列以及对角线相加的和为:%num1%&echo.
  9. set /a lie=%input%/2+1,hang=1,all=1
  10. if %num2% gtr 99 (set h1l%lie%=  1) else (set h%hang%l%lie%= 1)
  11. :agn
  12. set /a hang-=1,lie+=1,all+=1
  13. if %hang% lss 1 set hang=%input%
  14. if %lie% gtr %input% set lie=1
  15. if defined h%hang%l%lie% (set /a hang+=2,lie-=1)
  16. call :duiqi
  17. if "%hang%"=="1" (
  18.   if "%lie%"=="%input%" (
  19.     set /a hang+=1,all+=1
  20.     call :duiqi
  21.   )
  22. )
  23. if %all% geq %num2% goto :show
  24. goto :agn
  25. :show
  26. for /l %%a in (1 1 %input%) do (
  27.   for /l %%b in (1 1 %input%) do (
  28.     call set/p=%%h%%al%%b%%  <nul
  29.     set "h%%al%%b="
  30.   )
  31.   echo.&echo.
  32. )
  33. goto :bgn
  34. :duiqi
  35. if %num2% gtr 99 (
  36.   if %all% lss 10 (
  37.     set h%hang%l%lie%=  %all%
  38.   ) else (
  39.     if %all% lss 100 (
  40.       set h%hang%l%lie%= %all%
  41.     ) else (
  42.       set h%hang%l%lie%=%all%
  43.     )
  44.   )
  45. ) else (
  46.   if %num2% gtr 9 (
  47.     if %all% lss 10 (
  48.       set h%hang%l%lie%= %all%
  49.     ) else (
  50.       set h%hang%l%lie%=%all%
  51.     )
  52.   ) else (set h%hang%l%lie%= %all%)
  53. )
复制代码

作者: tyc    时间: 2009-4-2 20:35     标题: 兄弟不才,用了其它语言

我用pascal,批处理写不出来,一急就用其它高级语言了,不过这一题是初中生的竞赛题。

[ 本帖最后由 tyc 于 2009-4-3 07:34 编辑 ]
作者: lhjoanna    时间: 2009-4-2 20:38

Re:more
      呵,结果是可以对齐了,只是代码是不是繁了点。不需要在赋值的过程中多次调用duiqi,可以在赋值完毕后统一调整格式(包括1)。
   在兄11楼代码基础上修改:
  1. @echo off&setlocal enabledelayedexpansion
  2. :bgn
  3. echo.&set input=&set /p input=请输入一个单数(回车退出):
  4. if not defined input goto :eof
  5. cls
  6. echo %time%&echo.
  7. echo.%input%|findstr /v "^[0-9]*$" >nul&&(echo.请输入纯数字!!!&goto :bgn)
  8. echo.%input:~-1%|findstr "[^13579]" >nul&&(echo.请输入单数...&goto :bgn)
  9. set /a num1=(%input%*%input%+1)*%input%/2,num2=%input%*%input%
  10. echo.%input%阶幻方各行,列以及对角线相加的和为:%num1%
  11. set /a lie=%input%/2+1,hang=1,all=1
  12. set h1l%lie%=1
  13. :agn
  14. set /a hang-=1,lie+=1,all+=1
  15. if %hang% lss 1 set hang=%input%
  16. if %lie% gtr %input% set lie=1
  17. if defined h%hang%l%lie% (set /a hang+=2,lie-=1)
  18. set h%hang%l%lie%=%all%
  19. if "%hang%"=="1" (
  20.    if "%lie%"=="%input%" (
  21.      set /a hang+=1,all+=1
  22.      call set h%%hang%%l%lie%=%%all%%
  23.    )
  24. )
  25. if %all% geq %num2% goto :show
  26. goto :agn
  27. :show
  28. call :duiqi
  29. echo.
  30. for /l %%a in (1 1 %input%) do (
  31.   for /l %%b in (1 1 %input%) do (
  32.     call set/p=%%h%%al%%b%% <nul
  33.     set "h%%al%%b="
  34.   )
  35.   echo.
  36. )
  37. echo %time%&echo.
  38. goto :bgn
  39. :duiqi
  40. for /l %%a in (1 1 !input!) do (
  41.   for /l %%b in (1 1 !input!) do (
  42.    if !h%%al%%b! lss 10 set "h%%al%%b= !h%%al%%b!"
  43.    if !input! gtr 10  (
  44.         if !h%%al%%b! lss 100 ( set "h%%al%%b= !h%%al%%b!")
  45.    )
  46.   )
  47. )
复制代码
附:一点改进的建议
   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 编辑 ]
作者: 随风    时间: 2009-4-3 10:09

奇数阶幻方的构造方法(楼梯法)。
把1(或最小的数)放在第一行正中;
按以下规律排列剩下的n*n-1个数:
1)每一个数放在前一个数的右上一格;
2)如果这个数所要放的格已经超出了顶行那么就把它放在底行,仍然要放在右一列;
3)如果这个数所要放的格已经超出了最右列那么就把它放在最左列,仍然要放在上一行;
4)如果这个数所要放的格已经超出了顶行且超出了最右列那么就把它放在前一个数的下一行同一列的格内;
5)如果这个数所要放的格已经有数填入,处理方法同4)。
  1. @echo off
  2. :start
  3. setlocal enabledelayedexpansion
  4. echo.&set /p n= 请输入一个奇数 &cls
  5. set /a m=n/2+1,h=1,c=n*n,he=(n*n+1)*n/2
  6. echo  !n! 阶幻方各行,列以及对角线相加的和为: %he%&echo.
  7. set .1-!m!=1
  8. for /l %%a in (2 1 !c!) do call :loop %%a
  9. for /l %%a in (0 1 9) do set c=!c:%%a= %%a !
  10. for %%a in (!c!) do set /a j+=1
  11. for /l %%a in (1 1 !n!) do (
  12.    set "num="
  13.    for /l %%b in (1 1 !n!) do (
  14.       set "var=                                !.%%a-%%b!"
  15.       set "num=!num! !var:~-%j%!"
  16. )
  17.    echo.!num!
  18. )
  19. endlocal&goto start
  20. :loop
  21.    set /a h-=1,m+=1
  22.    if !h! lss 1 set /a h=n
  23.    if !M! gtr !n! set /a m=1
  24.    if defined .!h!-!m! (
  25.       if !qh! equ !n! (set /a h=2) else set /a h=qh+2
  26.    set /a qh=h-1,m=qm-1
  27.    goto loop
  28. )
  29.    set ".!h!-!m!=%~1"
  30.    set /a qh=h,qm=m
  31. goto :EOF
复制代码

[ 本帖最后由 随风 于 2009-4-3 10:46 编辑 ]
作者: lhjoanna    时间: 2009-4-3 11:57

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

不懂什么是一维变量,代码一写好就发现效率是个大问题,一直没有办法解决,这种幻方构造方法是临时在网上找的,lhjoanna兄是否还有更好的算法?拿来分享一下。又或者我的代码还可以如何改进,请指点。。
作者: lhjoanna    时间: 2009-4-4 19:11

呵,指点谈不上,说讨论更贴切些~~说实话,一维变量是我编出来的,官方没有这样的说法,举个例子,类似.%%a%%b我称它为二维的,而对比下 .%%a就是一维了。感觉这样说简炼些^_^
        我的算法也就是兄所说的楼梯法,更确切些叫罗伯法。这是目前比较容易的构造方法了。我也一直在思考效率的提高问题,在目前的这个算法下,我也只想到把变量改为一维(暂称)的可以提高一些效率,我的代码在下面,还请兄帮忙测试或者改进下!
  1. @echo off
  2. :begin
  3. setlocal enabledelayedexpansion
  4. color 0c
  5. cls
  6. echo.&echo  本程序功能为输出n阶幻方!
  7. echo.&echo  所谓n阶幻方:1-n^^2个数排为n行n列;
  8. echo.&echo  要求:横、竖、对角线相加和相同。
  9. echo.&echo  算法:loubere法
  10. echo.&set /p "n= 请输入方阵阶数(奇数):"
  11. echo !n!|findstr "^[1-9]*$">nul || (echo.& echo  Non-Numberic & pause>nul & goto begin)
  12. set /a a=n%%2
  13. if !a! equ 0 echo.&echo  Non-Odd & pause>nul & goto begin
  14. cls
  15. echo.&echo %time%
  16. set /a "sum=(1+n*n)*n/2"
  17. echo.&echo  !n!阶幻方横、竖、对角线相加和为 !sum!
  18. echo.
  19. set /a square=n*n,i=1,j=(n+1)/2,loc=j
  20. set ".!loc!=1"
  21. for /l %%i in (2 1 !square!) do (
  22.      set /a "i=(i-1)%%n,j=(j+1)%%n"
  23.      if !i! equ 0 set /a i=n
  24.      if !j! equ 0 set /a j=n
  25.      set /a "loc=n*(i-1)+j"
  26.      if defined .!loc! (
  27.          set /a "i=(i+2)%%!n!,j=(j-1)%%n"  
  28.          if !i! equ 0 set /a i=n
  29.          if !j! equ 0 set /a j=n
  30.          set /a "loc=n*(i-1)+j"
  31.      )
  32.      set .!loc!=%%i
  33.   rem echo  i:!i!,j:!j!,loc:!loc!,.loc:%%i
  34. )
  35. call :unify
  36. for /l %%i in (1 1 !square!) do (
  37.      set /a "c=%%i%%n"
  38.      set "result=!result! !.%%i!"
  39.      if !c! equ 0 echo !result!&set "result="
  40. )
  41. echo.&echo %time%&echo.
  42. pause>nul&endlocal&goto begin
  43. :unify
  44. for /l %%i in (1 1 !square!) do (
  45.      if !.%%i! lss 10 set ".%%i= !.%%i!"
  46.      if !n! gtr 10  (
  47.         if !.%%i! lss 100 ( set ".%%i= !.%%i!")
  48.      )
  49. )
  50. goto :eof
复制代码

作者: 随风    时间: 2009-4-4 21:58

仔细琢磨了兄的代码。效率及算法都比我的强多了。
最不懂的一句 set /a "loc=n*(i-1)+j" 应该也是精华吧。
不过有一处不太明白,好像也不太容易说明白。举个例吧
a    1    c
3    e    f
g    h    2
此时 4 应该放在 b 的位置,也就是 1 的位置,但位置被 1 占了,
所以 4 就应该放在前一个数的下一行同一列的格内,也就是 g 位,
问题来了,不知道幻方会不会有这种情况出现,就是 g 位此时也已经被别的数占了,
如果这种情况存在,那么按我的理解就应该放在g的下面。
同样,如果存在这种情况,那么兄的代码似乎没对这种反复的情况作处理啊。
作者: lhjoanna    时间: 2009-4-5 00:59

要存储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)&sup2;+(y-b)&sup2;+(z-c)&sup2;=R&sup2;有千丝万缕的联系。又一猜想:说不定幻方的方程(猜测:f(x,y,z)=n&sup2;)当n(阶数)趋于无穷时,幻方的方程也就等于球的方程(或类球方程)。
     呵,大晚上的容易乱想,想了一堆,还没有在网上找到类似支持的理论,只做一种猜测吧!
作者: 随风    时间: 2009-4-5 02:58     标题: 回复 22 楼 lhjoanna 兄

多谢兄的耐心讲解,认真看了看,说实话但也只看懂个大概,不过也受益匪浅了。
既然不存在目标数的下一行对应的数被占用的情况,那么代码可以修改一下提高效率。
我17楼代码之所以效率低下应该是因为call太多,loop就是为了处理这种情况,现在看来是多余的。
:
  1. @echo off
  2. :start
  3. setlocal enabledelayedexpansion
  4. echo.&set /p n= 请输入一个奇数 &cls
  5. set /a m=n/2+1,h=1,c=n*n,he=(n*n+1)*n/2
  6. echo  !n! 阶幻方各行,列以及对角线相加的和为: %he%&echo.
  7. set .1-!m!=1
  8. for /l %%a in (2 1 !c!) do (
  9.    set /a h-=1,m=m%%n+1
  10.    if !h! equ 0 set /a h=n
  11.    if defined .!h!-!m! set /a h=qh%%n+1,m=qm
  12.    set ".!h!-!m!=%%a"
  13.    set /a qh=h,qm=m
  14. )
  15. for /l %%a in (0 1 9) do set c=!c:%%a= %%a !
  16. for %%a in (!c!) do set /a j+=1
  17. for /l %%a in (1 1 !n!) do (
  18.    set "num="
  19.    for /l %%b in (1 1 !n!) do (
  20.       set "var=               !.%%a-%%b!"
  21.       set "num=!num! !var:~-%j%!"
  22.     )
  23.     echo.!num!
  24. )
  25. endlocal&goto start
复制代码

作者: lhjoanna    时间: 2009-4-5 10:33

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

凑热闹 马步的
修改前面的set ".!h!-!m!=1"这句放在FOR里面
  1. @echo off
  2. :start
  3. setlocal enabledelayedexpansion
  4. echo.&set /p n= 请输入一个奇数 &cls
  5. set /a m=n/2+1,c=n*n,he=(n*n+1)*n/2
  6. echo  !n! 阶幻方各行,列以及对角线相加的和为: %he%&echo.
  7. for /l %%i in (1 1 !c!) do (
  8.    set/a i=%%i%%n
  9.    if !i! equ 1 (set/a h=h%%n+1) else set/a h=h%%n+2,m=m%%n+1
  10.    if !h! gtr !n! set h=1
  11.       set ".!h!-!m!=%%i"
  12. )
  13. for %%i in (0 1 10) do if not "!c:~%%i,1!"=="" set /a j=%%i+2&set "k=!k! "
  14. for /l %%a in (1 1 !n!) do (
  15.    set "var="
  16.    for /l %%b in (1 1 !n!) do (
  17.       set "str=!k!!.%%a-%%b!"
  18.       set "var=!var! !str:~-%j%!"
  19.     )
  20.     echo.!var:~1!
  21. )
  22. pause
  23. endlocal&goto start
复制代码

[ 本帖最后由 terse 于 2009-4-6 11:07 编辑 ]
作者: 小勇12    时间: 2009-4-11 23:52

真是厉害,呀 向大家学习
作者: xxx    时间: 2009-4-12 14:03

嗯,我承认我是迟到了...而且还不是batch的...
是python的:
  1. #09/4/4/12
  2. def make_list(num):
  3.     n,k,b,c = num,0,num/2,num**2
  4.     listx = []
  5.     for x in xrange(n):
  6.         listx.append([])
  7.         for _x in xrange(n):
  8.             listx[x].append(False)
  9.     for _x in xrange(c):
  10.         if((_x+1)==1):
  11.             listx[k] = 1
  12.         elif((_x+1)%n==1):
  13.             k = k+1
  14.             if(k>n-1):
  15.                 k = k-n
  16.             listx[k] = _x+1
  17.         else:
  18.             k = k+2
  19.             b = b+1
  20.             if(b>n-1):
  21.                 b = 0
  22.             if(k>n-1):
  23.                 k = k-n
  24.             listx[k] = _x+1
  25.     for y in xrange(n):
  26.             print(listx[y])
  27. def start():
  28.     print("Input a number:")
  29.     x = input()
  30.     if(x%2==0):
  31.         print("Wrong.")
  32.     else:
  33.         make_list(x)
  34. if __name__ == "__main__":
  35.      start()
复制代码

[ 本帖最后由 xxx 于 2009-4-12 14:05 编辑 ]
作者: lhjoanna    时间: 2009-4-20 19:43

下午偶然从MATLAB上找到了构造幻方的源代码,是用MATLAB程序设计语言实现的(基于C语言设计),可以生成阶数不限的幻方。下午把此算法用批处理实现了。下面附上批版代码以及magic(n)函数源代码。
  1. @echo off
  2. :begin
  3. setlocal enabledelayedexpansion
  4. set rank=
  5. echo.&set /p "rank=请输入幻方阶数:"
  6. set /a remainder=rank%%2
  7. if !remainder! equ 1 (
  8.     call :odd !rank!
  9. ) else (
  10.      set /a remainder=rank%%4
  11.      if !remainder! equ 0 (
  12.         call :even_4
  13.      ) else call :even_2
  14.    )
  15. rem --------------奇数阶幻方------------------
  16. :odd
  17. set rank=%1
  18. call :create
  19. for /l %%i in (1 1 !rank!) do (
  20.      for /l %%j in (1 1 !rank!) do (
  21.          set /a $%%i%%j="(.%%i%%j+.%%j%%i-(rank+3)/2+rank)%%rank"
  22.          set /a #%%i%%j="(.%%i%%j+.%%j%%i*2-2+rank)%%rank"
  23.          set /a _%%i%%j="rank*$%%i%%j+#%%i%%j+1"
  24.      )
  25.   )
  26. if not "%~2" equ "" goto :eof
  27. call :output
  28. endlocal&goto :begin
  29. rem -------------偶数阶幻方(4整除)---------------
  30. :even_4
  31. call :create
  32. set num=0
  33. for /l %%i in (1 1 !rank!) do (
  34.      for /l %%j in (1 1 !rank!) do (
  35.          set /a "a=(.%%i%%j%%4)/2,b=(.%%j%%i%%4)/2"
  36.          if !a! equ !b! ( set "_%%i%%j=1" ) else set "_%%i%%j=0"
  37.          set /a "num+=1,n=rank*rank+1"
  38.          set /a #%%i%%j=!num!
  39.          if !_%%i%%j! equ 1 (set /a _%%i%%j=n-#%%i%%j) else set _%%i%%j=!#%%i%%j!
  40.      )
  41. )
  42. call :output
  43. endlocal&goto :begin
  44. rem --------------偶数阶幻方(2整除)--------------
  45. :even_2
  46. set /a p=rank/2,q=rank,p1=p+1
  47. call :odd !p! OK
  48. set rank=!q!
  49. call :rearrange 1 !p! !p1! !rank! 2
  50. call :rearrange !p1! !rank! 1 !p! 3
  51. call :rearrange !p1! !rank! !p1! !rank! 1
  52. call :transpos !p!
  53. if !rank! equ 2 (
  54.    call :output
  55.    endlocal&goto :begin
  56. )
  57. for /l %%i in (1 1 !p!) do set "var_i=!var_i! %%i"
  58. set /a k=(rank-2)/4,m=rank-k+2
  59. for /l %%i in (1 1 !k!) do set "var_j=!var_j! %%i"
  60. for /l %%i in (!m! 1 !rank!) do set "var_j=!var_j! %%i"
  61. call :exchange "!var_i!" "!var_j!"
  62. set /a i=k+1
  63. set "j=1 !i!"
  64. call :exchange "!i!" "!j!"
  65. call :output
  66. set i=
  67. set j=
  68. set var_i=
  69. set var_j=
  70. endlocal&goto :begin
  71. rem -------------以下为子函数-----------------
  72. :create
  73. set /a rank_2=rank*rank,i=1,j=1
  74. for /l %%i in (1 1 !rank_2!) do (
  75.        set .!i!!j!=!j!
  76.        set /a j+=1
  77.        if !j! gtr !rank! set j=1&set /a i+=1
  78. )
  79. goto :eof
  80. :output
  81.   call :append !rank!
  82.   for /l %%i in (1 1 !rank!) do (
  83.      for /l %%j in (1 1 !rank!) do set result=!result! !_%%i%%j:~-3!
  84.      echo.!result!&set result=
  85.   )
  86.   goto :eof
  87. :rearrange
  88. set /a p2=%5*p*p,i=1,j=1
  89. for /l %%i in (%1 1 %2) do (
  90.      for /l %%j in (%3 1 %4) do (
  91.          set /a _%%i%%j=_!j!!i!+p2
  92.          set /a j+=1
  93.      )
  94.      set /a "i+=1,j=1"
  95. )
  96. goto :eof
  97. :exchange
  98. for %%i in (%~1) do (
  99.      for %%j in (%~2) do (
  100.          set /a i=%%i+p
  101.          set tmp=!_%%i%%j!
  102.          call set _%%i%%j=%%_!i!%%j%%
  103.          set _!i!%%j=!tmp!
  104.      )
  105. )
  106. goto :eof
  107. :transpos
  108. for /l %%i in (1 1 %1) do (
  109.      for /l %%j in (%%i 1 %1) do (
  110.          if not %%i equ %%j (
  111.             set tmp=!_%%i%%j!
  112.             set _%%i%%j=!_%%j%%i!
  113.             set _%%j%%i=!tmp!
  114.          )
  115.      )
  116. )
  117. goto :eof
  118. :append
  119.   for /l %%i in (1 1 %1) do (
  120.      for /l %%j in (1 1 %1) do (
  121.          set "_%%i%%j=   !_%%i%%j!"
  122.      )
  123.   )
  124.   goto :eof
复制代码
函数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秒;可用批实现的代码效率却不尽如人意,比上面几楼各位的代码还要低些,可能是大量的变量赋值运算影响了效率吧;大家再来优化下代码,看哪里还有提升的空间。
作者: 随风    时间: 2009-4-20 21:11

想通过代码来了解算法太难了,大致看了下兄的代码流程,只发现一处影响代码效率的地方。
批处理的运行效率,个人认为 set 或 set /a 并不会太影响,关键是看代码的设计,for的循环次数尤其是嵌套循环,再就是call若在for循环中有call则一定会使效率大打折扣。
建议改进的地方:
:exchange 标签下
call set _%%i%%j=%%_!i!%%j%%
改为 for %%a in (!i!) do set _%%i%%j=!_%%a%%j!
作者: lhjoanna    时间: 2009-4-21 01:35

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

好早之前看到这个帖子了,在这个帖子还没有回复的时候就开始研究写了代码,可是错误不少,后来因为工作的事就一直没时间去斟酌。现在有时间了,仔细看了下,终于改出来了,本来挺高兴的,结果上来一看,前辈们早就把代码反复推敲了N久了,而且问题的本质已经从对症下药给出合理的解决代码上升倒了代码效率高下的研究,这是本人不敢企及的。本来不打算把代码贴上来了,可是本人后来输入较大点的数字的时候,又出现一个问题,就是“已经达到最大的setlocal递归层”但是似乎幻方的生成还是没有影响,数字也都对,我不太明白这个错误怎么长生的。老调重弹,麻烦前辈们给解释下,不胜感激!
我写的代码如下:
  1. @echo off
  2. :start
  3. set /p n=Please input your odd integer:
  4. set /a p=n%%2
  5. if %p% equ 0 echo Input error!&&goto start
  6. set /a i=%n%
  7. set /a t=(%n%+1)/2
  8. set /a a%t%_%n%=1,temp=1,m=n-1,p=n
  9. :repeat
  10. set /a p-=1
  11. if %p% lss 0 goto array
  12. for /l %%a in (1 1 %m%) do (
  13.    setlocal enabledelayedexpansion
  14.    if !t! gtr %n% set /a t=1
  15.    if !i! gtr %n% set /a i=1
  16.    set /a s=!t!+1,q=!i!+1
  17.    if !s! gtr %n% set /a s=1
  18.    if !q! gtr %n% set /a q=1
  19.    set /a a!s!_!q!=a!t!_!i!+1,t+=1,i+=1
  20.    set /a temp+=1
  21.    if !temp! equ %n% (
  22.          set /a temp=1,tmp=a!s!_!q!,q-=1,i-=1
  23.          if !q! equ 0 set /a q=n
  24.          set /a a!s!_!q!=tmp+1
  25.          goto repeat
  26. )   
  27. )
  28. pause
  29. :array
  30. echo Now behold the powerful Magic Sqaure^^!:
  31. set /a a!t!_!n!=1
  32. for /l %%c in (!n! -1 1) do (
  33.    for /l %%d in (1 1 !n!) do (
  34.               set /a result=a%%d_%%c
  35.               set /p=!result!<nul      
  36. )
  37. echo.
  38. )
  39. pause>nul
复制代码
如上,输入7以上的奇数就会出现那个问题,没弄明白,只好请教诸位了。
作者: Lumiere    时间: 2009-7-10 17:14

晕菜啊,这么久也没人来指点一下啊,再等~
作者: zhouyongjun    时间: 2009-7-10 17:21

变量延迟不要放在for里面
作者: Batcher    时间: 2009-7-10 17:49     标题: 回复 31楼 的帖子

“已经达到最大的setlocal递归层”的问题,请参考:
http://bbs.bathome.net/thread-1224-1-3.html
作者: Lumiere    时间: 2009-7-11 00:40     标题: 回复 33楼 的帖子

呵呵,就要这种效果,一句话就解决,我把变量延迟放到外面就不会提示那个错误了。再去好好看看这个问题的描述,多谢啦!
作者: Batcher    时间: 2009-7-11 00:48     标题: 回复 35楼 的帖子

确实应该好好看看,也许你会发现不把变量延迟扩展放在for里面有时可能带来更多的问题^_^
作者: Lumiere    时间: 2009-7-11 12:03     标题: 回复 36楼 的帖子

那个帖子我看了,上面说最好把变量延迟扩展申明放在for结构内,哪里需要哪里申明,然后再结束,那我的问题不就没办法解决了么?我试过了,在for里申明然后在结构结束之前用endlocal结束,结果还是会出现那个恼人的错误提示。但是我照33楼兄弟的说法把申明放到for结构之前,问题就没有了。到底哪个是对的?如果要放在for里面的话,如何把我的问题解决?
作者: keen    时间: 2009-7-11 13:44     标题: 回复 37楼 的帖子

把setlocal enabledelayedexpansion放在for语句里面是为了防止读取某些含有叹号!字符串时,丢失叹号!字符。

而你的这个算幻方的题,可能不涉及到叹号!字符串的处理。所以可以把setlocal enabledelayedexpansion放在for语句外面防止超过最大递归层。

但当你处理一些含有叹号!字符串时,应该注意把setlocal enabledelayedexpansion放在for语句内部,防止丢失。

这就叫 “随机应变”,就是看情况选择setlocal enabledelayedexpansion的位置。




欢迎光临 批处理之家 (http://bbs.bathome.net/) Powered by Discuz! 7.2