题目:
输入N,从1~N中挑出若干对数字,比如(a,b),(c,d)
规定这个数对的value为两数之和,比如(a,b)的value为a+b
现在从1~N中挑出若干个数对,他们满足:
每个数字只能被挑出一次
每个数对的value都不相等
每个数对的value都小于等于N
求:对于给定的N,能挑出这样的数对的最大个数max
举例:
N=1,无法挑出数对,max=0
N=2,1+2>2,max=0
N=3,可挑出1个数对(1,2),max=1
N=10,可挑出3个数对(1,9),(2,7),(3,6),max=3
我不太会做,找同学要了一个程序,但是看不懂

 

num = int(input('请输入n:'))

dic = {}
if num == 1:
    print(0)
elif num == 2:
    print(0)
elif num == 3:
    print(1)
else:
    dic[1] = []
    dic[2] = []
    dic[3] = [(1, 2)]

    for i in range(4, num + 1):
        ls = []
        k, k1 = 1, i - 1
        while k < k1:
            ls.append((k, k1))
            k += 1
            k1 -= 1
        dic[i] = ls

    for k, v in dic.items():
        print(k, v)

    vis = [False] * (num + 1)  # 1到num的数是否被访问过
    s = set()
    cnt = 0
    a = 0
    if num % 2 == 1:
        cnt = 1
        print("i=", num, dic[num][-1][0], dic[num][-1][1])
        s.add(num)
        vis[dic[num][-1][0]] = True
        vis[dic[num][-1][1]] = True
        num -= 1

    for kkk in range(num // 2 - 1, 0, -1):  # 先提供列
        a += 2
        for i in range(num, num - a, -1):  # 这是行
            ls = dic[i]
            k, k1 = ls[kkk - 1]
            if i not in s and not vis[k] and not vis[k1]:
                s.add(i)
                print("i=", i, k, k1)
                vis[k] = True
                vis[k1] = True
                cnt += 1

请输入n:22
1 []
2 []
3 [(1, 2)]
4 [(1, 3)]
5 [(1, 4), (2, 3)]
6 [(1, 5), (2, 4)]
7 [(1, 6), (2, 5), (3, 4)]
8 [(1, 7), (2, 6), (3, 5)]
9 [(1, 8), (2, 7), (3, 6), (4, 5)]
10 [(1, 9), (2, 8), (3, 7), (4, 6)]
11 [(1, 10), (2, 9), (3, 8), (4, 7), (5, 6)]
12 [(1, 11), (2, 10), (3, 9), (4, 8), (5, 7)]
13 [(1, 12), (2, 11), (3, 10), (4, 9), (5, 8), (6, 7)]
14 [(1, 13), (2, 12), (3, 11), (4, 10), (5, 9), (6, 8)]
15 [(1, 14), (2, 13), (3, 12), (4, 11), (5, 10), (6, 9), (7, 8)]
16 [(1, 15), (2, 14), (3, 13), (4, 12), (5, 11), (6, 10), (7, 9)]
17 [(1, 16), (2, 15), (3, 14), (4, 13), (5, 12), (6, 11), (7, 10), (8, 9)]
18 [(1, 17), (2, 16), (3, 15), (4, 14), (5, 13), (6, 12), (7, 11), (8, 10)]
19 [(1, 18), (2, 17), (3, 16), (4, 15), (5, 14), (6, 13), (7, 12), (8, 11), (9, 10)]
20 [(1, 19), (2, 18), (3, 17), (4, 16), (5, 15), (6, 14), (7, 13), (8, 12), (9, 11)]
21 [(1, 20), (2, 19), (3, 18), (4, 17), (5, 16), (6, 15), (7, 14), (8, 13), (9, 12), (10, 11)]
22 [(1, 21), (2, 20), (3, 19), (4, 18), (5, 17), (6, 16), (7, 15), (8, 14), (9, 13), (10, 12)]
i= 22 10 12
i= 20 9 11
i= 21 8 13
i= 13 6 7
i= 19 5 14
i= 18 3 15
i= 6 2 4
i= 17 1 16