一道华为面试题的分析(约瑟夫问题)17P.doc

/*据说是华为面试的一道题目:有一个数组a1000存放1000(干扰);要求每隔二个数删掉一个数，到末尾时循环至开头继续进行，求最后一个被删掉的数的原始下标位置。 以个数为例： 0,1,2,3,4,5,6,7 (干扰,其实完全没有必要非得从0-(n-1) 0-1-2（删除）-3-4-5(删除)-6-7-0（删除），如此循环直到最后一个数被删除。 程序就不写1000数组的了,10个元素吧,解决问题即可*/#include #include #include using namespace std;int deleted(int a,const int size,const int cnt)assert(a!=NULL&size0&cnt0);/该for循环并非算法必须for(int i=0;isize;i+)ai=i;int curCnt=0;int Deleted;int DelCnt=0;int flag=-1; do for(int i=0;isize;i+) /* 在遍历过程中,只要遇到不是flag的数字,计数器+1 当计数器=cnt时,删除当前数字(置为flag),将下标记录到delete,同时增加已经删除的个数DelCnt,重置计数器curCnt=0; */ if(ai!=flag) curCnt+; if(curCnt=cnt) ai=flag; Deleted=i; DelCnt+; curCnt=0; if(size=DelCnt)break; /以下代码显示当前数组情况 /* for(int i=0;isize;i+) coutai,; coutendl; */ while(size!=DelCnt); return Deleted;int main() int b10=0,1,2,3,4,5,6,7,8,9; cout最后一个删除的数组元素的下标:deleted(b,10,3)0&intCnt0); for(int i=0;iintSize-1;i+)aryProci=i+1; aryProcintSize-1=0; /* 声明四个变量 intRemain 当前剩下的有效节点 intDeleted 最后删除的一个节点的下标 intCurrent 指向当前元素的指针 intCurCnt 计数器 */ int intRemain,intDeleted,intCurrent,intCurCnt; intRemain=intSize; intDeleted=-1; intCurrent=0; intCurCnt=0; do /当前节点有效的标准是:不为-1(FLAG) if(aryProcintCurrent!=FLAG) /又发现一个活着的.嘻嘻 intCurCnt+; if(intCnt-intCurCnt=1) /删除后一个,主要是将当前节点的向量指向下一个节点的下一个节点 intDeleted=aryProcintCurrent; aryProcintCurrent=aryProcintDeleted; aryProcintDeleted=-1; intRemain-; intCurCnt=0; intCurrent=aryProcintCurrent;/当删除最后一个元素后,intCurrent变为-1,幸好后面已经不再使用该值来访问数组. while(intRemain!=0); return intDeleted;修改一下main函数,做个测试,看看我自己一开始写的”代码”和后来的函数int main() int a10000; int b1; int c3; int d10; int e3; int f5; int g8; clock_t start,finish; coutA: 使用flag作为删除标志,遍历数组进行删除操作endl; coutB: 使用向量数组,把数组作为链表来使用,仿照链表进行删除操作endlendl; cout正确性验证(可以自己数一下)endl; coutA: b1, 步长为最后一个删除的数组元素的下标:deleted(b,1,3)endl; coutB: b1, 步长为最后一个删除的数组元素的下标:joseph(b,1,3)endlendl; coutA: c3, 步长为最后一个删除的数组元素的下标:deleted(c,3,3)endl; coutB: c3, 步长为最后一个删除的数组元素的下标:joseph(c,3,3)endlendl; coutA: d10,步长为最后一个删除的数组元素的下标:deleted(d,10,3)endl; coutB: d10,步长为最后一个删除的数组元素的下标:joseph(d,10,3)endlendl; coutA: e3, 步长为最后一个删除的数组元素的下标:deleted(e,3,4)endl; coutB: e3, 步长为最后一个删除的数组元素的下标:joseph(e,3,4)endlendl; coutA: f5, 步长为最后一个删除的数组元素的下标:deleted(f,5,4)endl; coutB: f5, 步长为最后一个删除的数组元素的下标:joseph(f,5,4)endlendl; coutA: g8, 步长为最后一个删除的数组元素的下标:deleted(g,8,4)endl; coutB: g8, 步长为最后一个删除的数组元素的下标:joseph(g,8,4)endlendlendl; cout效率验证endl; start=clock(); for(int i=0;i1000;i+)deleted(a,10000,3); finish=clock(); coutA: a10000 步长为约瑟夫问题的次解决时间:(double)(finish-start)/1000endl; start=clock(); for(int i=0;i1000;i+)joseph(a,10000,3); finish=clock(); coutB: a10000 步长为约瑟夫问题的次解决时间:(double)(finish-start)/1000endlendl; start=clock(); for(int i=0;i10000;i+)deleted(a,10000,3); finish=clock(); coutA: a10000 步长为约瑟夫问题的次解决时间:(double)(finish-start)/1000endl; start=clock(); for(int i=0;i10000;i+)joseph(a,10000,3); finish=clock(); coutB: a10000 步长为约瑟夫问题的次解决时间:(double)(finish-start)/1000endlendl; start=clock(); for(int i=0;i1000;i+)deleted(a,10000,5); finish=clock(); coutA: a10000 步长为约瑟夫问题的次解决时间:(double)(finish-start)/1000endl; start=clock(); for(int i=0;i1000;i+)joseph(a,10000,5); finish=clock(); coutB: a10000 步长为约瑟夫问题的次解决时间:(double)(finish-start)/1000endlendl; start=clock(); for(int i=0;i1000;i+)deleted(a,10000,100); finish=clock(); coutA: a10000 步长为约瑟夫问题的次解决时间:(double)(finish-start)/1000endl; start=clock(); for(int i=0;i1000;i+)joseph(a,10000,100); finish=clock(); coutB: a10000 步长为约瑟夫问题的次解决时间:(double)(finish-start)/1000endlendl; system(pause); return 0;/*运行结果如下:A: 使用flag作为删除标志,遍历数组进行删除操作B: 使用向量数组,把数组作为链表来使用,仿照链表进行删除操作正确性验证(可以自己数一下)A: b1, 步长为3 最后一个删除的数组元素的下标:0B: b1, 步长为3 最后一个删除的数组元素的下标:0A: c3, 步长为3 最后一个删除的数组元素的下标:1B: c3, 步长为3 最后一个删除的数组元素的下标:1A: d10,步长为3 最后一个删除的数组元素的下标:3B: d10,步长为3 最后一个删除的数组元素的下标:3A: e3, 步长为4 最后一个删除的数组元素的下标:1B: e3, 步长为4 最后一个删除的数组元素的下标:1A: f5, 步长为4 最后一个删除的数组元素的下标:0B: f5, 步长为4 最后一个删除的数组元素的下标:0A: g8, 步长为4 最后一个删除的数组元素的下标:5B: g8, 步长为4 最后一个删除的数组元素的下标:5效率验证A: a10000 步长为3 约瑟夫问题的1000次解决时间:1.219B: a10000 步长为3 约瑟夫问题的1000次解决时间:0.343A: a10000 步长为3 约瑟夫问题的10000次解决时间:12.125B: