我要招人

去企业版

首页 > 试题广场 >

整数分解

[编程题]整数分解

热度指数：1335 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

一个正整数N可以分解为M(M>1)个正整数的和，即N=K+L，例如N=5、M=2时可以分解为(1+4,2+3)。

给定一个正整数N(1<N<200)及正整数M(1<M<200)，求有多少种可能的分解组合(注：K+L和L+K算一种)

输入描述:

输入两个数N和M

输出描述:

可以分解的组合数。

示例1

输入

5,2

输出

示例2

输入

6,3

输出

算法知识视频讲解

Python

刻苦的赖床专家在写bug

def integer_partition(N, M):
    # 创建二维 dp 数组，大小 (N+1) x (M+1)，初始值为 0
    dp = [[0] * (M + 1) for _ in range(N + 1)]

    # 初始化：把 n 拆成 1 个数的情况，只有一种（就是 n 本身）
    for n in range(1, N + 1):
        dp[n][1] = 1

    # 填表
    for n in range(1, N + 1):
        for m in range(2, M + 1):
            if m > n:
                dp[n][m] = 0
            elif m == n:
                dp[n][m] = 1  # 把 n 拆成 n 个 1
            else:
                dp[n][m] = dp[n - 1][m - 1] + dp[n - m][m]

    return dp[N][M]

# 输入读取
N, M = map(int, input().split())
print(integer_partition(N, M))

chatGPT写的，主要是用了公式: dp[n][m] = dp[n - 1][m - 1] + dp[n - m][m]，在建立的数组上进行递归计算的。

这个意思是：n分成m个正整数的情况 = 至少有1个数被分为1的情况 + 所有数至少为2的情况(m个数先都分到1，然后剩下的n-m再分成m个正整数)
然后dp[n - m][m]在n-m小于m的时候就退化为0，这为递归提供了便利，写一下这个N*M的数组会比较明白

编辑于 2025-04-26 00:47:25 回复(0)

Python

大侠李某

N, K = list(map(int,input().strip(' ').split(',')))
dic = {}
def recur(N,K):
    if N==K&nbs***bsp;N==K+1&nbs***bsp;K==1:
        return 1
    if K == 2:
        return (N//2)
    res = 0
    for i in range(1,min(N-K,K)+1):
        if (N-K,i) in dic:
            res += dic[(N-K,i)]
        else:
            res += recur(N-K,i)
    dic[(N,K)] = res
    return res
      
    
print(recur(N,K))

发表于 2020-09-05 23:13:22 回复(0)

Python

小橙子&

本题思路（暴力是只能通过50%）：动态规划处理

1、首先将数组分成全部最小的单位进行处理

2、将分成的数组的一部分用于处理全部的次数（这里可以看成桶）

3、考虑剩余的怎么分的问题

4、剩余的用几个桶进行分（这里我们需要进行考虑桶的取值范围）

剩下的就是码代码了

N, M = list(map(int,input().strip(' ').split(',')))
dic = {}
def DP(n,m):
    """
    n-----目前有的数
    m-----目前的次数
    n-m---剩余需要处理的数
    """
    global dic
    if n == m or n - m == 1 or m == 1:
        dic[(n,m)] = 1
        return
    if m == 2 and n >= m:
        dic[(n,m)] = int(n // 2)
        return
    i = 1
    res = 0
    while i <= n-m and i <= m:
        if (n-m,i) in dic:
            res += dic[(n-m,i)]
            i += 1
        else:
            DP(n-m,i)
    dic[(n,m)] = res
    return 
DP(N,M)
print(dic[(N,M)])

编辑于 2020-08-22 10:37:26 回复(0)

Python

游泳健将SSS

自己想的：通过70% 超时23333

思路比较简单，就是递归找出所有的k拆分，且拆分的数要求是单调增。因为l+k=k+l。

data= [int(x) for x in input().split(',')]
N=data[0]
K=data[1]

def Data(data,min_,k):
    if k==1:
        if data>=min_:
            return 1
        else:
            return 0
    else:
        temp=0
        for i in range(min_,data//k+1):
            temp+=Data(data-i,i,k-1)
        return temp
print(Data(N,1,K))

感觉应该用动态规划，理解了一下楼里大佬的，稍稍修改，另外加了注释。就100%通过了

data= [int(x) for x in input().split(',')]
N=data[0]
K=data[1]
 
def Data(data,k): #k拆分
    if data<k:
        return 0 #楼里大佬的问题，没判断无法划分的问题。。。
    else:
        if k==1:
            return 1
        else:
            D={}
            D[0,0]=0
            for i in range(1,data+1):
                for j in range(1,min(i+1,k+1)):
                    if j==1:
                        D[i,j]=1
                    else:
                        D[i,j]=D[i-1,j-1] #D[i,j]=D[i-j,j]+D[i-1,j-1]
                        if i>=2*j:        #意思是分割有两种情况：不包含1和包含1，当然可能不一定包含1
                            D[i,j]+=D[i-j,j]
            return D[data,k]
print(Data(N,K))

编辑于 2020-06-10 21:20:25 回复(2)

Python

zxcv19

n,m = map(int, input().split(","))
dic = {}
def loop(n, m):
    if (m == 1)&nbs***bsp;(n - m == 1)&nbs***bsp;(n == m):
        dic[(n, m)] = 1
    elif m == 2: 
        dic[(n, m)] = int( n / 2)
    else: 
        left, i, total = n - m, 1, 0
        while left >= i and i <= m:
            if (left, i) in dic.keys():
                total = total + dic[(left, i)]
                i = i + 1
            else:
                loop(left, i)
        dic[(n, m)] = total
loop(n,m)
print(dic[(n,m)])

发表于 2020-04-03 06:26:03 回复(6)