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

2744557306

1. board=zeros(100,100);: t# z& X1 w  a4 {/ q: w8 b
   
2. n=4;
   \" ]3 U+ r$ ]5 }\" K9 ^# h
3. size=2^n;5 i% k: |# L2 V& B) J\" l
   
4. amount=0;
   , w0 x# K: H  X8 G8 f  y9 T
5. [board,amount]=cover(1,1,2,5,board,size,amount);; x( c6 R1 p: u; ^\" R
   
6. board(1:size,1:size)  T% w\" G\" h- S) E
   
7. 
   / _4 c! ]% P1 Q* m% D4 U

复制代码

1. function [board,amount]=cover(i,j,k,l,board,size,amount)%(i,j)为左上角 (k,l)残缺 size为规模 amount为片数
   # p; e) @& g7 U\" r
2. 
   2 M+ ?2 J, s% r/ a) H4 m
3. if size==1\" N5 M# ^( T; `5 G0 e# Z8 Y
   
4. return- @& T1 I) t. Y2 G! d% R
   
5. end+ _6 L6 e) z6 @2 O\" i
   
6. amount=amount+1;  g: }) ^0 Y4 M2 x
   
7. size=size/2;) V4 S( ?) K, a) O1 @$ b* _
   
8. if (k<size+i)&(l<size+j)%残缺位于左上棋盘
   ! R; W' ?5 j: v; |
9. 
   6 ]* _0 k3 U3 t: W4 V% F9 G
10. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i,size+j-1)=amount;%放置- |1 R4 `$ u- ~7 ~8 {
    
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);0 L* z9 w' z1 D) s( C- g* H; E
    
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);9 T- f5 f$ \# i
    
13. elseif (k>=size+i)&(l<size+j)%残缺位于左下棋盘
    5 r. A* B) N/ p- U% z2 Q
14. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
    5 b+ n3 J9 B! B; ^
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);  e& X$ x\" r* V: u. s
    
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);
    ! d: m( {# v$ n( T
17. elseif (k<size+i)&(l>=size+j)%残缺位于右上棋盘- w# p! Z! D* h
    
18. board(size+i,size+j-1)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置; K* N) t- ]: b
    
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 O7 W( Q7 m' f6 U/ O- @/ q: C! D  t
    
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);. [. Y/ o\" D) I$ g& r
    
21. elseif (k>=size+i)&(l>=size+j)%残缺位于右下棋盘- Z: T$ j. e: ]  E  B8 h
    
22. board(size+i,size+j-1)=amount;board(size+i-1,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置, z, I  @- h; t) Z0 v
    
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);
    0 H$ b/ w6 M* f1 s) W( U
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);
    : ^9 D4 E) e' \; l- E\" V\" j% ]+ B0 d+ h
25. end
    2 Q7 o) m9 l; N1 |9 U
26. 3 Q+ E/ {\" k! @& M) m
    
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 的部分。这段代码实现了一个分治算法，通过递归地在每个棋盘区域填充缺失的部分，最终完成整个棋盘的填充。在递归的过程中，通过调整参数来实现在不同的子棋盘中填充片。函数的输出是填充完成后的部分棋盘。

: f, \# P1 f4 A' w