编程：现有1克，2克，3克，…100克砝码充分多枚，组合成100克共有多少种方式？

本文主要是介绍编程：现有1克，2克，3克，…100克砝码充分多枚，组合成100克共有多少种方式？，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

JAVA实现拉马努金的整数拆分全排列

致敬神一般的拉马努金

点此跳转：非递归方式

由于电脑垃圾，递归算不出来结果，结果在非递归方式的文章
编程：现有1克，2克，3克，…100克砝码充分多枚，组合成100克共有多少种方式？
偶然看见有这么一个面试题，新人小白，网上搜了一下，貌似并没有相关的答案和代码，所以特意自己记录一下，并发表一下，新人小白，错了勿喷。

首先这个题，乍一看，就想到了递归，作为递归，要注意几个点，第一：找到跳出点，第二，找到规律。
那么我们开始吧，注意是充分多枚，从0开始，0克组合方式1种，1克组合方式1种，2克组合方式2种，那么继续推，3克的砝码组合方式是3种，4克的方法组合方式是5种，到了这里，肯定有小伙伴觉得这简单，这不就是斐波那契数列吗？不急，5克的砝码组合方式是7种，到了这里就发现不对劲了，斐波那契数列是112358，可是这里是112357，很明显不是了，继续：1，1，2，3，5，7，11，15，22，30.好了，这里可以明显的发现这不是斐波那契数列，是拉马努金的整数拆分全排列。
*神一般的拉马努金~~~~~*
具体公式大家可以百度，这里我贴一下公式图：
在这里插入图片描述

好了既然知道了规律，也有了跳出条件，0，1都只有固定一种。
那么我们接下来就用JAVA，用递归的方式来实现一遍吧。
过程着实复杂，看不懂的看注释吧。。。。。。

/*** * @author An* 拉马努金的整数拆分**/
public class Test03 {public static void main(String[] args) {int result=f1(100);System.out.println(result);}private static int f1(int i) {int result = 0;//表示最终结果int count = 1;//表示循环的次数，用来控制下标int n =1;//表示当前下标下，应该传入的数boolean flag = true;//控制加减，true=+，false= -if(i==0||i==1) {return 1;//0和1的拆分次数固定是1种，也是递归的出口}else {while(i-n>=0){//i-应该减掉的n<0跳出if(count==1) {					result +=f1(i-n);count++;//下标置为第二次n= count;//第二次应该减掉的数
//count=1的时候，表示循环刚开始，应该添加i-n（默认初始值1）}else if(count==2) {result +=f1(i-n);count++;//下标继续自增n =count*2-1;//第三次下标预设flag=!flag;//此时修改标志位，false=减少
//count=2，循环开始第二次，第一个已添加，第二是i-2，}else {if(count%2!=0) {//求模，可以知道是单数or双数，单数无需修改标志位result=(flag==true ? result+f1(i-n) : result-f1(i-n));//三目运算，根据标志位，决定是+是-count++;//标志位继续增加n +=count/2;//后面的单数规律。}else {//求模，可以知道是单数or双数，单数无需修改标志位result=(flag==true ? result+f1(i-n) : result-f1(i-n));count++;//标志位继续增加n +=count;//后面的双数规律flag = !flag;//双数后要修改标志位}}}}return result;}
}