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

2744557306

1. board=zeros(100,100);\" C, U+ B2 j- u+ M+ l
   
2. n=4;
   + S( n& N* ?9 Z, v# E% I
3. size=2^n;
   & i+ K: H: i2 C/ u8 O$ B2 \: \
4. amount=0;4 @0 v9 {\" X2 T+ C; g& L
   
5. [board,amount]=cover(1,1,2,5,board,size,amount);
   ; i- s6 H0 {# E/ J5 e
6. board(1:size,1:size)\" f- F1 I' |( y7 R
   
7. + D\" J5 ~; E8 h' \3 f
   

复制代码

1. function [board,amount]=cover(i,j,k,l,board,size,amount)%(i,j)为左上角 (k,l)残缺 size为规模 amount为片数8 U$ \- s7 n+ o6 R
   
2. / k* e! Y4 g5 \. R2 C& X) c6 {8 Q! F' {
   
3. if size==1
   / m3 I/ M6 t% n  g$ o
4. return
   # d9 b4 k: Y8 I& F; R) Y# w/ `
5. end) y\" Q0 M3 G. P4 ~/ C4 ~, E+ U
   
6. amount=amount+1;
   * K; n  E% U9 S) w, n/ {, A& K7 t
7. size=size/2;
   ! n# S4 r! W$ C8 t
8. if (k<size+i)&(l<size+j)%残缺位于左上棋盘9 L+ g8 h$ z) e, v* J$ r
   
9. 
   , Y9 R* u3 t- n- }; r% A
10. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i,size+j-1)=amount;%放置
    % ?% G) m8 Q( E; t
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);
    $ R8 S# H1 b* U0 ]% y
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);1 b, C7 v, [8 p& H! u\" @
    
13. elseif (k>=size+i)&(l<size+j)%残缺位于左下棋盘$ A1 p- ]$ l/ B3 K5 d/ m
    
14. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
    ( T' j# J# w5 ]+ ]& M
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);
    & `\" ]& S4 W7 f2 W$ ?4 ^
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);' K$ f$ i  N4 @/ k
    
17. elseif (k<size+i)&(l>=size+j)%残缺位于右上棋盘
    % h4 u- a/ l. O
18. board(size+i,size+j-1)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置\" T5 u2 o/ {8 R$ x6 G. A, o5 _' U
    
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);! ~6 H8 c- M& p% `- P2 |
    
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);  [$ z& P0 {\" x
    
21. elseif (k>=size+i)&(l>=size+j)%残缺位于右下棋盘
    3 ]1 y4 E! F1 j8 y$ ^9 ]* M; f
22. board(size+i,size+j-1)=amount;board(size+i-1,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
    & d: {! E$ f) X( F
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);
    4 C( a. ?& h7 Q7 C  {. g
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);
    / c; o7 w  J3 C
25. end* U( A8 k/ Q6 q, z$ C3 h* n/ U  t
    
26. ) D# y: u% J+ q# j% b& P+ 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 的部分。这段代码实现了一个分治算法，通过递归地在每个棋盘区域填充缺失的部分，最终完成整个棋盘的填充。在递归的过程中，通过调整参数来实现在不同的子棋盘中填充片。函数的输出是填充完成后的部分棋盘。