DS实验题击鼓传花

题目：

代码1(数组实现)：

//

//  main.cpp

//  DS-击鼓传花

//

//  Created by wasdns on 16/11/9.

//  Copyright © 2016年 wasdns. All rights reserved.

//

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <string.h>

#include <string>

using namespace std;

int killman[1000];  //killer and alive man

int main()

{

    int n, m;

    cin >> n >> m;

    memset(killman, 0, sizeof(killman));

    int killt = 1;                  //死亡情况，如果killt=总人数，结束游戏

    killman[1] = -1;                //第一位发言差，根据题目要求首杀

    int rcd = 1, turn = 1;          //rcd记录存活者，turn为指针

    int cnt = 0;                    //cnt计数器，一旦为m，杀掉此时指针指向者

    while (1)

    {

        if (turn > n) {             //指针越界

            turn %= n;

        }

        if (killman[turn] == -1) {  //此时指向的人已经死亡

            turn++;

            continue;

        }

        cnt++;                      //指向的人还活着，更新计数器

        if (cnt == m) {             //计数器计数为m，同时指针指向的人还活着

            killman[turn] = -1;     //杀死

            killt++;                //总死亡人数加一

            rcd = turn;             //rcd记录截止目前最后一位阵亡的同学

            cnt = 0;                //计数器置0

            if (killt == n) break;  //游戏结束

        }

        turn++;                     //游戏还没有结束，指针后移

    }

    cout << rcd << endl;            //最后一位同学假死，存活

    return 0;

}

结果：

代码2(指针实现)：

//

//  main2.cpp

//  DS-击鼓传花

//

//  Created by wasdns on 16/11/9.

//  Copyright © 2016年 wasdns. All rights reserved.

//

#include <cstdio>

#include <string.h>

#include <iostream>

#include <algorithm>

#include <string>

using namespace std;

struct killman {

    int num;

    killman *next;

};

/*

 建立循环链表：

 */

killman* CreatCircle(int n) {

    killman *k;

    k = new killman;

    k -> next = NULL;

    k -> num = 1;

    killman *p1, *p2;

    p1 = p2 = k;

    for (int i = 2; i <= n; i++)

    {

        p1 = new killman;

        p1 -> next = NULL;

        p1 -> num = i;

        p2 -> next = p1;

        p2 = p1;

    }

    p1 -> next = k;

    return k;

}

/*

 根据题目要求，找到开始节点的前一个节点。

 目的是为了删除第一个节点。

 */

killman* FindKpre(killman *k)

{

    killman *p;

    p = k;

    while (p -> next != k) {

        p = p -> next;

    }

    return p;

}

/*

 杀人游戏主体：

 */

int killgame(killman *k, int m)

{

    int cnt = m;                        //计数器cnt，根据题目要求，初始置m

    killman *p1, *p2;                   //p1 为指向当前节点的指针；

                                        //p2 为指向前一个节点的指针。

    p1 = k;

    p2 = FindKpre(k);                   //找到开始节点的前一个节点，进行删除操作

    while (1)

    {

        if (cnt == m) {                 //计数器达到阈值时，删除当前节点

            p1 = p1 -> next;

            p2 -> next = p1;

            cnt = 1;                    //注意：删除之后，本质上进行了前移；

                                        //计数器置1.

            continue;

        }

        if (p2 -> next == p2) break;    //当出现回环(loop)的时候：

                                        //说明只剩下当前节点，游戏结束。

        cnt++;                          //计数器尚未溢出，指针前移，更新计数器。

        p2 -> next = p1;

        p2 = p1;

        p1 = p1 -> next;

    }

    return p1 -> num;                   //返回游戏的赢家

}

/*

 Debug，输出环形链表：

 */

void KPrint(killman *k) {

    killman *p;

    p = k -> next;

    while (p != k) {

        cout << "p " << p -> num << endl;

        p = p -> next;

    }

}

int main()

{

    int n, m;

    cin >> n >> m;

    killman *k;

    k = CreatCircle(n);

    //KPrint(k);

    int rcd = 1;

    rcd = killgame(k, m);

    cout << rcd << endl;

    return 0;

}

结果：

小结：

此题是经典的约瑟夫问题，采用ADT表，有两种实现方法：(1)指针实现 (2)数组实现。

需要注意的点是：

题目把第一个人直接出局
计数器和指针更新时的位置(更新指针之后马上更新计数器！)
循环结束条件

可以看到，使用环形链表的性能更优，但是实现相比数组而言更加复杂。

2016/11/9

巴特西

DS实验题击鼓传花

题目：

代码1(数组实现)：

代码2(指针实现)：

小结：

最新文章

热门文章

巴特西

DS实验题 击鼓传花

题目：

代码1(数组实现)：

代码2(指针实现)：

小结：

最新文章

热门文章

DS实验题击鼓传花