机试题二

约瑟夫环

 

问题描述： 

输入一个由随机数组成的数列（数列中每个数均是大于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}

#include <stdio.h>
#include <string.h>
void array_iterate(int len, int input_array[], int m, int output_array[]) {
    int i, j, pos = -1, count = 0;
    int flag[100] = {0};
    for(i = 0; i < len; i++) {
        for(j = 0; j < m; j++) {
            do {
                pos = (pos + 1) % len;
            } while(flag[pos] == 1);
            //pos = (pos + 1) % len;
            printf("当前位置: %d\n", input_array[pos]);
        }
        printf("第%d次出列的是：%d\n", i + 1, input_array[pos]);
        flag[pos] = 1;
        output_array[count++] = input_array[pos];
        m = input_array[pos];
    }
}

int main() {
    int input_array[4] = {3, 1, 2, 4};
    int m = 7, i;
    int output_array[4] = {0};
    array_iterate(4, input_array, m, output_array);
    for(i = 0; i < 4; i++) {
        printf("%d  ", output_array[i]);
    }
    printf("\n");
    return 0;
}