`
j夫子
  • 浏览: 92550 次
  • 性别: Icon_minigender_1
社区版块
存档分类
最新评论

分解和为N的所有加数的情况

 
阅读更多
/**
 * http://zjfhw.iteye.com/blog/2213877
 * 分解和为N的因子
 * 思路:
 * 和为N的因子 必然可以分成N组
 * 比如5
 * 因子数为5的组:1+1+1+1+1
 * 因子数为4的组:1+1+1+1   然后剩余的1 分配给任意一组 2+1+1+1 1+2+1+1 (如果位置不同算为2组的话)
 * 因子数为3的组:1+1+1   剩余2 ,问题变成 如何将2个1 分配给 3个组 
 * ......
 * 
 * 因子数为1的组:5
 */
public class ResolveSum {
	static int[] arr ;
	
	public static void main(String[] args) {
		//要分解的和为10
		int n = 10;
		//将10转化成 一个长度为n的数组 每个元素都为1
		arr =getData(n);
		//分别去求因子个数为i的因子集 i=1~n
		for(int i=1;i<=arr.length;i++){
			resolveSum(1,0,i,arr.length);
			clear(arr);
		}
	}
	/**
	 * 分解
	 * @param index 往第index个位置分发1
	 * @param payd 计数器,已经分发了payd个1
	 * @param group 该组有group个元素
	 * @param N 要分解的和
	 */
	static void resolveSum(int index,int payd,int group,int N){
		//循环着进行分发,覆盖  “n个数分发到m个地方” 的所有情况
		for(int i=payd;i<N-group;i++){
			//首先将第index个位置分发1
			arr[index-1]+=1;
			if(i==N-group-1){
				//当剩余值已经分发完,将该组因子打印出来
				printElement(arr,group);
				//将最后操作的位置还原成1 
				arr[index-1]=1;
			}else{
				//否则开始向index+1的位置进行分发,如果已经超出了该组的因数个数,则不操作
				if(index+1<=group)
				resolveSum(index+1,i+1,group,N);
			}
		}	
		
		
	}
	private static void printElement(int[] arr2, int group) {
		System.out.print(arr2.length+"=");
		for(int i=0;i<group;i++){
			System.out.print(+arr2[i]+ (i==group-1?"":"+"));
		}
		System.out.println("");
			
	}
	
	public static int[] getData(int n){
		int[] data = new int[n];
		for(int i=0;i<data.length;i++){
			data[i] = 1;
		}
		return data;
	}
	
	public static void clear(int[] data){
		for(int i=0;i<data.length;i++){
			data[i] = 1;
		}
	}
}

 

 

结果:(没有考虑 加数一样但位置不同的情况,视具体问题进行修改吧...很简单)

 

10=10

10=2+8

10=3+7

10=4+6

10=5+5

10=6+4

10=7+3

10=8+2

10=9+1

10=2+2+6

10=2+3+5

10=2+4+4

10=2+5+3

10=2+6+2

10=2+7+1

10=3+2+5

10=3+3+4

10=3+4+3

10=3+5+2

10=3+6+1

10=4+2+4

10=4+3+3

10=4+4+2

10=4+5+1

10=5+2+3

10=5+3+2

10=5+4+1

10=6+2+2

10=6+3+1

10=7+2+1

10=8+1+1

10=2+2+2+4

10=2+2+3+3

10=2+2+4+2

10=2+2+5+1

10=2+3+2+3

10=2+3+3+2

10=2+3+4+1

10=2+4+2+2

10=2+4+3+1

10=2+5+2+1

10=2+6+1+1

10=3+2+2+3

10=3+2+3+2

10=3+2+4+1

10=3+3+2+2

10=3+3+3+1

10=3+4+2+1

10=3+5+1+1

10=4+2+2+2

10=4+2+3+1

10=4+3+2+1

10=4+4+1+1

10=5+2+2+1

10=5+3+1+1

10=6+2+1+1

10=7+1+1+1

10=2+2+2+2+2

10=2+2+2+3+1

10=2+2+3+2+1

10=2+2+4+1+1

10=2+3+2+2+1

10=2+3+3+1+1

10=2+4+2+1+1

10=2+5+1+1+1

10=3+2+2+2+1

10=3+2+3+1+1

10=3+3+2+1+1

10=3+4+1+1+1

10=4+2+2+1+1

10=4+3+1+1+1

10=5+2+1+1+1

10=6+1+1+1+1

10=2+2+2+2+1+1

10=2+2+3+1+1+1

10=2+3+2+1+1+1

10=2+4+1+1+1+1

10=3+2+2+1+1+1

10=3+3+1+1+1+1

10=4+2+1+1+1+1

10=5+1+1+1+1+1

10=2+2+2+1+1+1+1

10=2+3+1+1+1+1+1

10=3+2+1+1+1+1+1

10=4+1+1+1+1+1+1

10=2+2+1+1+1+1+1+1

10=3+1+1+1+1+1+1+1

10=2+1+1+1+1+1+1+1+1

 

最后再加上

10=1+1+1+1+1+1+1+1+1+1

0
0
分享到:
评论

相关推荐

    整数因子分解

    // 继续递归分解n / i i--; // 测试下一个可能的因子 } } } int main() { int n; scanf("%ld", &n); // 读入n ok(n); // 开始分解 printf("%ld", num); // 输出不同的分解方式数量 } ``` 这段代码实现了...

    算法分析与设计:贪心算法(自然数加法分解乘积最大+马拉松接力问题+整数删除后取最大值)(C++可执行源码+完整算法分析)

    题目1:设 n 为一自然数,n 可以分解成若干个不同的自然数的和,这样的分法有很多种,比如 n=10, 10 可以分解为:10=5+4+1; 10=5+3+2; 10+9+1; 10=8+2; 10=7+3; 10=6+4;10=7+2+1; 10=6+3+1;…。在所有这些分法中,各...

    11091 最优自然数分解问题

    而如果整数n可以分解为若干互不相同的加数时,不考虑自身为单独加数的情况,比如4,问题(1)的解输出为3,而非4。 输入格式 只有一个正整数n(1&lt;=n)。 输出格式 输出待解问题(1)和(2)的最大乘积,中间...

    9718 整数因子分解

    1. **基本情况**:如果n等于1,则表示找到了一种因子分解的方式,此时计数器加1。 2. **递归步骤**:如果n大于1,那么对于每一个可能的因子i(2 &lt;= i &lt;= n),计算solve(n/i),这里solve()函数表示对正整数n的因子...

    质因数分解

    质因数分解是将一个数N(在这个例子中是7位数)拆分成一系列质数的乘积,形式为N = p1^a1 * p2^a2 * ... * pk^ak,其中p1, p2, ..., pk是质数,a1, a2, ..., ak是相应的指数,表示每个质数在分解中的出现次数。 质...

    西南交通大学算法理论课作业6.rar

    题目 1:设 n 为一自然数,n 可以分解成若干个不同的自然数的和,这样的分法有很多种, 比如 n=10, 10 可以分解为:10=5+4+1; 10=5+3+2; 10+9+1; 10=8+2; 10=7+3; 10=6+4; 10=7+2+1; 10=6+3+1;…。在所有这些分法中...

    20151910042-刘鹏-MC实验04-因子分解问题1

    - 明文M(0&lt;M&lt;n)通过公钥e和n进行加密,得到密文C,计算公式为:C=M^e mod n。 - 这个过程对任何人都是公开的,因为e和n是公钥。 3. **解密过程**: - 接收者使用私钥d和n来解密C,得到原始明文M,计算公式为:...

    时因式分解利用十字相乘法分解因式张PPT学习教案.pptx

    - 对于一次项系数 `b`,找到两个数 `m` 和 `n`,使得 `m * n = c` 且 `m + n = b`。 - 把 `m` 和 `n` 分别写在交叉点的两边,然后把它们与原多项式中的每一项相乘,最后合并同类项得到因式分解的结果。 4. **教学...

    RSA算法加密解密运算

    此外,如果能有效地分解N,那么就能找出p和q,进而计算出d,所以RSA的安全性与大数分解问题紧密相关。 7. **应用扩展**:RSA不仅用于加密,还可以实现数字签名,通过私钥生成签名,公钥验证签名,确保信息的完整性...

    第十三届蓝桥杯省赛真题解析-分解整数.pdf

    题目要求给定一个正整数 \(N\)(\(5 &lt; N )),将其分解为三个互不相同的正整数之和,并且这三个正整数中均不含数字3和7。目标是计算出所有符合条件的分解方法的数量。 #### 解题思路分析 ##### 理解题意 根据题目...

    RSA算法的基本加密原理

    - 欧拉函数φ(n)定义为小于n的所有正整数中与n互质的数的个数。 - 对于n = pq,φ(n) = (p-1)(q-1)。 **步骤3:选择公钥e** - 选择一个小于φ(n)且与φ(n)互质的正整数e作为公钥的一部分。 - 一般情况下,e可以...

    N-S方程详细推导

    N-S方程中的应力状态可以分解为法向应力和切应力。应力张量中的每一个元素都有特定的物理意义,分别对应于不同方向上的压力和剪切作用。 4. 流体单元的加速度和质量力 研究流体运动时,单元体的加速度与质量力是...

    RSA算法加密汉字.doc

    该算法基于大整数因子分解的困难性,即找到两个大素数p和q的乘积n的因数p和q非常困难。RSA算法包含两个密钥:公钥和私钥。公钥可以公开,用于加密信息;私钥必须保密,用于解密信息。 在给出的代码中,主要实现了...

    湖南专版2020年中考数学复习第一单元数与式课时训练03整式运算与因式分解20191217166

    【知识点详解】 1. **单项式的系数**:单项式的系数是指数字的部分,不包括变量。...此外,还包括了代数表达式的化简、求值、多项式的加减乘除、因式分解,以及实际问题中的应用,如优化问题和几何图形与代数的结合。

    中考数学复习-中考复习(2):整式和分解因式.doc

    - **单项式**:由数与字母组成的代数式,单独的数或字母也视为单项式。单项式的系数是指其中的数字因数,次数则是所有字母指数的和。 - **多项式**:由几个单项式相加组成,每个单项式称为多项式的项。多项式的...

    计算方法第五章1

    线性方程组的一般形式为n阶,即方程数和未知数相同,其矩阵形式为Ax=b,其中A是系数矩阵,x是未知数向量,b是常数向量。当系数矩阵A非奇异(行列式det(A)不等于零)时,方程组有唯一解。 解线性方程组的数值方法...

    RSA生成密钥对、公钥加密和私钥解密

    在支持最大2048位RSA计算的情况下,这意味着密钥长度可以达到2048位,这提供了极高的安全性,但同时也会带来计算上的复杂性和时间消耗。2048位的密钥长度在当前被认为足够抵御大多数攻击,尽管随着计算能力的增强,...

    rsa.rar_1U1_C++_RSA加解密算法_rsa加解密

    选取一个与φ(n)互质的整数e作为公钥的加密指数,计算d为e的模φ(n)的逆元,即d*e ≡ 1 (mod φ(n)),d作为私钥的解密指数。 2. **密钥生成**: - 选择两个大素数p和q。 - 计算n=p*q,n作为公钥和私钥的一部分。 ...

Global site tag (gtag.js) - Google Analytics