黑马程序员技术交流社区
标题:
分享我的一道基础测试题——耶稣门徒问题
[打印本页]
作者:
passchaos
时间:
2015-3-11 15:39
标题:
分享我的一道基础测试题——耶稣门徒问题
原题目为:耶稣有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技术分了)。
作者:
mata
时间:
2015-3-11 16:09
想屎。。。根本看不懂 我还能不能愉快的培训了
作者:
sun397721060
时间:
2015-3-11 22:27
本以为我的代码就很复杂了 你是大神 你厉害~~~~:L
作者:
liyang783
时间:
2015-3-11 22:35
挺好的。就是一点注释没有,看着费劲。
作者:
丶小千
时间:
2015-3-11 22:38
这么巧啊,我也有这道题。费了不少功夫
作者:
tianlin
时间:
2015-3-11 22:41
以前做过一个选猴王的题跟这个类似
作者:
still过客
时间:
2015-4-23 20:04
int a[15];
int num=0;
int count=0;
for (int i=0; i<15; i++) {
a[i]=0;//1代表遇到3出局
}
while(1){
for (int i=0; i<15; i++) {
if (a[i]==0) {
num++;
if(num==3){
a[i]=1;
num=0;
count++;
}
}
}
if((15-count)<3) //剩余数不够3个,跳出while循环
break;
}
for (int i=0; i<15; i++) {
if(a[i]==0)
printf("%d\n",i+1);
}
答案是5和14吧?
作者:
张恒宇
时间:
2015-4-27 01:22
still过客 发表于 2015-4-23 20:04
int a[15];
int num=0;
int count=0;
5和14也是要继续这样的。。。
作者:
talent123
时间:
2015-6-8 15:08
/*
耶稣有15个门徒,其中有一个就是出卖耶稣的叛徒,请用排除法找出这位叛徒:
15人围坐一圈,从第一个开始报号:1,2,3,1,2,3……,凡是报到“3”就退出圈子,
最后留在圈内的人就是出卖耶稣的叛徒,请找出它原来的序号。
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct _node{
int num;
struct _node *next;
}Node;
typedef struct _list{
Node *head;
Node *tail;
}List;
int main(){
List list;
list.head = list.tail = NULL;
int i;
for (i =0; i < 15; i++){
Node *p = (Node *)malloc(sizeof(Node));
p->num = i + 1;
p->next = NULL;
if (list.tail){
list.tail->next = p;
list.tail = p;
}else {
list.head = list.tail = p;
}
}
list.tail->next = list.head;
Node *p = list.head;
Node *q = NULL;
int count = 0;
for (i = 2; ; i++){
q = p;
p = p->next;
if (p->next == p){
printf("last = %d", p->num);
break;
}
if (i % 3 == 0){
q->next = p->next;
count++;
printf("delete%d\n", p->num);
}
}
return 0;
}
复制代码
结果是5
作者:
noway190
时间:
2015-7-16 16:25
这,教我如何安心学习。。。。
作者:
poxiao
时间:
2015-11-6 22:43
/*
程序思想:每次往前数三个数第三个数即为当前出队的数,将出队的数置为-1
当数间隔遇到为-1的数时不计入步长,每次循环完一次总长度减1,直到长度为1,
值不为-1的数就为答案
*/
#include <stdio.h>
int FindJuda(int per[], int start)
{
int count = 0, length = 15;
start = start - 1;//数组从0开始,所以开始下标需要减1
while (length != 1)
{
while (count != 3)
{
if (per[start] != -1)
{
count++;
if (count != 3)
start = (start + 1) % 15; //控制循环从0-14
}
else
{
start = (start + 1) % 15;
}
}
length--;
printf("Out people number: %d\n", per[start] + 1);
per[start] = -1;
start = (start + 1) % 15;
count = 0;
}
for (count = 0; count < 15; count++)
{
if (per[count] != -1)
return per[count] + 1;
}
}
int main()
{
int person[15], start;
int i = 0, juda;
//初始化数组0-14,代表每个人的编号
for (i = 0; i < 15; i++)
{
person[i] = i;
}
printf("Please input start number:");
scanf ("%d", &start);
juda = FindJuda(person, start);//执行函数找出叛徒
printf("The Juda is number: %d\n", juda);
return 0;
}
复制代码
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2