//调整计数的长度Р if(m==0)m=alist.getLength();Р if(point+m-1<alist.getLength()){point=point+m-1;} //设置偏移位置Р else{point=point+m-alist.getLength()-1;}Р alist.setPos(point);//设置当前需要删除的位置Р alist.remove(elem);//删除元素Р cout<<elem<<" ";//DOS输出Р fout<<elem<<" ";//文件输出Р四、测试结果(截图显示)Р五、遇到的问题及解决方法Р1、初始化部分为循环赋值,时间复杂度为Θ(n)。Р2、处理部分,我为了提高效率没有采用循环寻找的方法,直接利用数学关系通过当前位置获得下一位置,因此对于长度为n的约瑟夫环,只做了n次定位,每次定位的复杂度为Θ(1),所以时间复杂度为Θ(n)。Р但是用顺序表实现时,每次其移除的方法是时间复杂度为Θ(k)的(k与实际长度有关),所以处理部分总的结果是()的,化简后时间复杂度仍然为Θ(n2)。Р综上,该算法的时间代价为Θ(n2)。Р(PS:如果是用循环查找,在n次定位中每次都使用了m次的循环,至少是Θ(n*m),然后再用顺序表的移除方法,总的复杂度应该是Θ(m*n2)的。)Р事实上要用线性表来完成这道题,其复杂度最好也是Θ(n2)的,毕竟对于n个数据,每个都要进行时间复杂度为Θ(n)的删除工作。欲到达Θ(n)的效率除非不用线性表来实现。Р六、体会Р输入人数n,报数间隔m,创建顺序表对象。Р确定需要删除的位置Р主程序Р!isEmpty () //顺序表不为空Р Remove()//调用删除方法Р输入和输出的格式:Р输入:10,3Р输出:3 6 9 2 7 1 8 5 10 4Р(文本中的输出):3 6 9 2 7 1 8 5 10 4
全文预览
