N个数循环奇数位数的数组解法

浏览数：26 / 时间：2015年06月08日

原题是这样的：有N个数组成的数组，要求去除奇数位置上的数字，分别打印出这些数字；剩下的数字从新排列，继续去除其中技术位置上的数字，并打印这些数字；以此类推，直到只剩下最后一个数字，要求在屏幕上打印这些数字，并且显示最后剩下的一个数字在原来数组中的位置。

其实这是很有规律的，用数学方法解很方便。想法是第一次去除的是：{1,3,5,7….}全部的奇数，第二次去除的是{1,3,5,7,9…}×2，第三次去除的是{1,3,5,7,9}×2^2以此类推，很容易根据数学规律写出程式出来。

不巧的是下午头脑发热，一直想着数组，想着利用数组的晒法去求素数。结果愣是写了一个小时没写出来，回来冷静了下，把解决的过程记录下来。

首先，简单的描述下我的思路，其实直接，就是去模拟这个过程。比如这群数中都没有0。那么做一个循环，每间隔一位非零的数字就打印一个，并且把这个数字从新赋值为0。

想法很简单，在java中实现起来去很难。我写了一段非常糟糕的代码，打了很多补丁，测试的时候还是会报错。

说明：为了论述问题的方便，把所有的数看成一个boolean型数组，当这个数被去除时，这个位置的数组值就为false。

一开始我是想每次循环执行两步。每次循环中：第一步找到找到数组中第一个true值，把它的值变成false，第二步，找到数组中的第二个true值，它的值不变。这样写了代码。很糟糕，打了很多补丁，测试的时候还是会报错。代码我就省去了，写下我回来后的思考。

其实这样想法是没有问题的，关键是对于数组的操作。数组是很危险的类型，稍微不慎就会取值越过数组长度范围，导致报错，且这样的错误很难被发现。为此发明了多种方法来安全的操作数组。作为初学者的我，一直操作数组都是在for()中，以前for的下标在每次循环中安静的安全的递增1，从不做其他操作。这次却不同，出错的大部分原因在这里。

为此我总结了一个安全操作数组下标的方法，虽然看起来没有for那样的好看，但是其安全性以及灵活性得到了很大的提高。

它的基本结构如下：
while (bl[i] == false) {                                         //while条件
            i++;                   //对下标进行操作
            if (i >=n) {          //防止i的值出数组的长度
                                     ...                                //下面的操作可以多样化，为下次循环初始化值
        }
}

使用for(){};在大括号中对下标的值进行改写是有风险的，使用类似上述结构的语句可以有效的避免这种风险。

用这种方法为基础，以下是N个数，循环除去奇数位置数字，求最后一位数字的实现代码(java)：

int n =100；

        boolean[] bl = new boolean[n];

        for (int i = 0; i < n; i++) {
            bl[i] = true;
        }                                                   //初始化，将所有的boolean数组值写出true。

        int count = 0;
        int i = 0;
        int k = 1;
        while (count != n - 1) {

            while (bl[i] == false) {
                i++;
                if (i >=n) {                        //越界，在这里意味着一个新的循环开始，{}为下次循环做准备
                    i = i % n;
                    System.out.println();
                    k = 1;
                } // 从头开始,保证必定能找到
            }
            if (k % 2 == 1) {
                bl[i] = false; // 将找到的数杀掉
            //    System.out.print((i + 1) + " be killed\t");
                count++;
            }
            k++;
            i++;
            if (i / n == 1) {
                i = i % n;
            //    System.out.println();
                k = 1;
            }
        }
        //System.out.println();
        while (bl[i] == false) {
            i++;
            if (i >=n) {
                i = i % n;
            }
        }
        System.out.println("第" + (i + 1) + "个人，未被杀");
    }