算法数据结构（一）：猴子称王

【问题描述】

任务：一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照 1--m的顺序围 坐一圈，从第1开始数，每数到第 N个，该猴子就要离开此圈，这样依次下来，直到圈中只 剩下最后一只猴子，则该猴子为大王。  输入数据：输入m,n。 m,n 为整数，n

【其他要求】

（1）变量、函数命名符合规范。

（2）注释详细：每个变量都要求有注释说明用途；函数有注释说明功能，对参数、返回值也要以注释的形式说明用途；关键的语句段要求有注释解释。

（3）程序的层次清晰，可读性强。

（4）界面美观，交互方便。

一、数据结构说明

我采用的是动态数组数据结构，利用数组删除的方法每隔n个元素就进行一次向前覆盖操作，然后将计数向前推一位后继续进行间隔能个元素的删除操作，直到只剩下了一个元素后进行输出。

可视化界面我采用的是easyx图形化界面工具。

      int *a = new int[m];//设置动态数组

      for (int i = 0; i < m; i++) {//为动态数组赋值

             a[i] = i + 1;
      }

while (true) {

           if (m == 1)//只剩下一个元素的时候退出

                  break;

           for (int i = (num - 1 + n) % m; i < m - 1; i++) {//循环删除间隔元素

                  a[i] = a[i + 1];//向前覆盖
           }

           num = (num - 1 + n) % m;

           m--;
    }
    return a[0];//返回猴子王元素

二、算法设计

                                     1、猴子称王程序流程图

　　首先先构建开始界面，进入游戏后进行m和n的输入，在转换成数字之后利用m设置动态数组，并赋值。按照间隔n进行数组元素删除，即元素前移，直到只剩下一个元素的时候设置结果界面，输出结果，程序结束。如果出现了输入错误，就会进入错误界面，退出程序。

三、详细设计

#include // 绘图库头文件，绘图语句需要
#include // 控制台输入输出头文件，getch()语句需要
#include
#include 
char s1[10], s2[10];
int a, b;

void drawmenu();
void StartGame();

//核心算法
int monkeyking(int m, int n) {
    int num = 0,i;

    //构建动态数组
    int *a = new int[m];
    for (int i = 0; i < m; i++) {
        a[i] = i + 1;
    }
    //寻找并删除元素 
    while (true) {
        if (m == 1)
            break;
        for (int i = (num - 1 + n) % m; i < m - 1; i++) {
            a[i] = a[i + 1];
        }
        num = (num - 1 + n) % m;
        m--;
    }

    return a[0];

}

//输入错误
void wrong(){
    MOUSEMSG m;
    initgraph(800, 600);
    setbkcolor(WHITE);
    cleardevice();

    IMAGE img;
    loadimage(&img, _T("C:\\Users\\Hanson\\Desktop\\Project1\\timg.jpg"));
    putimage(0, 0, &img);

    setfillcolor(DARKGRAY);
    fillrectangle(200, 200, 600, 250);

    settextstyle(42, 0, "黑体");//设置文字格式
    setbkmode(TRANSPARENT);// 去掉文字背景

    outtextxy(210, 205, "输入错误，点击返回");

    settextcolor(BLACK);
    settextstyle(75, 0, "楷体");
    outtextxy(250, 0, "猴子称王");

    while (1) {
        m = GetMouseMsg();
        if (m.x >= 200 && m.x <= 600 && m.y > 200 && m.y <= 250) {
            if (m.uMsg == WM_LBUTTONDOWN) {
                StartGame();
            }
        }
    }



}

//结果
void OverGame() {
    int c;
    char s[5];

    c = monkeyking(a, b);
    MOUSEMSG m;
    initgraph(800, 600);
    setbkcolor(WHITE);
    cleardevice();

    IMAGE img;
    loadimage(&img, _T("C:\\Users\\Hanson\\Desktop\\Project1\\timg.jpg"));
    putimage(0, 0, &img);


    setfillcolor(DARKGRAY);
    fillrectangle(200, 200, 600, 250);
    fillrectangle(200, 260, 395, 310);
    fillrectangle(405, 260, 600, 310);


    settextstyle(42, 0, "黑体");//设置文字格式
    setbkmode(TRANSPARENT);// 去掉文字背景

    itoa(c,s,10);
    outtextxy(230, 205, s);
    outtextxy(250, 205,"号猴子是猴子王");
    outtextxy(250, 265, "退出");
    outtextxy(455, 265, "返回");

    settextcolor(BLACK);
    settextstyle(75, 0, "楷体");
    outtextxy(250, 0, "猴子称王");

    while (1) {
        m = GetMouseMsg();
        if (m.x >= 200 && m.x <= 395 && m.y > 260 && m.y <= 310) {
            if (m.uMsg == WM_LBUTTONDOWN) {
                exit(0);
            }
        }

        if (m.x >= 405 && m.x <= 600 && m.y > 260 && m.y <= 310) {
            if (m.uMsg == WM_LBUTTONDOWN) {
                drawmenu();
            }
        }
    }
    getchar();
}

//开始游戏
void StartGame()
{
    MOUSEMSG m;
    initgraph(800, 600);
    setbkcolor(WHITE);
    cleardevice();

    IMAGE img;
    loadimage(&img, _T("C:\\Users\\Hanson\\Desktop\\Project1\\timg.jpg"));
    putimage(0, 0, &img);


    setfillcolor(DARKGRAY);
    //           左边1 高1 左边2 高2
    fillrectangle(300,100,500,150);
    fillrectangle(300,200,500,250);
    fillrectangle(350, 300, 450, 350);

    settextstyle(42, 0, "黑体");//设置文字格式
    setbkmode(TRANSPARENT);// 去掉文字背景

    outtextxy(315, 105, "猴子数量");
    outtextxy(315, 205, "间隔数量");
    outtextxy(355, 305, "开始");

    settextcolor(BLACK);
    settextstyle(75, 0, "楷体");
    outtextxy(250, 0, "猴子称王");
    

    while (1) {
        m = GetMouseMsg();
        if (m.x >= 300 && m.x <= 500 && m.y > 100 && m.y <= 150) {
            if (m.uMsg == WM_LBUTTONDOWN) {
                InputBox(s1,10,"请输入猴子数量","猴子数量",0);
                a = atoi(s1);
            }
        }

        if (m.x >= 350 && m.x <= 450 && m.y > 200 && m.y <= 250) {
            if (m.uMsg == WM_LBUTTONDOWN) {
                InputBox(s2,10,"请输入间隔数量","间隔数量",0);
                b = atoi(s2);
            }
        }

        if (m.x >= 350 && m.x <= 450 && m.y > 300 && m.y <= 350) {
            if (m.uMsg == WM_LBUTTONDOWN) {
                if (b >= a) {
                    wrong();
                }
                else {
                    OverGame();
                }
            }
        }
    }
    
}

//初始界面
void drawmenu() {
    MOUSEMSG m;
    initgraph(800, 600);
    setbkcolor(WHITE);
    cleardevice();

    IMAGE img;
    loadimage(&img, _T("C:\\Users\\Hanson\\Desktop\\Project1\\timg.jpg"));
    putimage(0, 0, &img);

    setfillcolor(DARKGRAY);
    fillrectangle(250, 200, 550,250);
    fillrectangle(250, 255, 550,305);

    settextstyle(42, 0, "黑体");//设置文字格式
    setbkmode(TRANSPARENT);// 去掉文字背景

    outtextxy(315, 205, "开始游戏");
    outtextxy(315, 260, "退出游戏");

    settextcolor(BLACK);
    settextstyle(75, 0, "楷体");
    outtextxy(250, 0, "猴子称王");

    while (1) {
        m = GetMouseMsg();
        if (m.x >= 250 && m.x <= 550 && m.y > 200 && m.y <= 250) {
            if (m.uMsg == WM_LBUTTONDOWN) {
                StartGame();
            }
        }

        if (m.x >= 250 && m.x <= 550 && m.y > 255 && m.y <= 305) {
            if (m.uMsg == WM_LBUTTONDOWN) {
                exit(0);
            }
        }
    }
}
int main() {
    drawmenu();
    return 0;
}

四、测试结果

五、来自2021年的评价

　　 这是我2017年第一次在具体学会了一种语言后独自从设计并编写的一个小程序（过去有合作写过其他的）。

        没有什么良好的代码格式，也没有一个良好的界面，甚至说报告写的也很不规范，但是却是令我印象深刻的一个项目，以至于我是熬夜写完了它。

 　　我第一次，完全从无到有创造了属于自己的可视化程序，尽管很烂，但是我真的获得了编写代码的快乐。

　　 思考，设计，编写，遇到调试问题，查资料，解决继续。就这么一路循环下来，我真的收获了很多。也为我以后的代码编写打下了一定的基础。