老赵的自然数分解--少侠之非递归解

简介:

老赵的帖子

自然数分解的题目摘要:

输出所有将sum拆分为n个正整数之和,其中每个正整数k都满足: min <= k <= max。
这n个正整数之间可以重复,不过由于加法交换率的作用,1 + 2和2 + 1便算是重复的拆分了

非递归可不容易啊

昨天晚上睡觉着凉,大清早闹肚子,4点多了就醒了。
不过塞翁失马哦,灵感来了

最后花了半小时写下了核心思想

大清早在老赵哪里发了个报喜贴,没想到正式开始写又碰到点问题好在终于解决了

核心思想:

使用一个工作数组来记录每个位置的相关状态

1、最小分配数
2、最大分配数
3、剩余分配数

其实也就是递归的一个思想,分配掉第一个以后剩余的还是一个分解问题,只不过是总分配数,项数都变化了

例如: sum = 10, n = 4, min = 1, max = 5 的工作数组以及初始拆分数组如下

拆分结果数组   1 1 3 5
           
当前位置最小值   1 1 3 5
当前位置最大值   2 2 4 5
剩余分配数   9 8 5 0

 

另一个核心是在循环嵌套中使用一个标志量来指向最靠右的未达到该位置最大分配数的下标

使用这个标志量让循环反复多次执行,实现迭代的效果

 

public string PrintDivision(int sum, int n, int min, int max)
        {
            //定义返回变量
            string result;
            StringBuilder builder = new StringBuilder();

            //判断输入有效性
            if (min * n > sum || max * n < sum)
                result = "无解\n";
            else
            {
                //定义拆分数组
                //从左至右代表输出表达式的每个拆分结果,也就是当前取值
                int[] arr = new int[n];

                //定义工作数组
                //第1行代表每个位数上的最小取值
                //第2行代表每个位数上的最大取值
                //第3行代表累计到当前位置的累计总和
                int[,] arrWork = new int[3, n];

                //定义临时计算的最大值
                int maxValue;

                //局部待分配值
                int subSum = sum;

                //初始化工作数组
                for (int i = 0; i < n; i++)
                {
                    //第i个位置以后的位置都取最大值的结果
                    maxValue = max * (n - i - 1);
                    //第i个位置上的允许最小值
                    arrWork[0, i] = maxValue >= subSum ? min : subSum - maxValue;
                    //第i个位置上的允许最大值
                    arrWork[1, i] = subSum / (n - i);
                    //除了最后一个,其他位置都以最小值初始化,最后一个以最大值初始化
                    arr[i] = i < n - 1 ? arrWork[0, i] : arrWork[1, i];
                    //累加现有分配结果
                    subSum -= arr[i];
                    //累加结果保存到工作数组
                    arrWork[2, i] = subSum;
                }
                //添加初始分配到输出
                builder.Append(string.Join("+",Array.ConvertAll<int,string>(arr,Convert.ToString)));
                builder.Append("\n");

                //精华哦,这个变量标志需要进行重新排列的起点
                int startpoint = n - 2;
                //生成全部剩余拆分结果
                //从倒数第二个位置开始重置分配数,一直到左边第一个位置结束

                //另外由于标志变量的关系,这个for循环的执行次数会比这里表面看到的多很多
                for (int i = n-2; i >= 0; i--)
                {
                    //从第i个位置的对应最小值加1开始循环到本位置的最大值
                    //这里直接更改本位置分配数以及累计数,比较搞脑子哦。
                    //标准情况下不推荐这么写程序,不是良好的编码风格
                    //这里是因为少搞几个变量出来                    for (arr[i]++, arrWork[2, i]--; arr[i] <= arrWork[1, i]; arr[i]++, arrWork[2, i]--)
                    {
                        //本位置的分配数已经变化,下面重新分配后续位置
                        subSum = arrWork[2, i];
                        min = arr[i];
                        for (int j = i + 1; j < n; j++)
                        {
                            //第j个位置以后的位置都取最大值的结果
                            maxValue = max * (n - j - 1);

                            //第j个位置上的允许最小值                           
                            //按待处理数计算理论最小值
                            arrWork[0, j] = maxValue >= subSum && subSum-maxValue<min ? min : subSum - maxValue;


                            //如果理论最小值小于左边的数字,则使用左边的数字
                            arrWork[0, j] = arrWork[0, j]>min?arrWork[0, j]:min;


                            //第j个位置上的允许最大值
                            arrWork[1, j] = subSum / (n - j);


                            //除了最后一个,其他位置都以最小值初始化,最后一个以最大值初始化
                            arr[j] = j < n - 1 ? arrWork[0, j] : arrWork[1, j];


                            //累加现有分配结果
                            subSum -= arr[j];


                            //累加结果保存到工作数组
                            arrWork[2, j] = subSum;


                            //当一个位置没有达到该位置的最大值的时候,下次的重置起点就要从这里开始。这里是形成类似递归的关键位置
                            if (arr[j] < arrWork[1, j])
                                startpoint = j;
                        }
                        //重置起点
                        i = startpoint;
                        //完成一次分解,输出
                        builder.Append(string.Join("+", Array.ConvertAll<int, string>(arr, Convert.ToString)));
                        builder.Append("\n");
                    }
                }
                result =builder.ToString();
            }
            return result;
        }

 

谢谢大家来观赏哦

ps:源码 

源码已经更新,添加了Dragonpig的算法,并修正我的原有代码
添加了次数统计和时间检测

 按照Dragonpig的思路,在获取剩余排列时的代码可以简化如下

for (int j = i + 1; j < n; j++)
                        {
                            //第j个位置上的允许最大值
                            arrWork[1, j] = subSum / (n - j);
                            //计算并判断当前位置取值
                            arr[j]=Math.Max(min,subSum-max * (n - j - 1 )); //主要就是这个不同啦
                            //累加现有分配结果
                            subSum -= arr[j];
                            //累加结果保存到工作数组
                            arrWork[2, j] = subSum;
                            //当一个位置没有达到该位置的最大值的时候,下次的重置起点就要从这里开始
                            if (arr[j] < arrWork[1, j])
                                startpoint = j;
                        }

的确简洁不少了

 

 

作者: 徐少侠
出处: http://www.cnblogs.com/Chinese-xu/

本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接。
如有问题,可以通过 Chinese_Xu@126.com 联系我,非常感谢。

分享家:Addthis中文版
分类: C#

本文转自徐少侠博客园博客,原文链接:http://www.cnblogs.com/Chinese-xu/archive/2009/06/23/1509396.html,如需转载请自行联系原作者
目录
相关文章
|
6月前
|
算法
回溯-求出数组的所有子序列【学习算法】
回溯-求出数组的所有子序列【学习算法】
48 0
算法学习--递归斐波那契数
算法学习--递归斐波那契数
C语言经典实例:21-30例:插入排序、希尔排序1、快速排序、希尔排序2、递归法、完数、斐波那契数列、公约数和公倍数、判断水仙花数统计单词个数
C语言经典实例:21-30例:插入排序、希尔排序1、快速排序、希尔排序2、递归法、完数、斐波那契数列、公约数和公倍数、判断水仙花数统计单词个数
C语言经典实例:21-30例:插入排序、希尔排序1、快速排序、希尔排序2、递归法、完数、斐波那契数列、公约数和公倍数、判断水仙花数统计单词个数
|
算法
【递归与递推 3】AcWing 717. 简单斐波那契(求解斐波那契数列的若干方法)
【递归与递推 3】AcWing 717. 简单斐波那契(求解斐波那契数列的若干方法)
【递归与递推 3】AcWing 717. 简单斐波那契(求解斐波那契数列的若干方法)
|
机器学习/深度学习 算法
斐波拉契数列的递推递归求解算法
斐波拉契数列的递推递归求解算法
107 0
074.K阶斐波那契序列
074.K阶斐波那契序列
61 0
|
人工智能 BI
斐波那契II--规律/二分
小C养了一些很可爱的兔子。 有一天,小C突然发现兔子们都是严格按照伟大的数学家 斐波那契 提出的模型来进行繁衍:一对兔子从出生后第二个月起,每个月刚开始的时候都会产下一对小兔子。我们假定,在整个过程中兔子不会出现任何意外。 小C把兔子按出生顺序,把兔子们从1开始标号,并且小C的兔子都是1号兔子和1号兔子的后代。如果某两对兔子是同时出生的,那么小C会将父母标号更小的一对优先标号。如果我们把这种关系用图画下来,前六个月大概就是这样的:
197 0
斐波那契II--规律/二分
|
机器学习/深度学习 Windows
【组合数学】递推方程 ( 递推方程示例 2 汉诺塔 | 递推方程示例 3 插入排序 )
【组合数学】递推方程 ( 递推方程示例 2 汉诺塔 | 递推方程示例 3 插入排序 )
137 0
下一篇
无影云桌面