视频在线亚洲,国产精品乱码人人做人人爱 ,色综合天天狠狠

約瑟夫環(huán)問題求解

用數(shù)組實(shí)現(xiàn)約瑟夫出圈問題，n個(gè)人排成一圈，從第一個(gè)開始報(bào)數(shù)，報(bào)到m的人出圈，
剩下的人繼續(xù)開始從1報(bào)數(shù)，直到所有的人都出圈為止。對于給定的n，m，
求出所有的人出圈順序。

class OutOfCircle {

public OutOfCircle(int nn, int mm) {

n = nn;

m = mm;

man = new int[n]; //使用man數(shù)組表示N個(gè)人，man[i]為1表示i還在圈中，為0則表示i已經(jīng)不在圈中

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

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

}

public int[] out() {

int c = 0; //當(dāng)前人報(bào)的數(shù)

int j = 0;

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

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

c = c + man[i]; //報(bào)數(shù)，出去的人為0，相當(dāng)于沒報(bào)

if (c != 0 && c % m == 0) { //表示當(dāng)前c!=0一定要加上，因?yàn)?對任何數(shù)取余都為0

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

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

c = 0; //重新開始報(bào)數(shù)

}

return count;

}

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

//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 閱讀(2207) 評論(7) 編輯收藏

Comments

# re: 約瑟夫環(huán)問題求解[未登錄]
littleq
Posted @ 2008-11-20 12:30
判斷圈內(nèi)是否有人，用total這個(gè)方法，好像有點(diǎn)多余吧，你既然用for循環(huán)了，那就
if(t[i]!=0)return 1;
這樣還能少循環(huán)幾次
回復(fù) 更多評論
# re: 約瑟夫環(huán)問題求解
Bom Wu
Posted @ 2008-11-20 14:42
@littleq
對對對，不用關(guān)心還有幾個(gè)人，只要存在t[i]==1那就表示有人，不用全加起來了，多謝指教呀！回復(fù) 更多評論
# re: 約瑟夫環(huán)問題求解
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 {
    //報(bào)出了這個(gè)數(shù)的都退出
    public static int outNumber;
    //總的有多少個(gè)人
    public static int manSize;
    //上面2個(gè)一開始就固定好了，所以我就聲明成static

    //圈中的人
    private List<Man> allMan;
    //現(xiàn)在已經(jīng)報(bào)到第幾號了,初始化為1
    private int nowNumber=1;
    //現(xiàn)在已經(jīng)報(bào)到第幾個(gè)人了，初始化為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();
            //把這個(gè)人T出去
            allMan.remove(man);
            //當(dāng)T的是最后一個(gè)的時(shí)候,又從第一個(gè)開始數(shù)
            if(nowMan==allMan.size()){
                nowMan=0;
            }
            //說明T的不是最后一個(gè)
            //T的人的后面的都會往前移一個(gè)位置
            //這樣就把原來的nowman代替了,就可以從nowman開始數(shù)了
            else{

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

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

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

新用戶注冊刷新評論列表


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




網(wǎng)站導(dǎo)航: 博客園 IT新聞 Chat2DB C++博客博問管理

導(dǎo)航

常用鏈接

留言簿

隨筆分類

隨筆檔案

文章分類

文章檔案

搜索

最新評論

閱讀排行榜

評論排行榜