2

AP コンピューター サイエンス コースで、数日以内に次の課題を提出する必要があります。

「この課題では、ブルガリアン ソリティアのゲームをモデル化します。ゲームは 45 枚のカードから始まります。それらをランダムなサイズのいくつかの山にランダムに分割します。たとえば、サイズ 20、5、1、9、と 10. 各ラウンドで、各パイルから 1 枚のカードを取り、これらのカードで新しいパイルを形成します. たとえば、サンプルの開始構成は、サイズ 19、4、8、10、および 5 のパイルに変換されます. ソリティアは次のとおりです.パイルのサイズが 1、2、3、4、5、6、7、8、および 9 の場合は、ある順序でオーバーします。

プログラムで、ランダムな開始構成を作成して出力します。次に、ソリティア ステップを適用し続け、結果を出力します。ソリティアの最終構成に達したら停止してください。」

これを解決するプログラムを思いつきましたが、問題は非常に長い時間がかかることです。それ以外の場合は、予想どおりほぼ瞬時に解決されますが、18,000 回以上の反復が可能な場合もあります。

http://mancala.wikia.com/wiki/Bulgarian_Solitaireによると、解は (k^2)-k ステップ以下で見つけることができます。この場合、k は 9 です。多くの場合、72 ステップ以下で解決策を見つけることはできません。私はこのプログラムを何時間も見て、高速化できるかどうかを確認するためにさまざまなことをいじりましたが、十分な回数の反復で動作させることができません。だから今、スタック オーバーフローに来て、誰かが私を正しい方向に押し進めるのを手伝ってくれるかどうかを確認しました。

これが私のコードです：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Random;

public class BulgarianSolitaire {

    ArrayList<Integer> cards = new ArrayList<Integer>();
    Random rand = new Random();
    boolean cont = true;
    boolean cont2 = true;

    public static void main(String[] args) {
        BulgarianSolitaire game = new BulgarianSolitaire();
    }

    public BulgarianSolitaire() {
        System.out.println("Started");
        int sum = 0;
        while (cont) {
            if (sum < 45) {
                cards.add(rand.nextInt(46 - sum));
            } else {
                cont = false;
            }

            sum = 0;
            for (int i = 0; i < cards.size(); i++) {
                sum += cards.get(i);
            }

            removeZeros(cards);

            System.out.println(cards);
        }

        System.out.println("Finished Generating Start");

        while (cont2) {
            solitaireStep();
            System.out.println(cards);
            if (checkCards()) {
                cont2 = false;
            }
        }

        Collections.sort(cards);
        System.out.println("Cards are sorted");
        System.out.println(cards);
    }

    public void removeZeros(ArrayList<Integer> list) {
        for (int j = 0; j < list.size(); j++) {
            if (list.get(j) == 0) {
                list.remove(j);
            }
        }
    }

    public void solitaireStep() {

        int numberRemoved = 0;

        for (int i = 0; i < cards.size(); i++) {
            int value = cards.get(i);
            cards.set(i, value - 1);
            removeZeros(cards);
            numberRemoved++;
        }

        cards.add(numberRemoved);
    }

    public boolean checkCards() {
        ArrayList<Integer> expectedCards = new ArrayList<Integer>();

        for (int i = 1; i < 10; i++) {
            expectedCards.add(i);
        }

        ArrayList<Integer> sortedCards = cards;
        Collections.sort(sortedCards);
        boolean equal = true;
        if (sortedCards.size() != expectedCards.size()) {
            equal = false;
        }

        for (int i = 0; i < sortedCards.size(); i++) {
            if (sortedCards.size() == expectedCards.size()) {
                if (sortedCards.get(i) != expectedCards.get(i)) {
                    equal = false;
                }
            }
        }

        return equal;
    }
}

だから私は基本的に 0 から 45 の間の乱数を生成することから始めて、それをカードのリストに追加します。次に、乱数の生成を続け、合計が 45 未満である限り、生成された乱数が 0 から 45 (最後の反復での数値の合計) になるように、乱数を生成してリストに追加します。リスト内のゼロも同様に削除されます。

リストが生成されると、リスト内のすべての数値から 1 を減算し、ゼロを削除して、減少したスタックの数に等しい新しい値を追加するステップが実行されます。また、リスト {1, 2, 3, 4, 5, 6, 7, 8, 9} に対してカード スタックの順序付けられたバージョンをチェックし、一致が見つかると、ブール値の cont2 を false に設定して、そのソリティアステップの実行を停止します。

それはそれについてです。助けてくれる人に感謝します。

4

3 に答える 3

2

あなたの欠点はあなたのremoveZeros方法にあります。

public void removeZeros(ArrayList<Integer> list) {
    for (int j = 0; j < list.size(); j++) {
        if (list.get(j) == 0) {
            list.remove(j);
        }
    }
}

の要素を削除するとj、リストのサイズが 1 減少します。 も減少する必要がjあります。

これを変更します：

  public void removeZeros(ArrayList<Integer> list) {
        for (int j = 0; j < list.size(); j++) {
            if (list.get(j) == 0) {
                list.remove(j);
                j--;
            }
        }
    }

あなたのチェック方法も非常に複雑です。

ソリティアのステップで、ゼロに等しくなければならないすべての値をゼロに設定します。

次に、 loop の外側のゼロを (改訂された方法で) 削除します。

次に、配列をソートします。

次に、配列がソートされているため、チェックメソッドで：

public boolean checkCards() {
    for(int i = 0; i < cards.size(); i++) {
        if(cards.get(i) != i + 1) {
            return false;
        }
    }
    return true;
}

はるかに簡単です。そして、それは機能します。

于 2012-10-25T01:59:43.660 に答える
0 
    package learningofAlgorithm;
    import java.util.ArrayList;
    import java.util.Random;
    import java.util.Collections;
    public class bulgarianSolitaire {
    private Random gen;
    private int i=1;
    ArrayList<Integer> bs=new ArrayList<>();


    public bulgarianSolitaire(){
       /**gen=new Random();
       bs.add(gen.nextInt(45)+1);
       int sum=bs.get(0);
       while(sum!=45){
            bs.add(gen.nextInt(45-sum)+1);
            sum=sum+bs.get(i);
            i++;

        }*/
        bs.add(20);
        bs.add(5);
        bs.add(1);
        bs.add(9);
        bs.add(10);
    }

    public void dis(){
        for(Integer element:bs){
            System.out.print(element+" ");
        }
    }


    public void removeCard(ArrayList<Integer> s){
         int i=0;
        while(i<s.size()){
            if(s.get(i)==0){
                s.remove(i);
            }
             else{
                i++;
            }
        }

    }


     public void bsstep(){
         int newheap=0;
         for(int i=0;i<bs.size();i++){
             int key=bs.get(i);
                 bs.set(i, key-1);

             newheap++;

         }
        removeCard(bs);

         bs.add(newheap);   
    }


    public boolean checkCard()
    {   ArrayList<Integer> bscheck=new ArrayList<>();
        for(int i=1;i<10;i++){
        bscheck.add(i);
          }
        boolean flag=true;
        ArrayList<Integer> sortbs=bs;
        Collections.sort(sortbs);
        if(bscheck.size()!=sortbs.size()){
            flag=false;
        }

     for(int i=0;i<bscheck.size();i++){
         if(bscheck.size()==sortbs.size()){
              if(bscheck.get(i)!=sortbs.get(i)){
                  flag=false;
              }
          }
        }
        return flag;

    }


    }
于 2015-09-24T15:58:07.800 に答える
0

上記のコードを試しましたが、うまくいきませんでした。私は新しいものをコーディングし、それは動作します:

import java.util.ArrayList;
import java.util.Collections;


public class P74_BulgarianSolitaire {

public static void main(String[] args) {
    // TODO Auto-generated method stub
    final int MAX_CARD = 45; 
    ArrayList<ArrayList<Integer>> twoDArrayList =  new ArrayList<ArrayList<Integer>>();

    int column = 1; 
    int card = 0;
    int left = MAX_CARD;


    do{ 
        column = (int) (Math.random()*(left)+1);  // 
        System.out.println("Column :"+column);

        ArrayList<Integer> row = new ArrayList<Integer>(); //New row to add. Must declare here. 
        for (int j=0;j<column;j++){
            card++;

            row.add(card);
        }

        twoDArrayList.add(row);

        left = MAX_CARD - card ;


    } while (card <MAX_CARD);
    System.out.println(twoDArrayList);
    System.out.println();

    boolean finish = false;

    while (!finish){
        ArrayList<Integer> row = new ArrayList<Integer>(); //New row

        //remove one card from each row
        for (int i=0;i<twoDArrayList.size();i++){
            row.add(twoDArrayList.get(i).get(0));
            twoDArrayList.get(i).remove(0);  //Remove the first column 
            if (twoDArrayList.get(i).isEmpty()){
                twoDArrayList.remove(twoDArrayList.get(i)); 
                i--;
            }
        }

        twoDArrayList.add(row);

        ArrayList<Integer> size = new ArrayList<Integer>(); // New list
        for (int i=0;i<twoDArrayList.size();i++){
            size.add(twoDArrayList.get(i).size());
        }
        Collections.sort(size);

        for (int i=1;i<size.size();i++){
            if (size.get(i)== size.get(i-1)+1 ) finish = true; 
            else {
                finish = false;
                break;
            }
        }

        for (int i=0;i<twoDArrayList.size();i++) Collections.sort(twoDArrayList.get(i));
        System.out.println(twoDArrayList);
    }
    System.out.println(twoDArrayList);

}

}
于 2013-12-30T17:10:06.530 に答える