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++ 整数拆分方法详解，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对小牛知识库网站的支持！
-
主要内容：1、函数声明,2、函数调用,3、没有参数和返回值的函数,4、有参数但没有返回值的函数,5、有参数且有返回值的函数,6、类中的静态函数C# 中的函数（也可以称为方法）是一段具有签名（由函数名、参数类型和参数修饰符组成的函数信息）的代码块，可以用来实现特定的功能。一般情况下一个函数由以下几个部分组成： 访问权限修饰符：用于指定函数对一个类的可见性； 返回值类型：用于指定函数返回值的数据类型； 函数名称：用于进行函数调用的唯一名称； 参数列表：在调用函数时需要传递给函数的参数，参数列表是可选
-
我做了很多操作，将数字拆分为单独的数字，将数字放入ArrayList并将这些数字一个接一个地传递给其他ArrayList以进行进一步的操作，直到temList为空-然后是下一个比前一个大的数字。 我想知道哪种方法更快。 这两种方法的共同点是： 然后我可以通过两种方式将这些数字逐个传递给其他ArrayList mainList，并在之后删除它们：方式1： 方式2： 哪种方法更快？考虑到这是数十亿次操
-
将一个整数，分拆为若干整数的和。例如实现： 4=3+1 4=2+2 4=2+1+1 4=1+1+1+1 解决(Python) #! /usr/bin/env python #encoding:utf-8 """ """ def int_divided(m,r,out_list): if(r==0): return True tm=r while tm>0:
-
本文向大家介绍C#实现合并及拆分PDF文件的方法，包括了C#实现合并及拆分PDF文件的方法的使用技巧和注意事项，需要的朋友参考一下 有时我们可能会遇到下图这样一种情况 — 我们需要的资料或教程被分成了几部分存放在多个PDF文件中，不管是阅读还是保存都不是很方便，这时我们肯定想要把这些PDF文件合并为一个PDF文件。相对应的，有时候我们也需要拆分一个大的PDF文件，来从中获取我们需要的那一部分资料。
-
本文向大家介绍javascript 判断整数方法分享，包括了javascript 判断整数方法分享的使用技巧和注意事项，需要的朋友参考一下 判断整数的方法有两种：正则判断和逐字判断。 由于逐字判断效率过于低下，这里就不予描述了，有兴趣的看客可以自己谷歌。 1.正则判断 效果测试： http://jsfiddle.net/wzsdp9Lc/ 扩展功能列表 2.取整判断 该方法的思路是取整后判断是否等
-
本文向大家介绍C# MathF.Floor()方法查找最大整数，包括了C# MathF.Floor()方法查找最大整数的使用技巧和注意事项，需要的朋友参考一下 C#中的MathF.Floor()方法用于查找最大整数，该整数小于或等于指定的浮点值。 语法 以下是语法- 上面的Val是浮点值。 示例 现在让我们看一个实现MathF.Floor()方法的示例- 输出结果 示例 现在让我们来看另一个实现M