Question

谁来帮我用C语言写一下这个程序

Answer 1

这个是O(N)的算法（已知算法中效率最高的）：
#include <stdio.h>
#include <stdlib.h>
int main()
{
int i,m,k,ans=0;
scanf("%d%d",&m,&k);
for(i=2;i<=m;i++)
ans=(ans+k)%i;
printf("%d",ans+1);
return 0;
}

这个是O(M*N)的算法（通过链表实现）：
#include <stdio.h>
#include <stdlib.h>
struct PERSON
{
int no;
struct PERSON *next;
};
int main()
{
struct PERSON *head,*p,*t;
int i,n,m,s=1;
FILE *fin=fopen("input.txt","r");
p=head=(struct PERSON *)malloc(sizeof(struct PERSON));
scanf("%d%d",&n,&m);
for (i=s;i<n+s;i++)
{
p->next=(struct PERSON *)malloc(sizeof(struct PERSON));
p=p->next;
p->no=(i-1)%n+1;
}
p->next=head->next;
p=head;
while (p!=p->next)
{
for (i=0;i<m-1;i++)
p=p->next;
printf("%d ",p->next->no);
t=p->next;
p->next=p->next->next;
free(t);
}
printf("%d",p->no);
return 0;
}

Answer 2

这就是那个猴子选大王的程序呀，以前写过一次
这就是那个题目：
猴子选大王
[ 问题描述 ]
一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1~ m的顺序围坐一圈，
从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，
则该猴子为大王。
[ 基本要求 ]
（1）输入数据：输入m、n ，m、n 为整数，且n<m；
（2）输出形式：中文提示按照m个猴子，数n 个数的方法，输出为大王的猴子是几号。
做这个程序 你控制好循环 很简单的

Answer 3

这个就是Josephe问题
;最好使用单向循环链表来完成.
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
typedef int datatype ;
typedef struct node
{
datatype data;
struct node *next;
}nodelist,*nodelink;
nodelink add_node(int n)//创建一个没有头结点的n个结点的单向循环链表
{
nodelink head = NULL,p = NULL;
nodelink q = NULL;
int i;
for(i = 1;i <= n;i++ )
{
p = (nodelink)malloc(sizeof(nodelist));
if(NULL == p)
return NULL;
p->data = i;
if(head == NULL)
head = p;
else
q->next = p;
q = p;
}
p->next = head;
return head;
}
bool josephu(nodelink head,int k,int m)
{
int i;
nodelink q,p = head;
for(i = 1;i < k; i++)//使p只向第K个人
p = p->next;
while(p->next != p)//当p 的下一个结点为p 时循环结束
{
for(i = 1;i < m; i++)//使p只向第m个人，使q只向第m-1个人
{
q = p;
p = p->next;
}
printf("%d --> ",p->data);
q->next = p->next;//删除第M个人
free(p);
p = q->next;

}
printf("%d\n",p->data);
free(p);
return true;
}
int main(void)
{
int n,k,m;
nodelink head = NULL;
printf("intput some person n =");
scanf("%d",&n);
printf("intput for start k =");
scanf("%d",&k);
printf("intput m =");
scanf("%d",&m);
head = add_node(n);
josephu(head,k,m);
return 0;
}