2746-约瑟夫问题-模拟(但是可以优化)
方法
主流两种方法,像这种数据量n和m比较小,则直接模拟
其次是数学推导出规律《具体数学》一书,第一章有推导
其实,这个是约瑟夫问题,我们还是得知道方法二,也就是数学的
想想,要是不会,那时候约瑟夫在故事中就已经over了。。。
方法一,直接模拟
思想来源于,数据结构一书中,学循环队列的时候,取模
#include<stdio.h> #include<string.h> int main() { int array[301]={0};//表示数字在 int n,m; while((~scanf("%d%d",&n,&m))&&(0!=n)&&(0!=m)) { memset(array,0,sizeof(array)); int count=0;//表示数数字到几号了 int sum=0; int i=1;//当前序号 while(1) { //判断有没有被筛 if(0==array[i])//没有被筛掉了 { ++count; //数数字 } //判断需不需要筛掉 if(m==count) { array[i]=1; ++sum;//筛掉了一个 count=0;//继续下一次 } if(sum==(n-1)) { break; } ++i; if((n+1)==i) { i=1; } } for(i=1;i<=n;++i) { if(!array[i]) { printf("%d\n",i); } } } return 0; }