分治法解决残缺棋盘的规划

2744557306

1. board=zeros(100,100);% z6 {. }1 d3 b5 C: v% c
   
2. n=4;' A: \; [4 Q\" @. [7 ?: M7 b
   
3. size=2^n;7 p& A8 W4 U' \  [1 b8 L, G
   
4. amount=0;% w: l\" j' Q9 C, B$ E
   
5. [board,amount]=cover(1,1,2,5,board,size,amount);
   2 k/ j7 }* w1 {; n4 J/ O3 \/ ]
6. board(1:size,1:size)! N% K; @* v+ ~  j6 r. I$ S
   
7. # V; M$ C$ S& @3 z) {3 g
   

复制代码

1. function [board,amount]=cover(i,j,k,l,board,size,amount)%(i,j)为左上角 (k,l)残缺 size为规模 amount为片数3 s9 [1 O! I9 D* ^3 v
   
2. ( ^9 g6 H$ d  f0 R1 B
   
3. if size==1
   9 I5 a, [  N' {; _# e# N6 z1 D) n
4. return, ~\" C' t$ V% h+ O\" }
   
5. end  h* C$ f4 U! c3 O) V7 B3 j
   
6. amount=amount+1;
   4 E. z, W( o$ e  B0 f  l
7. size=size/2;
   + k, n/ M, f) X% T) T! U
8. if (k<size+i)&(l<size+j)%残缺位于左上棋盘1 J/ }, R4 X6 ~4 |+ q, c7 g
   
9. / C# o, O4 I0 J3 w) V
   
10. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i,size+j-1)=amount;%放置
    # w: c3 j. C4 [( b5 x0 ?
11. [board,amount]=cover(i,j,k,l,board,size,amount);[board,amount]=cover(i,j+size,size+i-1,j+size,board,size,amount);
    ( J. w; ]# F* A, m; o) v
12. [board,amount]=cover(size+i,size+j,size+i,size+j,board,size,amount);[board,amount]=cover(i+size,j,i+size,j+size-1,board,size,amount);& N% @& k% s* @  e  {
    
13. elseif (k>=size+i)&(l<size+j)%残缺位于左下棋盘4 d+ o5 r0 H7 b  Y4 g% s3 E
    
14. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置- n\" r# a2 ?! D7 I% O\" u( ]; g
    
15. [board,amount]=cover(i+size,j,k,l,board,size,amount);[board,amount]=cover(i,j+size,size+i-1,j+size,board,size,amount);& H6 t. X\" t; P4 {0 I5 G\" u- U
    
16. [board,amount]=cover(size+i,size+j,size+i,size+j,board,size,amount);[board,amount]=cover(i,j,i+size-1,j+size-1,board,size,amount);
    $ T$ W# ~! q: _2 b) K3 x
17. elseif (k<size+i)&(l>=size+j)%残缺位于右上棋盘0 q0 M/ ^' Q  Y6 u: p2 b& O% [
    
18. board(size+i,size+j-1)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
    # Q2 J5 p0 i+ m* ~
19. [board,amount]=cover(i,j+size,k,l,board,size,amount);[board,amount]=cover(i,j,i+size-1,j+size-1,board,size,amount);9 P, K4 u' I7 s2 r4 f, ~4 X
    
20. [board,amount]=cover(size+i,size+j,size+i,size+j,board,size,amount);[board,amount]=cover(i+size,j,i+size,j+size-1,board,size,amount);1 g( ^: T0 O1 p) A0 j\" m* N4 U. Z
    
21. elseif (k>=size+i)&(l>=size+j)%残缺位于右下棋盘, o1 _9 N% C' P  G
    
22. board(size+i,size+j-1)=amount;board(size+i-1,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置4 z, U+ {\" X3 U; y& X2 [
    
23. [board,amount]=cover(size+i,size+j,k,l,board,size,amount);[board,amount]=cover(i,j+size,size+i-1,j+size,board,size,amount);
    + h' K, J' s( n; S) x$ w
24. [board,amount]=cover(i,j,i+size-1,j+size-1,board,size,amount);[board,amount]=cover(i+size,j,i+size,j+size-1,board,size,amount);
    ; p) C1 h$ ~8 x/ z$ T  P# E+ r7 R
25. end
    ) N6 }  J3 k; R7 \$ }/ J8 J
26. 1 L* B; ~( ]5 ~2 L
    
27. end

复制代码

这段代码实现了一个递归算法，用于在一个二维棋盘上填充缺失的部分，其中棋盘大小为100x100。下面是对代码的详细解释：1.初始化：2.board 是一个100x100的矩阵，初始化为全零。这个矩阵表示棋盘，其中的元素将被填充。3.n 表示棋盘的2的幂次方边长，这里设置为4，所以 size = 2^n 就是棋盘的边长。4.amount 用于计数已经填充的片数，初始化为0。5.调用 cover 函数：6.cover 函数是一个递归函数，用于填充缺失的部分。它接受左上角坐标 (i, j) 和残缺区域的左上角坐标 (k, l)，以及当前棋盘的大小 size 和已填充的片数 amount。7.函数首先检查 size 是否为1，如果是，表示当前棋盘已经缩小到最小规模，不再分割，直接返回。8.递归填充：9.然后，函数增加 amount，表示填充了一个片。10.接下来，根据缺失区域的位置，分别在左上、左下、右上、右下四个棋盘中的合适位置填充片，然后递归调用 cover 函数。11.递归终止条件：12.递归的终止条件是 size 变为1，此时直接返回。13.输出结果：14.最后，输出已经填充的棋盘的左上角大小为 size 的部分。这段代码实现了一个分治算法，通过递归地在每个棋盘区域填充缺失的部分，最终完成整个棋盘的填充。在递归的过程中，通过调整参数来实现在不同的子棋盘中填充片。函数的输出是填充完成后的部分棋盘。

. O+ p+ s" Y# S