package cn.magicdu.algorithm;

import java.util.LinkedList;
import java.util.List;

/**
 * 出圈问题，数到某个数字的倍数就出圈，打印最后剩下的元素的原来位置
 * 
 * @author xiaoduc
 *
 */
public class Circle {
    public static void main(String[] args) {
        System.out.println("剩下元素原来的位置"+cycle(50,3));
    }

    private static int cycle(int total, int k) {
        List<Integer> dataList=new LinkedList<Integer>();
        for(int i=0;i<total;i++)
            dataList.add(new Integer(i+1));
        //定义下标，模拟已经去掉一个元素
        int index=-1;
        while(dataList.size()>1){
            index=(index+k)%dataList.size();//得到应该出局的下标
            dataList.remove(index--);//去除元素    
        }
        return (Integer)dataList.get(0).intValue();
    }
}