算法题目:
T个人围成一圈,依次报数第M个人离开,直到剩下一个人,求离开的次序或者最后离开的人
思路分析:
一共有T个人,因为每次到M个数,就会有人离开,所以某个人的下一个人和上一个人不是固定的,所以需要对每个人设置属性上一个人,下一个人,同时为了区分个人,需要个人下标,典型的双向链表数据结构。
//这里需要特别注意两个人,第0人的上一个是第T个和第T人的下一个是第0个
1 初始化: 第x人的下标是x,上一个人(parent)是x-1,下一个人(child)是x+1;
2 计算过程详解:从第0人开始数M个数,我们for循环迭代M次child,得到第M个人(t),然后修改t的上一个人的child为t的下一个人,修改t 的下一个人的parent为t的上一个人。循环此过程,最终剩余一个人
算法实现如下(使用双向链表):
struct Person {
int idx;
int parent;
int child;
};
-(void)getOnlyWithTotalP:(int)T outP:(int)M{
T = 100;
M = 11;
//init
struct Person all[T];
for (int i = 0; i < T; i ++) {
struct Person p;
p.idx = i;
if (i-1 < 0) {
p.parent = T-1;
}else{
p.parent = i-1;
}
if(i+1 == T){
p.child = 0;
}else{
p.child = i+1;
}
all[i] = p;
}
struct Person op = all[0];
int number = 0;
struct Person t = all[0];
do {
for (int i = 1; i < M; i++) {
t = all[t.child];
}
struct Person parentN = all[t.parent];
struct Person childN = all[t.child];
all[t.parent].child = childN.idx;
all[t.child].parent = parentN.idx;
number++;
NSLog(@"走---%d",t.idx);
// }while (number != T - 1);//走了T-2个人,剩下两个人后再执行一次
}while (t.parent != t.child);//当剩下两个人的时候会出现再执行一次
}