营销型网站建设公司推荐,一键网站建设,旅游产品设计方案,青州做网站电话题目描述
有#xff4e;(n100)个人依次围成一圈#xff0c;从第#xff11;个人开始报数#xff0c;数到第#xff4d;个人出列#xff0c;然后从出列的下一个人开始报数#xff0c;数到第#xff4d;个人又出列#xff0c;…#xff0c;如此反复到所有的人全部…题目描述
有(n100)个人依次围成一圈从第个人开始报数数到第个人出列然后从出列的下一个人开始报数数到第个人又出列…如此反复到所有的人全部出列为止。设个人的编号分别为12…n打印出列的顺序。
输入
n和m。
输出
出列的顺序。
样例输入
4 17
样例输出
1 3 4 2
我们可以看到这个围圈报数即约瑟夫问题其实就是链表问题。我们通过这道题需要掌握的是循环单链表的写法以c语言为例
一、循环链表的写法
1.先定义链表的结构体
struct child{int data;struct child* next;
};
然后再全局变量定 “头节点”和“约瑟夫环的两个参数”
struct child* headnode;
int n,m;
下面我们来定义两个函数分别是“创建空节点”与“创建有数据的节点”
struct child* emptynode(){struct child* p (struct child*)malloc(sizeof(struct child));p-data NULL;p-next NULL;return p;
}struct child* createnode(int num){struct child* p (struct child*)malloc(sizeof(struct child));p-data num;p-next NULL;return p;
}
我们可以看出这两段代码的主要差别其实就是p-dataNULL和p-datanum
接下来定义一个函数“createlistBytail”以尾接法创建循环单链表
void createlistBytail(struct child* headnode,int num){struct child* rheadnode;for (int i2; inum; i ){struct child* s createnode(i);s-next r-next;r-next s;rs;} r-next headnode;
}
其中需要注意的是这段代码看似为单纯的创建单链表其实我们在结尾处添加了一段代码
r-next headnode;
这段代码保证了单链表的循环也正因为这段代码使得我们的单链表成功升级为循环单链表
当然为了检验我们的链表是否创建成功我们可以写入这列代码来遍历出链表的数据
void printlist(struct child* headnode){struct child* pMove headnode;while(pMove) {printf(%d,pMove-data );pMove pMove-next ;}
} 接下来我们开始创建solve函数实现围圈报数功能
void solve(struct child* headnode,int n,int m){int i,j;struct child* p;struct child* q;for(i1;in;i){p headnode;j 1;for(j1;jm-1;j){p p-next ;}q p-next ;printf(%d ,q-data );p-next q-next ;headnode p-next ;}
}
其中我们需要注意的是 我们在进行第二个for循环时jm-1这个数值不要搞错。我们为什么要jm-1呢因为我们要保证p是在第m个人的前一个人这样我们就可以使q指向p-next,也就是我们想要的那个第m个人实现精准查找然后精准“删除”。但是问题来了我们为什么不直接将p指向第m个人呢这样我们直接输出p不就好了么:(。非也非也你只是想到了输出数值的事但是后面的事你却没能想到。
我们在这段函数的主要任务是什么呢1.输出第m个人2.删除m,让m前一个人接上m后一个人3.将领头人headnode变成m的下一个人也就是说从m的下一个人开始报数。这样我们不难发现我们将p设为m的前一个人是要将p-next指向q-next实现删除m的目的,因为我们节点的指针能指向某节点的后面,却指向不了节点的前面,所以哦我们需要这样的一个p指向m前一个点。
最后我们编写主函数将上面的函数包装进去
其中我们要注意的是创建空节点与数据节点不在主函数里。
int main(){struct child* headnode createnode(1);scanf(%d %d,n,m);createlistBytail(headnode,n);//printlist(headnode);solve(headnode,n,m);return 0;
}
这样我们的代码就算结束了。最后给大家奉上“围圈报数”即约瑟夫问题的完整版代码
#includestdio.h
#includestdlib.h
struct child{int data;struct child* next;
};struct child* headnode;
int n,m;struct child* emptynode(){struct child* p (struct child*)malloc(sizeof(struct child));p-data NULL;p-next NULL;return p;
}struct child* createnode(int num){struct child* p (struct child*)malloc(sizeof(struct child));p-data num;p-next NULL;return p;
}void createlistBytail(struct child* headnode,int num){struct child* rheadnode;for (int i2; inum; i ){struct child* s createnode(i);s-next r-next;r-next s;rs;} r-next headnode;
}void printlist(struct child* headnode){struct child* pMove headnode;while(pMove) {printf(%d,pMove-data );pMove pMove-next ;}
}void solve(struct child* headnode,int n,int m){int i,j;struct child* p;struct child* q;for(i1;in;i){p headnode;j 1;for(j1;jm-1;j){p p-next ;}q p-next ;printf(%d ,q-data );p-next q-next ;headnode p-next ;}
}int main(){struct child* headnode createnode(1);scanf(%d %d,n,m);createlistBytail(headnode,n);//printlist(headnode);solve(headnode,n,m);return 0;
}
