服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|JAVA教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|JavaScript|易语言|

服务器之家 - 编程语言 - JAVA教程 - Java基于分治算法实现的棋盘覆盖问题示例

Java基于分治算法实现的棋盘覆盖问题示例

2021-02-18 14:10萌神哆啦A梦 JAVA教程

这篇文章主要介绍了Java基于分治算法实现的棋盘覆盖问题,简单描述了棋盘覆盖问题,并结合具体实例形式分析了java基于分治算法实现棋盘覆盖问题的相关操作技巧,需要的朋友可以参考下

本文实例讲述了java基于分治算法实现的棋盘覆盖问题。分享给大家供大家参考,具体如下:

在一个2^k * 2^k个方格组成的棋盘中,有一个方格与其它的不同,若使用以下四种l型骨牌覆盖除这个特殊方格的其它方格,如何覆盖。四个l型骨牌如下图:

Java基于分治算法实现的棋盘覆盖问题示例

棋盘中的特殊方格如图:

Java基于分治算法实现的棋盘覆盖问题示例

实现的基本原理是将2^k * 2^k的棋盘分成四块2^(k - 1) * 2^(k - 1)的子棋盘,特殊方格一定在其中的一个子棋盘中,如果特殊方格在某一个子棋盘中,继续递归处理这个子棋盘,直到这个子棋盘中只有一个方格为止如果特殊方格不在某一个子棋盘中,将这个子棋盘中的相应的位置设为骨牌号,将这个无特殊方格的了棋盘转换为有特殊方格的子棋盘,然后再递归处理这个子棋盘。以上原理如图所示:

Java基于分治算法实现的棋盘覆盖问题示例

具体代码如下:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package demo;
public class chess {
  /*tr表示棋盘左上角行号
  tc表示棋盘左上角列号
  dr表示特殊棋盘的行号
  dc表示特殊棋盘的列号*/
  public static void chessboard(int tr, int tc, int dr, int dc, int size) {
    if(size == 1) {
      return;
    }
    int t = title ++;
    int s = size/2;
    //覆盖左上角子棋盘
    if(dr < tr + s && dc < tc +s) {
      //特殊方格在此棋盘中
      chessboard(tr, tc, dr, dc, s);
    }
    else {
      //此棋盘中无特殊方格,用t号l型骨牌覆盖右下角
      board[tr + s - 1][tr + s -1] = t;
      //覆盖其余方格
      chessboard(tr, tc, tr + s - 1, tc + s - 1, s);
    }
    //覆盖右上角子棋盘
    if(dr < tr + s && dc >= tc + s) {
      //特殊方格在此棋盘中
      chessboard(tr, tc+s, dr, dc, s);
    }
    else {//此棋盘中午特殊方格,用t号l型骨牌覆盖左下角
      board[tr + s - 1][tc + s] = t;
      //覆盖其余方格
      chessboard(tr, tc + s, tr + s - 1, tc + s, s);
    }
    //覆盖左下角子棋盘
    if(dr >= tr + s && dc < tc +s) {
      //特殊方格在此棋盘中
      chessboard(tr + s, tc, dr, dc, s);
    }
    else {
      //此棋盘中无特殊方格,用t号l型骨牌覆盖右上角
      board[tr + s][tr + s -1] = t;
      //覆盖其余方格
      chessboard(tr, tc, tr + s , tc + s - 1, s);
    }
    //覆盖右下角子棋盘
    if(dr >= tr + s && dc >= tc + s) {
      //特殊方格在此棋盘中
      chessboard(tr + s, tc+s, dr, dc, s);
    }
    else {//此棋盘中无特殊方格,用t号l型骨牌覆盖左上角
      board[tr + s ][tc + s] = t;
      //覆盖其余方格
      chessboard(tr + s, tc + s, tr + s , tc + s, s);
    }
  }
   @suppresswarnings("static-access")
 public static void main(string args[]) {
     system.out.println("服务器之家测试结果:");
     board[2][2] = 0;
     chess ch = new chess();
     ch.chessboard(0, 0, 2, 2, size);
     for(int i = 0; i < size; ++ i) {
       for(int j = 0; j < size; j++) {
         system.out.print(board[i][j] + " ");
       }
       system.out.println();
     }
   }
  static final int size = 4;
  static int title = 1;
  static int board[][] = new int[size][size];
}

运行结果:

Java基于分治算法实现的棋盘覆盖问题示例

希望本文所述对大家java程序设计有所帮助。

原文链接:http://blog.csdn.net/u014755255/article/details/50531621

延伸 · 阅读

精彩推荐