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

2024-03-19 20:43:08

题目描述：将一个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)))

结果显示：

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

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使用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()
python微信跳一跳系列之色块轮廓定位棋盘

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

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

题目描述:将一个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时,回

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

相关推荐

随机推荐