黑马程序员技术交流社区

标题: 约瑟夫环问题 [打印本页]
作者: song0619    时间: 2015-12-22 19:19
标题: 约瑟夫环问题
下面这道题是基础测试时做过的题，这是一类题，叫约瑟夫环，我用的是数组和循环实现了。但是这类问题应该用循环链表更方便些，不知道哪位能提供些循环链表方面的详细视频资料。谢谢啦！


**************************************************************************************************************
10、 耶稣有15个门徒，其中有一个就是出卖耶稣的叛徒，请用排除法找出这位叛徒：15人围坐一圈，从第一个开始报号：1，2，3，1，2，3……，凡是报到“3”就退出圈子，最后留在圈内的人就是出卖耶稣的叛徒，请找出它原来的序号。（C语言）



作者: Manli123    时间: 2015-12-22 23:11
#include <stdio.h> int main() {     int a[13];     for (int i = 0; i < 13; i++)         a[i] = 1;     void fun(int *, int);     fun(a, 13);     return 0; } void fun(int *a, int size) {     int flag = 0,mun = size,*yuan=a;     while (mun > 1)     {         for (flag = 1; flag < 4; flag++)         {             if (a == yuan + size)                 a = yuan;             while (*a == 0)             {                 a++;                 if (a == yuan + size)                     a = yuan;             }             if (flag == 3)             {                 *a = 0;                  mun--;             }             a++;         }     }     a = yuan;     for (; a < yuan + size;a++)         if (*a != 0)         {         printf("是原来第%d号！\n", a - yuan + 1);         break;         } }
作者: song0619    时间: 2015-12-23 09:40
Manli123 发表于 2015-12-22 23:11
#include  int main() {     int a[13];     for (int i = 0; i < 13; i++)         a = 1;     void fun(i ...

这个我已经解决了
作者: w261215    时间: 2015-12-25 13:22
来观摩一下
作者: huaduwuzhe    时间: 2015-12-26 08:51
怎么是用的C语言
作者: s1714534118    时间: 2015-12-26 13:39
发给你了
#include<<a  target="_blank" class="baidu-highlight">stdio.h</a>>
#include <<a  target="_blank" class="baidu-highlight">stdlib.h</a>> 
//n表示最初有多少个人，m表示报数到多少的人离开，函数Joseph返回最后剩下的人的编号 
 
int Joseph(int n,int m) 
{  
    //int m=3;
    int count = n;   //count表示当前圈内剩下的人数 
    int num=0;     //num表示当前报的数 
    int i,j;       //i表示当前报数的人对应的下标 
    int *a, remain; 
    //动态申请连续的n个存储单元用来存放每个人的编号，将空间首地址赋值给a
    a = (int *)malloc(n*sizeof(int)); 
    for(i=0; i<n; i++) 
        a[i] = i+1; //a[i]保存第i个人的编号 
    i = 0; //从下标为0的人开始报数 
    //printf("Delete In Order: ");
    while(count>1) //如果剩余人数大于1则循环 
    { 
         
        num++; 
        if(num == m) //报数到m的人离开 
        { 
            //将下标为i的元素删除
            //printf("%d\t",a[i]);
            for(j=i; j<count-1; j++) 
                a[j] = a[j+1]; 
            count--; //当前剩余人数减1 
            num = 0; //下一个人重新从1开始报数 
            i-=1;          
        }
        i=(i+1)%count; //计算下一个要报数的人的下标 
    } 
    remain = a[0]; //最后只剩下一个人，将其编号赋值给remain
    return remain; 
}
 
int main()
{
    int n,m;
    int i;
    printf("input n and m:n表示最初有多少个人，m表示报数到多少的人离开\n");
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        //printf("%d\n",Joseph(n));
        printf("\nRemain: NO.%d\n",Joseph(n,m));
    }
    return 0;
}
作者: 帝都    时间: 2015-12-27 15:15
看好几个发的了，我就不用发了
作者: sunshine429    时间: 2016-1-2 11:43
  1. // 循环链表，希望采纳
  2. #include <stdio.h>
  3. #include <stdlib.h>

  5. typedef struct node
  6. {
  7.         int data;
  8.         struct node *next;
  9. }node;

  11. node *create(int n)
  12. {
  13.         node *p = NULL, *head;
  14.         head = (node*)malloc(sizeof (node ));
  15.         p = head;
  16.         node *s;
  17.         int i = 1;

  19.         if( 0 != n )
  20.         {
  21.                 while( i <= n )
  22.                 {
  23.                         s = (node *)malloc(sizeof (node));
  24.                         s->data = i++;    // 为循环链表初始化，第一个结点为1，第二个结点为2。
  25.                         p->next = s;
  26.                         p = s;
  27.                 }
  28.                 s->next = head->next;
  29.         }

  31.         free(head);

  33.         return s->next ;
  34. }

  36. int main()
  37. {
  38.         int n = 41;
  39.         int m = 3;
  40.         int i;
  41.         node *p = create(n);
  42.         node *temp;

  44.         m %= n;   // m在这里是等于2

  46.         while (p != p->next )
  47.         {
  48.                 for (i = 1; i < m-1; i++)
  49.                 {
  50.                         p = p->next ;
  51.                 }

  53.                 printf("%d->", p->next->data );

  55.                 temp = p->next ;                                //删除第m个节点
  56.                 p->next = temp->next ;
  57.                 free(temp);

  59.                 p = p->next ;
  60.         }

  62.         printf("%d\n", p->data );

  64.         return 0;
  65. }
复制代码
作者: ydy2511000    时间: 2016-1-7 15:17
约瑟夫·~~~~~
作者: 1066715808    时间: 2016-1-8 08:46
先顶了，因为还没有学到
作者: song0619    时间: 2016-1-8 11:13
加油                     
作者: q6777017    时间: 2016-1-9 14:30
#include "stdio.h" #include "stdlib.h" #define S sizeof(struct node)  struct node {     int num;     struct node *next; };  typedef struct node NODE;  NODE *createlinklist(int n) {     NODE *head,*p,*q;     int i=1;     head=p=(struct node*)malloc(sizeof(struct node));     p->num=i;     for(i=2;i<=n;i++)     {         q=(struct node*)malloc(sizeof(struct node));         if(q==0) return(0);         p->next=q;         p=q;         p->num=i;     }     p->next=head;          /*使链表尾指向链表头 形成循环链表*/  return head; }  void printlinklist(NODE *p,int n) {     int i;  NODE *q = p;     if(NULL == q->next){   printf("the list is NULL!");   return;  }     printf("所有玩家的信息列表:\n");     for(i=1;i<=n;i++)     {      if(NULL == q){    printf("the list is NULL!");    return;   }         printf("%d  ",p->num);         p=p->next;     }  printf("\n"); }  void joseph(NODE *p,int n,int m) {  int i,j;  NODE *q;  for(i=1;i<n;i++)  {   for(j=1;j<=m-1;j++)   {    p=p->next;   }   q=p->next;   p->next = q->next;   printf("%d  ",q->num);   free(q);  }  printf("\n最后剩余的是第%d号.\n",p->num);  p->next=NULL; }  void main() {     NODE *head;     int n,m;  printf("请输入人数N:\n");  scanf("%d",&n);  printf("输入K:\n");  scanf("%d",&m);     head=createlinklist(n);     printlinklist(head,n);  printf("依次被选出的是:\n");     joseph(head,n,m); }
作者: 胡思乱想的猫    时间: 2016-1-20 23:10
         * 约瑟夫环
         * * 幸运数字
         */
        public static void main(String[] args) {
                System.out.println(getLucklyNum(8));
        }

        /*
         * 获取幸运数字
         * 1,返回值类型int
         * 2,参数列表int num
         */
        public static int getLucklyNum(int num) {
                ArrayList<Integer> list = new ArrayList<>();                //创建集合存储1到num的对象
                for(int i = 1; i <= num; i++) {
                        list.add(i);                                                                        //将1到num存储在集合中
                }
               
                int count = 1;                                                                                //用来数数的,只要是3的倍数就杀人
                for(int i = 0; list.size() != 1; i++) {                                //只要集合中人数超过1,就要不断的杀
                        if(i == list.size()) {                                                        //如果i增长到集合最大的索引+1时
                                i = 0;                                                                                //重新归零
                        }
                       
                        if(count % 3 == 0) {                                                        //如果是3的倍数
                                list.remove(i--);                                                                //就杀人
                        }
                        count++;
                }
               
                return list.get(0);
        }
}
我吧老师的代码给你了 自己看吧  我也还要慢慢看才懂  一起进步吧



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2