[抛砖引玉]一起来做道算法题吧。解决方案

2012-01-19

[抛砖引玉]一起来做道算法题吧。有n个孩子（编号1,2...n）围成一圈，现在从编号为k的孩子开始报数，当报数到m时

[抛砖引玉]一起来做道算法题吧。
有n个孩子（编号1,2...n）围成一圈，现在从编号为k的孩子开始报数，当报数到m时，报m的那个孩子出列，然后从报m的那个孩子的下一个孩子重新开始从1报数...
求：孩子们出列的序列。

以上是题目，我自己实现了一下，感觉不好，但测试了几个，序列还是正确的，现贴出来，希望和大家讨论以后能够得到更精妙的算法。本人算法实在是太差了。

C# code

static void Main(string[] args)        {            int[] a = new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };            OutQueue(a, 2, 4);        }        static void OutQueue(int[] obj, int k, int m)        {            if (obj == null || obj.Length == 0)                return;            if (k < 1 || k > obj.Length)            {                Console.WriteLine("K value is invalid!");                return;            }            if (m <= 0)            {                Console.WriteLine("m value is invalid!");                return;            }            int count = 0;               //同m比较，数到m就输出当前位置            int mod = m % obj.Length == 0 ? obj.Length : m % obj.Length;    //防止m超过数组长度，取模代替之            int index = k-1;               //存放当前的index,为什么要-1？因为数组下标从0开始            int got = 0;            while (got < obj.Length - 1)            {                count = 1;                for (int j = 0; j < mod; j++)                {                    if (count == mod)                    {                        while (obj[index % obj.Length] == 0)                            index++;                        Console.WriteLine("The {0} person is out of queue!", index % obj.Length + 1);                        got++;                        obj[index % obj.Length] = 0;                    }                    count++;                    index++;                }            }            for (int i = 0; i < obj.Length; i++)            {                if (obj[index % obj.Length] != 0)                    Console.WriteLine("The {0} person is out of queue!", index % obj.Length + 1);                index++;            }        }

输出结果：

XML code

The 5 person is out of queue!The 9 person is out of queue!The 2 person is out of queue!The 6 person is out of queue!The 10 person is out of queue!The 3 person is out of queue!The 7 person is out of queue!The 11 person is out of queue!The 4 person is out of queue!The 8 person is out of queue!The 1 person is out of queue!

[解决办法]
约瑟夫环
[解决办法]
网上找的：

C++版
int fun(int n, int m)
{

int i, r = 0;

for (i = 2; i <= n; i++)

r = (r + m) % i;

return r+1;

}

循环链表解决

优化
[解决办法]
类似于猴子选大王问题: 一堆猴子都有编号，编号是1，2，3 ...m ,这群猴子（m个）按照1到m的顺序围坐一圈，

从第1开始数，每数到第n个，该猴子就要离开此圈，这样依次下来，直到圈中只剩下最后一只猴子，则该猴子为大王

C# code

using System;using System.Collections.Generic;using System.Text;namespace ExMonkey{    class Monkey    {        public int King(int M, int N)        {            //总人数 M ，数到第 N 个排除。             int k=0;            for (int i = 2; i <= M; i++)                k = (k + N) % i;            return ++k;        }        static void Main(string[] args)        {            Monkey M = new Monkey();            Console.WriteLine ("第"+M.King(10,3)+"号猴子为大王。");        }    }}
[解决办法]
只要排成队的增插删改一律用链表，高效。
[解决办法]
using System;  
 
using System.Collections.Generic; 
using System.Text; 

namespace Monkey 
{ 
 class Program 
 { 
 static void Main(string[] args) 
 { 
 int num; 
 num=Monkey(3, 1, 2); 
 Console.WriteLine(num); 
 Console.ReadKey(); 
 } 

 static int Monkey(int sum, int diJiGe, int shuDaoJi) 
 { 
 int paiChu=0; 
 int i =diJiGe - 1; 
 int k = 0; 
 int [] myMonkey=new int [sum]; 
 while ((sum - paiChu) != 1) 
 { 
 if (myMonkey[i] == 0) 
 { 
 k = k + 1; 
 if (k == shuDaoJi) 
 { 
 myMonkey[i] = 1; 
 k = 0; 
 paiChu = paiChu + 1; 
 } 
 } 
 i = i + 1; 
 if (i > (sum - 1)) 
 i = 0; 
 } 
 int m=0; 
 for (int j = 0; j < myMonkey.Length; j++) 
 { 
 if (myMonkey[j] == 0) 
 m = i; 
 } 
 return m+1; 
 } 
 } 
} 
循环链表解决(约瑟夫环算法) 
class ClassJose    {
       //从第start人开始计数，以alter为单位循环记数出列，总人数为total  
       public int[] Jose(int total, int start,int alter)
       {
           int j, k = 0;
           //count数组存储按出列顺序的数据，以当结果返回  
           int[] count = new int[total + 1];
           //s数组存储初始数据  
           int[] s = new int[total + 1];
           //对数组s赋初值,第一个人序号为0,第二人为1，依此下去
           for (int i = 0; i < total; i++)
           {
               s[i] = i;
           }
           //按出列次序依次存于数组count中  
           for (int i = total; i >= 2; i--)
           {
               start = (start + alter - 1) % i;
               if (start == 0)
                   start = i;
               count[k] = s[start];
               k++;
               for (j = start + 1; j <= i; j++)
                   s[j - 1] = s[j];
           }
           count[k] = s[1];
           //结果返回  
           return count;
       }

       static void Main(string[] args)
       {
           ClassJose    e=new ClassJose     ();
           int[] a = e.Jose(10,3,4);
           for (int i = 0; i < a.Length; i++)
           {
               Console.WriteLine(a[i].ToString ());
           }
       }

[解决办法]
基本约瑟夫问题，有公式的，直接可以计算。可惜忘记了。
[解决办法]
各位大哥,你们写的好复杂,让我看的有点头晕!我自己写了一个,
C# codeusing System;using System.Collections.Generic;using System.Text;class Myclass{    static void Main(string[] args)   {     int[] a = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };     OutQueue(a,2,4);   }   static void OutQueue(int[] obj,int k,int m)   {      int x=0;     for(int i=0;i<obj.Length;i++)   {      x=k+m;      if(x>12)       {         x=x-13;       }       else       {         x=x-2;       }       Console.WriteLine("The {0} person is out of queue!", obj[x]);       if(x+1>10)       {          k=obj[x-10];       }       else       {          k=obj[x+1];        }     }   }}
[解决办法]
C# code        static void Main(string[] args)        {            int n,k,m;            n=11;            k=2;            m=4;            Queue<int> q = new Queue<int>();            for (int i = k; i <= n; ++i) q.Enqueue(i);            for (int i = 1; i < k; ++i) q.Enqueue(i);            int c=0;            while (q.Count > 0)            {                int t = q.Dequeue();                ++c;                if (c != m)                 {                    q.Enqueue(t);                }                else                {                    Console.WriteLine("The " + t + " person is out of queue!");                    c = 0;                }            }            Console.ReadKey();        } 
 
[解决办法]
static void Main(string[] args)
       {
           int[] a = new int[] { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
           OutQueue(a, 2, 4);
       }

       static void OutQueue(int[] obj, int k, int m)
       {
           if (obj == null || obj.Length == 0)
               return;
           if (k < 1 || k > obj.Length)
           {
               Console.WriteLine("K value is invalid!");
               return;
           }
           if (m <= 0)
           {
               Console.WriteLine("m value is invalid!");
               return;
           }

           int count = 0;               //同m比较，数到m就输出当前位置
           int mod = m % obj.Length == 0 ? obj.Length : m % obj.Length;    //防止m超过数组长度，取模代替之
           int index = k-1;               //存放当前的index,为什么要-1？因为数组下标从0开始
           int got = 0;

           while (got < obj.Length - 1)
           {
               count = 1;
               for (int j = 0; j < mod; j++)
               {
                   if (count == mod)
                   {
                       while (obj[index % obj.Length] == 0)
                           index++;
                       Console.WriteLine("The {0} person is out of queue!", index % obj.Length + 1);
                       got++;
                       obj[index % obj.Length] = 0;
                   }
                   count++;
                   index++;
               }
           }


           for (int i = 0; i < obj.Length; i++)
           {
               if (obj[index % obj.Length] != 0)
                   Console.WriteLine("The {0} person is out of queue!", index % obj.Length + 1);
               index++;
           }
       }



输出结果：
XML code

The 5 person is out of queue!
The 9 person is out of queue!
The 2 person is out of queue!
The 6 person is out of queue!
The 10 person is out of queue!
The 3 person is out of queue!
The 7 person is out of queue!
The 11 person is out of queue!
The 4 person is out of queue!
The 8 person is out of queue!
The 1 person is out of queue!
[解决办法]
呵呵,这个我以前做过,用两维数组最快,一维数组次之,然后是一维数组指针,然后是二维数组指针,链表最慢
但是用二维数组和一组数组必须得提前知道有多少个人,所以有局限性,个人觉得用一维数组指针最好

附:本人以前是用C做的,可能这种实现方法的测试结果与别的语言实现有些不同
[解决办法]
其他的没细看，感觉25楼的程序是错误的！可以手工演示一下看看结果！
[解决办法]
探讨

以上是题目，我自己实现了一下，感觉不好，但测试了几个，序列还是正确的，现贴出来，希望和大家讨论以后能够得到更精妙的算法。本人算法实在是太差了。

[解决办法]
把n个孩子挂在一个节点数是n的链表上，在建立一个n长度的队列，定义一个计数器，遍历链表，不停计数，当计数到m时，把该节点入队，并删除该节点，当队列满时，出对。
[解决办法]
探讨
有n个孩子（编号1,2...n）围成一圈，现在从编号为k的孩子开始报数，当报数到m时，报m的那个孩子出列，然后从报m的那个孩子的下一个孩子重新开始从1报数...
求：孩子们出列的序列。

以上是题目，我自己实现了一下，感觉不好，但测试了几个，序列还是正确的，现贴出来，希望和大家讨论以后能够得到更精妙的算法。本人算法实在是太差了。


C# code

static void Mai……

[解决办法]
这么好的东西以后要多多分享一下
[解决办法]
是数据结构中经典的约瑟夫问题
[解决办法]
[code=C/C++][/code] 
 
#include <iostream.h>
const int num=17;
void main()
{
 int interval=3;
 int a[num];
 for(int i=0; i<num; i++)
   cout <<(a[i]=i+1) <<",";
 cout <<endl;
 i=(interval-1)%num;
 for(int k=1; k<num; k++){
   cout <<a[i] <<",";
   a[i]=0;
   for(int j=1; !(a[i]&&(j++==interval)); i=(i+1)%num);  //数数
 }
 cout <<"\nNo." <<a[i] <<" boy has won.\n";    //输出胜利者
}
[解决办法]
我也写了一个，参考参考
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace 算法
{
   class Program
   {
       static void Main(string[] args)
       {
          PaiXu(11,5);
           Console.ReadLine();
       }
       public static void PaiXu(int n,int m)
       {
           List<Penson> pensons=new List<Penson>();
           for(int i=0;i<n;i++)
           {
            Penson penson=new Penson();
               pensons.Add(penson);
           }
           for(int i=0;i<n;i++)
           {
             
               if(i<n-1)
               {
                   pensons[i].num = i;
                   pensons[i].Next = pensons[i+1];  
               }
               if (i == n - 1)
               {
                   pensons[i].num = i;
                   pensons[i].Next = pensons[0];  
               }
           }
           A a=new A(pensons);
           int k = m%a.pensons.Count;
           int j;
           while (a.pensons.Count>0)
           {
               j = m%a.pensons.Count;
              a.pensons= a.Delete(j);
              if (a.pensons.Count > 0)
              {
                  j = (j == 0) ? a.pensons.Count+1 : j;
                  m = (j + k - 1) % a.pensons.Count;
              }
                
              
           }
       }
   }
   public class Penson
   {
       public int num { get; set; }
       public Penson Next { get; set; }
      
   }
   public class A
   {
       private List<Penson> listP;
       public A(List<Penson> ps)
       {
           listP = ps;
       }
       public List<Penson> pensons  
       {  
           get
           {
               return listP;
           }
           set
           {
               listP = value;
           }
       }
       public List<Penson> Delete(int m)
       {
            if(m==0)
           {
               Console.Write("{0},", pensons[pensons.Count - 1].num+1);
               if (pensons.Count >= 2)
                   pensons[pensons.Count - 2].Next = pensons[0];
               pensons.RemoveAt(pensons.Count - 1);
           }
            else  if(m==1)
           {
               Console.Write("{0},", pensons[m - 1].num+1);
               if(pensons.Count>=2)
               pensons[pensons.Count - 1].Next = pensons[m];
               pensons.RemoveAt(m - 1);
           }
           else if(m-1<pensons.Count-1)
           {
               Console.Write("{0},", pensons[m-1].num+1);
               if (pensons.Count >= 2)
               pensons[m - 2].Next = pensons[m];
               pensons.RemoveAt(m - 1);
           }
         
          
           return pensons;
       }
   }
}
[解决办法]
public class CountGame {
private static boolean same(int[] p, int l, int n) { 
 
for (int i = 0; i < l; i++) {
if (p[i] == n) {
return true;
}
}
return false;
}

public static void play(int playerNum, int step) {
int[] p = new int[playerNum];
int counter = 1;
while (true) {
if (counter > playerNum * step) {
break;
}
for (int i = 1; i < playerNum + 1; i++) {
while (true) {
if (same(p, playerNum, i) == false){
break;
}else{
i = i + 1;
}
}
if (i > playerNum){
break;
}
if (counter % step == 0) {
System.out.print(i + " ");
p[counter / step - 1] = i;
}
counter += 1;
}
}
System.out.println();
}

public static void main(String[] args) {
play(10, 7);
}

}

热点排行