频道栏目
首页 > 考试 > 其他 > 正文
编程开发技巧之回溯法统计数组排列数目
2017-10-03 14:33:00      个评论    来源:obrcnh的博客  
收藏   我要投稿

编程开发技巧之回溯法统计数组排列数目。

题目

Suppose you have N integers from 1 to N. We define a beautiful arrangement as an array that is constructed by these N numbers successfully if one of the following is true for the ith position (1 <= i <= N) in this array:

The number at the ith position is pisible by i.
i is pisible by the number at the ith position.
Now given N, how many beautiful arrangements can you construct?

Example:
Input: 2
Output: 2
Explanation:
The first beautiful arrangement is [1, 2]:
Number at the 1st position (i=1) is 1, and 1 is pisible by i (i=1).
Number at the 2nd position (i=2) is 2, and 2 is pisible by i (i=2).
The second beautiful arrangement is [2, 1]:
Number at the 1st position (i=1) is 2, and 2 is pisible by i (i=1).
Number at the 2nd position (i=2) is 1, and i (i=2) is pisible by 1.

解题分析

拿到这道题,可能第一想法就是找找规律,但很遗憾其实规律挺难找的。我们可以这样考虑,从最后一个数n出发,尝试将这个数与前面一个数进行交换,如果交换后的数组满足要求,就进一步进行交换。如果交换后不满足要求,就后退一步,将两个数交换回来。
其实我上面描述的思想就是回溯法的思想。 回溯算法实际上是一个类似枚举的搜索尝试过程。其基本思想是,在包含问题的所有解的解空间树中,按照深度优先搜索的策略,从根结点出发深度探索解空间树。当探索到某一结点时,要先判断该结点是否包含问题的解,如果包含,就从该结点出发继续探索下去,如果该结点不包含问题的解,则逐层向其祖先结点回溯。
上面我就将最大的数字作为根节点,将其它数字作为其叶子节点。每往前访问一个数,就尝试将其与前面的数字交换,这其实就是探索的过程。如果交换后满足条件就继续往前交换,这就很类似深度优先探索了;如果不满足条件就交换回来,往祖先节点回溯。所以当根节点的所有子树都被访问也即遍历到最小的一个数时,这个过程就结束了,结果也就出来了。下面是这个算法的源代码。

源代码

class Solution {
public:
    int number = 0;

    int countArrangement(int N) {
        int* nums = new int[N + 1];
        for (int i = 0; i <= N; i++) {
            nums[i] = i;
        }
        count(nums, N);
        return number;
    }

    void count(int* nums, int n) {
        if (n == 0) {
            number++;
            return;
        }
        for (int i = n; i > 0; i--) {
            swap(nums[i], nums[n]);
            if (nums[n] % n == 0 || n % nums[n] == 0) {
                count(nums, n - 1);
            }
            swap(nums[n], nums[i]);
        }
    }
};

以上是我对这道问题的一些想法,有问题还请在评论区讨论留言~

点击复制链接 与好友分享!回本站首页
上一篇:编程开发习题_Mooo 奶牛的歌声(单调栈)
下一篇:编程开发习题_Modernizacja autostrady
相关文章
图文推荐

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站