黑马程序员技术交流社区

标题: 数学方面的题,想不明白. [打印本页]

---

作者: 王广彬    时间: 2012-7-27 10:04
标题: 数学方面的题,想不明白.
具体题目是：122345这6个数，打印出它所有可能的组合；要求4不能在第3位，3和5不能相连。
有好多种方法，现在提供一种，看不明白，求详细讲解，谢谢！
package org.qh.demo;
import java.util.ArrayList;
import java.util.List;
public class demo5 {
        public static void main(String[] args) {
                int len = 6;
                int[] numArray = { 1, 2, 2, 3, 4, 5 };
                int[] currentArray = new int[len];
                getNextNumber(0, 1, numArray, currentArray);
        }
        private static void getNextNumber(int preNum, int level, int[] numArray,
                        int[] currentArray) {
                List<Integer> intList = new ArrayList<Integer>();
                for (int i = 0; i < numArray.length; i++) {
                        int currentNum = numArray[i];
                        if (intList.indexOf(Integer.valueOf(currentNum)) > -1)
                                continue;
                        intList.add(currentNum);
                        // 4不能在第3位出现
                        if (level == 3 && currentNum == 4)
                                continue;
                        if (level != 1) {
                                // 3和5不能相连
                                if ((currentNum == 5 && preNum == 3)
                                                || (currentNum == 3 && preNum == 5)) {
                                        continue;
                                }
                        }
                        currentArray[level - 1] = currentNum;
                        int nextLevel = level + 1;
                        if (level == currentArray.length) {
                                OutArray(currentArray);
                                return;
                        } else {
                                getNextNumber(currentNum, nextLevel,
                                                createNewArray(numArray, i), currentArray);
                        }
                }
        }
        private static int[] createNewArray(int[] oldArray, int orderNumber) {
                if (oldArray.length <= 1)
                        return null;
                int newLen = oldArray.length - 1;
                int[] newArray = new int[newLen];
                int newOrderNumber = 0;
                for (int i = 0; i < oldArray.length; i++) {
                        if (i == orderNumber)
                                continue;
                        newArray[newOrderNumber] = oldArray[i];
                        newOrderNumber++;
                }
                return newArray;
        }
        private static void OutArray(int[] array) {
                for (int i = 0; i < array.length; i++) {
                        System.out.print(array[i]);
                }
                System.out.println("");
        }
}

---

作者: 创出一片辉煌    时间: 2012-7-27 10:32
应该是这样吧！
这个程序的核心是一个递归算法，计算每一位的数据，看结果是否满足条件。
我简单对这个算法的方法进行了注释，你可以看一下：      //  preNum：上一位的值

      //  level：当前位数

      //  numArray：原数组

      //  currentArray：当前正在组合的数组

      private static void getNextNumber(int preNum, int level, int[] numArray,

                        int[] currentArray) {

                // 定义集合，保存已经加入过的数值

                List<Integer> intList = new ArrayList<Integer>();

                // 循环原数组

                for (int i = 0; i < numArray.length; i++) {

                        // 取得一个值

                        int currentNum = numArray[i];

                        // 判断集合中是否出现过这个值，如果出现过，则不使用这个值

                        if (intList.indexOf(Integer.valueOf(currentNum)) > -1)

                                continue;

                        // 将值添加到数组中

                        intList.add(currentNum);



                        // 4不能在第3位出现

                        if (level == 3 && currentNum == 4)

                                continue;

                        if (level != 1) {

                                // 3和5不能相连

                                if ((currentNum == 5 && preNum == 3)

                                                || (currentNum == 3 && preNum == 5)) {

                                        continue;

                                }

                        }



                        // 将通过判断条件的值加入到正组合的数组中

                        currentArray[level - 1] = currentNum;

                        // 计算下一位的位数

                        int nextLevel = level + 1;

                        // 如果当前位数已经达到数组的总位数，则输出结果

                        if (level == currentArray.length) {

                                OutArray(currentArray);

                                return;

                        } else {

                                // 否则继续进行下一位的计算。

                                getNextNumber(currentNum, nextLevel,

                                                createNewArray(numArray, i), currentArray);

                        }

                }

        }

---

作者: 刘奇    时间: 2012-7-27 11:00
程序的算法是一个深度优先算法（dfs），如果想理解这个程序，你应该先去了解一下深度优先拓展的算法，实现方式很多，可以用栈也可以递归。这个程序的模型是一个六层六叉树，用的是递归，其实理解了dfs通用的算法流程后，这个程序的关键点只是处理每一层节点拓展以及判断父节点的值来决定拓展什么样的子节点，说起来很抽象，其实理解了非常简单
如果你喜欢做这样的题目，建议你多去 poj 和 hdoj 上做一些题目，都是acm算法的题，非常不错，如果有哪些问题，看一下解题报告，讨论都比较多

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2