猫吃老鼠问题的求解
昨天看到一片帖子关于猫吃老鼠的问题。一、问题描述
现有n个老鼠围成一圆圈，有一只猫从任意位置开始吃老鼠，每次都隔一个老鼠吃，请给出最后一个老鼠的编号？题目要求是任给老鼠数n，输出猫最后吃的老鼠的编号。
二、问题求解
我们假设老鼠按顺时针方向编号，猫从第一号老鼠开始吃。比如现有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("%d\n",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);
}
这是小弟的代码，还请高手斧正。多多指教。
