python遞歸法如何解決棋盤分割問題

小編給大家分享一下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遞歸法如何解決棋盤分割問題”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！