题目:n人围成一个圈,顺序排列。
从第一个人开始报数,从一报到三,凡是报到三的人退出圈子,
问最后留下的是原来第几号的那位。
问题来源:> C语言论坛提问帖 <
献丑了!
// 20190421_circle_report_3_last_one_.c
/* 题目:n人围成一个圈,顺序排列。
* 从第一个人开始报数,从一报到三,凡是报到三的人退出圈子,
* 问最后留下的是原来第几号的那位。
*/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
// 去除值为0的元素,重整数组长度
int del_zero(int *p, int *source, int new_n, int *temp);
int main(int argc, char const *argv[])
{
int n;
printf("Enter a num > 0 ==> people quantity: ");
if (scanf("%d", &n) != 1) {
printf("Enter error!\n");
exit(1);
}
if (n < 1) {
printf("Number is too small. Bye!\n");
exit(1);
}
int *p, *source;
source = (int *)malloc(n * sizeof(int));
if (source == NULL) {
printf("source malloc error!\n");
exit(1);
}
for (p = source; p < source + n; p++) {
*p = p - source + 1;
}
int new_n = n;
int *temp = (int *)malloc(n * sizeof(int));
if (temp == NULL) {
printf("temp malloc error!\n");
exit(1);
}
int num = 1;
while (1) {
for (p = source; p < source + new_n; num++) {
if (new_n >= 3) {
if (num % 3 == 0) {
*p = 0;
num = 0;
new_n = del_zero(p, source, new_n, temp);
// 重整数组后,后面的元素向前移动了一位,
// 所以下一次要从这次的位置开始数1
p = p - 1;
}
} else if (new_n == 2) {
*p = 0;
new_n = del_zero(p, source, new_n, temp);
break;
} else {
break;
}
// 如果遍历到了最后一位元素,则下一次从头开始
if (p == source + new_n - 1) {
p = source;
} else {
p++;
}
}
if (new_n == 1) {
free(temp);
temp = NULL;
break;
}
}
printf("The last number is %d\n", *source);
free(source);
source = NULL;
return 0;
}
// 去除值为0的元素,重整数组长度
int del_zero(int *p, int *source, int new_n, int *temp)
{
int i;
for (i = 0, p = source; p < source + new_n; p++) {
if (*p != 0)
temp[i++] = *p;
}
new_n = i;
int j;
for (j = 0, p = source; j < new_n; j++) {
*p = temp[j];
p++;
}
return new_n;
}
简单测试
Linux环境下,clang编译,测试运行结果:
(1)
Enter a num > 0 ==> people quantity: 0
Number is too small. Bye!
(2)
Enter a num > 0 ==> people quantity: 1
The last number is 1
(3)
Enter a num > 0 ==> people quantity: 2
The last number is 2
(4)
Enter a num > 0 ==> people quantity: 3
The last number is 2
(5)
Enter a num > 0 ==> people quantity: 4
The last number is 1
(6)
Enter a num > 0 ==> people quantity: 5
The last number is 4
(7)
Enter a num > 0 ==> people quantity: 6
The last number is 1
(8)
Enter a num > 0 ==> people quantity: 7
The last number is 4
(9)
Enter a num > 0 ==> people quantity: 11
The last number is 7
(10)
Enter a num > 0 ==> people quantity: 16
The last number is 8