Chinaunix首页 | 论坛 | 博客
  • 博客访问: 359889
  • 博文数量: 53
  • 博客积分: 139
  • 博客等级: 入伍新兵
  • 技术积分: 589
  • 用 户 组: 普通用户
  • 注册时间: 2012-12-27 01:55
个人简介

学习linux,学习编程。

文章分类

全部博文(53)

文章存档

2019年(1)

2018年(4)

2016年(4)

2014年(11)

2013年(33)

分类: C/C++

2013-11-25 23:13:22

/* C程序设计教程(等2版)谭浩强著, 习题7.5和习题8.6类似,其中习题8.6要求使用链表来实现。
7.5 有n个人围成一圈,顺序排号。从第一个人开始报数(从1到3报数),凡报到3的人退出圈子,
问最后留下的是原来等几号的那位。

Input a number of people to n, and n is between 1 and 1000. Use an array[n], let array[i]=1. If a
person quit, a corresponding array element becomes '-1'. Use k to count the numbers of array[n]
that are equal '1'. At first m=0, after a cycle, let m=(k+m)%3. When array[i]==1 && (k+m)%3==0,
let array[i]='-1'. At end of a cycle, j is equal reserved people. When j==1, exit cycle.*/

#include

int main()
{ int remove_from_circle (int n);
  int i,k;
  printf ("Please input a integer number of people between 1 and 1000: \n");
  scanf ("%d", &k);
  if (k<1 || k >1000) printf ("The input number is not right.\n");
  else { i=remove_from_circle (k);
  printf ("The number of last reserve person is: %d .\n",i);
  }
  return 0;
}

int remove_from_circle (int n)
{ int i,j=n,k=n,m=0,x=0,array[1000];
  if (n<1 || n>1000) return (-1);
  for (i=0; i   while (j!=1)
  { j=0;k=0;
    for (i=0; i     { if (array[i]==1)
      { ++j;++k;
      if ((k+m)%3==0) { array[i]=-1; --j; }
      else x=i;
      }
    }  
  m=(k+m)%3;
  }
  return (x+1);
}

============================================================

/* 习题8.6 13个人围成一个圈,从等1个人开始报号1,2,3。凡是报到3者退出圈子。找出最后留在圈中的人的序号。要求用链表实现。
在这里使用了循环链表,编程的时候会方便一些。
reserved in circle, using a cycle chain table. It's easy and useable.
the "creat ()" function can creat a cycle chain table, and the "reserved_in_circle  ()" function can remove people, and find the last reserved person. */

#include
#include
#define LEN sizeof (struct person)
struct person
{ int num;
  struct person * next;
};

int main ()
{ struct person * creat (int n);
  int reserved_in_circle (struct person * head);
  struct person * head;
  int i,n=13;
  head=creat(n);            //调用creat函数,返回第1个结点的起始地址
  i=reserved_in_circle (head);
  printf ("The number of the reserved person is %d.\n",i);
  return 0;
}

struct person * creat (int n)    //建立链表的函数
{ struct person * head, * p1, * p2;
  int i=1;
  p1=p2= (struct person *) malloc (LEN);
  p1->num = i;
  head=NULL;
  while (i <= n)
  { if (i==1) head=p1;
    else p2->next=p1;
    p2=p1;
    p1= (struct person *) malloc (LEN);
    p1->num = ++i;
  }
  p2->next=head;
  free (p1);
  return (head);
}

int reserved_in_circle (struct person * head)    //按规则删除链表里报数为3的结点的函数
{ struct person * p1, * p2 ;
  int i;
  if (head == NULL) return 0;
  p2=head;
  p1=p2->next;
  i=2;
  while (p1 != p2)            //当循环链表只有1个结点时,退出循环    
  { if (i%3==0)             //当报数为3时删除一个结点
    { if (p1 == head) head=p1->next;    //如果要删除的结点是头指针指向的结点,则让头指针指向下一个结点
      p2->next = p1->next;
      free (p1);
      p1=p2->next;
      i++;
    }
    p2=p1;
    p1=p1->next;
    i++;
  }
  return (p1->num);
}
 

阅读(1440) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~