请在下方输入要搜索的题目：

设计一棋盘覆盖问题算法(分治法)? 并计算其时间复杂度?(要求写出递推公式,及其求解过程)在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。(该算法中可能用到的变量:tr :棋盘中左上角方格所在行; tc :棋盘中左上角方格所在列。dr: 残缺方块所在行; dl :残缺方块所在列。size:棋盘的行数或列数; 用二维数组board[ ][ ],模拟棋盘。)

设计一棋盘覆盖问题算法(分治法)? 并计算其时间复杂度?(要求写出递推公式,及其求解过程)在一个2k×2k 个方格组成的棋盘中,恰有一个方格与其它方格不同,称该方格为一特殊方格,且称该棋盘为一特殊棋盘。在棋盘覆盖问题中,要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格,且任何2个L型骨牌不得重叠覆盖。(该算法中可能用到的变量:tr :棋盘中左上角方格所在行; tc :棋盘中左上角方格所在列。dr: 残缺方块所在行; dl :残缺方块所在列。size:棋盘的行数或列数; 用二维数组board[ ][ ],模拟棋盘。)

发布时间：2025-04-01 22:34:04

推荐参考答案 ( 由快搜搜题库官方老师解答 )

联系客服

答案：答:void chessBoard(int tr, int tc, int dr, int dc, int size){if (size == 1) return; //size:棋盘行数int t = tile , // L型骨牌号s = size/2; // 分割棋盘// 覆盖左上角子棋盘if (dr < tr s && dc < tc s) // 特殊方格在此棋盘中chessBoard(tr, tc, dr, dc, s);else {// 此棋盘中无特殊方格board[tr s - 1][tc s - 1] = t; // 用 t 号L型骨牌覆盖右下角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 {// 此棋盘中无特殊方格board[tr s - 1][tc s] = t; // 用 t 号L型骨牌覆盖左下角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 {board[tr s][tc s - 1] = t; // 用 t 号L型骨牌覆盖右上角chessBoard(tr s, tc, tr s, tc s-1, s);} // 覆盖其余方格// 覆盖右下角子棋盘if (dr >= tr s && dc >= tc s) // 特殊方格在此棋盘中chessBoard(tr s, tc s, dr, dc, s);else {board[tr s][tc s] = t; // 用 t 号L型骨牌覆盖左上角

专业技术学习

相关试题

专业技术学习

搜搜题库系统

注会试题题库试卷题库银行从业资格个人贷款题库医疗考试题库银从题库辅警招聘考试题库计算机考试题库和答案行测题库下载国企笔试题库法律法规题库行政管理题库及答案文化素养题库试题库在线区域考试题库小学语文面试试讲题库经济学题库教师资格证面试结构化面试题库综合知识题库及答案执法考试题库行测题库及答案解析