下面是用回溯法求解馬的周游問(wèn)題的算法;空白處應(yīng)填?
馬的周游問(wèn)題:給出一個(gè)n*n棋盤(pán),已知一個(gè)中國(guó)象棋馬在棋盤(pán)上的某個(gè)起點(diǎn)位置(x0,y0),求一條訪問(wèn)每個(gè)棋盤(pán)格點(diǎn)恰好一次,最后回到起點(diǎn)的周游路線。(設(shè)馬走日字。)
算法HORSETRAVEL
輸入:正整數(shù)n,馬的起點(diǎn)位置x0,y0),1<=x0,y0<=n。
輸出:一條從起點(diǎn)始訪問(wèn)n*n棋盤(pán)每個(gè)格點(diǎn)恰好一次,最后回到起點(diǎn)的周游
路線;若問(wèn)題無(wú)解,則輸出nosolution。
設(shè)n個(gè)不同的整數(shù)按升序存于數(shù)組A[1..n]中,求使得A[i]=i的下標(biāo)i。下面是求解該問(wèn)題的分治算法。空白處應(yīng)填寫(xiě)?
1.1,n
2.low>high
3.A[mid]=mid
4.mid+1,high
5.find(low,mid-1)