huan.c

c语言一些基础编码

 /* 约瑟夫环的程序设计 */





#include <stdio.h>
#include <conio.h>

#include <stdlib.h>
#include <malloc.h>


#define Null 0


typedef struct tagnode
 {
  int num;
  struct tagnode *next;
 } LinkList;

LinkList *creat(int n);
LinkList *select(LinkList *head,int m);
LinkList *head=Null,*last;

int main()
{
 int n,m;
 printf("\nInput the total number of people:\n");
 scanf("%d",&n);
 printf("\ninput the number of person you are to call:\n");
 scanf("%d",&m);
 head=creat(n);
 last=select(head,m);
 n=last->num;
 printf("the last one:%d\n",n);
 free(last);
 printf("\nPress any key to continue...\n");
 getch();
 return (1);
} /* main */


void Josephas(int n,int m,int s)
{
 int *R,i,j;
 R=(int *)malloc(n*sizeof(int));
 for(i=1;i<=n;i++)
  R[i]=i;
 for(i=n;i>=2;i--)
 {
   s=(s+m-1) % i;
   if(s==0) s=i;
   printf("%d",R[s]);
   for(j=s+1;j<=i;j++)
    R[j-1]=R[j];
 }
 printf("%d\n",R[1]);
} /* Johephas */

/*

int main()
{
 printf("Johephas problem\n");
 scanf("%d,%d,%d",n,m,s);
 Josephas(n,m,s);
}
*/

/* main */

LinkList *select(LinkList *head,int m)
{
 LinkList *p,*q;
 int i,t,flag=0;
 p=head;
 t=1;
 q=p;  /* q--前趋指针, p--当前指针 */
 do
 {
  p=q->next;
  t=t+1;
  if(t%m==0)/* 报数到 */
  {
    printf("%4d\t",p->num);
    if(q->next==q) { flag=1;break;}
    q->next=p->next;
    free(p);
    p=q;
  }
  else q=p;
 } while((q==p)||(flag==0));
 head=p;
 return (head);
}/* Select */

LinkList *creat(int n)
{
 /* 使 n 个人围成一圈，并给每个人标识号数 */
 LinkList *head,*s, *p;
 int i;
 s=(LinkList *)malloc(sizeof(LinkList));
 head=s;
 s->num=1;
 p=s;
 for(i=2;i<=n;i++)
 {
  s=(LinkList *)malloc(sizeof(LinkList));
  s->num=i;
  p->next=s;
  p=s;
 }
 p->next=head;
 return (head);
}/*  creat  */