精华内容
下载资源
问答
  • 将整数n分成k份(回溯)

    千次阅读 2018-12-16 16:40:45
     Name: 将整数n分成k份(回溯)   Copyright:   Author: 巧若拙   Date: 16/12/18 13:25  Description: 将整数n分成k份 将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。  例如:n=7,k=3,...

    /*
        Name: 将整数n分成k份(回溯) 
        Copyright: 
        Author:  巧若拙 
        Date: 16/12/18 13:25
        Description: 将整数n分成k份
    将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。 
    例如:n=7,k=3,下面三种分法被认为是相同的。 
    1,1,5; 1,5,1; 5,1,1; 
    问有多少种不同的分法。
         
    算法1:回溯算法框架1:先处理递归出口(即终点),再枚举各种可能值,递归搜索下一层。 
    算法2:回溯算法框架2:先枚举各种可能值,再判断是否到达终点,若到达终点则输出结果,否则递归搜索下一层。 
    算法2的搜索深度比算法1要少一层,但是不如算法1结构清晰。
    算法3:非递归算法:自定义栈模拟算法2的递归过程。
    */
    #include<iostream>
    #include<cmath>

    using namespace std;

    const int N = 10; //整数n范围 
    int a[N+1] = {1}; //确保a[1]不小于1 
    int s = 0;

    void Print(int t);
    void dfs1(int n, int k, int t); //框架1 
    void dfs2(int n, int k, int t); //框架2 
    void dfs3(int n, int k); //非递归算法 

    int main()
    {
        int n, k;
        cin >> n >> k;
        
        //dfs1(n, k, 1);
        //dfs2(n, k, 1);
        dfs3(n, k);
        
        cout << s << endl;
        
        return 0;
    }

    void Print(int t)
    {
        for (int i=1; i<t; i++)
        {
            cout << a[i] << "+";
        }
        cout << a[t] << endl; 
    }

    void dfs1(int n, int k, int t) //框架1 
    {
        if (t == k) //到达终点,输出结果 
        {
            a[t] = n;
            Print(t); 
            s++;
        }
        else
        {
            for (int i=a[t-1]; i<=n/(k-t+1); i++) //枚举各种可能值,生成一个非递减序列 
            {
                a[t] = i;
                dfs1(n-i, k, t+1); //搜索下一层 
            }
        }
    }

    void dfs2(int n, int k, int t)//框架2 
    {
        for (int i=a[t-1]; i<=n/(k-t+1); i++) //枚举各种可能值,生成一个非递减序列 
        {
            if (t == k) //到达终点,输出结果 
            {
                a[t] = n;
                Print(t); 
                s++;
                break;
            }
            else
            {
                a[t] = i;
                dfs2(n-i, k, t+1); //搜索下一层 
            }
        }
    }

    void dfs3(int n, int k) //非递归算法 
    {
        int t = 1;
        while (t >= 1)
        {
            while (++a[t] <= n/(k-t+1)) //枚举各种可能值,生成一个非递减序列 
            {
                if (a[t] >= a[t-1])   //满足条件 
                {
                    if (t == k) //到达终点,输出结果 
                    {
                        a[t] = n;
                        Print(t); 
                        s++;
                        break;
                    }
                    else
                    {
                        n -= a[t];  //修改标记  
                        t++;  //搜索下一层 
                    }
                }
            }
            a[t--] = 0; //回溯 
            n += a[t]; //恢复标记 
        }
    }

    展开全文
  • 将整数n分成k份,且每份不能为空,任意两种划分方案不能相同(不考虑顺序)。求整数n分为k份,共有多少种不同的分法。输入两个整数n,k(6&lt;n&lt;=200,2&lt;=k&lt;=6)。输出一个整数,即有几种不同...

    题目:

    将整数n分成k份,且每份不能为空,任意两种划分方案不能相同(不考虑顺序)。求整数n分为k份,共有多少种不同的分法。输入两个整数n,k(6<n<=200,2<=k<=6)。输出一个整数,即有几种不同的分法。

    思路:

    定义一个数组dp[][],dp[i][j]表示将整数 i 划分为 j 份 的方案数。dp[i][j]的动态转移方程为 :

    如何理解该式子呢?首先,如果拿到一个整数 i ,因为题目中要求每份不能为空,因此必须先拿出 j 个数位将 j 份分别放上1,此时剩下 i - j个数。那么剩下的数如何处理呢?可以将其全部分到一份当中(dp[i-j][1]),也可以分到两份中(dp[i-j][2]),...,也可以分到 j 份中(dp[i-j][j]),而每一种分法都是不相同的,所以可以将其全部加起来,和即为dp[i][j]。

    不过这个式子看起来并不简洁,为了求得一个简洁的式子,我们再求一个dp[i-1][j-1],

    比较上面两个式子可得,

    这就是一个比较简洁的递推式子了,有点类似于高中数学中的裂项相消原理。 

    这里注意 i , j 的取值范围,i = 1~n,j = 1~ k,但是求dp[i][j]时,必须保证 i>=j(划分的份数不能超过给定的整数)。

    另外就是,做了好几道动态规划的题,发现动态转移方程真的好重要(也可以说是递推公式),看似很难很绕的题目,只要提炼出它的动态转移方程,搞清楚遍历的次序以及各变量的取值范围,写程序就相当快了。

    代码如下:

    // Chapter14_5.cpp : Defines the entry point for the application.
    // 数的划分
    // 将整数n分成k份,且每份不能为空,任意两种划分方案不能相同(不考虑顺序)。
    // 求整数n分为k份,共有多少种不同的分法。
    // 输入两个整数n,k(6<n<=200,2<=k<=6)。
    // 输出一个整数,即有几种不同的分法。
    
    #include "stdafx.h"
    #include<iostream>
    using namespace std;
    
    int main()
    {
    	int n,k;
    	cout << "输入整数n和划分的份数k:";
    	cin >> n >> k;
    	int dp[201][7];
    	//全部初始化为0
    	memset(dp,0,sizeof(dp));
    	//对于dp[0][0]作特殊处理(为了后面的动态转移方程能够起作用)
    	dp[0][0] = 1;
    	int i,j;
    	//i的取值范围是1~n(不能超过给定的整数)
    	for(i=1;i<=n;i++)
    		//j的范围是1~k(不能超过需要划分的份数)
    		for(j=1;j<=k;j++)
    		{
    			//划分的分数要小于等于该数本身
    			if(i>=j)
    				//动态转移方程
    				dp[i][j] = dp[i-j][j] + dp[i-1][j-1];
    		}
    	cout << "共有" << dp[n][k] << "种分法" << endl;
    	system("pause");
    	return 0;
    }

    运行结果如下:

    展开全文
  • 将整数n分为k份

    千次阅读 2020-04-23 20:17:00
    POJ3080 #include<iostream> #include<stdio.h> #include<string.h> #include<algorithm> #include<math.h> #include<vector>...int n,t; string s[11]; in...

    题意
    将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。
    例如:n=7,k=3,下面三种分法被认为是相同的。
    1,1,5; 1,5,1; 5,1,1;
    问有多少种不同的分法。
    输入:n,k ( 6 < n ≤ 200,2 ≤ k ≤ 6 )
    输出:一个整数,即不同的分法。
    思路
    用一个二维数组,a[i][j]表示 可以将i分成j份
    1.可以先拿出一个x,题目便成为将n-x分成k-1份,为了不重复,保证每次拿的x不小于上一次拿的x,现在我们拿出一个1(即现在是有1的情况),有a[i-1][j-1]种情况。
    2.没有1的情况,每份先分配一个1,有a[i-j][j]种情况。(i<=j时不会出现这种情况)
    3.注意:把n分成1份,有一种情况。
    代码

    #include <bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    int a[205][7];///a[i][j] 将i分成j份
    int main()
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
            a[i][1]=1;
        for(int i=2;i<=n;i++)
        {
            for(int j=2;j<=k;j++)
            {
                if(i>j)
                    a[i][j]=a[i-1][j-1]+a[i-j][j];
                else
                    a[i][j]=a[i-1][j-1];
            }
        }
        printf("%d\n",a[n][k]);
        return 0;
    }
    
    展开全文
  • c++ 整数n分成k份 递归实现

    千次阅读 2017-06-14 22:35:41
    最近学到了递归的用法,在课堂上感受到递归的魅力,课后做了这道练习,怎样把整数n分成k份,一开始,只是统计总情况数,后来改进下,顺便输出所有的情况。 写个博客,记录下。 // // main.cpp // ...

    最近学到了递归的用法,在课堂上感受到递归的魅力,课后做了这道练习,怎样把整数n分成k份,一开始,只是统计总情况数,后来改进下,顺便输出所有的情况。

    写个博客,记录下。

    //

    //  main.cpp

    //  整数n分成k

    //

    //  Created by scnulpc on 2017/6/13.

    //  Copyright © 2017 scnulpc. All rights reserved.

    //


    #include <iostream>

    #include <stdio.h>

    using namespace std;

    #define Max 100

    int parts;

    //整数n分成k份,不考虑顺序,譬如把3分成2份,1 2  2 1 是同一种情况。 统计所有情况

    int divideNtoKpart(int n,int k,int start)//n:整数,k:分成k start:start开始分类

    {

        if (k==1) {

            return 1;

        }

        int sum=0;

        for (int i=start; i<=n/k; i++) {

            sum = sum + divideNtoKpart(n-i, k-1, i);

        }

        return sum;

    }

    //统计情况并输出所有情况

    int divideNtoKpartAndPrintAllConditions(int n,int k,int start,int condition[Max],int index)

    {       //n:整数,k:分成k start:start开始分类 数组condition[Max]:存储分类的情况  index:数组下标,0开始

        if (k==1) {

            condition[index]=n;

            for (int m=0; m<parts; m++) {

                cout<<condition[m]<<" ";

            }

            cout<<endl;

            return 1;

        }

        int sum=0;

        

        

        for (int i = start; i<=n/k; i++) {

            condition[index]=i;

            sum = sum + divideNtoKpartAndPrintAllConditions(n-i, k-1, i, condition, index+1);

            

        }

        return sum;

    }

    int main(int argc, const char * argv[]) {

        // insert code here...

        

        int n=0,k=0;

        int conditions[Max];

        cout<<"输入整数n"<<endl;

        cin>>n;

        cout<<"输入份数k"<<endl;

        cin>>k;

        parts=k;

        cout<<divideNtoKpartAndPrintAllConditions(n, k, 1, conditions, 0)<<""<<endl;

        return 0;

    }


    展开全文
  • JavaScript递归算法实现将整数n分成k份,任意两份不能相同题目: 将整数n分成k份,且每份不能为空,任意两种分法不能相同,求有多少种分法。例如:n=7,k=3,下面三种分法被认为是相同的:(1,1,5)(1,5,1)( ...
  • C++ 将整数n分为k份(递归)

    千次阅读 2019-01-14 11:29:04
    一、问题描述   二、思路: ...从剩下的数n-i中分第2(递归),剩下要分的份数为k-1,同样分的数i不能大于 (n-i)/(k-1)  ……  3.一直到k==1结束;  4.考虑如何存储分法:使用数组,每分...
  • 将整数n划分为k份

    千次阅读 2020-08-03 21:21:08
    将整数n划分为k份(java) 题目描述: 给出2个整数n和k,如果n分为k份,每份均不能为0,一共有多少种分法?注:仅顺序不同视为同一种分法。 题解: 我们发现k为2时最易计算,任何数一分为二的分法有(n-1)种,...
  • 整数N分成K份

    千次阅读 2009-07-11 16:37:00
    整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。例如,n=7,k=3则4中分法应为:1,1,5; 1,2,4; 1,3,3; 2,2,3.且下面3中分法被认为是相同的1,1, 5; 1,5,1; 5,1,1问有多少种不同的分法。...
  • (Java实现) 洛谷 P1025 数的划分

    万次阅读 多人点赞 2019-06-01 07:44:29
    将整数n分成k份,且每份不能为空,任意两个方案不相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; 1,5,1; 5,1,1. 问有多少种不同的分法。 输入输出格式 输入格式: n,k (6<n≤...
  • 将整数n分成k份,且每份不能为空,任意两种分法不能相同(不考虑顺序)。例如:n=7,k=3,下面三种分法被认为是相同 的。  1,1,5; 1,5,1;  5,1,1; 问有多少种不同的分法。   输入 输入n,k (6,2≤k...
  • N整数划分

    千次阅读 2016-11-29 13:36:55
    将整数n分成k份,且每份不能为空,任意两个方案不相同(不考虑顺序)。例如:n=7,k=3,下面三种分法被认为是相同的。1,1,5; 1,5,1; 5,1,1;问有多少种不同的分法。#include<bits/stdc++.h>using namespace std;...
  • 求每一部分有最小和 加起来平方和也是最小和 输入 n k 9 4 1 2 3 4 5 6 7 8 9 输出 1 2 3 4 | 5 6 |7 8 |9 最小和 (1+2+3+4)^2+....9^2
  • 将整数N分解成K个整数的和

    千次阅读 2018-03-15 10:10:38
    #include&lt;bits/stdc++.h&gt; #define LL long long #define Max(a,b) a&gt;b?...int k; int sum=0; int A[100]; void solve(int n,int p) { sum++; if(n==0 &amp;&amp;...
  • 整数分成连续正整数之和

    千次阅读 2019-10-21 17:20:41
    一个正整数有可能可以被表示为n(n>1)个连续正整数之和,如: 15=1+2+3+4+5 15=4+5+6 15=7+8 请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列。 1.在标准输出上打印出符合题目描述...
  • 一个整数m分成n整数之和

    千次阅读 2017-04-09 20:38:00
    放苹果 Time Limit:1000MS ...Memory Limit:10000K ...把M个同样的苹果放在N个同样的盘子里,允许有的盘子空着不放,问共有多少种不同的分法?(用K表示)5,1,1和1,5,1 是同一种分法。 In...
  • 题解-数的拆分

    千次阅读 2019-02-13 17:09:13
    将整数n分成k份,且每份不能为空,任意两个方案不相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; 1,5,1; 5,1,1; 问有多少种不同的分法。 输入输出格式 输入格式: n,k (6&amp...
  • 对于整数的拆分中的性质一有不解,在网上搜索的答案中,竟找不到相应的令人满意的解释,郁闷,在群上讨论发现了如此代码,但给出的人又不能做出解释,只好,先记录在案下图,是我自己根据给出的代码进行一定的理解...
  • 求一个正整数n无序拆分为小等于k个正整数的拆分方案数量,要求所有的拆分方案不重复(注意:拆分后的子集是无序的,对于类似 1 2 1 1与2 1 1 1拆分,它们是一种拆分方案)。 输入格式 输入包含一个整数nk,分别...
  • 数的划分(递归)

    千次阅读 2018-04-27 17:40:07
    将整数n分成k份,且每份不能为空,任意两种划分方案不能相同(不考虑顺序)。 例如:n=7,k=3,下面三种划分方案被认为是相同的。 7=1+1+5 7=1+5+1 7=5+1+1 问有多少种不同的分法。 输入描述 Input ...
  • 当数据规模较大时,递归的方式效率很低。 public class Main { ... int arr[][]=new int[n+1][k+1]; for(int i=1;i&lt;=n;i++) { for(int j=1;j&lt;=k;j++) { if(i==1||j=...
  • 数的划分

    2014-07-28 11:19:31
     将整数n分成k份,且每份不能为空,任意两种分法不能相同(不考虑顺序)。例如:n=7,k=3,下面三种分法被认为是相同的。  1,1,5; 1,5,1; 5,1,1; 问有多少种不同的分法。 【输入格式】  n,k (6 ...
  • N个排列好的数,不改变排列次序,要分成K个部分,每个部分至少有一个数, (其中K <=N),若每一个部分的数相乘,然后K个部分相加,则可以得到一个表达式,求这个表达式的最大数值。 输入格式 文件第一行为2个...
  • 整数nk拆分问题

    千次阅读 2009-09-28 11:35:00
    算法小菜鸟刚开始做POJ,1664是一个关于整数拆分的问题,即:整数n分成k个不能整数的和,0比如:7差分成3个不同整数的拆分法有8中,其中1,1,5和1,5,1属于同一种拆分法。该问题等同于:n个完全相同的物品...
  • Du熊正在负责一个大型的项目,目前有K台服务器,有N个任务需要用这K台服务器来完成,所以要把这些任务分成K个部分来完成,在同上台服务器上执行的任务必须是连续的任务,每个任务有各自需要的执行时间。 例如N=5,K=...
  • noip2001 数的划分 (动态规划)

    千次阅读 2015-08-26 09:12:16
    将整数n分成k份,且每份不能为空,任意两份不能相同(不考虑顺序)。 例如:n=7,k=3,下面三种分法被认为是相同的。 1,1,5; 1,5,1; 5,1,1; 问有多少种不同的分法。 格式 输入格式 输入n,k (6 ...
  • //整数n划分成k个不同的正整数(不大于max)的乘积,输出所有划分方法,如果不能则输出“无法划分” public class MultiDivision { public static boolean multiDivide(int n, int k, int max, int[] buf){ ...
  • 题目:给定一个整数数组nums和一个正整数k,找出是否有可能把这个数组分成k个非空子集,其总和都相等。 示例 1: 输入: nums = [4, 3, 2, 3, 5, 2, 1], k = 4 输出: True 说明: 有可能其分成 4 个子集(5),...
  • 一个包含m个整数的数组分成n个数组,每个数组的和尽量接近 3 思路 这个问题是典型的动态规划的问题,理论上是无法找到最优解的,但是本次只是为了解决实际生产中的问题,而不是要AC,所以我们只需要找到一个相对...
  • PTA46题(Java基础练习)

    万次阅读 多人点赞 2019-10-03 20:40:59
    编写一个函数Grade getGrade(int score)传递进来的score转化为枚举类型 score>=90 and 返回A, score>=80 and 返回B, score>=70 and 返回C, score>=60 and 返回D, 其他的返回E main方法 输入分数后,...
  • //一个整数数组,长度为n,其分为m,使得各分的和相等 //比如:{3,4,2,3,6}可以分成{3,2,4,3,6} m=1;或者 {3,6},{2,4,3} m=2; //{3,3},{2,4}{6} m=3,所以m最大值为3 //思路:使用多重背包 //首先遍历一次数组...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 61,416
精华内容 24,566
关键字:

将整数n分成k份