注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

信息 灵感 创新

I? =Information,Inspiration,Innovation

 
 
 

日志

 
 
关于我

we are 5. Mathematics, Computation, Programming, Engineering, and Making fun of life.

网易考拉推荐

Josephus环问题的数组解法  

2011-07-21 11:53:37|  分类: C# & .NET |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
话说Josephus环问题作为数据结构中链表的演练程序,基本上在任何一本数据结构的书籍中都有所论述。今日试图使用以前就有的一个想法,尝试使用传统的数组来完成,当然,考虑到使用的简便性,就使用C#语言吧。
下面是代码:
using System;
namespace Josephus
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] ss = Josephus(13, 1, 4);
            foreach (int i in ss)
                Console.Write(i.ToString() + " ");
            Console.Read();
        }
        /*
         *已知n个人(以编号1,2,3...n分别表示)围坐在一张圆桌周围。
         *从编号为k的人开始报数,数到m的那个人出列
         *他的下一个人又从1开始报数,数到m的那个人又出列
         *依此规律重复下去,直到圆桌周围的人全部出列
         */
        public static int[] Josephus(int n, int k, int m)
        {
            int[] ret = new int[n];
            int[] ori = new int[n];
            for (int i = 0; i < n; i++)
                ori[i] = i + 1;
            int s = 0;
            int p = 0;
            int t = 1;//报数
            //先从编号为1的人开始报数
            while (s < n)
            {
                if (t % m == 0 && ori[p] != 0)//有出列
                {
                    ret[s] = ori[p];
                    ori[p] = 0;
                    t = 1;
                    p = (p + 1 + n) % n;
                    s++;
                }
                else if (t % m == 0 && ori[p] == 0)//本应出列,但已经出列,顺移下一个
                {
                    p = (p + 1 + n) % n;
                }
                else if (t % m != 0 && ori[p] == 0)//不出列,但是是已出列的元素
                {
                    p = (p + 1 + n) % n;
                }
                else//t % m != 0 && ori[p] != 0//不出列,也没有出过列
                {
                    t++;
                    p = (p + 1 + n) % n;
                }
            }
            //对于编号为k开始的报数,简单将结果顺移K-1位即可。
            for (int i = 0; i < n; i++)
            {
                ret[i] = (ret[i] + k - 1) % n;
                if (ret[i] == 0) ret[i] = n;
            }
            return ret;
        }
    }
}
值得一提的是,出列的时候将k开头直接无视,等都出列之后,就简单地使用相对位移法,每个都移动k-1位,这简化了思考过程。
运行结果,有图有真相:
Josephus环问题的数组解法 - Castor - 趁年轻,多折腾~~
 
  评论这张
 
阅读(1011)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2016