批处理之家 - Powered by Discuz! Board

标题: [数值计算] 批处理怎样生成n阶蛇形方阵和螺旋方阵？ [打印本页]

作者: DAIC 时间: 2011-8-14 16:00 标题: 批处理怎样生成n阶蛇形方阵和螺旋方阵？

n=4时：

蛇形方阵：
01 02 06 07
03 05 08 13
04 09 12 14
10 11 15 16

顺时针螺旋方阵：
01 02 03 04
12 13 14 05
11 16 15 06
10 09 08 07

逆时针螺旋方阵：
01 12 11 10
02 13 16 09
03 14 15 08
04 05 06 07

n=5时：

蛇形方阵：

01 02 06 07 15
03 05 08 14 16
04 09 13 17 22
10 12 18 21 23
11 19 20 24 25

顺时针螺旋方阵：
01 02 03 04 05
16 17 18 19 06
15 24 25 20 07
14 23 22 21 08
13 12 11 10 09

逆时针螺旋方阵：
01 16 15 14 13
02 17 24 23 12
03 18 25 22 11
04 19 20 21 10
05 06 07 08 09

作者: ArdentMan 时间: 2011-8-14 21:27

论坛搜索，早就有了

作者: DAIC 时间: 2011-8-14 22:00

回复 2# ArdentMan

搜索蛇形方阵，只有我发的这个求助帖，你怎么搜的？

作者: ArdentMan 时间: 2011-8-14 23:23

其实这些和我先前的输出趣味数列是一样的
通过合适的算法就可以实现~~~

作者: hanyeguxing 时间: 2011-8-15 09:38

本帖最后由 hanyeguxing 于 2011-8-16 21:17 编辑

蛇形：

@echo off&set/a c=9
for /l %%a in (1 1 %c%) do (
    for /l %%b in (1 1 %c%) do set/a "d=%%a+%%b-1,e=(%%a+%%b)%%2,f=e*((d*d-d)/2+%%a)+!e*((d*d+d)/2-%%a+1)-!!(d/(c+1))*(d-c)*(d-c)+100"&call set/p=%%f:~-2%% <nul
    echo;
)
复制代码

顺时针：

@echo off&set c=9
for /l %%a in (1,1,%c%) do (
    for /l %%b in (1,1,%c%) do set/a "d=!!(%%b/%%a)*!(%%b/(c-%%a+2))*(4*(c-%%a)*%%a-4*c+7*%%a+%%b-3)+!(%%b/(%%a+1))*!!(%%b/(c-%%a+2))*(4*(c-%%a)*%%a-2*c+5*%%a-%%b-1)+!!(%%b/(%%a+1))*!!(%%b/(c-%%a+2))*(4*(c-%%b)*%%b-2*c+%%a+3*%%b-1)+!(%%b/%%a)*!(%%b/(c-%%a+2))*(4*(c-%%b)*%%b-%%a+%%b+1)+100"&call set/p=%%d:~-2%% <nul
    echo;
)
复制代码

逆时针原理同上。。。

作者: broly 时间: 2011-8-15 22:37

本帖最后由 broly 于 2011-8-18 01:15 编辑

这种题，主要是算法的问题，只要找到算法，就可以做出来了

N阶蛇形输出:

@echo off
setlocal enabledelayedexpansion
set /p n=输入整数阶数n(n^>0)：
set /a line=%n%-1,line2=%n%*2-1,x=1

for %%o in (%n% %line%) do (
        if %%o equ %n% (set "run=1 1 %n%") else (set "run=%line% -1 1")
        for /l %%i in (!run!) do (
                set str=
                set /a mod=%%i%%2
                for /l %%j in (1 1 %%i) do (
                        set /a sum+=1
                        if !mod! equ 1 (
                                set "str=!sum! !str!"
                        ) else (
                                set "str=!str! !sum!"
                        )
                )
                
                set y=1
                if %%o equ %line% set /a y+=%n%-%%i
                
                for %%j in (!str!) do (
                        set ary[!x!][!y!]=%%j
                        set /a y+=1
                )
                set /a x+=1
        )
)

for /l %%i in (1 1 %n%) do (
        for /l %%j in (1 1 %line2%) do (
                if defined ary[%%j][%%i] (
                        set /p=!ary[%%j][%%i]!	<nul
                        set /a count+=1
                        set /a mod=!count!%%%n%
                        if !mod! equ 0 echo.
                )
        )
)

pause>nul
复制代码

作者: plp626 时间: 2011-8-16 20:51

直觉上觉得三个方阵都有O(1)型算法存在；慢慢找规律吧

作者: slore 时间: 2011-8-17 00:13

CN-DOS貌似08年就有蛇形和螺旋矩阵的帖子，已经很久上不去了，翻了下自己写的，贴出来，没有补2位，顺时的。。。自己可以改改。

蛇形矩阵

@echo off&setlocal enabledelayedexpansion
set flag=i&set i=1&set j=1
set /p n=输入阶数:
set /a nn=n*n
for /l %%a in (1,1,%nn%) do (
    if %%a LSS 10 (set _!i!!j!= %%a) else set _!i!!j!=%%a
    if !flag!==i (if !i! GTR 1 (set/a i-=1&set/a j+=1) else (set/a j+=1&set flag=j)) else (if !j! GTR 1 (set/a j-=1&set/a i+=1) else (set/a i+=1&set flag=i))
    if !i! GTR %n% set/a i-=1&set/a j+=1
    if !j! GTR %n% set/a i+=1&set/a j-=1
    if !i! EQU %n% if defined _!i!!j! set/a j+=1&set flag=i
    if !j! EQU %n% if defined _!i!!j! set/a i+=1&set flag=j
)

for /l %%m in (1,1,%n%) do (
    for /l %%n in (1,1,%n%) do (
       set /p =!_%%m%%n! <nul
     )
    echo.
)
pause>nul
复制代码

螺旋矩阵

@echo off&setlocal enabledelayedexpansion
set flag=i&set i=1&set j=1&set o=1
set /p n=输入阶数:
set /a nn=n*n
set /a n1=n+1
set _1%n1%=Sl挡&set _%n1%%n%=o顶&set _%n%0=re推
for /l %%a in (1,1,%nn%) do (
    if %%a LSS 10 (set _!i!!j!= %%a) else set _!i!!j!=%%a
    if !flag!==i  (set/a j+=!o!) else set/a i+=!o!
    if defined _!i!!j! (if !flag!==i (set flag=j&set/a i+=!o!&set/a j-=!o!) else (set flag=i&(set/a o=-!o!)&set/a i+=!o!&set/a j+=!o!))
)

for /l %%m in (1,1,%n%) do (
    for /l %%n in (1,1,%n%) do (
       set /p =!_%%m%%n! <nul
     )
    echo.
)
pause>nul
复制代码

作者: hanyeguxing 时间: 2011-8-17 01:36

本帖最后由 hanyeguxing 于 2011-8-17 11:59 编辑

回复 6# hanyeguxing

01 02 06 07 15 16 28 29 45
03 05 08 14 17 27 30 44 46
04 09 13 18 26 31 43 47 60
10 12 19 25 32 42 48 59 61
11 20 24 33 41 49 58 62 71
21 23 34 40 50 57 63 70 72
22 35 39 51 56 64 69 73 78
36 38 52 55 65 68 74 77 79
37 53 54 66 67 75 76 80 81

　　所谓蛇形，实际是指从左上顶点开始，按斜线的连续数列。我们这样分析（以下算法由寒夜孤星原创）：
1，将整个图形以 45-37 开始的斜线分割，只看左半部分。
2，整个表达式以 for 跌代嵌套设置坐标，如 for /l %%a in (1 1 %c%) do for /l %%b in (1 1 %c%) do ，%%a 为行，%%b 为列，%c% 为阶数。
3，我们提取每条斜线里最小的数字，分别是 1  2  4  7 11 16 22 29 37  ... 。这个数列可以用 (n-1)*n/2+1 计算。
以第一行为例，则 (%%b-1)*%%b/2+1 。以下每行向左移动一次，即 (%%b-1+%%a-1)*(%%b-1+%%a)/2+1 ，即  (%%a+%%b-1-1)*(%%b-1+%%a)/2+1 。
令 d=%%a+%%b-1 ，则 (d-1)*d/2+1 即 (d*d-d)/2+1 。
4，我们提取每条斜线里最大的数字，分别是 1  3  6 10 15 21 28 36 45  ... 。这个数列可以用 (n+1)*n/2 计算。
以第一行为例，则 (%%b+1)*%%b/2 。以下每行向左移动一次，即 (%%b-1+%%a+1)*(%%b-1+%%a)/2 ，即  (%%a+%%b-1+1)*(%%b-1+%%a)/2 。
令 d=%%a+%%b-1 ，则 (d+1)*d/2+1 即 (d*d+d)/2 。
5，我们以坐标 (xy)大、 (xy)小来表示自上而下分别从最大数、最小数开始的规律
11大 12小 13大 14小 15大 16小 17大 18小 19大
21小 22大 23小 24大 25小 26大 27小 28大 29小
31大 32小 33大 34小 35大 36小 37大 38小 39大
41小 42大 43小 44大 45小 46大 47小 48大 49小
...省略...
数学规律是 e=(%%a+%%b)%%2 ，当余数为 0 时大，余数为 1 时小。
6，综合以上，我们得到一个批处理：

@echo off&set/a c=9
for /l %%a in (1 1 %c%) do (
    for /l %%b in (1 1 %c%) do set/a "d=%%a+%%b-1,e=(%%a+%%b)%%2,f=e*((d*d-d)/2+%%a)+!e*((d*d+d)/2-%%a+1)+100"&call set/p=%%f:~-2%% <nul
    echo;
)
pause
复制代码

输出结果：
01 02 06 07 15 16 28 29 45 (46) (66) (67) (91) (92) (20) (21) (53)
03 05 08 14 17 27 30 44 47 (65) (68) (90) (93) (19) (22) (52)
04 09 13 18 26 31 43 48 64 (69) (89) (94) (18) (23) (51)
10 12 19 25 32 42 49 63 70 (88) (95) (17) (24) (50)
11 20 24 33 41 50 62 71 87 (96) (16) (25) (49)
21 23 34 40 51 61 72 86 97 (15) (26) (48)
22 35 39 52 60 73 85 98 14 (27) (47)
36 38 53 59 74 84 99 13 28 (46)
37 54 58 75 83 00 12 29 45
(55) (57) (76) (82) (01) (11) (30) (44)
(56) (77) (81) (02) (10) (31) (43)
(78) (80) (03) (09) (32) (42)
(79) (04) (08) (33) (41)
(05) (07) (34) (40)
(06) (35) (39)
(36) (38)
(37)
7，对比此结果与标准输出，左半部分与要求一致，需要修正的是右半部分，与要求的区别是：
自左向右，每斜线之间差为 n*n （上、下大小半个三角相加即为正方形），即 (%%a+%%b-1-c)*(%%a+%%b-1-c) 。
8，使用 !!((%%a+%%b-1)/(c+1)) 定位这些右半部分斜线。
9，综合得到代码：

@echo off&set/a c=9
for /l %%a in (1 1 %c%) do (
    for /l %%b in (1 1 %c%) do set/a "d=%%a+%%b-1,e=(%%a+%%b)%%2,f=e*((d*d-d)/2+%%a)+!e*((d*d+d)/2-%%a+1)-!!(d/(c+1))*(d-c)*(d-c)+100"&call set/p=%%f:~-2%% <nul
    echo;
)
pause
复制代码

作者: plp626 时间: 2011-8-17 22:14

本帖最后由 plp626 于 2011-8-17 22:34 编辑

看楼上代码得到的蛇形方阵数学关系式为
设c表示阶数，a(i,j)表示第i行第j列的数字，并记d=i+j-1，则有公式：

当i+j-2<c 时：  a(i,j)=(d*d-d)/2+j+rem(i+j,2)*(i-j)
当i+j-2>=c时：  a(i,j)=(d*d-d)/2+j+rem(i+j,2)*(i-j)-(d-c)*(d-c)
复制代码

其中，rem(x,y)表示x除以y的余数；

进而寒夜版主的代码可精简为：

@echo off&set/a c=19
for /l %%i in (1 1 %c%)do echo;&for /l %%j in (1 1 %c%)do (
    set/a i=%%i,j=%%j,d=i+j-1
    set/a "f=(d*d-d)/2+j+(i+j)%%2*(i-j)-!!((d-1)/c)*(d-c)*(d-c)+1000"
    call set/p=%%f:~-3%% <nul
)
pause>nul
复制代码

19阶的：

001 002 006 007 015 016 028 029 045 046 066 067 091 092 120 121 153 154 190
003 005 008 014 017 027 030 044 047 065 068 090 093 119 122 152 155 189 191
004 009 013 018 026 031 043 048 064 069 089 094 118 123 151 156 188 192 225
010 012 019 025 032 042 049 063 070 088 095 117 124 150 157 187 193 224 226
011 020 024 033 041 050 062 071 087 096 116 125 149 158 186 194 223 227 256
021 023 034 040 051 061 072 086 097 115 126 148 159 185 195 222 228 255 257
022 035 039 052 060 073 085 098 114 127 147 160 184 196 221 229 254 258 283
036 038 053 059 074 084 099 113 128 146 161 183 197 220 230 253 259 282 284
037 054 058 075 083 100 112 129 145 162 182 198 219 231 252 260 281 285 306
055 057 076 082 101 111 130 144 163 181 199 218 232 251 261 280 286 305 307
056 077 081 102 110 131 143 164 180 200 217 233 250 262 279 287 304 308 325
078 080 103 109 132 142 165 179 201 216 234 249 263 278 288 303 309 324 326
079 104 108 133 141 166 178 202 215 235 248 264 277 289 302 310 323 327 340
105 107 134 140 167 177 203 214 236 247 265 276 290 301 311 322 328 339 341
106 135 139 168 176 204 213 237 246 266 275 291 300 312 321 329 338 342 351
136 138 169 175 205 212 238 245 267 274 292 299 313 320 330 337 343 350 352
137 170 174 206 211 239 244 268 273 293 298 314 319 331 336 344 349 353 358
171 173 207 210 240 243 269 272 294 297 315 318 332 335 345 348 354 357 359
172 208 209 241 242 270 271 295 296 316 317 333 334 346 347 355 356 360 361
复制代码

作者: 风之语故乡 时间: 2011-8-17 22:35

本帖最后由风之语故乡于 2011-8-19 00:36 编辑

这是我自己写的，很粗陋了。

@echo off
setlocal enabledelayedexpansion
set mdebug=0
if %mdebug%==1 (set "trace=echo") else (set "trace=rem")
%trace%.调试
echo.鉴于排版和显示问题，输入的数字不要大于9
echo.
set /p input=你想要的螺旋方阵是几阶的？请输入任意数字: 
set /p input2=顺时针还是逆时针？顺时针输入1，逆时针输入2: 

for /l %%i in (1,1,%input%) do (
  for /l %%j in (1,1,%input%) do (
  set "数组[%%i][%%j]=0"
  )
)

set "方向=0"
set /a "数组长=input*input"
set "行=1"
set "列=1"
set "数组[%行%][%列%]=01"

for /l %%j in (2,1,%数组长% ) do (

if !方向!==0 (
if !列!==%input% (set "bool1=1")  else  (set "bool1=0")
set /a "t=!列!+1"
for /f "delims=" %%a in ("数组[!行!][!t!]") do (set "t2=!%%a!")
if !t! leq %input% (if !t2! neq 0 (set "bool2=1")  else  (set "bool2=0"))
set /a "bool3=bool1|bool2"
if !bool3!==1 (
set /a "方向=(!方向!+1)%%4"
))

if !方向!==1 (
if !行!==%input% (set "bool1=1")  else  (set "bool1=0")
set /a "t=!行!+1"
for /f "delims=" %%a in ("数组[!t!][!列!]") do (set "t2=!%%a!")
if !t! leq %input% (if !t2! neq 0 (set "bool2=1")  else  (set "bool2=0"))
set /a "bool3=bool1|bool2"
if !bool3!==1 (
set /a "方向=(!方向!+1)%%4"
))

if !方向!==2 (
if !列!==1 (set "bool1=1")  else  (set "bool1=0")
set /a "t=!列!-1"
for /f "delims=" %%a in ("数组[!行!][!t!]") do (set "t2=!%%a!")
if !t! geq 1 (if !t2! neq 0 (set "bool2=1")  else  (set "bool2=0"))
set /a "bool3=bool1|bool2"
if !bool3!==1 (
set /a "方向=(!方向!+1)%%4"
))

if !方向!==3 (
if !行!==1 (set "bool1=1")  else  (set "bool1=0")
set /a "t=!行!-1"
for /f "delims=" %%a in ("数组[!t!][!列!]") do (set "t2=!%%a!")
if !t! geq 1 (if !t2! neq 0 (set "bool2=1")  else  (set "bool2=0"))
set /a "bool3=bool1|bool2"
if !bool3!==1 (
set /a "方向=(!方向!+1)%%4"
))

if !方向!==0 ( set /a "列=!列!+1" ) 
if !方向!==1 ( set /a "行=!行!+1" )
if !方向!==2 ( set /a "列=!列!-1" )
if !方向!==3 ( set /a "行=!行!-1" )
set /a "t3=%%j+100"
set "数组[!行!][!列!]=!t3:~1!"
)

if %input2%==2 (
for /l %%i in (1,1,%input%) do (
  for /l %%j in (1,1,%input%) do (
  (set /p "=!数组[%%j][%%i]!  ") < nul
  )
echo.
)
) else (
for /l %%i in (1,1,%input%) do (
  for /l %%j in (1,1,%input%) do (
  (set /p "=!数组[%%i][%%j]!  ") < nul
  )
echo.
)
)

pause >nul
复制代码

关于为啥数组要加[][]是因为当n>11时，变量会重复比如:
数组111你说，到底是11行1列还是1行11列？

下面是我的第二种方法：

@echo off
setlocal enabledelayedexpansion
set mdebug=0
if %mdebug%==1 (set "trace=echo") else (set "trace=rem")
%trace%.调试
echo.鉴于排版和显示问题，输入的数字不要大于9
set /p n=你想要的螺旋方阵是几阶的？请输入任意数字: 
set /p input=顺时针还是逆时针？顺时针输入1，逆时针输入2: 
echo.
set /a "nn=n*n"
set "i=1"&set "j=1"
set /a "圈=(n+1)/2"

set "阶=!n!"
set "首位数值=1"
set "首位=1"
for /l %%a in (1,1,%圈%) do (
call :构造边缘 !首位数值! !阶! !首位!
set /a "首位数值+=(阶-1)*4"
set /a "阶-=2"
set /a "首位+=1"
)



if %input%==2 (
for /l %%i in (1,1,%n%) do (
  for /l %%j in (1,1,%n%) do (
  (set /p "=!数组[%%j][%%i]!  ") < nul
  )
echo.
)
) else (
for /l %%i in (1,1,%n%) do (
  for /l %%j in (1,1,%n%) do (
  (set /p "=!数组[%%i][%%j]!  ") < nul
  )
echo.
)
)
%trace%.调试
pause >nul
goto :eof

:构造边缘
if %2==1 (
set /a "t=%1+100"
set "数组[%3][%3]=!t:~1!"
) else (
set /a "圈长=(%2-1)*4"
set "i=%3"&set "j=%3"
set /a 末尾数值=%1+!圈长!-1
set "头=%3"
set /a "尾=头+%2-1"
for /l %%b in (%1,1,!末尾数值!) do (
set /a "t=%%b+100"
set "数组[!i!][!j!]=!t:~1!"
set "key1=1"
if !key1!==1 (if !i!==!头! (if !j! lss !尾! (
set /a j+=1
set "key1=0"
)))
if !key1!==1 (if !j!==!尾! (if !i! lss !尾! (
set /a i+=1
set "key1=0"
)))
if !key1!==1 (if !i!==!尾! (if !j! gtr !头! (
set /a j-=1
set "key1=0"
)))
if !key1!==1 (if !j!==!头! (if !i! gtr !头! (
set /a i-=1
set "key1=0"
)))
)
)
复制代码

作者: plp626 时间: 2011-8-17 23:03

想到用待定系数法求多变元数列通项公式：
一般地【如果】a(x,y,z)存在多项式关系，或，和奇数偶数相关的多项式关系，或者和变元的最大最小值相关的多项式关系，以及后两者皆相关的多项式关系；我们可以用待定系数法求出其关系式（第一种情况最简单，第二种第三种情况没有详细研究）；

这个方法是通用的，求出关系式后只需下一步归纳验证关系式的正确性即可，若否则升高多项式的次数，再待定系数法求其系数，归纳验证，，，，

欢迎光临批处理之家 (http://bbs.bathome.net/)