Question

python问题，跪求大神解答

书上的一个题，我知道答案，但是怎么用python写出来啊？求大神帮助
对乒乓球选手参加双打比赛，他们的球衣号码是1，2，…18．这时裁判惊喜地发现，每对选手的球衣号码之和都恰好是一个完全平方数，则求1号选手结对的是几号选手

Answer 1

#!/usr/bin/python
#encoding=utf-8
import sys

def get_candidates(n):
    ''' 返回小于n的所有完全平方数 '''
    ret = set()
    i = 2
    while (i*i <= n):
        ret.add(i*i)
        i += 1
    return ret

_table = []
def bt(paired_numbers, player_numbers, candidates):
    global _table
    for s in _table:
        if player_numbers == s:
            return
    _table.append(player_numbers)
    if len(paired_numbers) == 9:
        print "find solution"
        print paired_numbers
        sys.exit(0)
    for p1 in player_numbers:
        for p2 in player_numbers:
            if p1 >= p2:
                continue
            if (p1+p2) in candidates:
                new_player_numbers = player_numbers.copy()
                new_paired_numbers = paired_numbers.copy()
                new_player_numbers.remove(p1)
                new_player_numbers.remove(p2)
                new_paired_numbers.add((p1, p2))
                bt(new_paired_numbers, new_player_numbers, candidates)



if __name__ == "__main__":
    player_numbers = set()
    for n in range(1,19):
        player_numbers.add(n)
    # 获取最大可能的号码和
    candidates = get_candidates(18+17)
    bt(set(), player_numbers, candidates)

代码都写出来了，不至于看不懂吧，最后结果为
set([(3, 13), (6, 10), (7, 18), (1, 15), (9, 16), (4, 12), (8, 17), (5, 11), (2, 14)])

也就是说，1的对手是15

追问

大神，我可以问下这题的思路吗，我才学，有许多地方看不懂·········

追答

这属于一到算法题目，和语言本身无关，相关资料去查阅回溯算法，也就是所说的backtracking，核心思路就是bt那个函数，它从候选人中选取两个出来，看这两个p1+p2是否为一个完全平方数，如果是，就将这两个候选人数据加入到paired_numbers中，然后递归剩下的players。相当于一种计算机的暴力算法，执行可能的所有步骤，最终总会找到答案。去看算法书吧，比我这里讲的详细多了。

Answer 2

from random import shuffle
ls = []#存储完全平方数
for i in range(10):
    if i*i <=18+17 and i*i >= 1+2:#完全平方数取值范围
        ls.append(i*i)
print '完全平方数： ' + str(ls)

players = []#存储选手号码
for i in range(1,19):
    players.append(i)
print '参赛选手： ' + str(players)

def jiance(l):
    c=0
    shuffle(l)
    for i in range(0,18,2):#九组组合
        if l[i] + l[i+1] in ls:
            c += 1
    if c == 9:
        print '可能的结果： ' + str(l)

if __name__ == '__main__':
    while 1:
        jiance(players)

基本思路就是总共有九组对手，我们假设一号位置和二号位置对打，三号位置和四号位置对打，以此类推，借用random函数，随机产生可能的排列组合情况，总有一组情况会满足题目要求，这种方法的弊端就是随机产生的排列效率低下。下面是一个结果，1号和15号对打。

完全平方数： [4, 9, 16, 25]
参赛选手： [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]
可能的结果： [17, 8, 2, 14, 6, 10, 5, 11, 16, 9, 12, 4, 7, 18, 13, 3, 1, 15]