问题:
将一个正整数n表示成一系列正整数之和,求一共有多少种划分的情况。
下面是代码和注释:
#include <stdio.h>
/*
6
5 + 1
4 + 2, 4 + 1 + 1
3 + 3, 3 + 2 + 1, 3 + 1 + 1 + 1
2 + 2 + 2, 2 + 2 + 1 + 1, 2 + 1 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1 + 1
共11种
*/
// 将整数n按照最大加数为m来划分,返回可能的情况个数
int q(n, m) {
// 1只有自身一种情况,最大加数为1也只有一种情况就是加数全部为1
if(n == 1 || m == 1) return 1;
// 最大加数m大于n,则最大加数为n
if(n < m) return q(n, n);
// 最大加数为n只有一种情况就是自身
if(n == m) return q(n, m - 1) + 1;
// 当 m < n且m > 1时,例如
// q(6, 4) = q(6, 3) + q(2, 4)
// 拆分成最大加数为3、2、1的情况 和
// 最大加数为4的情况6 = 4 + 2 继续递归拆分后面的2,最大加数仍保持4,即得q(2, 4)
return q(n, m-1) + q(n - m, m);
}
void main() {
int n = q(6, 6);
printf("%d\n", n);
}
分享到:
相关推荐
C语言之整数划分问题(递归法)实例代码 整数划分问题是算法中的一个经典命题之一,有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分,是指把一个正整数n写成如下形式: n=m1+m2+…+mi; (其中mi为正...
最近我写了一篇csdn文章:【算法设计与分析】——整数划分问题(回溯法),并且画了一个流程图,为了让大家更加清楚的理解我讲的内容,所以我给大家录了一个讲解视频,希望大家一起进步哦~
设计算法求解整数的划分问题,对给定的整数,输出划分数。并思考如何实现输出每个具体的划分。
整数划分方法2及代码(有注释),递归方法,解决了循环游戏的问题
整数划分方法1及代码(有注释),使用递归的方法,同时解决了循环游戏的问题
递归思想和案列(阶乘函数,Fibonacci数列,Ackerman函数,整数划分问题,Hanoi塔问题)分治法思想的介绍(大整数的乘法,Strassen矩阵乘法,棋盘覆盖问题,二分搜索,快速排序,合并排序,线性时间选择)。算法课使用的ppt,可结合...
阶乘函数,Fibonacci数列,基于递归的插入排序,时间递归方程和复杂性分析,整数划分问题,Hanoi塔问题,分治法的适用条件,二分搜索算法,大整数的乘法,Strassen矩阵乘法, 棋盘覆盖,合并排序,快速排序
姜尚仆 -《模线性方程的应用——用数论方法解决整数问题》 金 恺 -《探寻深度优先搜索中的优化技巧——从正方形剖分问题谈起》 雷环中 -《结果提交类问题》 林希德 -《求最大重复子串》 刘才良 -《平面图在信息...
L型组件填图问题 1.问题描述 设B是一个n×n棋盘,n=2k,(k=1,2,3,…)。用分治法设计一个算法,使得:用若干个L型条块可以覆盖住B的除一个特殊方格外的...经典的递归问题, 这是我的大代码, 只是本人很懒, 不想再优化
3.4.2 计算整数的划分数 3.4.3 递归的折半查找算法 3.5 贪心算法思想 3.5.1 基本概念 3.5.2 最优装船问题 3.6 回溯法 3.6.1 基本概念 3.6.2 四皇后问题求解 3.7 数值概率算法 3.7.1 基本概念 3.7.2 计算定积分 第2...
由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如,在计算X和Y的最长公共子序列时,可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题,即计算Xm-1和Yn-1的最长...
·快速排序(第7.1节)中用到的划分方法与期望线性时间顺序统计算法(expected linear-time order-statistic algorithm,第9.2节)有所变化。现在,我们采用了Lomuto提出的方法,并将该方法与指示器随机变量一起使用,...
A:迭代法是数值分析中通过从一个初始估计出发寻找一系列近似解来解决问题的过程 B:分治法的基本思想是把一个规模为n的问题划分为若干个规模较小、且与原问题相似的子问题,因此和递归问题相同 C:递归法是利用函数...
·快速排序(第7.1节)中用到的划分方法与期望线性时间顺序统计算法(expected linear-time order-statistic algorithm,第9.2节)有所变化。现在,我们采用了Lomuto提出的方法,并将该方法与指示器随机变量一起使用,...
其程序结构是按功能划分为若干个基本模块;各模块之间的关系尽可能简单,在功能上相对独立;每一模块内部均是由顺序、选择和循环三种基本结构组成;其模块化实现的具体方法是使用子程序。结构化程序设计由于采用了...
1.4.1. 递归和非递归俩种方法实现二叉树的前序遍历.................................... 73 1.4.2. 请修改 append 函数,利用这个函数实现............................................. 78 1.4.3. 有 n 个长为 m+...
• 主要的软件开发方法(生命周期法、原型法、面向对象法、CASE) • 软件开发工具与环境知识 • 软件过程改进知识 • 软件质量管理知识 • 软件开发过程评估、软件能力成熟评估基础知识 3.2 系统分析...
算法基本设计方法:列举法、归纳法、递推、递归、减半递推技术、回溯法。 (5)指令系统 所谓指令系统指的是一个计算机系统能执行的所有指令的集合。 (2)数据结构研究的3个方面 ① 数据集合中各数据元素之间所固有...