啊哈算法原书有一个题叫小猫钓鱼(有的地方叫拖拉机?)

原书中的代码有问题,作者收牌时没有将相同的牌一起收进去

在这里写了个正确的代码

#include<iostream>
#define MAXQ 1001
#define MAXS 11
#define MAXB 11
using namespace std;
​
struct queue
{
    int data[MAXQ];
    int head;
    int tail;
};
struct stack
{
    int data[MAXS];
    int top;
};
​
struct queue q1, q2;
struct stack s;
int n;                              //the number of the cards
int cur;                            //current card
int book[MAXB];                     //mark if some certain card has been existed
​
int main()
{
    q1.head = 1, q1.tail = 1;
    q2.head = 1, q2.tail = 1;
    s.top = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)    //input Shaun's cards
        cin >> q1.data[q1.tail++];
    for (int i = 1; i <= n; i++)    //input Shaw's cards
        cin >> q2.data[q2.tail++];
    while (q1.head < q1.tail && q2.head < q2.tail)
    {
        cur = q1.data[q1.head];
        if (book[cur] == 0)
        {
            q1.head++;
            s.data[++s.top] = cur;
            book[cur] = 1;
        }
        else
        {
            q1.head++;
            q1.data[q1.tail++] = cur;
            while (s.data[s.top] != cur)
            {
                book[s.data[s.top]] = 0;
                q1.data[q1.tail] = s.data[s.top];
                q1.tail++;
                s.top--;
            }
            book[cur] = 0;
            q1.data[q1.tail] = cur;
            q1.tail++;
            s.top--;
        }
        cur = q2.data[q2.head];
        if (book[cur] == 0)
        {
            q2.head++;
            s.data[++s.top] = cur;
            book[cur] = 1;
        }
        else
        {
            q2.head++;
            q2.data[q2.tail++] = cur;
            while (s.data[s.top] != cur)
            {
                book[s.data[s.top]] = 0;
                q2.data[q2.tail] = s.data[s.top];
                q2.tail++;
                s.top--;
            }
            book[cur] = 0;
            q2.data[q2.tail] = cur;
            q2.tail++;
            s.top--;
        }
    }
    if (q1.head == q1.tail)
    {
        cout << "Shaw won!" << endl;
        cout << "Shaw's cards are as follows:";
        for (int i = q2.head; i < q2.tail; i++)
            cout << q2.data[i] << " ";
        cout << endl;
        if (s.top > 0)
        {
            cout << "Cards left on the table are as follow:";
            for (int i = 1; i < s.top; i++)
                cout << s.data[i] << " ";
        }
        else
            cout << "There are no cards left on the table!";
    }
    else
    {
        cout << "Shaun won!" << endl;
        cout << "Shaun's cards are as follows:";
        for (int i = q1.head; i < q1.tail; i++)
            cout << q1.data[i] << " ";
        cout << endl;
        if (s.top > 0)
        {
            cout << "Cards left on the table are as follow:";
            for (int i = 1; i <= s.top; i++)
                cout << s.data[i] << " ";
        }
        else
            cout << "There are no cards left on the table!";
    }
    cout << endl << endl;
    return 0;
}
/*
6
2 4 1 2 5 6
3 1 3 5 6 4
​
3
1 2 3
3 2 1
​
3
1 2 1
4 5 6
*/
​

这道题调了很久很久 为什么呢?

忘记了栈的变化和book的变化要时刻保持一致!栈一旦变化标记也要改变

很久没做题了,意识都淡薄了,以后要注意!

附上HarryShaunWang 在火车上口述”一遍过“的代码:

#include<iostream>
#define MAXN 1000
using namespace std;
int n;
int a[MAXN], b[MAXN], c[MAXN];
bool vis[MAXN];
int la, lb, lc;
int ha, hb;
​
int main()
{
    cin >> n;
    ha = 1, hb = 1;
    la = n, lb = n;
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    while (ha <= la && hb <= lb)
    {
        int x = a[ha];
        if (vis[c[++lc] = a[ha++]])
        {
            do
            {
                vis[a[++la] = c[lc--]] = 0;
            }
            while (c[lc] != x);
            a[++la] = c[lc--];
            vis[x] = 0;
        }
        else
            vis[x] = 1;
        int y = b[hb];
        if (vis[c[++lc] = b[hb++]])
        {
            do
            {
                vis[b[++lb] = c[lc--]] = 0;
            }
            while (c[lc] != y);
            b[++lb] = c[lc--];
            vis[y] = 0;
        }
        else
            vis[y] = 1;
    }
    if (ha > la)
    {
        cout << "Shaw won!" << endl;
        for (int i = hb; i <= lb; i++)
            cout << b[i] << " ";
        cout << endl;
        cout << "Card left on table are:";
        for (int i = 1; i <= lc; i++)
            cout << c[i] << " ";
    }
    else
    {
        cout << "Shaun won!" << endl;
        for (int i = ha; i <= la; i++)
            cout << a[i] << " ";
        cout << endl;
        cout << "Card left on table are:";
        for (int i = 1; i <= lc; i++)
            cout << c[i] << " ";
    }
}
​
分类: c/c++

发表评论

电子邮件地址不会被公开。 必填项已用*标注