注册 登录
编程论坛 数据结构与算法

猴子选大王的题,就是不知道哪里错了。。。

编程的未来 发布于 2013-03-31 19:05, 798 次点击
练习2: 1)题目描述:n只猴子要选大王,选举方法如下:所有猴子按 1,2 ……… n 编号并按照顺序围成一圈,从第 k 个猴子起,由1开始报数,报到m时,该猴子就跳出圈外,下一只猴子再次由1开始报数,如此循环,直到圈内剩下一只猴子时,这只猴子就是大王。

2)输入数据:猴子总数n,起始报数的猴子编号k,出局数字m

3)输出数据:猴子的出队序列和猴子大王的编号

#include<stdio.h>
#include<malloc.h>
#define MONKEY_NUMBER 50

typedef int datatype;
typedef struct node
{
    datatype number;
    struct node *next;
}Linklist;
Linklist *head,*s,*t,*r;
Linklist *p;

int main()
{
    void Sign_number(Linklist *,Linklist*,Linklist*);
    void Circulate_main(Linklist *,Linklist*,Linklist*);
    t = (Linklist*)malloc(sizeof(Linklist));
    head = t;
    s = (Linklist*)malloc(sizeof(Linklist));

    Sign_number(head,s,t);
    Circulate_main(head,s,t);
    return 0;
}

void Sign_number(Linklist *head,Linklist *s,Linklist *t)
{
    int i,j,k;
    for(i = 0;i < MONKEY_NUMBER;i++)
    {
        s = (Linklist*)malloc(sizeof(Linklist));
        s->number = i + 1;
        t->next = s;
        t = s;

    }

    s->next = head->next;

    s = head->next;
    for(j = 0;j < 50;j++)
    {
        printf("%2d ",s->number);
        s = s->next;
    }

}

void Circulate_main(Linklist *head,Linklist *s,Linklist *t)
{
    int i,j,k;
    s = head->next;
    t = head;

    while(s->number != s->next->number)
    {
        i = 0;
        while(i < 4-1)
        {
            p = s->next;
            t = t->next;
            s = p;
        }
        p = s->next;
        s->next = p->next;
        printf("%d",s->number);
        s = s->next;
        free(p);
            
    }

}
6 回复
#2
azzbcc2013-03-31 20:12
链表创建没问题。

输出的时候,i值不变的,那个while是个死循环

还有就是输出的应该是 p的number吧

最后的小问题就是

还剩两个结点的空间没有释放
#3
编程的未来2013-03-31 20:46
回复 2楼 azzbcc
改了还是不正确。。输出的结果不对,都是八九位数的。。
#4
azzbcc2013-03-31 21:07
找到了,那个循环里面这一句 t = t -> next 不知道是干嘛的,问题,就在这
#5
编程的未来2013-03-31 22:40
回复 4楼 azzbcc
现在改成这样,刚才的我已经完全没办法,不会搞了。。但是最后的结果很不对
#include<stdio.h>
#include<malloc.h>
#define MONKEY_NUMBER 50

typedef int datatype;
typedef struct node
{
    datatype number;
    struct node *next;
}Linklist;
Linklist *head,*s,*t,*r;
Linklist *p;

int main()
{
    void Sign_number(Linklist *,Linklist*,Linklist*);
    void Circulate_main(Linklist *,Linklist*,Linklist*);
    t = (Linklist*)malloc(sizeof(Linklist));
    head = t;
    s = (Linklist*)malloc(sizeof(Linklist));

    Sign_number(head,s,t);
    Circulate_main(head,s,t);
    return 0;
}

void Sign_number(Linklist *head,Linklist *s,Linklist *t)
{
    int i,j,k;
    for(i = 0;i < MONKEY_NUMBER;i++)
    {
        s = (Linklist*)malloc(sizeof(Linklist));
        s->number = i + 1;
        t->next = s;
        t = s;

    }

    s->next = head->next;

    s = head->next;
    for(j = 0;j < 50;j++)
    {
        printf("%2d ",s->number);
        s = s->next;
    }

}

void Circulate_main(Linklist *head,Linklist *s,Linklist *t)
{
    int i,j,k;
    s = head->next;
    while(s->next != s)
    {
        for(i = 0;i < 3;i++)
        {
            t = s;
            s = s->next;
            
            
        }
        t->next = s->next;
        printf("%2d",s->number);
        free(s);
        s = t->next;   
    }
    printf("%2d",s->number);
    getchar();
    getchar();
}
#6
azzbcc2013-03-31 23:45
我实在不明白你那个 t是做什么的

事实上我把 1楼 while循环里面填个++

再把有 t的那行代码注释掉,程序就正确了
#7
peach54602013-04-02 21:29
程序代码:
#include <iostream>
#include <vector>

int main()
{
    int n,m,k;
    std::cin >> n >> m >> k;

    std::vector<int> vec;
    vec.resize(n);
    for(int index = 0; index < n; ++index)
    {
        vec[index] = index + 1;
    }

    int num = 1;
    std::vector<int>::iterator itr = vec.begin();
    std::advance(itr, k);
    while(1 < vec.size())
    {
        itr = vec.begin();
        for( ; itr != vec.end(); ++num, ++itr)
        {
            if(num == m)
            {
                std::cout << *itr << std::endl;
                vec.erase(itr);

                num = 1;
                break;
            }
        }
    }
    std::cout << "dawang:" << vec.front() << std::endl;
}


随便写了一下...
n个猴子,k开始数,m淘汰
1