首页 > 试题广场 >

整数分解

[编程题]整数分解

热度指数：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

输出

算法知识视频讲解

清雪冰橙

O(N^4)的dp水过去了..

dp[i][j][k]表示由i个元素组成，和为j，且最大元素为k的合法组合个数

详细的看代码把..注释写的很清楚了

#include<iostream>
#include<bits/stdc++.h>
using namespace std;

int main(void){
    int n, m;
    while(~scanf("%d,%d", &n, &m)){
        //6,3
        int dp[m+1][n+1][n+1]; //dp[i][j][k]由i个元素组成，和为j，且最大元素为k的组合个数
        
        memset(dp,0,sizeof(dp));
        // 初始化
        for(int i=1; i<=n; ++i)
            dp[1][i][i] = 1;
        // 取第i个元素
        for(int i=2; i<=m; ++i){
            // 更新取了i个元素，和为j的情况
            for(int j=1; j<=n; ++j){
                // 假设第i个元素取了k
                for(int k=1; k<=j; ++k){
                    // 第i个元素取k是最大值
                    dp[i][j][k] += (dp[i-1][j-k][k]);
                    // 第i个元素取k但不是最大值的情况
                    for(int z=1; z<k; ++z)
                        dp[i][j][k] += dp[i-1][j-k][z];
                }
            }
        }
        int res = 0;
        for(int i=n; i>=0; --i)
            if ( dp[m][n][i]>0 )
                res += dp[m][n][i];
        cout<<res<<endl;
    }
}

发表于 2020-05-24 19:08:50 回复(0)

Rago

实际上就是N个球装到M个杯子里，要求每个杯子都要有球，有多少种装法。

发表于 2020-03-08 14:54:34 回复(4)

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)

yc是我儿子

def GetTypeNum(n,k):
    n = n-1 #间隔总数
    k = k-1 #需要的分割的间隔数
    if n%2 == 0:
        half = int(n/2)
    if n%2 != 0:
        half = int((n+1)/2)        
    j = []
    for i in itertools.combinations(range(1,half+1), k): #无放回不重复抽样
        li = list(i)
        j.append(li)
    return len(j)

用了排列组合的思想比如：N=5，M=2 5=1+1+1+1+1 1与1之间共有4个间隔(标记为①，②，③，④) 需要用M-1=1个间隔可以将数据分解成M=2份但是间隔需要折半(偶数除以2 奇数先加1再除以2) 插在间隔①位置为1+4 插在间隔④位置为4+1(题中说K+L和L+K算一种) 折半4/2=2后再无放回不重复抽样每次抽2-1个间隔即C₂¹

编辑于 2020-03-19 09:38:40 回复(4)

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)

pein531

动态规划，但是需要用字典的键去一下重

def solve(n, m):
    for i in range(2, n + 1):
        for j in range(2, i + 1):
            dic[(i, j)] = dic[(i - 1, j - 1)]
            if i >= 2*j:
                dic[(i, j)] += dic[(i - j, j)]

n, m = map(int, input().split(','))
if n < m:
    print(0)
else:
    dic = dict()
    dic[(0, 0)] = 1
    for k in range(1, n + 1):
        # 将k分解为1个正整数只有一种组合
        dic[(k, 1)] = 1
    solve(n, m)
    print(dic[(n, m)])

发表于 2020-12-23 15:32:04 回复(0)

leftheaven

n,m = map(int,input().split(","))
dic = {}
dic[(0,0)] = 1
for k in range(1,n+1):
    dic[(k,1)] = 1
def loop(n, m):
    for i in range(2,n+1):
        for j in range(2,i+1):
            dic[(i,j)] = dic[(i-1,j-1)]
            if (i >= 2*j):
                dic[(i,j)] += dic[(i-j,j)]
loop(n,m)
print(dic[(n,m)])

本人菜鸟根据DP公式写的递归代码通过90%。检查是否存在语法错误或数组越界非法访问。实在是不知道哪里出错了求大佬解答

发表于 2020-05-15 17:29:17 回复(2)

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)

4fbd81e

# 分拆数p(n,k)  integer partition
# $p(n,k)=p(n-1,k-1)+p(n-k,k)$
n,k=map(int,input().split(","))
p=[[0 for i in range(1000)]for j in range(1000)]
p[0][0]=1
p[1][1]=1
p[1][2]=0
for i in range(1,n+1):
    for j in range(1,i+1):
        p[i][j]=p[i-1][j-1]+p[i-j][j]
print(p[n][k])

发表于 2021-12-20 19:50:42 回复(1)

遥望星空~~脚踏实地

N, K= list(map(int, input().split(',')))  #输入数据
memo = dict() #词典备忘录，避免重复计算
def re(n, m): 
    global memo
    if n==m&nbs***bsp;m==1: #边界条件
        return 1
    if n<m:  #边界条件
        return 0
    res = 0
    for i in range(1, min(n-m, m)+1): #
        if (n-m, i) in memo:
            res = res + memo[(n-m, i)] #查看备忘录中是否有记录
        else:
            res = res + re(n-m, i) #状态转移方程
    memo[(n, m)] = res #存入备忘录
    return memo[(n, m)] 
print(re(N, K))

发表于 2020-11-18 14:34:12 回复(1)

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)

gogogoovo

C++回溯通过70%

#include <vector>
#include <iostream>
using namespace std;


void dfs(int total, int len, vector<int>&temp, int & res, int cur, int sum){
    if(temp.size() >= len) return;
    if(temp.size() == len-1) res++;
    for(int i = cur; i <= (total - sum)/(len - temp.size()); i++){
        temp.push_back(i);
        int store = i;
        sum += store;
        dfs(total, len, temp, res, i, sum);
        sum -= store;
        temp.pop_back();
    }
}

int solution(int total, int len){
    int res = 0;
    vector<int> temp;
    dfs(total, len, temp, res, 1, 0);
    return res;
}

int main(){
    char temp;
    int total, len;
    cin >> total >> temp >> len;
    cout << solution(total, len);
    return 0;
}

发表于 2020-05-23 18:15:50 回复(0)

牛客832305471号

from itertools import combinations
m0=[]
a0=[]
def GetTypeNum(n,k):
    j = []
    for i in combinations(range(0,n-1), k-1): 
        j.append(i)
    for i in range(len(j)):
        a=[]
        for t in range(len(j[i])-1):
            a.append(j[i][t+1]-j[i][t])
        a.insert(0,j[i][0]+1)
        a.append(int(n-j[i][len(j[i])-1]))
        a.sort()
        a0.append(a)
    newList = []
    for x in a0:
        if x not in newList :
            newList.append(x)
    return(len(newList))  
if __name__ == '__main__':
    n,k =list(map(int,input().split(',')))
    print(GetTypeNum(n,k)-1)

超时了2333。。。没想到去重的好办法。。。

发表于 2020-04-13 00:05:04 回复(0)

BugAngel

#include <iostream>
 
using namespace std;
 
int main()
{
    char temp;
    int n, m;
    cin >> n >> temp >> m;
 
    //dp[n][m]=
    //1,n=1,m=1
    //q(n,n) n<m
    //1+q(n,n-1) n=m
    //q(n,m-1)+q(n-m,m) n>m>1
    int dp[201][201];//dp[i][j]表示把i拆分，最大的数不超过j的排列。
    for (int i = 0; i <= n; i++) {
        dp[i][0] = 0;
    }
    for (int i = 0; i <= m; i++) {
        dp[0][i] = 0;
    }
    for (int i = 1; i <= n; i++) {
        dp[i][1] = 1;
    }
    for (int i = 1; i <= m; i++) {
        dp[1][i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (i < j) {
                dp[i][j] = dp[i][i];
            }
            else if (i == j) {
                dp[i][j] = 1 + dp[i][i - 1];
            }
            else {
                if (i - j < 1) {
                    dp[i][j] = dp[i][j - 1];
                }
                else {
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j];
                }              
            }
        }
    }
     
    cout << dp[n][m]- dp[n][m - 1];
 
    return 0;
}

发表于 2020-03-12 03:01:20 回复(0)