1 unit AmidaU; 2 3 interface 4 5 uses 6 Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, 7 StdCtrls, ExtCtrls; 8 9 const 10 TateSuu = 13; // 縦線の数 11 YokoSuu = TateSuu*(TateSuu-1) div 2; // 横線の最大数 12 // = 1+2+...+(TateSuu-1) 13 YokoHaba = 60; // 縦線の間隔 14 TateHaba = 10; // 横線の間隔 15 type 16 TMitiNo = 0..TateSuu; // 道(縦線)の番号 17 TKawaNo = 0..TateSuu-1; // 川(縦線の間)の番号 18 TYokoNo = 0..YokoSuu; // 橋桁(横線)の番号 19 TYokoSen = (ysNone,ysKeta,ysHasi); // 何もない,桁,橋 20 THasi = array [TKawaNo,TYokoNo] of TYokoSen ; // 横線の状況 21 TJunretu = array [TMitiNo] of Byte; // 並べ替えるデータ 22 TAmida = class(TImage) 23 constructor Create(AOwner : TComponent); override; 24 private 25 Hasi : THasi; 26 Hajime : TJunretu; // データの初めの状態 27 Genzai : TJunretu; // データの現在の状態 28 LastYoko : TYokoNo; // 最後に橋を架けた位置 29 Style : 0..3; // くじのスタイル 30 procedure MondaiSakusei; 31 procedure SyokiSettei; 32 procedure HasiWoKakeru(Kawa : TKawaNo; Yoko : TYokoNo); 33 function Seikou : Boolean; 34 procedure HasiWoKaku(Kawa : TKawaNo; Yoko : TYokoNo); 35 procedure JunretuWoKaku(Junretu : TJunretu; Y : Integer); 36 procedure AmidaWoKaku; 37 procedure IdouSuru(M1,M2 : TMitiNo; Y : TYokoNo; PM : Integer); 38 procedure Compact; 39 procedure InsertSort; 40 procedure BubbleSort; 41 procedure InsertSort2; 42 procedure BubbleSort2; 43 procedure InsertSort3; 44 procedure InsertSort4; 45 procedure BubbleSort3; 46 procedure BubbleSort4; 47 procedure ShellSort; 48 procedure AmidaMouseDown(Sender: TObject; Button: TMouseButton; 49 Shift: TShiftState; X, Y: Integer); 50 end; 51 TFormAmida = class(TForm) 52 PanelMain: TPanel; 53 ButtonClose: TButton; 54 ButtonRestart: TButton; 55 ButtonNew: TButton; 56 RadioGroupStyle: TRadioGroup; 57 ButtonInsert: TButton; 58 ButtonBubble: TButton; 59 ButtonInsert2: TButton; 60 ButtonBubble2: TButton; 61 ButtonCompact: TButton; 62 ButtonInsert3: TButton; 63 ButtonInsert4: TButton; 64 ButtonBubble3: TButton; 65 ButtonBubble4: TButton; 66 ButtonShell: TButton; 67 procedure ButtonCloseClick(Sender: TObject); 68 procedure FormCreate(Sender: TObject); 69 procedure ButtonRestartClick(Sender: TObject); 70 procedure ButtonNewClick(Sender: TObject); 71 procedure RadioGroupStyleClick(Sender: TObject); 72 procedure ButtonInsertClick(Sender: TObject); 73 private 74 Amida : TAmida; 75 procedure AmidaSakusei; 76 public 77 { Public 宣言 } 78 end; 79 80 var 81 FormAmida: TFormAmida; 82 83 implementation 84 85 {$R *.DFM} 86 (******************** 一般のプロシージャ ********************) 87 (******************** TAmida のメソッド ********************) 88 procedure TAmida.IdouSuru(M1,M2 : TMitiNo; Y : TYokoNo; PM : Integer); 89 (* M1 から M2 に一方通行の橋を架ける *) 90 (* 符号 PM によって上下に少しずらして描く *) 91 begin 92 with Canvas do 93 begin 94 Pen.Width := 1; 95 if PM = 0 96 then Pen.Color := clred 97 else Pen.Color := clYellow; 98 MoveTo(M1*YokoHaba,(Y+5)*TateHaba+PM*3); 99 LineTo(M2*YokoHaba,(Y+5)*TateHaba+PM*3); 100 Genzai[M2] := Genzai[M1]; 101 end; 102 end; (* IdouSuru *) 103 104 procedure TAmida.Compact; 105 (* 段数最小で整列する *) 106 var 107 Kawa : 1..TateSuu+1; 108 Yoko : 1..YokoSuu+1; 109 begin 110 for Yoko := 1 to TateSuu do 111 begin 112 Kawa := 2-Yoko mod 2; 113 repeat 114 Hasi[Kawa,Yoko] := ysKeta; // 桁を作る 115 HasiWoKaku(Kawa,Yoko); 116 if Genzai[Kawa] < Genzai[Kawa+1] // 左が右より小さいなら 117 then HasiWoKakeru(Kawa,Yoko); // 橋を架ける(交換する) 118 Inc(Kawa,2); 119 until Kawa >= TateSuu; 120 end; 121 122 end; (* Compact *) 123 124 procedure TAmida.InsertSort; 125 (* 挿入法で整列する *) 126 var 127 Kawa : TKawaNo; 128 Yoko : 1..YokoSuu+1; 129 KawaStart : TKawaNo; 130 begin 131 Yoko := 1; 132 for KawaStart := 1 to TateSuu-1 do 133 for Kawa := KawaStart downto 1 do 134 begin 135 Hasi[Kawa,Yoko] := ysKeta; // 桁を作る 136 HasiWoKaku(Kawa,Yoko); 137 if Genzai[Kawa] < Genzai[Kawa+1] // 左が右より小さいなら 138 then HasiWoKakeru(Kawa,Yoko); // 橋を架ける(交換する) 139 Inc(Yoko); 140 end; 141 end; (* InsertSort *) 142 143 procedure TAmida.BubbleSort; 144 (* 泡法で整列する *) 145 var 146 Kawa : TKawaNo; 147 Yoko : 1..YokoSuu+1; 148 KawaEnd : TKawaNo; 149 begin 150 Yoko := 1; 151 for KawaEnd := TateSuu-1 downto 1 do 152 for Kawa := 1 to KawaEnd do 153 begin 154 Hasi[Kawa,Yoko] := ysKeta; // 桁を作る 155 HasiWoKaku(Kawa,Yoko); 156 if Genzai[Kawa] < Genzai[Kawa+1] // 左が右より小さいなら 157 then HasiWoKakeru(Kawa,Yoko); // 橋を架ける(交換する) 158 Inc(Yoko); 159 end; 160 end; (* BubbleSort *) 161 162 procedure TAmida.InsertSort2; 163 (* 挿入法で整列する 改良版 *) 164 var 165 Kawa : 0..TateSuu-1; 166 Yoko : 1..YokoSuu+1; 167 KawaStart : TKawaNo; 168 begin 169 Yoko := 1; 170 for KawaStart := 1 to TateSuu-1 do 171 begin 172 Kawa := KawaStart; 173 repeat 174 Hasi[Kawa,Yoko] := ysKeta; // 桁を作る 175 HasiWoKaku(Kawa,Yoko); 176 if Genzai[Kawa] < Genzai[Kawa+1] // 左が右より小さいなら 177 then HasiWoKakeru(Kawa,Yoko) // 橋を架ける(交換する) 178 else Kawa := 1; // 最後まで調べたことにする 179 Inc(Yoko); 180 Dec(Kawa); 181 until Kawa = 0; 182 end; 183 end; (* InsertSort2 *) 184 185 procedure TAmida.BubbleSort2; 186 (* 泡法で整列する 改良版 *) 187 var 188 Kawa : TKawaNo; 189 Yoko : 1..YokoSuu+1; 190 KawaEnd : 0..TateSuu-1; 191 KawaStart : TKawaNo; 192 KoukanFirst : TKawaNo; 193 KoukanLast : TKawaNo; 194 begin 195 Yoko := 1; 196 KawaStart := 1; 197 KawaEnd := TateSuu-1; 198 repeat 199 KoukanFirst := TateSuu-1; 200 KoukanLast := 1; 201 for Kawa := KawaStart to KawaEnd do 202 begin 203 Hasi[Kawa,Yoko] := ysKeta; // 桁を作る 204 HasiWoKaku(Kawa,Yoko); 205 if Genzai[Kawa] < Genzai[Kawa+1] // 左が右より小さいなら 206 then begin 207 HasiWoKakeru(Kawa,Yoko); // 橋を架ける(交換する) 208 if Kawa < KoukanFirst 209 then KoukanFirst := Kawa; // 最初に橋を架けた川を記憶する 210 KoukanLast := Kawa; // 最後に橋を架けた川を記憶する 211 end; 212 Inc(Yoko); 213 end; 214 if KoukanFirst > 1 215 then KawaStart := KoukanFirst-1; 216 KawaEnd := KoukanLast-1; 217 until KawaStart > KawaEnd; 218 end; (* BubbleSort2 *) 219 220 procedure TAmida.InsertSort3; 221 (* 挿入法で整列する 改良版 *) 222 var 223 Kawa : 0..TateSuu-1; 224 Yoko : 1..YokoSuu+1; 225 KawaStart : TKawaNo; 226 begin 227 Yoko := 1; 228 for KawaStart := 1 to TateSuu-1 do 229 begin 230 Kawa := KawaStart; 231 while (Kawa > 0) and (Genzai[Kawa] < Genzai[Kawa+1]) do // 左が小さい間 232 begin 233 IdouSuru(Kawa+1,0,Yoko,-1); // 交換する 234 IdouSuru(Kawa,Kawa+1,Yoko,0); 235 IdouSuru(0,Kawa,Yoko,+1); 236 Inc(Yoko); 237 Dec(Kawa); // 左の川へ 238 end; 239 JunretuWoKaku(Genzai,(YokoSuu+7)*TateHaba); 240 end; 241 end; (* InsertSort3 *) 242 243 procedure TAmida.InsertSort4; 244 (* 挿入法で整列する 再改良版 *) 245 var 246 Kawa : TKawaNo; 247 Yoko : 1..YokoSuu+1; 248 KawaStart : TKawaNo; 249 begin 250 Yoko := 1; 251 for KawaStart := 1 to TateSuu-1 do 252 begin 253 Kawa := KawaStart; 254 IdouSuru(Kawa+1,0,Yoko,-1); // 0 番に退避 255 while (Kawa > 0) and (Genzai[Kawa] < Genzai[0]) do // 小さい間 256 begin 257 IdouSuru(Kawa,Kawa+1,Yoko,0); // 右に移動 258 Inc(Yoko); 259 Dec(Kawa); // 左の川へ 260 end; 261 IdouSuru(0,Kawa+1,Yoko-1,+1); // 0 番を挿入 262 JunretuWoKaku(Genzai,(YokoSuu+7)*TateHaba); 263 end; 264 end; (* InsertSort4 *) 265 266 procedure TAmida.ShellSort; 267 (* シェルソート,挿入整列法の高速版 *) 268 (* InsertSort2 を初めは粗く、段々細かく行なう *) 269 var 270 KawaStart : TKawaNo; 271 Kawa,Amari,Arasa : Integer; 272 Yoko : 1..YokoSuu+1; 273 Bairitu : Real; 274 begin 275 Bairitu := 0.4; 276 Yoko := 1; 277 Arasa := TateSuu; 278 repeat 279 Arasa := Trunc(Arasa*Bairitu); 280 if Arasa < 2 281 then Arasa := 1; // 最後は InsertSort2 になる 282 for KawaStart := 1 to TateSuu-Arasa do 283 begin 284 Kawa := KawaStart; 285 while (Kawa > 0) and (Genzai[Kawa] < Genzai[Kawa+Arasa]) do 286 begin 287 //IdouSuru(Kawa+Arasa,0,Yoko,-1); 288 Genzai[0] := Genzai[Kawa+Arasa]; 289 IdouSuru(Kawa,Kawa+Arasa,Yoko,0); 290 //IdouSuru(0,Kawa,Yoko,+1); 291 Genzai[Kawa] := Genzai[0]; 292 Inc(Yoko); 293 Dec(Kawa,Arasa); 294 end; 295 end; 296 JunretuWoKaku(Genzai,(YokoSuu+7)*TateHaba); 297 until Arasa = 1; 298 end; (* ShellSort *) 299 300 301 procedure TAmida.BubbleSort3; 302 (* 泡法で整列する 改良版 *) 303 var 304 Kawa : TKawaNo; 305 Yoko : 1..YokoSuu+1; 306 KawaEnd : 0..TateSuu-1; 307 KawaStart : TKawaNo; 308 KoukanFirst : TKawaNo; 309 KoukanLast : TKawaNo; 310 begin 311 Yoko := 1; 312 KawaStart := 1; 313 KawaEnd := TateSuu-1; 314 repeat 315 KoukanFirst := TateSuu-1; 316 KoukanLast := 1; 317 for Kawa := KawaStart to KawaEnd do 318 begin 319 if Genzai[Kawa] < Genzai[Kawa+1] // 左が右より小さいなら 320 then begin 321 IdouSuru(Kawa+1,0,Yoko,-1); // 交換する 322 IdouSuru(Kawa,Kawa+1,Yoko,0); 323 IdouSuru(0,Kawa,Yoko,+1); 324 if Kawa < KoukanFirst 325 then KoukanFirst := Kawa; // 最初に橋を架けた川を記憶する 326 KoukanLast := Kawa; // 最後に橋を架けた川を記憶する 327 end; 328 Inc(Yoko); 329 end; 330 if KoukanFirst > 1 331 then KawaStart := KoukanFirst-1; 332 KawaEnd := KoukanLast-1; 333 JunretuWoKaku(Genzai,(YokoSuu+7)*TateHaba); 334 until KawaStart > KawaEnd; 335 end; (* BubbleSort3 *) 336 337 procedure TAmida.BubbleSort4; 338 (* 泡法で整列する 改良版 *) 339 var 340 Kawa : TKawaNo; 341 Yoko : 1..YokoSuu+1; 342 KawaEnd : 0..TateSuu-1; 343 KawaStart : TKawaNo; 344 KoukanFirst : TKawaNo; 345 KoukanLast : TKawaNo; 346 begin 347 Yoko := 1; 348 KawaStart := 1; 349 KawaEnd := TateSuu-1; 350 repeat 351 IdouSuru(KawaStart,0,Yoko,-1); // 0 番に退避 352 KoukanFirst := TateSuu-1; 353 KoukanLast := 1; 354 for Kawa := KawaStart to KawaEnd do 355 begin 356 if Genzai[Kawa+1] > Genzai[0] // 右が大きいなら 357 then begin 358 IdouSuru(Kawa+1,Kawa,Yoko,0); // 左に移動 359 if Kawa < KoukanFirst 360 then KoukanFirst := Kawa; // 最初に橋を架けた川を記憶する 361 KoukanLast := Kawa; // 最後に橋を架けた川を記憶する 362 end 363 else begin 364 IdouSuru(0,Kawa,Yoko,+1); 365 IdouSuru(Kawa+1,0,Yoko+1,-1); 366 end; 367 Inc(Yoko); 368 end; 369 IdouSuru(0,KawaEnd+1,Yoko-1,+1); 370 if KoukanFirst > 1 371 then KawaStart := KoukanFirst-1; 372 KawaEnd := KoukanLast-1; 373 JunretuWoKaku(Genzai,(YokoSuu+7)*TateHaba); 374 until KawaStart > KawaEnd; 375 end; (* BubbleSort4 *) 376 377 378 procedure TAmida.MondaiSakusei; 379 (* 問題(初めの状態)を作る *) 380 var 381 Miti : TMitiNo; 382 begin 383 for Miti := 1 to TateSuu do 384 Hajime[Miti] := Random(90)+10; // 2桁の乱数 385 SyokiSettei; 386 end; (* MondaiSakusei *) 387 388 procedure TAmida.SyokiSettei; 389 (* 横線の状況を初期化する *) 390 var 391 Kawa : 1..TateSuu+1; 392 Yoko : 1..YokoSuu+1; 393 KawaStart : TKawaNo; 394 KawaEnd : TKawaNo; 395 begin 396 // どこにも橋も桁もない状態にする 397 for Kawa := 1 to TateSuu-1 do 398 for Yoko := 1 to YokoSuu do 399 Hasi[Kawa,Yoko] := ysNone; 400 // スタイルに従って桁を作る 401 case Style of 402 0 : begin // 段数最小 403 for Yoko := 1 to TateSuu do 404 begin 405 Kawa := 2-Yoko mod 2; 406 repeat 407 Hasi[Kawa,Yoko] := ysKeta; 408 Inc(Kawa,2); 409 until Kawa >= TateSuu; 410 end; 411 end; 412 1 : begin // 挿入整列法 413 Yoko := 1; 414 for KawaStart := 1 to TateSuu-1 do 415 for Kawa := KawaStart downto 1 do 416 begin 417 Hasi[Kawa,Yoko] := ysKeta; 418 Inc(Yoko); 419 end; 420 end; 421 2 : begin // 泡整列法 422 Yoko := 1; 423 for KawaEnd := TateSuu-1 downto 1 do 424 for Kawa := 1 to KawaEnd do 425 begin 426 Hasi[Kawa,Yoko] := ysKeta; 427 Inc(Yoko); 428 end; 429 end; 430 end; 431 // データを初期状態に戻す 432 Genzai := Hajime; 433 LastYoko := 1; 434 AmidaWoKaku; 435 end; (* SyokiSettei *) 436 437 procedure TAmida.HasiWoKakeru(Kawa : TKawaNo; Yoko : TYokoNo); 438 (* 橋を架ける *) 439 var 440 Hidari : Byte; 441 begin 442 Hasi[Kawa,Yoko] := ysHasi; 443 LastYoko := Yoko; 444 HasiWoKaku(Kawa,Yoko); 445 Hidari := Genzai[Kawa]; 446 Genzai[Kawa] := Genzai[Kawa+1]; 447 Genzai[Kawa+1] := Hidari; 448 JunretuWoKaku(Genzai,(YokoSuu+7)*TateHaba); 449 if (Style < 3) and Seikou 450 then ShowMessage(' お め で と う '); 451 end; (* HasiWoKakeru *) 452 453 function TAmida.Seikou : Boolean; 454 (* Genzai が降順に整列したら成功 *) 455 var 456 Miti : TMitiNo; 457 begin 458 Miti := 1; 459 while (Miti < TateSuu) and (Genzai[Miti] >= Genzai[Miti+1]) do 460 Inc(Miti); 461 Seikou := Miti >= TateSuu; 462 end; (* Seikou *) 463 464 procedure TAmida.HasiWoKaku(Kawa : TKawaNo; Yoko : TYokoNo); 465 (* 何もない → 描かない  *) 466 (* 橋桁   → 白線を描く *) 467 (* 橋    → 赤線を描く *) 468 begin 469 if Hasi[Kawa,Yoko] <> ysNone 470 then with Canvas do 471 begin 472 Pen.Width := 1; 473 case Hasi[Kawa,Yoko] of 474 ysKeta : Pen.Color := clWhite; 475 ysHasi : Pen.Color := clRed; 476 end; 477 MoveTo(Kawa*YokoHaba,(Yoko+5)*TateHaba); 478 LineTo((Kawa+1)*YokoHaba,(Yoko+5)*TateHaba); 479 end; 480 end; (* HasiWoKaku *) 481 482 procedure TAmida.JunretuWoKaku(Junretu : TJunretu; Y : Integer); 483 (* 順列を描く *) 484 var 485 Miti : TMitiNo; 486 begin 487 for Miti := 1 to TateSuu do 488 Canvas.TextOut(Miti*YokoHaba-10,Y,IntToStr(Junretu[Miti])); 489 end; (* JunretuWoKaku *) 490 491 procedure TAmida.AmidaWoKaku; 492 (* あみだくじを描く *) 493 var 494 Miti : TMitiNo; 495 Kawa : TKawaNo; 496 Yoko : TYokoNo; 497 begin 498 with Canvas do 499 begin 500 FillRect(ClipRect); 501 for Kawa := 1 to TateSuu-1 do 502 for Yoko := 1 to YokoSuu do 503 HasiWoKaku(Kawa,Yoko); 504 Pen.Width := 3; 505 Pen.Color := clRed; 506 for Miti := 1 to TateSuu do 507 begin 508 MoveTo(Miti*YokoHaba,5*TateHaba); 509 LineTo(Miti*YokoHaba,(YokoSuu+6)*TateHaba); 510 end; 511 JunretuWoKaku(Hajime,2*TateHaba); 512 JunretuWoKaku(Genzai,(YokoSuu+7)*TateHaba); 513 end; 514 end; {AmidaWoKaku} 515 516 procedure TAmida.AmidaMouseDown(Sender: TObject; Button: TMouseButton; 517 Shift: TShiftState; X, Y: Integer); 518 (* OnMouseDown イベントハンドラー *) 519 (* クリックした橋桁に橋を架ける *) 520 var 521 Kawa : Integer; 522 Yoko : Integer; 523 begin 524 Kawa := X div YokoHaba; 525 Yoko := Round(Y / TateHaba) -5; 526 if (Kawa in [1..TateSuu-1]) and (Yoko in [LastYoko..YokoSuu]) and 527 (Hasi[Kawa,Yoko] = ysKeta) 528 then HasiWoKakeru(Kawa,Yoko); 529 end; (* AmidaMouseDown *) 530 531 constructor TAmida.Create(AOwner : TComponent); 532 (* 生成する *) 533 begin 534 inherited; // 元になるImageを生成 535 Parent := TWinControl(AOwner); // AOwnerの中に置く 536 Height := (YokoSuu+10)*TateHaba; // サイズ 537 Width := (TateSuu+1)*YokoHaba; 538 Left := 0; // 位置 539 Top := 0; 540 with Canvas do 541 begin 542 Font.Height := 20; 543 Brush.Color := clAqua; 544 FillRect(ClipRect); // 水色で塗りつぶす 545 end; 546 OnMouseDown := AmidaMouseDown; 547 end; (* Create *) 548 549 (******************** フォームのメソッド ********************) 550 procedure TFormAmida.AmidaSakusei; 551 (* Amida を作成する *) 552 begin 553 Amida := TAmida.Create(Self); // Self=FormAmida 554 ClientHeight := Amida.Height; // FormのClient部のサイズ 555 ClientWidth := Amida.Width +PanelMain.Width; 556 end; (* AmidaSakusei *) 557 558 (******************** イベントハンドラー ********************) 559 procedure TFormAmida.ButtonCloseClick(Sender: TObject); 560 begin 561 Close; 562 end; (* ButtonCloseClick *) 563 564 procedure TFormAmida.FormCreate(Sender: TObject); 565 begin 566 AmidaSakusei; 567 Amida.MondaiSakusei; 568 end; (* FormCreate *) 569 570 procedure TFormAmida.ButtonRestartClick(Sender: TObject); 571 begin 572 Amida.SyokiSettei; 573 end; (* ButtonRestartClick *) 574 575 procedure TFormAmida.ButtonNewClick(Sender: TObject); 576 begin 577 Amida.MondaiSakusei; 578 end; (* ButtonNewClick *) 579 580 procedure TFormAmida.RadioGroupStyleClick(Sender: TObject); 581 begin 582 Amida.Style := RadioGroupStyle.ItemIndex; 583 Amida.SyokiSettei; 584 end; (* RadioGroupStyleClick *) 585 586 procedure TFormAmida.ButtonInsertClick(Sender: TObject); 587 begin 588 Amida.Style := 3; 589 Amida.SyokiSettei; 590 case TButton(Sender).Tag of 591 0 : Amida.Compact; 592 1 : Amida.InsertSort; 593 2 : Amida.BubbleSort; 594 3 : Amida.InsertSort2; 595 4 : Amida.BubbleSort2; 596 5 : Amida.InsertSort3; 597 6 : Amida.InsertSort4; 598 7 : Amida.BubbleSort3; 599 8 : Amida.BubbleSort4; 600 9 : Amida.ShellSort; 601 end; 602 end; (* ButtonInsertClick *) 603 604 end.