原题目为:耶稣有15个门徒,其中有一个就是出卖耶稣的叛徒,请用排除法找出这位叛徒:15人围坐一圈,从第一个开始报号:1,2,3,1,2,3……,凡是报到“3”就退出圈子,最后留在圈内的人就是出卖耶稣的叛徒,请找出它原来的序号。
这个有很多中解决方法,但是为了能解决同类型的问题(比如30个门徒,报到5就退出),我使用了单向循环链表:
/*
* 15人围成一圈,从第一个开始报数:1,2,3,1,2,3······,凡是报到“3”就退出圈子,
* 找出最后留在圈内的人原来的序号
* 最直接方法,就是利用单循环链表
*/
#include <stdio.h>
#include <stdlib.h>
#define M 15
#define N 3
struct node {
int value;
struct node *next;
};
struct node *add_to_list(struct node *list, int n);
struct node *finding(struct node *list1, struct node *list2);
int main(void)
{
struct node *first = NULL;
struct node *end = NULL;
int i;
end = first = add_to_list(first, M);
for (i = M-1; i > 0; i--)
first = add_to_list(first, i);
end->next = first;
printf("%d\n", finding(first, end)->value);
return 0;
}
struct node *add_to_list(struct node *list, int n)
{
struct node *new_node;
new_node = malloc(sizeof(struct node));
if (new_node == NULL) {
printf("Error: malloc failed in add_to_list\n");
exit(EXIT_FAILURE);
}
new_node->value = n;
new_node->next = list;
return new_node;
}
struct node *finding(struct node *list1, struct node *list2)
{
int i = 0;
struct node *curr, *prev;
prev = list2;
curr = list1;
for (;;) {
if (prev == curr)
return curr;
i++;
if (i == N) {
prev->next = curr->next;
curr = curr->next;
i = 0;
continue;
}
prev = prev->next;
curr = curr->next;
}
}
只需要更改宏M和N的值,即可使用与所有的情况(希望版主加分,我马上就够25技术分了)。
|
|