不敢死队

桃扇骨 2022-07-12 12:37 179阅读 0赞

称热打铁刚刚写完赶快就来博客上发表一下

不敢死队问题  
Time Limit: 1000MS Memory Limit: 65536KB  
Problem Description

说到“敢死队”，大家不要以为我来介绍电影了，因为数据结构里真有这么道程序设计题目，原题如下：

有M个敢死队员要炸掉敌人的一个碉堡，谁都不想去，排长决定用轮回数数的办法来决定哪个战士去执行任务。如果前一个战士没完成任务，则要再派一个战士上去。现给每个战士编一个号，大家围坐成一圈，随便从某一个战士开始计数，当数到5时，对应的战士就去执行任务，且此战士不再参加下一轮计数。如果此战士没完成任务，再从下一个战士开始数数，被数到第5时，此战士接着去执行任务。以此类推，直到任务完成为止。

这题本来就叫“敢死队”。“谁都不想去”，就这一句我觉得这个问题也只能叫“不敢死队问题”。今天大家就要完成这道不敢死队问题。我们假设排长是1号，按照上面介绍，从一号开始数，数到5的那名战士去执行任务，那么排长是第几个去执行任务的？  
Input

输入包括多试数据，每行一个整数M（0<=M<=10000)（敢死队人数），若M==0，输入结束，不做处理。

Output

输出一个整数n，代表排长是第n个去执行任务。  
Example Input

9  
6  
223  
0

Example Output

2  
6  
132

这个问题解决的思路就是判断如果是在5的倍数的时候，就要删除那个结点（因为去战场了嘛）  
如果删除的那个结点的num编号就是1的话（也就是排长的编号） 那么输出数数序号n/5  
详情参见代码注释:)

#include <stdio.h>
    #define LEN sizeof(struct node)
    
    typedef struct node
    {
        int num;
        struct node *next;
    } node;
    
    node *creat(int n)
    {
        int i;
        node *head,*tail,*p;
        head = (node*)malloc(sizeof(LEN));
        head->num = 1;
        head->next = NULL;
        tail = head;
        for(i=2; i<=n; i++)
        {
            p = (node*)malloc(sizeof(LEN));
            p->num = i;
            p->next = NULL;
            tail->next = p;
            tail = p;
        }
        tail->next = head;
        return head;
    }
    
    void bravo(node *head)
    {
        node *p,*q,*t;
        int n = 0;
        p = head;
        while(p->next!=head)
        {
            p = p->next;
        }
        while(p->next!=p)
        {
            q = p->next;//q为p的后继
            n++;
            if(n%5==0)//当数到5或5的倍数的时候 开始进入判断 如果该结点的num域是1，即排长 就打印排长应该上战场的次序
            {
                if(q->num==1)
                {
                    printf("%d\n",n/5);
                    break;
                }
                p->next = q->next;
                free(q);//因为上战场了，要把该结点删除 有两个办法 一个是free掉q 还有一个是可以让q被赋值为p的后继地址 q = p->next,如果这么做的话 else就要为 p = p->next
    //          q = p->next;
            }
            else
            {
                p = q;
    //          p = p->next;
            }
        }
        if(p->next==p)
            printf("%d\n",n/5+1);
    
    }
    
    int main()
    {
        int m;
        while(~scanf("%d",&m)&&m!=0)
        {
            node *head;
            head = creat(m);
            bravo(head);
        }
        return 0;
    }

刚刚看别人的代码发现其实可以这样  
没有必要去额外判断是不是排长刚好数到5的倍数的第一个上 直接在while（p）里面判断  
胡扯胡扯 根本不是p的问题 这个里面只要一直判断循环就行了while(250)都没问题

void bravo(node *head)
    {
        node *p,*q,*t;
        int n = 0;
        p = head;
        while(p->next!=head)
        {
            p = p->next;
        }
        while(p)
        {
            q = p->next;//q为p的后继
            n++;
            if(n%5==0)//当数到5或5的倍数的时候 开始进入判断 如果该结点的num域是1，即排长 就打印排长应该上战场的次序
            {
                if(q->num==1)
                {
                    printf("%d\n",n/5);
                    break;
                }
                p->next = q->next;
                free(q);//因为上战场了，要把该结点删除 有两个办法 一个是free掉q 还有一个是可以让q被赋值为p的后继地址 q = p->next,如果这么做的话 else就要为 p = p->next
    //          q = p->next;
            }
            else
            {
                p = q;
    //          p = p->next;
            }
        }
    //    if(p->next==p)
    //        printf("%d\n",n/5+1);
    
    }

今天学到的很重要的方法就是，如果你在链表中总是出现问题，最好把链表打印出来，看看到底是哪里出了问题，这样比自己费脑筋去想快得多！