C-猫吃老鼠问题

Question

现有n个老鼠围成一圆圈，有一只猫从任意位置开始吃老鼠，每次都隔一个老鼠吃，请给出最后一个老鼠的编号？要求是任给老鼠数n，输出猫最后吃的老鼠的编号.（从猫开始吃的老鼠起编号为1，方向也一致）

Answer 1

现有n个老鼠围成一圆圈，有一只猫从第一只老鼠开始吃，每次都隔一个老鼠吃，请给出最后一个老鼠的编号？要求是任给老鼠数n，输出猫最后吃的老鼠的编号.

#include <stdio.h>

int main(void)
{
int n, m, i, s=0;
printf ("N "); scanf("%d", &n);
m = 1;
for (i=2; i<=n; i++) s=(s+m)%i;
printf ("The winner is %dn", s+1);
return 0 ;
}

如果是中间隔m只的话，把上面的代码m的值从键盘输入就行了。
如果题目真如原作者说的，从任意位置开始，把结果(s+1 + 任意起始位置)%n就是结果了。
题目不严谨...
n是总数，m是中间相隔的数

Answer 2

因为目前还无法写评论，所以作为答案发出来，对magic答案的进行补充。
magic给出了漂亮的计算公式，但是在计算时可以不用对数函数，这是更加精益求精的追求。具体的修改如下：

int test(int n){
int mask = 1<<30;
while(mask > 0 && (n&mask) == 0){

mask = mask >> 1;

}
int r = ~mask & n;
return r == 0 ? n : r<<1;
}

以上函数假定n是大于0的整数，对n小于等于0的情况需要在函数外或者在入口处检查。

Answer 3

们假设老鼠按顺时针方向编号，猫从第一号老鼠开始吃。比如现有4个老鼠围成一个圆，则猫吃老鼠的顺序应该为1->3->2->4,即最后一个吃的老鼠的编号是4。

#include <stdio.h>
#include <stdlib.h>
typedef struct tagCatEatMouse
{
int flag;
struct tagCatEatMouse *last;
}CATEatMouse,*pCatEatMouse;
pCatEatMouse create(int n);
pCatEatMouse eat(pCatEatMouse LastCat,int n);
void EatTheMouse(pCatEatMouse food);
int main()
{
pCatEatMouse HeadCat;
HeadCat=eat(create(9),9);
printf("%dn",HeadCat->flag);
return 0;
}
pCatEatMouse create(int n)
{
pCatEatMouse head,savepoint;
head=(pCatEatMouse)malloc(sizeof(CATEatMouse));
savepoint=head;
head->flag=0;
for (int i=0;i<n-1;i++)
{
pCatEatMouse next;
next=(pCatEatMouse)malloc(sizeof(CATEatMouse));
head->last=next;
next->flag=i+1;
head=next;
}
head->last=savepoint;
return savepoint;
}
pCatEatMouse eat(pCatEatMouse LastCat,int n)
{
pCatEatMouse lcat,eatmouse;
lcat=eatmouse=LastCat;
for (int i=0;i<n-1;i++)
{
LastCat=LastCat->last;
}
for (i=0;i<n-1;i++)
{
lcat=lcat->last;
LastCat->last=lcat;
LastCat=lcat;
EatTheMouse(eatmouse);
pCatEatMouse eatmouse;
eatmouse=(pCatEatMouse)malloc(sizeof(CATEatMouse));
eatmouse=LastCat->last;
lcat=lcat->last;
}
EatTheMouse(eatmouse);
return LastCat;
}
void EatTheMouse(pCatEatMouse food)
{
free(food);
}

Answer 4

简化为从第一只老鼠开始，公式为：
如果n是2的幂，则结果为 n，
否则结果为 2 * (n - 小于n的2的最大的幂)。

 #include <stdio.h>
#include <stdlib.h>
#include <math.h>

int test(int n, int m)
{
int b = log(n) / log(m);
int p = pow(m, b);

printf("%d:t%dn", n, (n == p ? n : (n - p) * 2));
}

int main(int argc, char *argv[])
{
int m = 2;

for(int i = 0; i < 20; i++) {
test(i + 1, m);
}

return 0;
}

输出：

1: 1
2: 2
3: 2
4: 4
5: 2
6: 4
7: 6
8: 8
9: 2
10: 4
11: 6
12: 8
13: 10
14: 12
15: 14
16: 16
17: 2
18: 4
19: 6
20: 8