算法-約瑟夫環問題

1.問題:

請注意：這一節部分隻有

count_off

函數部分可以修改，要先了解其他部分在做什麼後再下手實作

count_off

函數喔

在學習了連結清單結構後，這一節我們需要用連結清單解決一個稍有改動的“約瑟夫環（Josephus problem）”問題：

計算理工學院有 N 個同學，圍成了一個圓圈，每人被順序地編了一個序号（分别為 1,2,3... n1,2,3...n），從編号為 K 的人開始報 1，他之後（順初始數字增長方向計算序号）的人報 2，以此類推，數到某一個數字 M 的人出列。出列同學的下一個人又從 1 開始繼續報數，數到某一個數字 M 的人出列。不斷重複這一過程，直到所有人都出列為止。

你需要根據同學人數 N 和給出的 K 和 M 計算出同學的正确出列順序。

這一題的

main

函數已經幫你寫好了，同時，已經幫你定義了一個節點的結構體類型、通過

circle_create

建立了一個循環連結清單。

現在請在

count_off

函數中根據傳入的編号為 1 的節點 headhead、學生數 n、起始報數學生編号 k、數到出列的數字 m 實作報數的過程，按照題目要求進行輸出。

輸入格式

測評機會反複運作你的程式。每次程式運作時，輸入為一行，包括三個被空格分隔開的符合描述的正整數 N、K 和 M（1<= K<= N<= 10001≤K≤N≤1000，1 <= M <= 20001≤M≤2000）。

輸出格式

輸出為一行，包含 N 個整數，為依次順序出列的學生編号，由空格分隔開。

樣例輸入1

9 1 1      

樣例輸出1

1 2 3 4 5 6 7 8 9      

樣例輸入2

8 5 2      

樣例輸出2

6 8 2 4 7 3 1 5      

知識點:

1.指針

2.連結清單

3.動态記憶體配置設定 ，動态記憶體釋放

重點：

    1.需要考慮到頭尾相接的問題

    2.需要得到目前人的上一個人的指針（非常重要，我就是沒注意到這一點，卡了半小時找問題）

具體代碼如下:

#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    int data;
    struct node *next;
} Node;

Node *circle_create(int n);
void count_off(Node *head, int n, int k, int m);

int main() {
    int n, k, m;
    scanf("%d%d%d", &n, &k, &m);
    Node *head = circle_create(n);
    count_off(head, n, k, m);
    return 0;
}

Node *circle_create(int n) {
    Node *temp, *new_node, *head;
    int i;

    // 建立第一個連結清單節點并加資料
    temp = (Node *) malloc(sizeof(Node));
    head = temp;
    head->data = 1;

    // 建立第 2 到第 n 個連結清單節點并加資料
    for(i = 2; i <= n; i++) {
        new_node = (Node *) malloc(sizeof(Node));
        new_node->data = i;
        temp->next = new_node;
        temp = new_node;
    }

    // 最後一個節點指向頭部構成循環連結清單
    temp->next = head;

    return head;
}

void count_off(Node *head, int n, int k, int m) {
    Node *tempk = head;
    Node *lasttemp = head;
    if(tempk->data == k){
        //如果是頭部,則循環到最後一個
        for(int j=0;j<n;j++){
            if(j == n-1){
                break;
            }
            lasttemp = lasttemp->next; 
        }
    }else{
        for(int i=0;i<n;i++){
            if(tempk->data == k-1){
                lasttemp = tempk;
                tempk = tempk->next;
                break;
            }
            tempk = tempk->next;
        }
    }
    Node *temp = tempk;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<m;j++){
            if(j == m-1){
                printf("%d",temp->data);
                if(i!=n-1) printf(" ");
                if(temp == head){
                    tempk = head;
                    lasttemp->next = head->next;
                    head = head->next;
                    temp = head;
                }   
                else{
                    tempk=temp;
                    lasttemp->next = temp->next;
                    temp=temp->next;   
                }
                free(tempk);
                tempk = NULL;    
                break;
            }else{
                lasttemp = temp;   
                temp = temp->next;
            }
        }
    }
    return;
}