猴子选大王

题目描述
一群猴子要选新猴王。新猴王的选择方法是：让N只候选猴子围成一圈，从某位置起顺序编号为1~N号。从第1号开始报数，每轮从1报到3，凡报到3的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

输入描述
输入在一行中给一个正整数N（≤1000）。

输出描述
在一行中输出当选猴王的编号。

输入样例

11

输出样例

7

Yizuodi的答案1

//别问为什么 反正答案就是对
#include <iostream>
using namespace std;

int main()
{
    int n,i,s=0;
    cin>>n;
    for(i=2 ; i<=n ; i++)
    s = (s+3) % i ;
    ++s;
    cout<<s;
}

zhc的低级代码，数组版

//低级代码
#include<iostream>
using namespace std ;
int main(){
    int N;
    cin >> N ;
    int A[N+1];
    for(int i = 0 ; i < N+1 ; ++i){
        A[i+1] = i+1 ;
    }
    int j=1;
    for(int i = 0 ; i < N-1 ; ++i){
        int t = 0;
        while(t!=2){
            if(A[j]!=0) ++t ; 
            ++j;
            if(j>N) j=1;
        }
        while(A[j]==0){
            ++j;
            if(j>N) j=1;
        }   
        A[j]=0;
        ++j;
        if(j>N) j=1;
    }
    for(int i = 0 ; i < N ;++i){
        if(A[i+1]!=0) cout<<i+1 ;
    }
}

Yizuodi的答案

#include <iostream>
using namespace std;

struct Node
{
    int data;
    Node *next;
};

Node *NewNode(int data)
{
    Node *tmp = (Node *)malloc(sizeof(Node));
    tmp->next = NULL;
    tmp->data = data;
    return tmp;
}

int Monkey(int n)
{
    Node *List = NewNode(0);
    Node *temp = List;
    for (int i = 1; i <= n; i++)
    {
        List->next = NewNode(i);
        List = List->next;
    }
    List->next = temp->next;
    List = temp->next; //以上代码生成了一个循环列表

    int k = 1; //单向链表，仅能删除下一个node
    while (List->next != List)
    {
        k++;
        if (k == 3) //删除下一个node
        {
            Node *next = List->next->next;
            free(List->next);
            List->next = next;
            List = List->next;
            k = 1;
        }
        else
        {
            List = List->next;
        }
    }
    return List->data;
}

int main()
{
    int n;
    cin >> n;
    cout << Monkey(n);
}

zhc的循环链表版：

//猴子选大王
#include<iostream>
using namespace std ;
struct Node{
    int data;
    Node *next;
};
class linkedlist{
private:
    Node * tail ;//尾指针 tail->next=head_node头节点;
    int len;
public:
    linkedlist(): tail(0),len(0) {}
    ~linkedlist(){
        while(len>1){
           Delete3th(tail->next) ; 
        } //最终只剩下tail->next
        delete tail->next ;
    }
    void addlast(int e){//往链表尾添加元素并实现循环链表
        Node* node = new Node() ;
        node->data = e ; 
        if(len==0){ //链表为空时添加元素
            node->next = node ;//实现循环链表
        }
        else{ 
        node->next = tail->next ;
        tail->next = node ;
        }
       tail = node ; //使tail始终为尾指针
          ++len;
    }
    void Delete3th(Node *&p){ 
        if(len>1){//删除p节点往后数的第3个节点p3并令p=p4
            p=p->next; //p从p1到p2
            Node* p2 = p ;//记录p2
            p=p->next;//此时p为p3，要删除
            Node * temp = p;
            p2->next = p->next ;  //使p2->next = p4 
            p=p->next;   // 令p = p4 ，p4即为下一轮的p1 
            delete temp ;//删除p3
            --len ;
        }
    }
    Node * getlast(){ //返回尾指针
        return  tail ;
    }
};
int main(){
    int N;
    cin >> N ;
    linkedlist Monkey;
    for(int i = 0 ; i < N  ; ++i){
        Monkey.addlast(i+1);
    }
    Node *p= Monkey.getlast()->next;//此时p为头节点
    for(int i = 0 ; i < N-1 ;++i){//删除N-1个节点，剩下的这个节点即为猴王
        Monkey.Delete3th( p );
    }
    cout<<p->data;
}