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

Python  /  管理员 发布于 7年前   220

题目描述：将一个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 npimport 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中的最上面加入一行0s=np.insert(s,0,values=zero1,axis=0)#向s中的第一列加入一列0s=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)))

结果显示：

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