小程序（六）随机数按计数输出问题

78 阅读 0 评论 52 点赞

我是靠谱客的博主粗暴咖啡豆，最近开发中收集的这篇文章主要介绍小程序（六）随机数按计数输出问题，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

约瑟夫问题

输入一个由随机数组成的数列（数列中每个数均是大于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<stdlib.h>
void array_iterate(int len, int input_array[], int m, int output_array[])
{
int startIndex = 0; // 下一次开始计数的下标
int chooseIndex = 0; // 选中的下标
int outputIndex = 0; // 输出数组的下标
while(len > 0)
{
startIndex = chooseIndex;
chooseIndex = (startIndex + (m - 1) % len) % len;
m = input_array[chooseIndex];
output_array[outputIndex++] = m;
// 数组左移
for(int i = chooseIndex; i <= len
- 2; ++i)
{
input_array[i] = input_array[i + 1];
}
-- len;
}
}
int main()
{
int input_array[] = {3,1,2,4,7,9,13};
int output_array[7];
int len = 7, m=7;
array_iterate(len, input_array, m, output_array);
//output(output_array, len);
// int *q = output_array;
for(int i=0;i<7;i++)
printf("%d ",output_array[i]);
getchar();
return 0 ;
}

第2种方法，用循环链表，直观，方便。

#include<stdio.h>
#include<stdlib.h>
typedef struct node{
int data;
struct node *next;
}node,*Linklist;
void create( Linklist &L,int *input_array,int len )
{
Linklist p,s;
int i;
//int len = sizeof(input_array)/sizeof(int);
//int len=4;
p = L;
p->data = input_array[0];
for(i=1;i<len;i++)
{
s = (Linklist)malloc(sizeof(node));
s->data = input_array[i];
p->next = s;
p = s;
}
p->next = L;
}
void array_iterate( int len, int input_array[], int m, int output_array[] )
{
Linklist L,p,q,s;
int i,j;
j=0;
L = (Linklist)malloc(sizeof(node));
create(L,input_array,len);
p = L;
while( p != p->next )
{
for(i=1;i<m;i++)
{
s = p;
p = p->next;
}
output_array[j++] = p->data;
m = p->data;
q = p;
s->next = p->next;
p = p->next;
free(q);
}
output_array[j++] = p->data;
}
int main()
{
int input_array[]={3,1,2,4};
int len=4;
int m=2;
int output_array[4];
array_iterate(len,
input_array, m,output_array);
for(int i=0;i<4;i++)
printf("%dn",output_array[i]);
return 0;
}

如果作为函数的参数是没法求的,> 但这样是可以的:

> > #define LENGTH(s) (sizeof(s) / sizeof(int))

> > int s[12];

> int length = LENGTH(s);

这样的方法只能用于数组变量的数组名，对于指向数组的指针，以及作为参数的数组名都是没有效果的，上面已经有人解释了