C++ 整数拆分方法详解

一、问题背景

　 整数拆分，指把一个整数分解成若干个整数的和

　　如 3=2+1=1+1+1 共2种拆分

　　我们认为2+1与1+2为同一种拆分

二、定义

　　在整数n的拆分中，最大的拆分数为m，我们记它的方案数为 f(n,m)

　　即 n=x1+x2+······+xk-1+xk ，任意 x≤m

　　在此我们采用递归递推法

三、递推关系

　　1、n=1或m=1时　

　　　 拆分方案仅为 n=1 或 n=1+1+1+······

　　　　　f(n,m)=1

　　2、n=m时

　　　　　S1选取m时，f(n,m)=1，即n=m

　　　　　S2不选取m时，f(n,m)=f(n,m-1)=f(n,n-1)，此时讨论最大拆分数为m-1时的情况

　　　　可归纳 f(n,m)=f(n,n-1)+1

　　3、n<m时

　　　　　因为不能选取m，所以可将m看作n，进行n=m时的方案，f(n,m)=f(n,n)

　　4、n>m时

　　　　　S1选取m时，f(n,m)=f(n-m,m)，被拆分数因选取了m则变为n-m，且n-m中可能还能选取最大为m的数

　　　　　S2不选取m时，f(n,m)=f(n,m-1)，此时讨论最大拆分数为m-1时的情况

　　　　　可归纳 f(n,m)=f(n,m-1)+f(n-m,m)

总递推式为

代码如下

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
int f(int n,int m)
{
if ((n!=1)&&(m!=1))
{
if (n>m) return f(n-m,m)+f(n,m-1);
else return 1+f(n,n-1);
}
else return 1;
}
void work()
{
int n,m;
cin>>n>>m;
cout<<f(n,m);
}
int main()
{
freopen("cut.in","r",stdin);
freopen("cut.out","w",stdout);
work();
return 0;
}

以上所述是小编给大家介绍的C++ 整数拆分方法详解，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对我们网站的支持！

赞 (0)

相关推荐

  • c++ 一个二进制串转化为整数的解决方法

    代码如下: 复制代码 代码如下: <SPAN style="FONT-SIZE: 18px"> char* p = "1010110001100"; int n = 0; for(int i=0;i<strlen(p); i++) {  n = n * 2 + (p[i] - '0'); } printf("%d\n", n);</SPAN>

  • JavaScript 正则表达式 验证整数、小数、实数、有效位小数最简单

    说明:IE6.0.IE7.0.IE8.0.Firefox/3.0.11下测试通过 验证数字最简单正则表达式大全 输入完按回车后即可验证!(自认为最简单!) 正整数: 负整数: 整 数: 正小数: 负小数: 小 数: 实 数: 保留1位小数: 保留2位小数: 保留3位小数: [Ctrl+A 全选 注:如需引入外部Js需刷新才能执行] 出处:http://blog.csdn.net/xxd851116

  • C++初学者之根据输入的任何一个正整数，输出可能被表示的连续正整数

    题目描述:一个正整数有可能可以被表示为 n(>=2) 个连续正整数之和,如: 15=1+2+3+4+5 15=4+5+6 15=7+8 请编写程序,根据输入的任何一个正整数,找出符合这种要求的所有连续正整数序列. 输入数据:一个正整数,以命令行参数的形式提供给程序. 输出数据:在标准输出上打印出符合题目描述的全部正整数序列,每行一个序列,每个序列都从该序列的最小正整数开始.以从小到大的顺序打印.如果结果有多个序列,按各序列的最小正整数的大小从小到大打印各序列.此外,序列不允许重复,序列内的整数用

  • javascript 计算两个整数的百分比值

    复制代码 代码如下: ///计算两个整数的百分比值 function GetPercent(num, total) { num = parseFloat(num); total = parseFloat(total); if (isNaN(num) || isNaN(total)) { return "-"; } return total <= 0 ? "0%" : (Math.round(num / total * 10000) / 100.00 + &qu

  • C++实现十六进制字符串转换为十进制整数的方法

    本文实例讲述了C++实现十六进制字符串转换为十进制整数的方法.分享给大家供大家参考.具体实现方法如下: /* * 将十六进制数字组成的字符串(包含可选的前缀0x或0X)转换为与之等价的整型值 */ #include <stdio.h> #include <math.h> /* 将十六进制中的字符装换为对应的整数 */ int hexchtoi(char hexch ) { char phexch[] = "ABCDEF"; char qhexch[] = &qu

  • C++通过自定义函数找出一个整数数组中第二大数的方法

    本文实例讲述了C++通过自定义函数找出一个整数数组中第二大数的方法.分享给大家供大家参考.具体实现方法如下: const int MINNUMBER = -32767 ; //2字节的Int 0x8000-1, //4字节的Int 0x80000000-1 -2147483647 int find_sec_max( int data[] , int count) { int maxnumber = data[0] ; int sec_max = MINNUMBER ; for ( int i =

  • JavaScript将数据转换成整数的方法

    JavaScript提供将数值转成整数的方法parseInt,用于转换字符串数据"123",或者浮点数1.23. 复制代码 代码如下: parseInt("1");  // 1parseInt("1.2");  // 1parseInt("-1.2");  // -1parseInt(1.2);  // 1parseInt(0);  // 0parseInt("0");  // 0 但是这个parseInt

  • C++求四个正整数最大公约数的方法

    C++求四个正整数最大公约数的方法

    本文实例讲述了C++求四个正整数最大公约数的方法.分享给大家供大家参考,具体如下: /* * 作 者: 刘同宾 * 完成日期:2012 年 11 月 16 日 * 版 本 号:v1.0 * * 输入描述: 输入四个正整数,输出其最大公约数. * 问题描述: * 程序输出: * 问题分析:略 * 算法设计:略 */ #include<iostream> using namespace std; int f(int,int); int g(int,int,int,int); int main()

  • C++ 整数拆分方法详解

    C++ 整数拆分方法详解

    一.问题背景 整数拆分,指把一个整数分解成若干个整数的和 如 3=2+1=1+1+1 共2种拆分 我们认为2+1与1+2为同一种拆分 二.定义 在整数n的拆分中,最大的拆分数为m,我们记它的方案数为 f(n,m) 即 n=x1+x2+······+xk-1+xk ,任意 x≤m 在此我们采用递归递推法 三.递推关系 1.n=1或m=1时 拆分方案仅为 n=1 或 n=1+1+1+······ f(n,m)=1 2.n=m时 S1选取m时,f(n,m)=1,即n=m S2不选取m时,f(n,m)=

  • 使用Math.floor与Math.random取随机整数的方法详解

    Math.random():获取0~1随机数 Math.floor() method rounds a number DOWNWARDS to the nearest integer, and returns the result. (小于等于 x,且与 x 最接近的整数.)其实返回值就是该数的整数位:Math.floor(0.666)   -->  0Math.floor(39.2783)   -->  39 所以我们可以使用Math.floor(Math.random())去获取你想要的一

  • Golang实现快速求幂的方法详解

    今天讲个有趣的算法:如何快速求nm,其中n和m都是整数. 为方便起见,此处假设m>=0,对于m< 0的情况,求出n|m|后再取倒数即可. 另外此处暂不考虑结果越界的情况(超过 int64 范围). 当然不能用编程语言的内置函数,我们只能用加减乘除来实现. n的m次方的数学含义是:m个n相乘:n*n*n...*n,也就是说最简单的方式是执行 m 次乘法. 直接用乘法实现的问题是性能不高,其时间复杂度是 O(m),比如 329要执行29次乘法,而乘法运算是相对比较重的,我们看看能否采用什么方法将时

  • C++中new和delete的使用方法详解

    C++中new和delete的使用方法详解 new和delete运算符用于动态分配和撤销内存的运算符 new用法:           1.     开辟单变量地址空间 1)new int;  //开辟一个存放数组的存储空间,返回一个指向该存储空间的地址.int *a = new int 即为将一个int类型的地址赋值给整型指针a. 2)int *a = new int(5) 作用同上,但是同时将整数赋值为5           2.     开辟数组空间 一维: int *a = new in

  • Android中gson、jsonobject解析JSON的方法详解

    Android中gson、jsonobject解析JSON的方法详解

    JSON的定义: 一种轻量级的数据交换格式,具有良好的可读和便于快速编写的特性.业内主流技术为其提供了完整的解决方案(有点类似于正则表达式 ,获得了当今大部分语言的支持),从而可以在不同平台间进行数据交换.JSON采用兼容性很高的文本格式,同时也具备类似于C语言体系的行为. JSON对象: JSON中对象(Object)以"{"开始, 以"}"结束. 对象中的每一个item都是一个key-value对, 表现为"key:value"的形式, ke

  • PHP中filter函数校验数据的方法详解

    介绍PHP中filter函数校验数据的方法详解,PHP过滤器包含两种类型:Validation用来验证验证项是否合法 .Sanitization用来格式化被验证的项目,因此它可能会修改验证项的值,将不合法的字符删除. input_filters_list() 用来列出当前系统所支持的所有过滤器. 复制代码 代码如下: <?php foreach(filter_list() as $id => $filter) {     echo $filter.' '.filter_id($filter).

  • Python对象类型及其运算方法(详解)

    Python对象类型及其运算方法(详解)

    基本要点: 程序中储存的所有数据都是对象(可变对象:值可以修改 不可变对象:值不可修改) 每个对象都有一个身份.一个类型.一个值 例: >>> a1 = 'abc' >>> type(a1) str 创建一个字符串对象,其身份是指向它在内存中所处的指针(在内存中的位置) a1就是引用这个具体位置的名称 使用type()函数查看其类型 其值就是'abc' 自定义类型使用class 对象的类型用于描述对象的内部表示及其支持的方法和操作 创建特定类型的对象,也将该对象称为该类

  • Python中格式化format()方法详解

     Python中格式化format()方法详解 Python中格式化输出字符串使用format()函数, 字符串即类, 可以使用方法; Python是完全面向对象的语言, 任何东西都是对象; 字符串的参数使用{NUM}进行表示,0, 表示第一个参数,1, 表示第二个参数, 以后顺次递加; 使用":", 指定代表元素需要的操作, 如":.3"小数点三位, ":8"占8个字符空间等; 还可以添加特定的字母, 如: 'b' - 二进制. 将数字以2为基

  • Java this 关键字的使用方法详解

    Java this 关键字的使用方法详解 构造方法中的this关键字 构造方法是一个类的对象在通过new关键字创建时自动调用的,在程序中不能向调用其他方法一样通过方法名(也就是类名)来调用.但如果一个类有多个构造方法,可以在一个构造方法中通过this(paras-)来调用其他的构造方法. 使用this来调用其他构造方法有如下几个约束. 1) 只能在构造方法中通过this来调用其他构造方法,普通方法中不能使用. 2) 不能通过this递归调用构造方法,即不能在一个构造方法中通过this直接或间接调

  • Android View.onMeasure方法详解及实例

    Android View.onMeasure方法详解及实例 View在屏幕上显示出来要先经过measure(计算)和layout(布局). 1.什么时候调用onMeasure方法? 当控件的父元素正要放置该控件时调用.父元素会问子控件一个问题,"你想要用多大地方啊?",然后传入两个参数--widthMeasureSpec和heightMeasureSpec. 这两个参数指明控件可获得的空间以及关于这个空间描述的元数据. 更好的方法是你传递View的高度和宽度到setMeasuredDi

随机推荐