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

yipeiwu_com6年前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)))

结果显示:

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持【听图阁-专注于Python设计】。

相关文章

python在windows下实现ping操作并接收返回信息的方法

本文实例讲述了python在windows下实现ping操作并接收返回信息的方法。分享给大家供大家参考。具体分析如下: 这段python代码调用windows下的ping命令,通过sub...

基于Django框架利用Ajax实现点赞功能实例代码

基于Django框架利用Ajax实现点赞功能实例代码

概要: 要实现点赞功能,需要实现的有:谁进行的点赞、什么时候进行点赞、点赞的对象是谁、每一个对象的点赞数量是多少、点赞过后还需要能够取消点赞,为了是点赞后的信息能够及时的显示在前端页面,...

python覆盖写入,追加写入的实例

追加写入: # -*- coding:utf-8 -*- # a 指定打开文件的模式,a为追加 r为只读 a=open('test.txt', 'a') a.write('追...

Python设计足球联赛赛程表程序的思路与简单实现示例

Python设计足球联赛赛程表程序的思路与简单实现示例

每年意甲德甲英超西甲各大联赛的赛程表都是球迷们的必看之物,想起之前写过的一段生成赛程表的代码,用Python来写这类东西太舒服了。 这个算法叫做蛇环算法。 即,把所有球队排成一个环形(2...

让你Python到很爽的加速递归函数的装饰器

今天我们会讲到一个[装饰器] 注记:链接“装饰器”指Python3教程中的装饰器教程。可以在这里快速了解什么是装饰器。 @functools.lru_cache——进行函数执行结果备忘,...