第20講 一般種法による魔方陣ソフトの高速化
第3話 新しい番号付けのヒントその3

再度偶数の場合の規則性について考えてみましょう。
前回と違う例をとってみましょう。
18次の場合

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
0 0 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 18
1 52 1 68 69 70 71 72 73 74 75 76 77 78 79 80 81 19 82
2 53 83 2 98 99 100 101 102 103 104 105 106 107 108 109 20 110 111
3 54 84 112 3 126 127 128 129 130 131 132 133 134 135 21 136 137 138
4 55 85 113 139 4 152 153 154 155 156 157 158 159 22 160 161 162 163
5 56 86 114 140 164 5 176 177 178 179 180 181 23 182 183 184 185 186
6 57 87 115 141 165 187 6 198 199 200 201 24 202 203 204 205 206 207
7 58 88 116 142 166 188 208 7 218 219 25 220 221 222 223 224 225 226
8 59 89 117 143 167 189 209 227 8 26 236 237 238 239 240 241 242 243
9 60 90 118 144 168 190 210 228 27 9 252 253 254 255 256 257 258 259
10 61 91 119 145 169 191 211 28 244 260 10 268 269 270 271 272 273 274
11 62 92 120 146 170 192 29 229 245 261 275 11 282 283 284 285 286 287
12 63 93 121 147 171 30 212 230 246 262 276 288 12 294 295 296 297 298
13 64 94 122 148 31 193 213 231 247 263 277 289 299 13 304 305 306 307
14 65 95 123 32 172 194 214 232 248 264 278 290 300 308 14 312 313 314
15 66 96 33 149 173 195 215 233 249 265 279 291 301 309 315 15 318 319
16 67 34 124 150 174 196 216 234 250 266 280 292 302 310 316 320 16 322
17  35  97 125 151 175 197 217 235 251 267 281 293 303 311 317 321 323 17

今回の場合も4つの系列
36,68,98,126,152,176,198,218,236
52,83,112,139,164,187,208,227,244
252,268,282,294,304,312,318,322
260,275,288,299,308,315,320,323
の規則性は明らかです。
差をとれば
32,30,28,26,24,22,20,18
31,29,27,25,23,21,19,17
16,14,12,10,8,6,4
15,13,11,9,7,5,3
ですね。
しかも、1番目の数列のはじまり36には、普遍的(一般的)な法則があります。
2×nから始まっています。
2番目の数列のはじまり52も2×n+(n−2)=3×n−2です。
n−2になっている理由は、対角線のセルと逆対角線のセルこの場合は0と18を考慮に入れているからです。
つまり、n−2とは、

36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

のセル数に対応しています。

iが2×n≦i<3×n−2(36≦i<52)のとき、

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
0  0 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 18

y[i]=0であり、x[i]=i−(36−1)=i−(2×n−1)です。
全く混沌として、手がかりがないように見えましたが、
普遍的プログラミングの道筋が、光明が見えてきました。

次の

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
1 52  1 68 69 70 71 72 73 74 75 76 77 78 79 80 81 19 82

の場合、すなわちiが68≦i<83の未満の場合はどうでしょうか。
y[i]=1、x[i]=(i−68)+2=i−(68−2)は明らかですが、
68や83はnによってどう表されるのでしょうか。
68は2×nに

36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51

のセル数を加え、さらに

52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67






のセル数を加えればよいわけです。
それぞれn−2ですから、2×(n−2)です。
n=18ですから、32です。
36+32=68で正しいですね。
ですから68は結局
68=2×n+2×(n−2)=4×n−4と表されます。
これはn=18には限定されず、偶数であえば一般的に成り立ちます。
















では、83はどうでしょうか。
83=52+21ですが、21とは何でしょうか。

52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67



のセル数(n−2)と

68 69 70 71 72 73 74 75 76 77 78 79 80 81 19 82

の逆対角線上の水色のセル19を除いたセル数(n−3)の合計です。

したがって、
(n−2)+(n−3)=2×n−5=2×18−5=21
です。
ゆえに、
83は
(3×n−2)+(2×n−5)=5×n−7(=5×18−7=83)
です。



以上より、y[i]=1、x[i]=(i−68)+2=i−(68−2)は
y[i]=1、x[i]=i−((4×n−4)−2)です。
つまり、
4×n−4≦i≦5×n−7のとき、
y[i]=1、x[i]=i−((4×n−4)−2)







このようにして個々のケースは明らかにできます。
しかし、nの値は任意(=nは普遍的)ですから、個々のケースをつないでより一般的に考えなければなりません。
それぞれののケース
  2×n≦i<3×n−2のとき、
    y[i]=0、x[i]=i−(2×n−1)
  4×n−4≦i≦5×n−7のとき、
    y[i]=1、x[i]=i−{(4×n−4)−2}
            ・
            ・
            ・
は一般化できるでしょうか。
言い換えれば、for文で表現することはできるでしょうか。
int j,m;
m=n/2;
for(j=1;j<m+1;j++){
     ・
     ・
     ・
}

一般化するために再度数列と階差数列を掲げておきましょう。
数列
36,68,98,126,152,176,198,218,236
52,83,112,139,164,187,208,227,244
階差数列
32,30,28,26,24,22,20,18
31,29,27,25,23,21,19,17

階差数列の方は一般化が簡単です。
32,30,28,26,24,22,20,18は初項が32で公差が−2ですから、
32−2*(j−1)=2*n−4−2*j+2=2*n−2*j−2
(jはif文のj、そして (j−1)はy(行番号)すなわちj=+1
31,29,27,25,23,21,19,17は32,30,28,26,24,22,20,18からそれぞれ1引けばよいので、
2*n−2*j−3

数学の学習になってしまって申し訳ないのですが、
階差数列bから元の数列aを出す公式は、
=a+(b+b+b+・・・+bj−1)=a+Σb(kはk=1からk=j−1まで)
でした。
その公式に当てはめて36,68,98,126,152,176,198,218,236は
     j−1
2*n+Σ(2*n−2*k−2)=2*n*j−j*j−j+2
      k=1
52,83,112,139,164,187,208,227,244は
        j−1
3*n−2+Σ(2*n−2*k−3)=2*n*j+n−j*j−2*j+1
          k=1



52,83,112,139,164,187,208,227,244の一般項は次の考え方でも、導けます。

52,83,112,139,164,187,208,227,244
の階差数列ととると、
31,29,27,25,23,21,19,17

52=2*n+(n−2)=3*n−2
31={(n−2)−(−1)}+{(n−2)−)}=2*n−2*−3    
は下表の一番左、これはy(行番号)+1に対応、すなわち+1

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
1 0 0 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 18
2 1 52 1 68 69 70 71 72 73 74 75 76 77 78 79 80 81 19 82
3 2 53 83 2 98 99 100 101 102 103 104 105 106 107 108 109 20 110 111
4 3 54 84 112 3 126 127 128 129 130 131 132 133 134 135 21 136 137 138
5 4 55 85 113 139 4 152 153 154 155 156 157 158 159 22 160 161 162 163
6 5 56 86 114 140 164 5 176 177 178 179 180 181 23 182 183 184 185 186
7 6 57 87 115 141 165 187 6 198 199 200 201 24 202 203 204 205 206 207
8 7 58 88 116 142 166 188 208 7 218 219 25 220 221 222 223 224 225 226
9 8 59 89 117 143 167 189 209 227 8 26 236 237 238 239 240 241 242 243
10 9 60 90 118 144 168 190 210 228 27 9 252 253 254 255 256 257 258 259
11 10 61 91 119 145 169 191 211 28 244 260 10 268 269 270 271 272 273 274
12 11 62 92 120 146 170 192 29 229 245 261 275 11 282 283 284 285 286 287
13 12 63 93 121 147 171 30 212 230 246 262 276 288 12 294 295 296 297 298
14 13 64 94 122 148 31 193 213 231 247 263 277 289 299 13 304 305 306 307
15 14 65 95 123 32 172 194 214 232 248 264 278 290 300 308 14 312 313 314
16 15 66 96 33 149 173 195 215 233 249 265 279 291 301 309 315 15 318 319
17 16 67 34 124 150 174 196 216 234 250 266 280 292 302 310 316 320 16 322
18 17  35  97 125 151 175 197 217 235 251 267 281 293 303 311 317 321 323 17

((n−2)−(−1)は=1(すなわち=0(対角線上においてはx=y))のときは0列目の

0
0
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
35





の茶色のセル数、





(n−2)−は(n−2)−(+1)ですから=1すなわち=0とき、
+1)=行目の

 1 52 1 68 69 70 71 72 73 74 75 76 77 78 79 80 81 19 82

の緑のセル数に対応しています。

(ここ講義ではすべてそうですが、色を対応させて読んでください。例えば、

0

に対応いますし、

 1

に対応しています。










52,83,112,139,164,187,208,227,244の初項は3*n−2
で、階差数列は2*n−2*j−3ですから、この数列の一般項は、公式
=a+(b+b+b+・・・+bj−1)=a+Σb(kはk=1からk=j−1まで)
によって、
        j−1
3*n−2+Σ(2*n−2*k−3)=2*n*j+n−j*j−2*j+1
          k=1

36,68,98,126,152,176,198,218,236についても同様に導くこともできます。



y[i]については、

5 4 55 85 113 139 4 152 153 154 155 156 157 158 159 22 160 161 162 163

を見れば分かるように行番号y−1)に対応しているので、y[i]=j−1
x[i]については、
黄色の番号(36,68,98など)のとき、i=2*n*j−j*j−j+2ですので、
x[i]=i−(2*n*j−+2)+(下表で確認して下さい。98の座標3番号3が一致しています。)    
以上から緑色で塗った部分については

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
1 0 0 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 18
2 1 52 1 68 69 70 71 72 73 74 75 76 77 78 79 80 81 19 82
3 2 53 83 2 98 99 100 101 102 103 104 105 106 107 108 109 20 110 111
4 3 54 84 112 3 126 127 128 129 130 131 132 133 134 135 21 136 137 138
5 4 55 85 113 139 4 152 153 154 155 156 157 158 159 22 160 161 162 163
6 5 56 86 114 140 164 5 176 177 178 179 180 181 23 182 183 184 185 186
7 6 57 87 115 141 165 187 6 198 199 200 201 24 202 203 204 205 206 207
8 7 58 88 116 142 166 188 208 7 218 219 25 220 221 222 223 224 225 226
9 8 59 89 117 143 167 189 209 227 8 26 236 237 238 239 240 241 242 243
10 9 60 90 118 144 168 190 210 228 27 9 252 253 254 255 256 257 258 259
11 10 61 91 119 145 169 191 211 28 244 260 10 268 269 270 271 272 273 274
12 11 62 92 120 146 170 192 29 229 245 261 275 11 282 283 284 285 286 287
13 12 63 93 121 147 171 30 212 230 246 262 276 288 12 294 295 296 297 298
14 13 64 94 122 148 31 193 213 231 247 263 277 289 299 13 304 305 306 307
15 14 65 95 123 32 172 194 214 232 248 264 278 290 300 308 14 312 313 314
16 15 66 96 33 149 173 195 215 233 249 265 279 291 301 309 315 15 318 319
17 16 67 34 124 150 174 196 216 234 250 266 280 292 302 310 316 320 16 322
18 17  35  97 125 151 175 197 217 235 251 267 281 293 303 311 317 321 323 17

int j,m;
m=n/2;
for(j=1;j<m+1;j++){
  if((i>=2*n*j-j*j-j+2) && (i<2*n*j+n-j*j-2*j+1)){
    y[i]=j-1;
    x[i]=i-(2*n*j-j*j-j+2)+j;
    if(x[i]>=n-y[i]-1)x[i]++;   //(これは逆対角線を跨ぐときの処理)
  }
}
と一般化できます。

例えば、10次でも同様に成り立つことを確認してみましょう。

0 1 2 3 4 5 6 7 8 9
1 0 0 20 21 22 23 24 25 26 27 10
2 1 28 1 36 37 38 39 40 41 11 42
3 2 29 43 2 50 51 52 53 12 54 55
4 3 30 44 56 3 62 63 13 64 65 66
5 4 31 45 57 67 4 14 72 73 74 75
6 5 32 46 58 68 15 5 80 81 82 83
7 6 33 47 59 16 76 84 6 88 89 90
8 7 34 48 17 69 77 85 91 7 94 95
9 8 35 18 60 70 78 86 92 96 8 98
10 9 19 49 61 71 79 87 93 97 99 9

まず、m=n/2からm=5
for文をトレースしていきましょう。
j=1のとき   
  2*n*j−j*j−j+2=2×10×1−1×1−1+2=20
  2*n*j+n−j*j−2*j+1=2×10×1+10−1×1−2×1+1=28
  よって、iの範囲は20≦i<28
  y[i]=1−1=0
  x[i]=i−(2*n*j−j*j−j+2)+j=i−(2×10×1−1×1−1+2)+1=i−19
  したがって、
  y[20]=0,x[20]=i−19=20−19=1
  y[21]=0,x[21]=i−19=21−19=2
  y[22]=0,x[22]=i−19=22−19=3
  y[23]=0,x[23]=i−19=23−19=4
  y[24]=0,x[24]=i−19=24−19=5
  y[25]=0,x[25]=i−19=25−19=6
  y[26]=0,x[26]=i−19=26−19=7
  y[27]=0,x[20]=i−19=27−19=8
j=2のとき   
  2*n*j−j*j−j+2=2×10×2−2×2−2+2=36
  2*n*j+n−j*j−2*j+1=2×10×2+10−2×2−2×2+1=43
  よって、iの範囲は36≦i<43
  y[i]=2−1=1
  x[i]=i−(2*n*j−j*j−j+2)+j=i−(2×10×2−2×2−2+2)+2=i−34
  したがって、
  y[36]=1,x[36]=i−34=36−34=2
  y[37]=1,x[37]=i−34=37−34=3
  y[38]=1,x[38]=i−34=38−34=4
  y[39]=1,x[39]=i−34=39−34=5
  y[40]=1,x[40]=i−34=40−34=6
  y[41]=1,x[41]=i−34=41−34=7
  y[42]=1,x[42]=i−34=42−34=8
  n−y[42]−1=10−1−1=8なのでif(x[i]>=n-y[i]-1)x[i]++; によりx[42]=9
j=3のとき   
  2*n*j−j*j−j+2=2×10×3−3×3−3+2=50
  2*n*j+n−j*j−2*j+1=2×10×3+10−3×3−2×3+1=56
  よって、iの範囲は50≦i<56
  y[i]=3−1=2
  x[i]=i−(2*n*j−j*j−j+2)+j=i−(2×10×3−3×3−3+2)+3=i−47
  したがって、
  y[50]=2,x[50]=i−47=50−47=3
  y[51]=2,x[51]=i−47=51−47=4
  y[52]=2,x[52]=i−47=52−47=5
  y[53]=2,x[53]=i−47=53−47=6
  y[54]=2,x[54]=i−47=54−47=7
  n−y[55]−1=10−2−1=7なのでif(x[i]>=n-y[i]-1)x[i]++; によりx[54]=8
  y[55]=2,x[55]=i−47=55−47=8
  n−y[55]−1=10−2−1=7なのでif(x[i]>=n-y[i]-1)x[i]++; によりx[55]=9
j=4のとき   
  2*n*j−j*j−j+2=2×10×4−4×4−4+2=62
  2*n*j+n−j*j−2*j+1=2×10×4+10−4×4−2×4+1=67
  よって、iの範囲は62≦i<67
  y[i]=4−1=3
  x[i]=i−(2*n*j−j*j−j+2)+j=i−(2×10×4−4×4−4+2)+4=i−58
  したがって、
  y[62]=3,x[62]=i−58=62−58=4
  y[63]=3,x[63]=i−58=63−58=5
  y[64]=3,x[64]=i−58=64−58=6
  n−y[64]−1=10−3−1=6なのでif(x[i]>=n-y[i]-1)x[i]++; によりx[64]=7
  y[65]=3,x[65]=i−58=65−58=7
  n−y[65]−1=10−3−1=6なのでif(x[i]>=n-y[i]-1)x[i]++; によりx[65]=8
  y[66]=3,x[66]=i−58=66−58=8
  n−y[66]−1=10−2−1=7なのでif(x[i]>=n-y[i]-1)x[i]++; によりx[66]=9
j=5のとき   
  2*n*j−j*j−j+2=2×10×5−5×5−5+2=72
  2*n*j+n−j*j−2*j+1=2×10×5+10−5×5−2×5+1=76
  よって、iの範囲は72≦i<76
  y[i]=5−1=4
  x[i]=i−(2*n*j−j*j−j+2)+j=i−(2×10×5−5×5−5+2)+5=i−67
  したがって、
  y[72]=4,x[72]=i−67=72−67=5
  n−y[72]−1=10−4−1=5なのでif(x[i]>=n-y[i]-1)x[i]++; によりx[72]=6
  y[73]=4,x[73]=i−67=73−67=6
  n−y[73]−1=10−4−1=5なのでif(x[i]>=n-y[i]-1)x[i]++; によりx[73]=7
  y[74]=4,x[74]=i−67=74−67=7
  n−y[74]−1=10−4−1=5なのでif(x[i]>=n-y[i]-1)x[i]++; によりx[74]=8
  y[75]=4,x[75]=i−67=75−67=8
  n−y[75]−1=10−4−1=5なのでif(x[i]>=n-y[i]-1)x[i]++; によりx[75]=9

以上のトレースにより、n=10でもうまくいっていることが分かります。
皆さんは、是非他の偶数次で確認して下さい。  
  
では皆さん、以上を参考にして他の色

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
1 0 0 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 18
2 1 52 1 68 69 70 71 72 73 74 75 76 77 78 79 80 81 19 82
3 2 53 83 2 98 99 100 101 102 103 104 105 106 107 108 109 20 110 111
4 3 54 84 112 3 126 127 128 129 130 131 132 133 134 135 21 136 137 138
5 4 55 85 113 139 4 152 153 154 155 156 157 158 159 22 160 161 162 163
6 5 56 86 114 140 164 5 176 177 178 179 180 181 23 182 183 184 185 186
7 6 57 87 115 141 165 187 6 198 199 200 201 24 202 203 204 205 206 207
8 7 58 88 116 142 166 188 208 7 218 219 25 220 221 222 223 224 225 226
9 8 59 89 117 143 167 189 209 227 8 26 236 237 238 239 240 241 242 243
10 9 60 90 118 144 168 190 210 228 27 9 252 253 254 255 256 257 258 259
11 10 61 91 119 145 169 191 211 28 244 260 10 268 269 270 271 272 273 274
12 11 62 92 120 146 170 192 29 229 245 261 275 11 282 283 284 285 286 287
13 12 63 93 121 147 171 30 212 230 246 262 276 288 12 294 295 296 297 298
14 13 64 94 122 148 31 193 213 231 247 263 277 289 299 13 304 305 306 307
15 14 65 95 123 32 172 194 214 232 248 264 278 290 300 308 14 312 313 314
16 15 66 96 33 149 173 195 215 233 249 265 279 291 301 309 315 15 318 319
17 16 67 34 124 150 174 196 216 234 250 266 280 292 302 310 316 320 16 322
18 17  35  97 125 151 175 197 217 235 251 267 281 293 303 311 317 321 323 17

にも挑戦して下さい。
さらに、奇数の場合も考えてみましょう。
これでどんな値でもnに代入することのできる普遍的なプログラミングができます。

そして、番号付けに成功したなら、一般種法による魔方陣の高速化に挑戦して下さい。






第20講第2話へ 第20講第4話へ



VC++講義第1部へ
vb講義へ
VB講義基礎へ
初心者のための世界で一番わかりやすいVisual C++入門基礎講座
初心者のための世界で一番わかりやすいVisual Basic入門基礎講座