算法(JAVA)----两道小小课后题

发布时间:2013-09-18 09:58:00作者:左潇龙阅读(1313 )评论(4)

             LZ最近翻了翻JAVA版的数据结构与算法,无聊之下将书中的课后题一一给做了一遍,在此给出书中课后题的答案(非标准答案,是LZ的答案,猿友们可以贡献出自己更快的算法)。

     

    1、编写一个程序解决选择问题。令k=N/2,画出表格显示程序对于N种不同的值的运行时间。

     

             分析:选择问题是指从N个数当中,按升序(降序也可以)排列,找出第k个数。LZ的写法是采用书中给出的算法自己实现的,分别采用冒泡排序和分批处理的方式。以下为LZ写出的算法代码。

    import java.util.Arrays;
    import java.util.Random;
    
    //选择问题答案
    public class Select {
        
        public static final Random RANDOM = new Random(47);
        
        //假设N = 10
        public static void main(String[] args) {
            for (int i = 0; i < 10; i++) {
                printResult(createArray(RANDOM.nextInt(100000)));
            }
        }
        
        //冒泡排序
        public static void sort(int[] values){
            for (int i = 1; i < values.length; i++) {
                for (int j = 0; j < values.length - i; j++) {
                    if (values[j] > values[j + 1]) {
                        int temp = values[j];
                        values[j] = values[j + 1];
                        values[j + 1] = temp;
                    }
                }
            }
        }
        //分批处理
        public static int select(int[] values){
            if (values == null || values.length == 0) {
                throw new NullPointerException("values can"t be null.");
            }
            int k = values.length / 2;
            int[] temp = Arrays.copyOf(values, k);
            sort(temp);
            for (int i = k ; i < values.length; i++) {
                if (values[i] < temp[k - 1]) {
                    temp[k - 1] = temp[k - 2];
                    for (int j = k - 2; j >0; j--) {
                        if (values[i] > temp[j]) {
                            temp[j + 1] = values[i];
                            break;
                        }else {
                            temp[j] = temp[j - 1];
                        }
                    }
                }
            }
            return temp[k - 1];
        }
        //创建随即数组
        public static int[] createArray(int length){
            int[] values = new int[length];
            for (int i = 0; i < length; i++) {
                values[i] = RANDOM.nextInt(length * 2);
            }
            return values;
        }
        //打印结果
        public static void printResult(int[] values){
            System.out.println("length:" + values.length);
            long start = System.currentTimeMillis();
            System.out.println("result:" + select(values));
            System.out.println("cost:" + (System.currentTimeMillis() - start) + "ms");
            System.out.println("--------------------------------");
        }
        
    }

     

    2、编写一个程序求解字谜游戏问题。

     

              分析:字谜游戏是从一个二维的字符数组中按照标量寻找单词的过程,LZ写的算法就是最直观的算法,有很多嵌套循环,倘若字符表很大的时候,这种方式会很慢。想必书中的后面章节应该会有更简单的方式,只不过LZ还没看到,以后有机会改善这个算法。

    import java.util.Random;
    
    //字谜问题
    public class Character {
        
        public static final Random RANDOM = new Random(47);
        
        public static final String[] WORDS = new String[]{"ynz","yzgm","oqz","owznt","z"};
        
        public static void main(String[] args) {
            char[][] chars = createTable(5);
            printTable(chars);
            findWord(chars);
        }
        //按照标量方向寻找满足的单词(或者说字符串)
        public static void findWord(char[][] chars){
            long start = System.currentTimeMillis();
            for (int i = 0; i < chars.length; i++) {
                for (int j = 0; j < chars.length; j++) {
                    for (int k = 0; k < chars.length; k++) {
                        for (int l = 0; l < chars.length; l++) {
                            if (i == k && j == l) {
                                printWord(String.valueOf(chars[i][j]), i, j, k, l);
                                continue;
                            }
                            if (k != i && j != l && (k - i) != (j - l) && (k - i) != (l - j)) {
                                continue;
                            }
                            StringBuffer stringBuffer = new StringBuffer();
                            if (i == k) {
                                if (j > l) {
                                    for (int m = j; m >= l; m--) {
                                        stringBuffer.append(chars[i][m]);
                                    }
                                }else {
                                    for (int m = j; m <= l; m++) {
                                        stringBuffer.append(chars[i][m]);
                                    }
                                }
                            }
                            if (j == l) {
                                if (i > k) {
                                    for (int m = i; m >= k; m--) {
                                        stringBuffer.append(chars[m][j]);
                                    }
                                }else {
                                    for (int m = i; m <= k; m++) {
                                        stringBuffer.append(chars[m][j]);
                                    }
                                }
                            }
                            if ((k - i) == (j - l)) {
                                if (i > k) {
                                    for (int m = i,n = j; m >= k && n <= l; m--,n++) {
                                        stringBuffer.append(chars[m][n]);
                                    }
                                }else {
                                    for (int m = i,n = j; m <= k && n >= l; m++,n--) {
                                        stringBuffer.append(chars[m][n]);
                                    }
                                }
                            }
                            if ((k - i) == (l - j)) {
                                if (i > k) {
                                    for (int m = i,n = j; m >= k && n >= l; m--,n--) {
                                        stringBuffer.append(chars[m][n]);
                                    }
                                }else {
                                    for (int m = i,n = j; m <= k && n <= l; m++,n++) {
                                        stringBuffer.append(chars[m][n]);
                                    }
                                }
                            }
                            printWord(stringBuffer.toString(), i, j, k, l);
                        }
                    }
                }
            }
            System.out.println("-------------------------------------------------");
            System.out.println("cost time:" + (System.currentTimeMillis() - start) + "ms");
        }
        //判断是否是既定的一个单词(或字符串)并打印
        public static void printWord(String word,int i ,int j,int k,int l){
            for (int m = 0; m < WORDS.length; m++) {
                if (word.equals(WORDS[m])) {
                    System.out.println("find word:" + WORDS[m]);
                    System.out.println("scalar:" + "[" + (i+1) + "," + (j+1) + "]->[" + (k+1) + "," + (l+1) + "]");
                }
            }
        }
        //创建随即字符二维数组
        public static char[][] createTable(int length){
            char[][] chars = new char[length][length];
            for (int i = 0; i < chars.length; i++) {
                for (int j = 0; j < chars[i].length; j++) {
                    chars[i][j] = (char)(97 + RANDOM.nextInt(26));
                }
            }
            return chars;
        }
        //打印二维数组
        public static void printTable(char[][] chars){
            System.out.println("---------------------------------------------");
            for (int i = 0; i < chars.length; i++) {
                System.out.print("\t" + (i+1));
            }
            System.out.println();
            for (int i = 0; i < chars.length; i++) {
                System.out.print((i+1));
                for (int j = 0; j < chars.length; j++) {
                    System.out.print("\t" + chars[i][j]);
                }
                System.out.println();
            }
            System.out.println("---------------------------------------------");
        }
        
    }

     

    结束语

     

                    小算怡情,大算伤身。

     


    版权声明:本文版权归作者(左潇龙)所有,欢迎转载。但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

    5
    精彩
    0
    感动
    0
    搞笑
    0
    开心
    0
    愤怒
    0
    无聊
    0
    灌水
    0
    惊讶

上一篇:编程?事业?

#1楼     时间:2013-09-18 12:15:00      来源:雷厉*风行
强算灰飞烟灭~
#2楼     时间:2013-09-18 14:42:00      来源:OpenFire_
@ 雷厉*风行
引用强算灰飞烟灭~

#3楼     时间:2017-04-05 22:55:00      来源:accfcx
5重循环,天啊
#4楼     时间:2017-05-25 10:33:00      来源:WuLei吴磊
选择问题里面的分批处理这里是不是有错啊?判断这里。
if (values[i] > temp[j]) {
temp[j + 1] = values[i];
break;
}else {
temp[j] = temp[j - 1];
}
发表评论

站内搜索

最新评论