5kyu Square sums (simple)

題目背景：

Task

Write function square_sums_row (or squareSumsRow/SquareSumsRow depending on language rules) that, given integer number N (in range 2…43), returns array of integers 1…N arranged in a way, so sum of each 2 consecutive numbers is a square.

Example
For N=15 solution could look like this:
[ 9, 7, 2, 14, 11, 5, 4, 12, 13, 3, 6, 10, 15, 1, 8 ]

題目分析：

本道題題面的意思很容易領(lǐng)會，就是將1-N的數(shù)按照一定順序排列后，使得相鄰的兩個數(shù)兩兩相加為一個平方數(shù)。但是題目的下手點比較棘手，最簡單的思路就是DFS，從第一個數(shù)設(shè)置為 1 - N中的任意一個，之后不斷深搜遍歷，直至找到最終的解法，這種思路比較樸素，不過對我個人而言，我個人不是很擅長寫DFS代碼，也可能是寫得比較少orz。不過本道題如果采用DFS算法，因為數(shù)據(jù)量較少，直接深搜也可以AC。先附上DFS的AC代碼，之后會討論下另一種解法的思路。

AC代碼：

import numpy success = False ans = [0 for i in range(44)] hash1 = [False for i in range(44)]def judge(num1, num2):if numpy.square(numpy.floor(numpy.sqrt(num1 + num2))) == num1 + num2: return Trueelse: return Falsedef Dfs(num, cnt):global successif(num > 1):if(judge(ans[num], ans[num-1]) == False): returnif(num == cnt): success = Truereturn for i in range(2, cnt + 1):if not hash1[i]:ans[num + 1] = ihash1[i] = TrueDfs(num + 1, cnt)if success: returnhash1[i] = Falsedef square_sums_row(n):global successfor i in range(1, n + 1):for j in range(1, n + 1): hash1[j] = Falseans[1] = ihash1[i] = Truesuccess = FalseDfs(1, n)if success: return ans[1: n + 1]return False

第二種思路：
這是我在草稿上演練時想到的思路，感覺是一個更優(yōu)的思路的一部分，不過因為自己沒有理清楚代碼如何編寫，就只好說下思路了。大致的想法是，對于1 - N的每個數(shù)當(dāng)做圖中的一個節(jié)點，然后每個節(jié)點去找和它之和為平方數(shù)的節(jié)點，節(jié)點之間如果和為平方數(shù)那么添加一條連線，最后就就相當(dāng)于在整個圖中找一條連線可以把所有的節(jié)點過一遍同時每個節(jié)點只經(jīng)過一次，如果找到，那么存在一個排列滿足題目要求，否則不存在返回false。

如圖中所示，我們找到一個連線可以將所有節(jié)點過一遍同時只經(jīng)過每個節(jié)點一遍：9 -> 7 -> 2 -> 14 -> 11 -> 5 -> 4 -> 12 -> 13 -> 3 -> 6 -> 10 -> 15 -> 1 -> 8

總結(jié)

以上是生活随笔為你收集整理的5kyu Square sums (simple)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。