Joseph问题的数组解法(java)

通过数组而非循环链表来解决约瑟夫问题,该方法在逻辑方面比循环链表更加繁琐,实际意义不大,仅仅是突发奇想写出来的,做个记录,

因为数组长度不可变,没有提供删除方法,所以需要手写删除功能代码如下

    String[] delete(String[] str, int index) {//数组删除函数
        String[] str1 = new String[str.length - 1];
        for (int i = 0; i < str1.length; i++) {
            if (i < index) {
                str1[i] = str[i];
            }
            if (i >= index) {
                str1[i] = str[i + 1];
            }
        }
        return str1;
    }

该方法需要通过返回值来重新赋值,达到更新的效果;对于约瑟夫问题的具体逻辑代码,其中需要调用delete函数

 void Joseph(int n, String[] a) {//n为间隔,a为序列
        int i = n - 1;
        while (true) {
            if (a.length >= n) {//数组元素足够完成一次
                if (i < a.length) {//此时i在数组长度范围内
                    System.out.println(a[i]);//打印选中元素
                    a = delete(a, i);//调用函数,将被选中的元素删除
                    i -= 1;//下标回溯1
                    if (a.length - i <= n && n + i - a.length <= a.length - 1) {//当下一次必重新循环时
                        i = n + i - a.length;
                    } else if (a.length - i > n && n + i - a.length <= a.length - 1) {
                        i += n;
                    }
                }
            }
            if (n + i - a.length > a.length - 1) {//当数组元素不足完成一次时
                if (i + n % a.length <= a.length - 1) {//只需要循环一次
                    i += n % a.length;
                } else {//需要循环多次
                    i -= 1;
                    while (i > a.length - 1) {//当前下标等于当前下标加上循环一次之后的多余下标,通过while让其完成至不多余
                        i = n + i - a.length;
                    }
                }
                System.out.println(a[i]);
                a = delete(a, i);
                if (i != 0) {
                    i -= 1;
                }
            }
            if (a.length == 1) {//还剩一个元素
                System.out.println(a[i]);
                a = delete(a, i);
                break;
            }
        }
    }

该方法仅是将需要踢出元素进行打印,然后进行删除操作

public static void main(String[] args) {
    String[] a = {"a", "b", "c", "d", "e", "f", "g"};
    JosephRing j = new JosephRing();
    j.Joseph(3, a);
}

运行代码之后,可以看到踢出字符顺序