約瑟夫環變種

約瑟夫環變種： 

輸入一個由随機數組成的數列（數列中每個數均是大于0的整數，長度已知），和初始計數值m。從數列首位置開始計數，計數到m後，将數列該位置數值替換計數值m，并将數列該位置數值出列，然後從下一位置從新開始計數，直到數列所有數值出列為止。如果計數到達數列尾段，則傳回數列首位置繼續計數。請程式設計實作上述計數過程，同時輸出數值出列的順序

比如： 輸入的随機數列為：3,1,2,4，初始計數值m=7，從數列首位置開始計數（數值3所在位置）

第一輪計數出列數字為2，計數值更新m=2，出列後數列為3,1,4，從數值4所在位置從新開始計數

第二輪計數出列數字為3，計數值更新m=3，出列後數列為1,4，從數值1所在位置開始計數

第三輪計數出列數字為1，計數值更新m=1，出列後數列為4，從數值4所在位置開始計數

最後一輪計數出列數字為4，計數過程完成。

輸出數值出列順序為：2,3,1,4。

• 要求實作函數： 

void array_iterate(int len, int input_array[], int m, int output_array[])

【輸入】 int len：輸入數列的長度；

int intput_array[]：輸入的初始數列

int m：初始計數值

【輸出】 int output_array[]：輸出的數值出列順序

【傳回】 無

• 示例 

輸入：int input_array[] = {3,1,2,4}，int len = 4， m=7

輸出：output_array[] = {2,3,1,4}

分步：

1，肯定還是應用循環連結清單，是以先建立一個循環連結清單。在建立過程中，需要輸入随機數，進行建立。

2，找出要出列的數，當找到第一個出列的數值時将此數值指派給m,進而進行下一個循環。

<span style="font-size:18px;">#include <iostream>
using namespace std;

class List;

class Node
{
    friend class List;
private:
    int data;
    Node * link;
public:
    Node (int a): data(a)
    {
        link = NULL;
    }
};

class List
{
private:
    Node * first;
public:
    void CreateList (int len);
    void Show ();
    void Output (int len,int m);
};
void List::Output (int len,int m)
{
    Node * pre = NULL;
    Node * cur = first;
    int l = len;
    int output[len];
    int i = 0;
    while(l--)
    {
        Node * p;
        int k = m-1;
        while(k--)
        {
            pre = cur;
            cur = cur->link;
        }
        p = cur;
        output[i++] = p->data;
        m = p->data;               //每一次循環，其m值将會改變
        pre->link = p->link;
        delete p;
        cur = pre->link;
    }

    cout << "{";
    for (int j=0; j<len; j++)
    {
        if (j == len-1)
        {
            cout << output [j] << "}";
        }
        else
        {
            cout << output [j] << ",";
        }
    }
}
void List::CreateList (int len)
{
    Node * pre = NULL;
    Node * cur = NULL;
    int n =len;
    int i,j,k;
    cin >> i;                  //因為是不帶表頭的循環連結清單，是以小輸入一個作為表頭節點
    Node * p;       
    first = new Node (i);
    cur = first;
    for (k =2; k <= n; k++)
    {
        cin >> j;               //輸入一個數，建立一個節點，然後連起來
        p = new Node (j);
        pre = cur;
        cur = p;
        pre->link = cur;
    }
    cur->link = first;
}

void List::Show ()              //測試連結清單建立是否成功
{
    cout << first->data << "->";
    cout << first->link->data << "->";
    cout << first->link->link->data << "->";
    cout << first->link->link->link->data << "->";
    cout << first->link->link->link->link->data << endl;
}
int main()
{
    List l;
    l.CreateList(4);            //建立連結清單
    l.Show ();
    l.Output(4,7);              //輸出出列數組
    return 0;
}
</span>