代码之家  ›  专栏  ›  技术社区  ›  John Carter

测试扑克手直抽(4比1)的算法?

  •  9
  • John Carter  · 技术社区  · 15 年前

    我正在痛苦地写一个扑克评估库的乐趣,并希望添加的能力,以测试抽奖(开放式,Gutshot)为一套给定的卡。

    只是想知道“最先进”是什么?我试图保持我的记忆足迹合理,所以使用查找表的想法不太好,但可能是一个必要的邪恶。

    我目前的计划是:

    • 从集合中所有牌的等级中减去最低等级。
    • 查看某个序列,即:0、1、2、3或1、2、3、4(对于OEDS)是否是修改后的集合的子集。

    我希望在复杂性方面做得更好,因为使用我的方法,7张牌或9张牌组会把事情搞得一团糟。

    如有任何意见和/或更好的想法,我们将不胜感激。

    4 回复  |  直到 15 年前
        1
  •  7
  •   supercat    15 年前

        2
  •  7
  •   Timo    15 年前




    #include <iostream>
    #include <vector>
    #include <hash_map>
    #include <numeric>
    using namespace std;
    
    const int MAXCARDS = 9;
    stdext::hash_map<long long, bool> lookup;
    
    //"Hash function" that is unique for a each set of card ranks, and also
    //symmetric so that the order of cards doesn't matter.
    long long hash(const vector<int>& cards)
    {
        static const int primes[52] = {
            2,3,5,7,11,13,17,19,23,29,31,37,41,
            2,3,5,7,11,13,17,19,23,29,31,37,41,
            2,3,5,7,11,13,17,19,23,29,31,37,41,
            2,3,5,7,11,13,17,19,23,29,31,37,41
        };
    
        long long res=1;
        for(vector<int>::const_iterator i=cards.begin();i!=cards.end();i++)
            res *= primes[*i];
        return res;
    }
    
    //Tests whether there is a straight draw (assuming there is no
    //straight). Only used for filling the lookup table.
    bool is_draw_slow(const vector<int>& cards)
    {
        int ranks[14];
        memset(ranks,0,14*sizeof(int));
    
        for(vector<int>::const_iterator i=cards.begin();i!=cards.end();i++)
            ranks[ *i % 13 + 1 ] = 1;
        ranks[0]=ranks[13]; //ace counts also as 1
    
        int count = ranks[0]+ranks[1]+ranks[2]+ranks[3];
        for(int i=0; i<=9; i++) {
            count += ranks[i+4];
            if(count==4)
                return true;
            count -= ranks[i];
        }
    
        return false;
    };
    
    void create_lookup_helper(vector<int>& cards, int idx)
    {
        for(;cards[idx]<13;cards[idx]++) {
            if(idx==cards.size()-1)
                lookup[hash(cards)] = is_draw_slow(cards);
            else {
                cards[idx+1] = cards[idx];
                create_lookup_helper(cards,idx+1);
            }
        }
    }
    
    void create_lookup()
    {
        for(int i=1;i<=MAXCARDS;i++) {
            vector<int> cards(i);
            create_lookup_helper(cards,0);
        }
    }
    
    //Test for a draw using the lookup table
    bool is_draw(const vector<int>& cards)
    {
        return lookup[hash(cards)];
    };
    
    int main(int argc, char* argv[])
    {
        create_lookup();
    
        cout<<lookup.size()<<endl; //497419
    
        int cards1[] = {1,2,3,4};
        int cards2[] = {0,1,2,7,12};
        int cards3[] = {3,16,29,42,4,17,30,43};
    
        cout << is_draw(vector<int>(cards1,cards1+4)) <<endl; //true
        cout << is_draw(vector<int>(cards2,cards2+5)) <<endl; //true
        cout << is_draw(vector<int>(cards3,cards3+8)) <<endl; //false
    
    }
    
        3
  •  3
  •   chillysapien    15 年前

        4
  •  0
  •   nonopolarity    15 年前

    A 1 J Q

    loop through 1 to 13 as i
      if my cards already has this card i, then don't worry about this case, skip to next card
      for this card i, look to the left for number of consecutive cards there is
      same as above, but look to the right
      if count_left_consecutive + count_right_consecutive == 4, then found case
    

    K