分苹果

Posted on | In

目录

题目：m个人分n个苹果，按分得个数排序前后相邻2个人最多相差3个，每个人最少分得1个，问有几种分法?

普通版的分苹果问题：

M个同样的苹果分在N个同样的篮子里，允许有篮子空着不放，求一共有多少种不同的分法。
说明，3，1，1和1，3，1是一种分法；篮子可以放入的苹果数量没有最大限制。

递归解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def share(apple, basket):
    if apple < 0 or basket <= 0:
        return 0
    elif apple == 0 or basket == 1:
        return 1
    elif apple < basket:
        return share(apple, apple)
    else:
        return share(apple, basket - 1) + share(apple - basket, basket)
 
echo = list(map(int, raw_input().split()))
apple = echo[0]
basket = echo[1]
print(share(apple, basket))

和本题有一定的相似，但没找到递归或动态规划的思路。

以下是一种不太好的解法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
# coding=utf8

""" 分苹果
m个人 分n个苹果 按分得数排序 前后相邻2个人最多相差3个 每个人最少分得1个 有几种分法?

注意：
A，B两人分4个苹果，分别 1，3 和 分别 3，1 视为同一种分法，不考虑人的对应顺序

n >= m
m > 0

示例：
2个人分4个苹果，输入：
2 4

有[3,1]，[2,2]共2种方案，输出：
2

"""

while True:
    try:
        m, n = map(int, raw_input().split())
        if n < m or m < 1:
            continue

        if m == 1:
            print "-------------------------->", [n]
            continue

        # 最后一个人最多km个，最少一个(n>=m)
        km = n // m
        Q = 4  # 比后一位多 0 1 2 3 四种取值，所以模为4

        nS = 0

        for pm in range(1, km + 1):
            print "pm:", pm  # 记最后一个人分得pm个
            # 均分特例
            if m * pm == n:
                nS += 1
                print "-------------*------------>", [pm] * m
                continue

            # 非均分的情况
            p = [0] * (m - 1)  # p[x] 表示第x个人 比第x+1个人 多p[x]个
            QL = [Q] * (m - 1)

            # 更新各位的模，以减少循环次数
            for y in range(m - 1):
                # p[y]*(y+1) + pm*m <= n
                QL[y] = min((n - m * pm) // (y + 1) + 1, Q)
            print "QL:", QL

            is_break = False
            while True:
                p[m - 2] += 1  # 循环+1，逐位检查是否进1退0，生成一个长度为m-1的序列p
                for j in range(m - 2, -1, -1):
                    if p[j] < QL[j]:
                        break
                    else:
                        if j > 0:
                            p[j - 1] += 1
                            p[j] = 0
                        elif j == 0:
                            is_break = True

                if is_break:
                    break

                sum_p = pm * m
                for x in range(m - 2, -1, -1):
                    sum_p += p[x] * (x + 1)

                if sum_p != n:
                    continue
                else:
                    # print "-------------------------->", p, pm, sum_p
                    nS += 1
                    t = p[-1] + pm
                    res = [t]
                    for k in range(len(p) - 2, -1, -1):
                        t += p[k]
                        res.insert(0, t)

                    print "-------------------------->", res + [pm]
        print "Total:", nS
    except:
        break

示例输出：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
2 4
pm: 1
QL: [3]
--------------------------> [3, 1]
pm: 2
-------------*------------> [2, 2]
Total: 2

5 7
pm: 1
QL: [3, 2, 1, 1]
--------------------------> [2, 2, 1, 1, 1]
--------------------------> [3, 1, 1, 1, 1]
Total: 2

5 12
pm: 1
QL: [4, 4, 3, 2]
--------------------------> [3, 3, 3, 2, 1]
--------------------------> [4, 4, 2, 1, 1]
--------------------------> [4, 3, 3, 1, 1]
--------------------------> [4, 3, 2, 2, 1]
--------------------------> [5, 4, 1, 1, 1]
--------------------------> [5, 3, 2, 1, 1]
--------------------------> [5, 2, 2, 2, 1]
--------------------------> [6, 3, 1, 1, 1]
pm: 2
QL: [3, 2, 1, 1]
--------------------------> [3, 3, 2, 2, 2]
--------------------------> [4, 2, 2, 2, 2]
Total: 10

13 27
pm: 1
QL: [4, 4, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2]
--------------------------> [3, 3, 3, 3, 3, 3, 3, 1, 1, 1, 1, 1, 1]
...（此处省略几十行）
--------------------------> [8, 5, 4, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
--------------------------> [7, 4, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1]
--------------------------> [8, 5, 3, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1]
--------------------------> [8, 5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1]
pm: 2
QL: [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
--------------------------> [3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]
Total: 81
0%