亚洲福利一区二区,亚洲精品无码不卡在线播放HE,亚洲第一中文字幕

約瑟夫環問題求解

用數組實現約瑟夫出圈問題，n個人排成一圈，從第一個開始報數，報到m的人出圈，
剩下的人繼續開始從1報數，直到所有的人都出圈為止。對于給定的n，m，
求出所有的人出圈順序。

class OutOfCircle {

public OutOfCircle(int nn, int mm) {

n = nn;

m = mm;

man = new int[n]; //使用man數組表示N個人，man[i]為1表示i還在圈中，為0則表示i已經不在圈中

count = new int[n]; //保存出圈順序

java.util.Arrays.fill(man, 1); //初始化man，一開始所有人都在圈中，所以都為1

}

public int[] out() {

int c = 0; //當前人報的數

int j = 0;

while (total(man) != 0) { //當圈中沒人時，man中元素之和為0

for (int i = 0; i < n; i++) {

c = c + man[i]; //報數，出去的人為0，相當于沒報

if (c != 0 && c % m == 0) { //表示當前c!=0一定要加上，因為0對任何數取余都為0

man[i] = 0; //出圈，置為0

count[j++] = i + 1; //保存出圈人的編號

c = 0; //重新開始報數

}

return count;

}

private int total(int[] t) { //求INT數組的和

//int sum = 0;

for (int i : t) {

//sum += i;
if(t[i]!=0) return 1;

}
return 0;

//return sum;

}

private int n;

private int m;

private int[] man;

private int[] count;

}

posted on 2008-11-19 17:34 Bom Wu 閱讀(2197) 評論(7) 編輯收藏

Comments

# re: 約瑟夫環問題求解[未登錄]
littleq
Posted @ 2008-11-20 12:30
判斷圈內是否有人，用total這個方法，好像有點多余吧，你既然用for循環了，那就
if(t[i]!=0)return 1;
這樣還能少循環幾次
回復更多評論
# re: 約瑟夫環問題求解
Bom Wu
Posted @ 2008-11-20 14:42
@littleq
對對對，不用關心還有幾個人，只要存在t[i]==1那就表示有人，不用全加起來了，多謝指教呀！回復更多評論
# re: 約瑟夫環問題求解
object
Posted @ 2008-11-20 14:57

import java.util.ArrayList;
import java.util.List;

/** *//**
* @author huangjie
* @createDate 2008-11-20
* @package
* @fileName OutofCircle.java
**/
public class Test{
    public static void main(String[] args){
        OutOfCirle ooc=new OutOfCirle(1000,10000);
        ooc.begin();
    }
}
class OutOfCirle {
    //報出了這個數的都退出
    public static int outNumber;
    //總的有多少個人
    public static int manSize;
    //上面2個一開始就固定好了，所以我就聲明成static

    //圈中的人
    private List<Man> allMan;
    //現在已經報到第幾號了,初始化為1
    private int nowNumber=1;
    //現在已經報到第幾個人了，初始化為0;
    private int nowMan=0;

    public OutOfCirle(int manSize,int outNumber){
        OutOfCirle.manSize=manSize;
        OutOfCirle.outNumber=outNumber;
        init();
    }
    private void init(){
        allMan=new ArrayList();
        //初始化所有人，即把所有人編上號
        int manNumber=0;
        while(OutOfCirle.manSize!=manNumber){
            allMan.add(new Man(++manNumber));
        }
    }
    public void begin(){
        while(allMan.size()>0){
            Man man =this.select();
            //把這個人T出去
            allMan.remove(man);
            //當T的是最后一個的時候,又從第一個開始數
            if(nowMan==allMan.size()){
                nowMan=0;
            }
            //說明T的不是最后一個
            //T的人的后面的都會往前移一個位置
            //這樣就把原來的nowman代替了,就可以從nowman開始數了
            else{

            }
            //選出來了以后又從1開始報
            nowNumber=1;
            System.out.println("我是第"+man.getNumber()
                    +"號，我現在被T出去了,我是第"
                    +(manSize-allMan.size())+"個被T的"
                    +"，還有"+allMan.size()+"在圈里");
        }
        System.out.println("所有人都被T出去完了");
    }
    //找出報outNumber的人
    private Man select(){
        Man man=null;
        //沒選出來就一直報數
        while(man==null){
            //nowman報數
            Man m=allMan.get(nowMan);
            boolean right=m.reckon(nowNumber);
            //就是他了
            if(right){
                man=m;
            }
            //說明不是他
            else{
                //報的數字到下一個
                nowNumber++;
                //人也到下一個去
                nowMan++;
                //說明已經到了最后一個了
                if(nowMan==allMan.size()){
                    //又從第一個開始報數
                    nowMan=0;
                }
            }
        }
        return man;
    }

}
class Man{
    private int number;
    public Man(int number){
        this.number=number;
    }
    public int getNumber() {
        return number;
    }
    //報數：判斷報出的數字是否和outNumber
    public boolean reckon(int num){
        return num==OutOfCirle.outNumber;
    }
}

你的方法太不面向對象了,看我寫的
  回復   更多評論
# re: 約瑟夫環問題求解
object
Posted @ 2008-11-20 14:59
你的太不面向對象了,看我的回復更多評論
# re: 約瑟夫環問題求解
Bom Wu
Posted @ 2008-11-20 15:08
看來對面向對象的理解還真是不一樣。多謝指教！回復更多評論
# re: 約瑟夫環問題求解
object
Posted @ 2008-11-20 15:32
其實每個人都有自己的一套理解方式,呵呵,對象這個東西,有的時候給別人講解的時候根本就講解不出來
回復更多評論
# re: 約瑟夫環問題求解
小七群
Posted @ 2008-11-20 16:59
要考慮到n<m的情況嗎？回復更多評論

新用戶注冊刷新評論列表


只有注冊用戶登錄后才能發表評論。




網站導航: 博客園 IT新聞 Chat2DB C++博客博問管理

導航

常用鏈接

留言簿

隨筆分類

隨筆檔案

文章分類

文章檔案

搜索

最新評論

閱讀排行榜

評論排行榜