程序設(shè)計綜合實踐 1.7

好玩的約瑟夫環(huán):有M個人迅矛,編號分別為1到M妨猩,玩約瑟夫環(huán)游戲,最初時按編號順序排成隊列秽褒;每遍游戲開始時壶硅,有一個正整數(shù)報數(shù)密碼N,隊列中人依次圍坐成一圈震嫉,從隊首的人開始報數(shù)森瘪,報到N的人出列,然后再從出列的下一人開始重新報數(shù)票堵,報到N的人出列扼睬;重復這一過程,直至所有人出列悴势,完成一遍游戲窗宇,所有出列的人形成新隊列;游戲可能玩很多遍特纤,每遍有新報數(shù)密碼军俊。求若干遍游戲完成后隊列次序。題目輸入包括若干個正整數(shù)(至少1個)捧存,第一個正整數(shù)為玩游戲人數(shù)M粪躬,后續(xù)每個正整數(shù)為每遍游戲報數(shù)密碼担败,報數(shù)密碼可能為1,題目要求按出隊列順序輸出他們的編號镰官。

輸入格式:
正整數(shù)M和后面的若干個正整數(shù)報數(shù)提前。

輸出格式:
每個測試用例結(jié)果占一行,每個編號占4位泳唠。

輸入樣例: 10 3 5 2
輸出樣例: 4 6 5 2 9 1 3 7 8 10
作者 李衛(wèi)明
單位 杭州電子科技大學
代碼長度限制 16 KB
時間限制 400 ms
內(nèi)存限制 64 MB

C語言版本:

#include <stdio.h>
#include<string.h>
typedef int bool;
#define true 1
#define false 0

typedef struct Node{
    int data;
    struct Node *next;
} Node;

Node* create_Yuesefu_List(int m){
    Node *head, *node,*end;//定義頭節(jié)點狈网,普通節(jié)點,尾部節(jié)點笨腥;
    head = (Node*)malloc(sizeof(Node));//分配地址
  head->data = 1;
    end = head;         //若是空鏈表則頭尾節(jié)點一樣
    for (int i = 1; i < m; i++) {
        node = (Node*)malloc(sizeof(Node));
    node->data = (i+1);
        head->next = node;
        head = head->next; 
    }
  head->next = end;
    return end;
}
Node* yuesefu_Problem(Node* head,int n){
  int counter = 1;
  bool is_First_Out = true;
  Node *node_new,*h,*node;
  node_new = (Node*)malloc(sizeof(Node));
  h=node_new;

  while(head!=NULL)
  {
    if(n!=1)counter++;
    else {
      if(is_First_Out==true){
        node_new->data = head->data;
        is_First_Out=false;
      }else{
        node = (Node*)malloc(sizeof(Node));
        node->data = head->next->data;//賦值操作
        node_new->next=node;
        head->next = head->next->next;
        node_new = node_new->next;

        if(head==head->next){
          node_new->next=h;
          return h;
        }
      }
    }

    if(counter==n && n!=1){
      if(is_First_Out==true){
        node_new->data = head->next->data;
        is_First_Out=false;
      }else{
        node = (Node*)malloc(sizeof(Node));
        node->data = head->next->data;
        node_new->next = node;
   //上面三句話 相當于1句話 node_new.next = new Node(head.next.value);
        node_new=node_new->next;
      }
      head->next = head->next->next;
      counter = 0;
    }else if(counter!=n&&n!=1){
      head = head->next;
      if(head == head->next){
        node = (Node*)malloc(sizeof(Node));
        node->data = head->data;
        node_new->next = node;
        node_new->next->next = h;
        break;
      }
    }
  }
    return h;
}
Node* input_LinkedList(){
  char str[1024];
  char *delim = " ";
  scanf("%[^\n]", str);
  Node* head = (Node*)malloc(sizeof(Node));
  Node * end = head;
  Node * node;
  int count=0;
  char *p = strtok(str, delim);
  head->data = atoi(p);
  // printf("%s \n", p);
  count++;
  while((p = strtok(NULL, delim))){
    node = (Node*)malloc(sizeof(Node));
    node->data = atoi(p);
    head->next = node;
    head = head->next;
    // printf("%s \n", p);
    count++;
  }
  return end;
}
void print_LinkedList(Node* head,int count){
  while(head->next != NULL && count !=0){
      printf("%4d",head->data);
      head = head->next;
      count--;
  }
  printf("\n");
}
int main(void) {
  Node* head = input_LinkedList();
  int m = head->data;
  head = head->next;
  Node* h = create_Yuesefu_List(m);
  while(head!=NULL){
      h = yuesefu_Problem(h,head->data);
      head = head->next;
    }
  print_LinkedList(h, m);
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末拓哺,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子脖母,更是在濱河造成了極大的恐慌士鸥,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,496評論 6 501
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件镶奉,死亡現(xiàn)場離奇詭異础淤,居然都是意外死亡,警方通過查閱死者的電腦和手機哨苛,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,407評論 3 392
  • 文/潘曉璐 我一進店門鸽凶,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人建峭,你說我怎么就攤上這事玻侥。” “怎么了亿蒸?”我有些...
    開封第一講書人閱讀 162,632評論 0 353
  • 文/不壞的土叔 我叫張陵凑兰,是天一觀的道長。 經(jīng)常有香客問我边锁,道長姑食,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,180評論 1 292
  • 正文 為了忘掉前任茅坛,我火速辦了婚禮音半,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘贡蓖。我一直安慰自己曹鸠,他們只是感情好,可當我...
    茶點故事閱讀 67,198評論 6 388
  • 文/花漫 我一把揭開白布斥铺。 她就那樣靜靜地躺著彻桃,像睡著了一般。 火紅的嫁衣襯著肌膚如雪晾蜘。 梳的紋絲不亂的頭發(fā)上邻眷,一...
    開封第一講書人閱讀 51,165評論 1 299
  • 那天眠屎,我揣著相機與錄音,去河邊找鬼肆饶。 笑死组力,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的抖拴。 我是一名探鬼主播,決...
    沈念sama閱讀 40,052評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼腥椒,長吁一口氣:“原來是場噩夢啊……” “哼阿宅!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起笼蛛,我...
    開封第一講書人閱讀 38,910評論 0 274
  • 序言:老撾萬榮一對情侶失蹤洒放,失蹤者是張志新(化名)和其女友劉穎,沒想到半個月后滨砍,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體往湿,經(jīng)...
    沈念sama閱讀 45,324評論 1 310
  • 正文 獨居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,542評論 2 332
  • 正文 我和宋清朗相戀三年惋戏,在試婚紗的時候發(fā)現(xiàn)自己被綠了领追。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點故事閱讀 39,711評論 1 348
  • 序言:一個原本活蹦亂跳的男人離奇死亡响逢,死狀恐怖绒窑,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情舔亭,我是刑警寧澤些膨,帶...
    沈念sama閱讀 35,424評論 5 343
  • 正文 年R本政府宣布,位于F島的核電站钦铺,受9級特大地震影響订雾,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜矛洞,卻給世界環(huán)境...
    茶點故事閱讀 41,017評論 3 326
  • 文/蒙蒙 一洼哎、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧缚甩,春花似錦谱净、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,668評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至郊丛,卻和暖如春李请,著一層夾襖步出監(jiān)牢的瞬間瞧筛,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 32,823評論 1 269
  • 我被黑心中介騙來泰國打工导盅, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留较幌,地道東北人。 一個月前我還...
    沈念sama閱讀 47,722評論 2 368
  • 正文 我出身青樓白翻,卻偏偏與公主長得像乍炉,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子滤馍,可洞房花燭夜當晚...
    茶點故事閱讀 44,611評論 2 353

推薦閱讀更多精彩內(nèi)容

  • 又見約瑟夫環(huán):有M個人圍坐成一圈岛琼, 編號依次從1開始遞增直到M,現(xiàn)從編號為1的人開始報數(shù)巢株,報到N的人出列槐瑞,然后再從...
    jack_programme閱讀 436評論 0 0
  • 說明: 本文中出現(xiàn)的所有算法題皆來自牛客網(wǎng)-劍指Offer在線編程題阁苞,在此只是作為轉(zhuǎn)載和記錄困檩,用于本人學習使用,不...
    秋意思寒閱讀 1,152評論 1 1
  • 二維數(shù)組中的查找 Q: 在一個二維數(shù)組中(每個一維數(shù)組的長度相同)那槽,每一行都按照從左到右遞增的順序排序悼沿,每一列都按...
    菜雞不得行閱讀 3,035評論 0 2
  • 1.二維數(shù)組的查找 題目描述:在一個二維數(shù)組中(每個一維數(shù)組的長度相同),每一行都按照從左到右遞增的順序排序骚灸,每一...
    少年夢游計_3403閱讀 1,164評論 0 1
  • 不要使用暴力的方法显沈,可以學學討論里的技巧 二維數(shù)組中的查找 題目:在一個二維數(shù)組中(每個一維數(shù)組的長度相同),每一...
    大大大大大大大熊閱讀 2,555評論 0 1