python递归法解决棋盘分割问题

题目描述:将一个8*8的棋盘进行分割,将原棋盘分割下一个矩阵,同时确保剩下的棋盘也是矩阵;
再将剩下的棋盘继续进行如上分割,这样割(n-1)次,最后原棋盘被分割成n块矩形棋盘;
注意:每次分割只能沿着棋盘格子的边进行分割

原棋盘每个格子都有一个分值,一个矩形棋盘的总分,为所含各格分值之和;

其中,Xi为第i块矩形棋盘的总分

对给出的棋盘和n,使得矩形棋盘总分的均方差最小,并输出

分析思路:

程序代码:

# -*- coding: utf-8 -*-
"""
Created on Mon Mar 12 09:55:35 2018
@author: lizihua
将一个8*8的棋盘进行分割,将原棋盘分割下一个矩阵,同时确保剩下的棋盘也是矩阵;
再将剩下的棋盘继续进行如上分割,这样割(n-1)次,最后原棋盘被分割成n块矩形棋盘;
注意:每次分割只能沿着棋盘格子的边进行分割
原棋盘每个格子都有一个分值,一个矩形棋盘的总分,为所含各格分值之和;
其中,Xi为第i块矩形棋盘的总分
对给出的棋盘和n,使得矩形棋盘总分的均方差最小,并输出
"""

import numpy as np
import math

n=int(input("请输入分割次数:"))
#每个格子的分值
s=np.zeros((8,8))
for i in range(8):
  s[i]=input("请输入第"+str(i)+"行各格的分值:").split(' ')
  #将line中的元素转换为整型
  s[i] = list(map(int, s[i]))

zero1=np.zeros(8)
zero2=np.zeros(9)
#向s中的最上面加入一行0
s=np.insert(s,0,values=zero1,axis=0)
#向s中的第一列加入一列0
s=np.insert(s,0,values=zero2,axis=1)
res=np.ones((15,8,8,8,8))*(-1) #fun的记录表
sums=np.zeros((9,9))       #(1,1)到(i,j)的矩形分值之和
res=np.ones((15,9,9,9,9))*(-1) #fun的记录表
sums=np.zeros((9,9))       #(1,1)到(i,j)的矩形分值之和
for i in range(1,9):
  #rowsum是列之和,所以当i变化时,rowsum要清零
  rowsum=0
  for j in range(1,9):

    rowsum+=s[i][j]
    sums[i][j]+=sums[i-1][j]+rowsum

print(sums)

#(x1,y1)到(x2,y2)的矩形分值之和
def calsum(x1,y1,x2,y2):
  return sums[x2][y2]-sums[x2][y1-1]-sums[x1-1][y2]+sums[x1-1][y1-1]

#定义递归函数fun()
def fun(n,x1,y1,x2,y2):
  #注意:MIN是局部变量,一定在函数里赋值,否则结果会有问题
  MIN=10000000
  if res[n][x1][y1][x2][y2] != -1:
    return res[n][x1][y1][x2][y2]
  if n==1:
    t=calsum(x1,y1,x2,y2)  #分割后的矩形棋盘(不再分割的那块)的总分
    res[n][x1][y1][x2][y2]=t*t   #Xi*Xi
    return t*t
  for i in range(x1,x2):
    a=calsum(x1,y1,i,y2)
    c=calsum(i+1,y1,x2,y2)
    t=min(fun(n-1,x1,y1,i,y2)+c*c,fun(n-1,i+1,y1,x2,y2)+a*a)
    if t<MIN:
      MIN=t

  for j in range(y1,y2):
    a=calsum(x1,y1,x2,j)
    c=calsum(x1,j+1,x2,y2)
    t=min(fun(n-1,x1,y1,x2,j)+c*c,fun(n-1,x1,j+1,x2,y2)+a*a)
    if t<MIN:
      MIN=t
  res[n][x1][y1][x2][y2]=MIN
  return MIN

result=n*fun(n,1,1,8,8)-sums[8][8]*sums[8][8]
print(math.sqrt(result/(n*n)))

结果显示:

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

(0)

相关推荐

  • Python基于回溯法子集树模板解决马踏棋盘问题示例

    本文实例讲述了Python基于回溯法子集树模板解决马踏棋盘问题.分享给大家供大家参考,具体如下: 问题 将马放到国际象棋的8*8棋盘board上的某个方格中,马按走棋规则进行移动,走遍棋盘上的64个方格,要求每个方格进入且只进入一次,找出一种可行的方案. 分析 说明:这个图是5*5的棋盘. 类似于迷宫问题,只不过此问题的解长度固定为64 每到一格,就有[(-2,1),(-1,2),(1,2),(2,1),(2,-1),(1,-2),(-1,-2),(-2,-1)]顺时针8个方向可以选择. 走到一

  • python自带tkinter库实现棋盘覆盖图形界面

    python实现棋盘覆盖图形界面,供大家参考,具体内容如下 一.解决方案和关键代码 工具: python tkinter库 问题描述:   在一个2^k×2^k个方格组成的棋盘中,若有一个方格与其他方格不同,则称该方格为一特殊方格,且称该棋盘为一个特殊棋盘.显然特殊方格在棋盘上出现的位置有4^k种情形.因而对任何k≥0,有4^k种不同的特殊棋盘.   在棋盘覆盖问题中,要用下图中 4 中不同形态的 L 型骨牌覆盖一个给定的特殊棋牌上除特殊方格以外的所有方格,且任何 2 个 L 型骨牌不得重叠覆盖

  • python微信跳一跳系列之色块轮廓定位棋盘

    在前几篇博文中,我们分别采用颜色识别,模板匹配,像素遍历等方法实现了棋子和棋盘的定位,具体内容可以参见我的前面的文章内容,在这一篇中,我们来探索一种定位棋盘的新方法. 分析 经过观察,我们看到,无论什么情况下,棋盘和背景之间总是存在着非常明显的色彩对比,这当然是必须的,否则玩游戏的人都无法分辨棋子.棋盘.背景,这个游戏就不可能大火.显然,如果我们将每一幅画面进行色块分割,将彩色图转变为黑白二值图,就可以将背景和棋盘隔离出来,然后对黑白图中的白色轮廓进行分析,将其中位置最高(y值最小)的轮廓标记出

  • python使用turtle绘制国际象棋棋盘

    本文实例为大家分享了python使用turtle画国际象棋棋盘的具体代码,供大家参考,具体内容如下 使用的方法是每一个小格每一个小格的画 import turtle for i in range(8): #一共有八列 for j in range(8):#每一行有八个格 turtle.forward(37.5) if j % 2 == 0:#判断是否为第奇数个格(是否画黑色格) if i % 2 ==0:#判断是否为奇数行(调整画黑色正方形时小海龟的转向) turtle.begin_fill()

  • Python3解决棋盘覆盖问题的方法示例

    本文实例讲述了Python3解决棋盘覆盖问题的方法.分享给大家供大家参考,具体如下: 问题描述: 在2^k*2^k个方格组成的棋盘中,有一个方格被占用,用下图的4种L型骨牌覆盖所有棋盘上的其余所有方格,不能重叠. 代码如下: def chess(tr,tc,pr,pc,size): global mark global table mark+=1 count=mark if size==1: return half=size//2 if pr<tr+half and pc<tc+half: c

  • python图形工具turtle绘制国际象棋棋盘

    本文实例为大家分享了python图形工具turtle绘制国际象棋棋盘的具体代码,供大家参考,具体内容如下 #编写程序绘制一个国际象棋的棋盘 import turtle turtle.speed(30) turtle.penup() off = True for y in range(-40, 30 + 1, 10): for x in range(-40, 30 + 1, 10): if off: turtle.goto(x, y) turtle.pendown() turtle.begin_f

  • python递归法解决棋盘分割问题

    题目描述:将一个8*8的棋盘进行分割,将原棋盘分割下一个矩阵,同时确保剩下的棋盘也是矩阵: 再将剩下的棋盘继续进行如上分割,这样割(n-1)次,最后原棋盘被分割成n块矩形棋盘: 注意:每次分割只能沿着棋盘格子的边进行分割 原棋盘每个格子都有一个分值,一个矩形棋盘的总分,为所含各格分值之和: 其中,Xi为第i块矩形棋盘的总分 对给出的棋盘和n,使得矩形棋盘总分的均方差最小,并输出 分析思路: 程序代码: # -*- coding: utf-8 -*- """ Created o

  • Python 实现递归法解决迷宫问题的示例代码

    迷宫问题 问题描述: 迷宫可用方阵 [m, n] 表示,0 表示可通过,1 表示不能通过.若要求左上角 (0, 0) 进入,设计算法寻求一条能从右下角 (m-1, n-1) 出去的路径. 示例图: 此示例图基本参数为: m:对应 x 轴n:对应 y 轴 绿色线代表期望输出的路径 算法思路 标记当前所在位置 如果此时所在位置为终点,说明可以到达终点,退出递归: 否则,则存在 4 种可能的移动方向即上.下.左.右,遍历这 4 个方向,如果这 4 个方向存在相邻值为 0 的点,则将当前点坐标标记为该相

  • python递归法实现简易连连看小游戏

    问题:简单版连连看小游戏 一个分割成w*h个正方格子的矩形板上,每个正方格子可以有游戏卡,也可以没有游戏卡 两个游戏卡之间有一条路径相连需满足以下三个条件: 1.路径只包含水平和垂直的直线段 2.路径不能穿过别的游戏卡片 3.允许路径临时离开矩形板 输入要求: 第一行包括两个整数:w 和 h ; w:矩形板的宽度,h:矩形板的长度 下面h行,每行包括w个字符,表示矩形板上卡片的分布情况:'X'代表这个地方有卡片:'O'代表无卡片 之后一行包括4个整数:X1,Y1,X2,Y2(1<=X1,X2<

  • Java使用递归法解决汉诺塔问题的代码示例

    汉诺(Hanoi)塔问题:古代有一个梵塔,塔内有三个座A.B.C,A座上有n个盘子,盘子大小不等,大的在下,小的在上(如图). 有一个和尚想把这n个盘子从A座移到B座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上.在移动过程中可以利用B座,要求打印移动的步骤.如果只有一个盘子,则不需要利用B座,直接将盘子从A移动到C. 如果有2个盘子,可以先将盘子1上的盘子2移动到B:将盘子1移动到c:将盘子2移动到c.这说明了:可以借助B将2个盘子从A移动到C,当然,

  • Python基于回溯法解决01背包问题实例

    本文实例讲述了Python基于回溯法解决01背包问题.分享给大家供大家参考,具体如下: 同样的01背包问题,前面采用动态规划的方法,现在用回溯法解决.回溯法采用深度优先策略搜索问题的解,不多说,代码如下: bestV=0 curW=0 curV=0 bestx=None def backtrack(i): global bestV,curW,curV,x,bestx if i>=n: if bestV<curV: bestV=curV bestx=x[:] else: if curW+w[i]

  • python 递归调用返回None的问题及解决方法

    今天在做python获取邮件时需要递归调用解析函数才可以解析邮件内容,最后想要将解析出的内容返回时发现返回的是None 可以内容却可以打印出来,很费解.后来在网上找到了解决方案,才想明白 在这里记录下. 原文:https://www.jb51.net/article/182765.htm 原始测试代码如下: def print_info(msg, indent=0): if indent == 0: for header in ['From', 'To', 'Subject']: value =

  • C++基于回溯法解决八皇后问题示例

    本文实例讲述了C++基于回溯法解决八皇后问题的方法.分享给大家供大家参考,具体如下: 回溯法的基本做法是搜索,或是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法.这种方法适用于解一些组合数相当大的问题. 回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树.算法搜索至解空间树的任意一点时,先判断该结点是否包含问题的解.如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯:否则,进入该子树,继续按深度优先策略搜索. 回溯法指导思想--走不通,就掉头.设计过程:确

  • Python使用遗传算法解决最大流问题

    本文为大家分享了Python遗传算法解决最大流问题,供大家参考,具体内容如下 Generate_matrix def Generate_matrix(x,y): import numpy as np import random return np.ceil(np.array([random.random()*10 for i in range(x*y)]).reshape(x,y)) Max_road def Max_road(A,degree,start): import random imp

  • python 回溯法模板详解

    什么是回溯法 回溯法(探索与回溯法)是一种选优搜索法,又称为试探法,按选优条件向前搜索,以达到目标.但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点称为"回溯点". 无重复元素全排列问题 给定一个所有元素都不同的list,要求返回list元素的全排列. 设n = len(list),那么这个问题可以考虑为n叉树,对这个树进行dfs,这个问题里的回溯点就是深度(也就是templist的长度)为n时,回

随机推荐