卡片游戏_算法

问题描述：

　　桌上有一叠牌，从第一张牌（即位于顶面的牌）开始从上往下依次编号为1~n。当至少还剩两张牌时进行一下操作：把第一张牌扔掉，然后把新的第一张牌放到整叠牌的最后。输入n，输出每次扔掉的牌，以及最后剩下的牌。

　　样例输入：7

　　样例输出：1 3 5 7 4 2 6

【分析】

　　显然这是关于队列的应用，复习并采用了课本的循环队列。代码如下：

 1   #include<iostream>
 2   using namespace std;
 3   const int QueueSize=100;
 4   template<class T>
 5   class CircleQueue
 6   {
 7   public:
 8       CircleQueue(){front=rear=0;}
 9       void EnQueue(T x);
10      T DeQueue();
11      T GetFront();
12      int GetLength();
13      bool Empty(){return front==rear?true:false;}
14  private:    
15      int data[QueueSize];
16      int front;
17      int rear;
18  };
19  template<class T>
20  void CircleQueue<T>::EnQueue(T x)
21  {
22      if((rear+1)%QueueSize==front)    throw"overflow";
23      rear=(rear+1)%QueueSize;
24      data[rear]=x;
25  }
26  template<class T>
27  T CircleQueue<T>::DeQueue()
28  {
29      if(rear==front)    throw"underflow";
30      front=(front+1)%QueueSize;
31      return data[front];
32  }
33  template<class T>
34  T CircleQueue<T>::GetFront()
35  {
36      if(rear==front)    throw"underflow";
37      return data[(front+1)%QueueSize];
38  }
39  template<class T>
40  int CircleQueue<T>::GetLength()
41  {
42      return (rear-front+QueueSize)%QueueSize;
43  }
44  int main()
45  {
46      CircleQueue<int> a;
47      int m;
48      cin>>m;                                //输入牌的张数
49      for(int i=0;i<m;i++)               　　 //依次入队
50      {
51          a.EnQueue(i+1);
52      }
53      while(a.GetLength()>=2)                //关键算法
54      {
55          int temp=a.DeQueue();
56          cout<<temp<<" ";
57          int temp2=a.DeQueue();
58          a.EnQueue(temp2);
59      }
60      cout<<a.GetFront();
61  }

C++提供了一种更加简单的处理方式——STL队列。代码如下：

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 queue<int> q;
 5 int main()
 6 {
 7     int n;
 8     cin>>n;
 9     for(int i=0;i<n;i++)
10         q.push(i+1);
11     while(!q.empty())
12     {
13         cout<<q.front();
14         q.pop();
15         if(q.empty())    break;            //这句代码书上没有，会导致最后出队越界访问
16         q.push(q.front());
17         q.pop();
18     }
19     return 0;
20 }

也可以用数组来模拟队列，代码如下：

 1 #include<iostream>
 2 using namespace std;
 3 const int MAXN=50;
 4 int queue[MAXN];
 5 void main()
 6 {
 7     int n,front,rear;
 8     cin>>n;
 9     for(int i=0;i<n;i++)
10         queue[i]=i+1;                    //下标从0到n-1
11     front=0;
12     rear=n;
13     while(front<rear)
14     {
15         cout<<queue[front++];            //front后移，模拟出队过程
16         queue[rear++]=queue[front++];    //同时实现模拟入队、出队过程
17     }
18 }

【总结】

　　显然使用STL的代码更简洁，且不用事先知道n的大小。