整数划分问题(算法分析与设计P12):将正整数n表示成一系列正整数之和:n=n1+n2+…+nk,其中n1≥n2≥…≥nk≥1,k≥1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数和方案。例如正整数6有如下11种不同的划分:
-
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
由于将思路写作注释更方便理解,就不再在前面赘述了,给出代码及思路如下:
-
#include
-
-
intlist[255];
-
-
// num: 要分割的原始数字, n: 当前要分割的数字, k: 已经分割出的数量, sum: 已分割出的数字之和
-
voidsplit(intnum,intn=0,intk=0,intsum=0){
-
// 如果当前要分割的数字未传入,则当前分割的数字即为要分割的原始数字,减少传入参数数量
-
if(n==0){
-
n=num;
-
}
-
// 如果已分割的数字之和等于要分割的原始数字,即分割完毕
-
if(sum+n==num){
-
// 将最后一个数字存入数组
-
list[k]=n;
-
// 判断已分割的数字是否后面小于前面,防止重复
-
boolflag=true;
-
// 暂时未想到更好办法去除重复项,每次都要遍历数组,性能较低
-
for(inti=1;i<=k;++i){
-
if(list[i]>list[i-1]){
-
flag=false;
-
}
-
}
-
// 如果数组合法,则输出
-
if(flag){
-
printf("%d",list[0]);
-
for(inti=1;i<=k;++i){
-
printf("+%d",list[i]);
-
}
-
printf("\n");
-
}
-
}
-
// 从小到大进行分割
-
for(inti=1;i<n;++i){
-
// 分割剩下的数字存入数组
-
list[k]=n-i;
-
// 分割出的数字继续分割
-
split(num,i,k+1,sum+n-i);
-
}
-
}
-
-
intmain(){
-
intn;
-
while(~scanf("%d",&n)){
-
split(n);
-
}
-
return0;
- }
=======================签 名 档=======================
原文地址(我的博客):http://www.clanfei.com/2012/12/1672.html
欢迎访问交流,至于我为什么要多弄一个博客,因为我热爱前端,热爱网页,我更希望有一个更加自由、真正属于我自己的小站,或许并不是那么有名气,但至少能够让我为了它而加倍努力。。
=======================签 名 档=======================
分享到:
相关推荐
C 算法 整数划分问题的源代码实现过程!
算法:整数划分问题,将一个整数n表示成一系列正整数之和。
java算法分析与设计之整数划分问题源代码 算法作为计算机专业学生的必修课,同时也是软件开发过程中必备的编程思想,对学习研究计算机专业意义重大;正因为这门课程难,所以除了相关方面的书籍,网络资源少的可怜,...
整数的分划问题 将正整数n表示成一系列正整数之和,n=n1+n2+...+nk,其中n1>n2>...>nk,k>=1。正整数n的不同划分个数称为n的划分数
算法中的整数划分代码,代码实现,教材中的代码实现
最近我写了一篇csdn文章:【算法设计与分析】——整数划分问题(回溯法),并且画了一个流程图,为了让大家更加清楚的理解我讲的内容,所以我给大家录了一个讲解视频,希望大家一起进步哦~
采用Java语言写的关于一个正整数划分成多个正整数的和的问题!
中科大软件学院 算法导论课程实验 练手题一 整数划分 Visual Studio 2012 项目包
使用C实现的整数划分程序,测试通过,可实现整数划分功能。
C++整数划分算法
例如正整数6有如下11种不同的划分: 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。 Input 输入包含n+1行; 第一行是一个整数n,表示有n个测试用例; 第2至n+...
中科大软件学院 算法导论课程实验 练手题一 整数划分 实验报告
中国科学技术大学软件学院《算法设计与分析》实验题目一
介绍一些算法,是用递归实现的,但也可以用dp来实现
算法中的整数划分问题,用c++语言实现的,操作简单的很,医学就会
输入正整数n的值,输出n的划分种类数及具体的划分情况
算法设计与分析实验-整数划分(可以输出划分结果) https://blog.csdn.net/m0_49558200/article/details/122800456有源码
整数划分问题是算法中的一个经典命题之一,有关这个问题的讲述在讲解到递归时基本都将涉及。所谓整数划分,是指把一个正整数n写成如下形式: n=m1+m2+…+mi; (其中mi为正整数,并且1 <= mi <= n),则{m1,...
整数划分的vs2010实现,c++语言
指把一个正整数n写成多个大于等于1且小于等于其本身的整数的和,则其中各加数所构成的集合为n的一个划分。这是一个典型的递归算法。