[抛砖引玉]一起来做道算法题吧。
有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# code
using 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时，把该节点入队，并删除该节点，当队列满时，出对。
[解决办法]
[解决办法]
这么好的东西以后要多多分享一下
[解决办法]
是数据结构中经典的约瑟夫问题
[解决办法]
[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);
}
}