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

2744557306

1. board=zeros(100,100);# A! Y) l) z  o9 M  l\" E
   
2. n=4;
   % G0 Z3 ~, M/ C5 Z9 H  P$ j
3. size=2^n;1 w- ~- J4 H* p4 c
   
4. amount=0;
   7 z* G\" T8 ~; U: B9 G
5. [board,amount]=cover(1,1,2,5,board,size,amount);1 P% y3 [- x9 {. s% N
   
6. board(1:size,1:size), f+ {7 Y) n- c/ e! B- s# t
   
7. . A6 ]1 V3 o; s* k1 Y3 i
   

复制代码

1. function [board,amount]=cover(i,j,k,l,board,size,amount)%(i,j)为左上角 (k,l)残缺 size为规模 amount为片数, [  O3 B, u, D; P( N- @  a
   
2. 
   $ O  Z7 c2 U6 A
3. if size==1' J\" o* j2 }, e& u\" H. ?9 \; z: q
   
4. return5 \/ ]* B1 D: M* a% k9 t* Q3 H- e: X
   
5. end! M4 F% d4 \5 _: y# k7 ?
   
6. amount=amount+1;! a$ x0 g: a2 P' B
   
7. size=size/2;0 r/ b* t+ k3 `* i. }1 v
   
8. if (k<size+i)&(l<size+j)%残缺位于左上棋盘
   ! f. ^5 }  _+ I  _
9. 4 i! E7 H: Q\" q\" ~
   
10. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i,size+j-1)=amount;%放置
    8 x4 G+ U4 d( G, I
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);: I' L2 U2 G# u6 ]  X& w  E! v2 x
    
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);- Q7 W\" B) ~5 t7 d. }* R
    
13. elseif (k>=size+i)&(l<size+j)%残缺位于左下棋盘
    ) l9 U1 \( @4 a- V; O
14. board(size+i-1,size+j)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置' v* ?' @# |) ~  Q. P9 t- C
    
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);6 p5 i# @$ c. M' f9 y! Q  e
    
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);
    6 @3 p$ k! |$ }/ I\" {. D! C
17. elseif (k<size+i)&(l>=size+j)%残缺位于右上棋盘
    ; w& s\" U. i+ i0 ]
18. board(size+i,size+j-1)=amount;board(size+i,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置
    ( u- J6 w3 s% Y6 U8 C4 ?7 N6 X& X
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);2 c4 J) y) P1 `
    
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);3 l* ?& g* T0 W2 p+ d3 P
    
21. elseif (k>=size+i)&(l>=size+j)%残缺位于右下棋盘
    4 ?# C+ q, A; S
22. board(size+i,size+j-1)=amount;board(size+i-1,size+j)=amount;board(size+i-1,size+j-1)=amount;%放置, [- O7 i6 ]! I8 l
    
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);* @' L6 [* g* C/ T  t& o7 O0 f
    
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);
    * q: D3 W7 |8 W% a
25. end$ b% ^% s3 ]8 W  `
    
26. 2 o  ~1 N/ d4 L4 w! m) D. \$ k
    
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 的部分。这段代码实现了一个分治算法，通过递归地在每个棋盘区域填充缺失的部分，最终完成整个棋盘的填充。在递归的过程中，通过调整参数来实现在不同的子棋盘中填充片。函数的输出是填充完成后的部分棋盘。

2 D- c8 h# a+ Z, K, a2 H# h