数据结构--约瑟夫问题

2017-12-12 08:26:17来源:CSDN作者:Vrwang人点击

分享

约瑟夫问题 

约瑟夫问题是一个经典的问题。已知n个人(不妨分别以编号123,…,代表 )围坐在一张圆桌周围,从编号为 k 的人开始,从1开始顺时针报数1, 2, 3, ...,顺时针数到的那个人,出列并输出。然后从出列的下一个人开始,从1开始继续顺时针报数,数到m的那个人,出列并输出,…依此重复下去,直到圆桌周围的人全部出列。

输入:n, k, m

输出:按照出列的顺序依次输出出列人的编号,编号中间相隔一个空格,每10个编号为一行。

非法输入的对应输出如下

a) 

输入::n、k、m任一个小于1
输出:n,m,k must bigger than 0. 

b) 

输入:k>n

输出:k should not bigger than n.

例:

输入:9,3,2

输出:4 6 8 1 3 7 2 9 5

 测试输入关于“测试输入”的帮助期待的输出关于“期待的输出”的帮助时间限制关于“时间限制”的帮助内存限制关于“内存限制”的帮助额外进程关于“{$a} 个额外进程”的帮助
测试用例 1以文本方式显示
  1. 9,3,2↵
以文本方式显示
  1. 4 6 8 1 3 7 2 9 5↵
1秒64M0
测试用例 2以文本方式显示
  1. 10,12,3↵
以文本方式显示
  1. k should not bigger than n.↵
1秒64M0

主要代码

////  main.c//  1. 约瑟夫问题////  Created by 王耀 on 15/10/2017.//  Copyright © 2017 WYY. All rights reserved.//#include <stdio.h>#include <string.h>#include <stdlib.h>typedef struct node{    int num;    struct node *next;}node;                                         //定义结构体int main(){    int i, count, flag=0;                      //count:总数    int n,k,m,x;    node *p = NULL,*q,*begin = NULL,*head;    scanf("%d,%d,%d",&n,&k,&m);    x=n*k*m;    if(x>0&&k<=n&&m<=n){                       //判断满足条件的情况        head=q=(node*)malloc(sizeof(node));    //建空结点,并使head,q指针指向空结点                for(i=1;i<=n;i++){            p=(node*)malloc(sizeof(node));     //使p指针指向新建结点            p->num=i;                          //依次给每个结构中num赋值            if(i==k)begin=p;            q->next=p;                         //给每个结构建立指向下一个结构体的指针            q=p;        }                                      //建立树链,结果为begin指针指向k结点,pq指针指向n结点        q->next=head->next;                    //使n个结点链连接成环                count=n;flag=0;       //flag:按照出列的顺序依次输出出列人的编号,编号中间相隔一个空格,每10个编号为一行。        while(1){            for(i=0;i<m-1;i++)                 //不断的接着数k个值            {                p=begin;                begin=begin->next;            }                                  //begin向后移m-1项            count--;            printf("%d",begin->num);           //输出第k项值            flag++;            if(flag%10==0||count==0)putchar('/n');            else printf(" ");                        if(count==0)break;            begin=begin->next;            p->next=begin;                     //begin再往后移一位,以此项为初始继续数        }    }    else if(x<=0) printf("n,m,k must bigger than 0./n");    else if(k>n)  printf("k should not bigger than n./n");}


   

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台