- 论坛徽章:
- 0
|
5可用积分
要求如下：
有一只猫抓了n (n>1)个老鼠后向老鼠宣布：老鼠按自然数进行编号（1～n），并按自然数顺序排队，以后先后次序不准变；于是猫每天吃掉编号为奇数的老鼠，剩下的老鼠再按原次序进行自然数编号，直至某一天只剩下一只小老鼠；而该小老鼠是猫从第一天起就想吃掉的那只，请问这只小老鼠的最初编号是几？
我的程序如下：
#include <iostream.h>
#include <assert.h>
struct mouse //链“节点”类声明
{
int n;
mouse *nextptr;
};
int cat_mouse(int num) //函数定义
{
mouse *headptr=0,*tailptr=0,*frontptr,*p;
int i;
//先把1个老鼠加入链作为链首节点
headptr=tailptr=new mouse;
assert(headptr!=NULL); //动态内存分配异常处理
headptr->n=1; //老鼠的编号
headptr->nextptr=NULL;
//在链尾再添加n-1个老鼠
for(i=2;i<=num;++i)
{p=new mouse;
assert(p!=NULL);
p->n=i;
cout<<p->n<<" ";
tailptr->nextptr=p;
tailptr=p;
}
tailptr->nextptr=NULL; //设置链尾节点的“下一节点地址”为空
//开始删除老鼠
while(headptr!=tailptr) //每循环一次，删除链上的奇节点，直至只剩下１个节点
{ p=headptr->nextptr; //链的首节点总是先被删除
delete headptr; //析构首节点
headptr=frontptr=p; //本次循环的第２个节点成为链的首节点
i=２; //从第２个节点开始循环：删除链的奇节点
while(p!=NULL) //从２开始循环至链尾节点
{if((i%2)==１) //是奇节点
{if (p->nextptr==NULL) //如果该奇节点是最后一个节点
{frontptr->nextptr=NULL; //前一节点成为链的尾节点
tailptr=frontptr;
delete p;
p=NULL; //因本循环的判断条件是p!=NULL,到链尾，所以置为０
}
else //是奇节点但不是尾节点，删除
{frontptr->nextptr=p->nextptr; //从链上删除该奇节点
delete p;
p=frontptr->nextptr; //下一节点的地址已保存在frontPtr的nextPtr中
++i;
}
}
else
{frontptr=p;
p=p->nextptr;
++i;
}
}
}
return headptr->n; //返回最后一个节点的编号
}
void main() //主函数
{
int i, num;
do{cout<<"\n请输入老鼠的只数（大于1，输入0退出）：";
cin>>num;
if(num>1)
{i=cat_mouse(num);
cout<<"最后剩下的一只老鼠是："<<i<<endl;
}
}while(num!=0);
}
为何运行算法后只剩一只老鼠时，不管我输入多少数字 那老鼠的最初编号总为1？？？
还有如果猫每天吃掉编号为偶数的老鼠 那老鼠的最初编号是几？如何改程序，我是新手请大家指点下，谢谢了!! |
|
免费注册
发表于 2007-10-31 10:27
发表于 2007-10-31 10:27
