建站
咨詢
售后
建站咨詢
新聞中心
這里有您想知道的互聯(lián)網(wǎng)營銷解決方案
python遞歸法如何解決棋盤分割問題-創(chuàng)新互聯(lián)
小編給大家分享一下python遞歸法如何解決棋盤分割問題，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
創(chuàng)新互聯(lián)主營公主嶺網(wǎng)站建設(shè)的網(wǎng)絡(luò)公司,主營網(wǎng)站建設(shè)方案,成都app開發(fā),公主嶺h5成都微信小程序搭建,公主嶺網(wǎng)站營銷推廣歡迎公主嶺等地區(qū)企業(yè)咨詢題目描述：將一個8*8的棋盤進行分割，將原棋盤分割下一個矩陣，同時確保剩下的棋盤也是矩陣；
再將剩下的棋盤繼續(xù)進行如上分割，這樣割(n-1)次，最后原棋盤被分割成n塊矩形棋盤；
注意：每次分割只能沿著棋盤格子的邊進行分割
原棋盤每個格子都有一個分值，一個矩形棋盤的總分，為所含各格分值之和；
其中，Xi為第i塊矩形棋盤的總分
對給出的棋盤和n，使得矩形棋盤總分的均方差最小，并輸出
分析思路：
程序代碼：
# -*- coding: utf-8 -*-
"""
Created on Mon Mar 12 09:55:35 2018
@author: lizihua
將一個8*8的棋盤進行分割，將原棋盤分割下一個矩陣，同時確保剩下的棋盤也是矩陣；
再將剩下的棋盤繼續(xù)進行如上分割，這樣割(n-1)次，最后原棋盤被分割成n塊矩形棋盤；
注意：每次分割只能沿著棋盤格子的邊進行分割
原棋盤每個格子都有一個分值，一個矩形棋盤的總分，為所含各格分值之和；
其中，Xi為第i塊矩形棋盤的總分
對給出的棋盤和n，使得矩形棋盤總分的均方差最小，并輸出
"""
import numpy as np
import math
n=int(input("請輸入分割次數(shù)："))
#每個格子的分值
s=np.zeros((8,8))
for i in range(8):
s[i]=input("請輸入第"+str(i)+"行各格的分值：").split(' ')
#將line中的元素轉(zhuǎn)換為整型
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]
#定義遞歸函數(shù)fun()
def fun(n,x1,y1,x2,y2):
#注意：MIN是局部變量，一定在函數(shù)里賦值，否則結(jié)果會有問題
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結(jié)果顯示：
以上是“python遞歸法如何解決棋盤分割問題”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對大家有所幫助，如果還想學習更多知識，歡迎關(guān)注創(chuàng)新互聯(lián)成都網(wǎng)站設(shè)計公司行業(yè)資訊頻道！
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機、免備案服務(wù)器”等云主機租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應用場景需求。
文章名稱：python遞歸法如何解決棋盤分割問題-創(chuàng)新互聯(lián)
新聞來源：http://fisionsoft.com.cn/article/cdoghs.html
