网站备案 接电话,怎样做移动端网站,西安做效果图的公司,wordpress 兼容ie约瑟夫环#xff08;约瑟夫问题#xff09;是一个数学的应用问题#xff1a;已知n个人#xff08;以编号1#xff0c;2#xff0c;3...n分别表示#xff09;围坐在一张圆桌周围。从编号为k的人开始报数#xff0c;数到m的那个人出列#xff1b;他的下一个人又从1开始报…约瑟夫环约瑟夫问题是一个数学的应用问题已知n个人以编号123...n分别表示围坐在一张圆桌周围。从编号为k的人开始报数数到m的那个人出列他的下一个人又从1开始报数数到m的那个人又出列依此规律重复下去直到圆桌周围的人全部出列。 约瑟夫环运作如下
1、一群人围在一起坐成环状如N
2、从某个编号开始报数如S
3、数到某个数如M的时候此人出列下一个人重新报数
4、一直循环直到所有人出列 约瑟夫环结束
模拟过程求出最后的人。
把数组看成一个环从第s个元素开始按m-1间隔删除元素重复过程直到元素全部去掉。 void Josephus(int a[],int n,int m,int s)
{int i,j;int kn;for(i0;in;i)a[i]i1;//编号i(sn-1)%n;while(k){for(j1;jm;j)i(i1)%k;//依次报数头尾相连printf(%d\n,a[i]);//出局for(ji1;jk;j)a[j-1]a[j];//删除本节点k--;}//模拟结束最后输出的就是留下的人
} 可以用带头单循环链表来求解
也是一样的只是实现不同给出核心代码 while(k){for(j1;jm;j){prp;pp-link;if(phead)//头结点跳过{prp;pp-link;}}k--;//打印pr-linkp-link;//删结点free(p);ppr-link;//从下一个继续}
双向循环链表也可以解和单链表类似只是不需要保持前趋指针。 数学可解
效率最高 int check_last_del(int n,int m)
{int i 1;int ret 0;for (i 2; in;i)ret (ret m) %i;return ret1;//因为ret是从0到n-1最后别忘了加1。
}
