创的技术博客
C++对我而言就是有STL带class能处理多态,继承的C.
问题描述:约瑟夫环
 有编号从1到N的N个人坐成一圈报数,报到M的人出局,下一位再从1开始,
 如此持续,直止剩下一位为止,报告此人的编号X。输入N,M,求出X。

常规的解法,简单描述一下,就不写算法了.用所有的元素生成一个循环链表,第一次从第一个向前走M步,将当前元素分离出链表,然后从下一个元素开始走M步,再将当前元素分离出链表,重复以上过程,直到链表中只有一个元素时即为所求.

递归的解法:
int f(int n, int m)
{
  
if (n > 1)
    return (m 
+ f(n - 1, m)) % m;
  
else
    return 
0;
}

非递归的解法,很巧妙:
int f(int n, int m)
{
    
int i, r = 0;
    
for (i = 2; i <= n; i++)
        r 
= (r + m) % i;
    return r
+1;
}
posted on 2007-12-29 00:05 阅读(1148) 评论(4)  编辑 收藏 引用 所属分类: 算法与数据结构
Comments

标题  
姓名  
主页
验证码 *
内容(提交失败后,可以通过“恢复上次提交”恢复刚刚提交的内容)  
  登录  使用高级评论  新用户注册  返回页首  恢复上次提交      
[使用Ctrl+Enter键可以直接提交]