每天一道算法题：整数的加法划分

谁践踏了优雅 2022-10-29 05:25 171阅读 0赞

## 整数的加法划分 ##

要求：`对于给定的正整数n，编写算法打印该数的所有加法划分`

demo：n = 6  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]  
**分析：**  
我们对该数的划分进行观察，可以发现以下规律

*  它的每一行的第一个数是按从小到大的一个顺序排列的
 *  每一行都是按从小到大的顺序排列的

**递归思路：**  
首先，我们需要构造相似性，找到递归的变化条件，这里很明显一个参数是不够的，因为我们需要一个变量来保存每一层循环里符合条件的数据。要保存多个数据，很明显，数组是最合适的，同时，我们还需要定义数组的下标，用来指定数据的存储位置

对于第一个条件，我们可以通过一个循环来实现，从n开始到1，在这个循环内，我们需要拿到每次i变化的最大值作为第一个元素，因为循环是从n开始的，所以当前循环的n是最大值（注意，这里的n实际是赋值给变量i的，所以是会随着循环变化的）然后，对于第二个条件，我们需要对后面的数进行判断，如果后一个元素大于前一个元素，则跳过当前循环，不进行赋值，完成这些操作之后就可以进行下一层的递归了。

**代码实现:**

public static void f(int n,int arr[],int k){ 
     		//当前的n为0时，打印数组中所有的数据
            if(n<=0x00){ 
                for(int i=0;i<k;i++)
                    System.out.print(arr[i]+" ");
                System.out.println();
            }
            //从n开始遍历
            for(int i=n;i>0;i--){ 
                //有前一项 且 后一项的值小于前一项
                //从k>0的所有项里面去判断，如果后一项的值大于前一项就continue
                if(k>0 && i>arr[k-1])
                    continue;
                arr[k] = i;
                //这里用n-i就是为了能够使下一层的n=0,然后对数组中保存的数据进行打印
                //因为k在第一层函数中一直是0，它是不变的，所以实际上我们是不断的在覆盖数组中的元素
                //当n=0时就将中间回调得到的数据全部打印出来
                f(n-i,arr,k+1);
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ3OTUzODU1_size_16_color_FFFFFF_t_70]: /images/20221024/b653ec8c3fd54bcdbb72011fb3e582be.png