一道计算题

Question

100个人做游戏，让100个人围成一个大圈，每个人分别报数，报数方式是从1开始到7结束，报到7的人退出游戏，余下的人继续报数，从推出的下一个人开始从新报1 ，报7的人退出，一次循环，找出最终获胜选手。
大家试一下！挺有意思！

Answer 1

约瑟夫环问题，使用LinkedList实现即可。记得LinkedList是循环链表的。

Answer 2

两个类：Person.java   GetOut.java
Person.java 人类，包含一个名字属性，一个报数的方法
GetOut.java 计数类，包含一个队列，添加100个人进队列后，经过out()方法，剩下唯一的幸存者。
^_^    勇敢者游戏，I love this game !!附源程序：
/*
 *  Author   : Lislie
 *  Time     : 2007-9-13  19:32
 *  About    : 100个人做游戏，让100个人围成一个大圈，每个人分别报数，报数方式是从1开始到7结束，报到7的人退出游戏，余下的人继续报数，
 *     从推出的下一个人开始从新报1 ，报7的人退出，一次循环，找出最终获胜选手。
 *  Founction: class 人
 * 
 * */
package arithmetic.person;public class Person {
String name;

public Person(String name) {
this.name = name;
}

public int callNum(int a) {
return ++a;
}
}
/*
 *  Author   : Lislie
 *  Time     : 2007-9-13  19:32
 *  About    : 100个人做游戏，让100个人围成一个大圈，每个人分别报数，报数方式是从1开始到7结束，报到7的人退出游戏，余下的人继续报数，
 *     从推出的下一个人开始从新报1 ，报7的人退出，一次循环，找出最终获胜选手。
 *  Founction: 
 * 
 * */
package arithmetic.person;import java.util.ArrayList;public class GetOut {

ArrayList array; // 队列

public GetOut(int NUM) {
array = new ArrayList();

// 人类初始化,加入队列中
for(int i=0;i<NUM;i++) 
array.add(new Person("a" + i));
}

public Person out() {
int count = 0;   // 喊吧

while(array.size()>1) {
for(int i=0;i<array.size();i++) {
Person p = (Person)array.get(i);
count = p.callNum(count);

// 喊道7,出局  计数从新开始
if(count == 7) {
array.remove(i);
count = 0;   // 计数归0
}
}
}

// 唯一的幸存者
return (Person)array.get(0);
}

public static void main(String args[]) {
int NUM = 100;

GetOut go = new GetOut(NUM);
Person p = go.out();
System.out.println("My name is " + p.name + "!");
}
}运行结果：
My name is a58!

Answer 3

java有点忘了,给个C的算法吧.
10个人数2的.算法时间复杂度不大好.
这个问题的更好方法查看具体数学第一章.#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
int main()
{
int array[10] ={1,2,3,4,5,6,7,8,9,10};
int i = 0;
int fac = 0;
int count = 0;
for( ; ;)
{
if(count == 9)
break;
if(array[i] != 0)
if(fac == 1)
{
array[i] = 0;
i = (i+1)%10;
++count;
fac = 0;
}else
{
i = (i+1)%10;
++fac;
}
        else
         i = (i+1)%10;
} for(int i = 0; i < 10; ++i)
printf("%d\n",array[i]); return 0;
}

Answer 4

稍微调整得直观一点.
#include <stdio.h>int main()
{
int array[10] ={1,2,3,4,5,6,7,8,9,10};
int fac = 0;
int count = 0;
for( int i = 0; ;i = (i+1)%10)
{
if(count == 9)
break;
if(array[i] != 0)
if(fac == 1)
{
array[i] = 0;
++count;
fac = 0;
}else
++fac;
}
for(int i = 0; i < 10; ++i)
if(array[i] != 0)
printf("%d\n",array[i]); return 0;
}

Answer 5

http://community.csdn.net/Expert/topic/5738/5738951.xml?temp=7.319278E-02

Answer 6

改变了的变态算法.
编号是从0开始的,如果从1开始,返回值+1就好......public class KillMan { /**
 * @param args
 */
public static void main(String[] args) {
int liveNum=new KillMan().liveNum(100,7);
System.out.println("此人原来是"+liveNum+"号");
}

/*
 * @total 总人数 
 * @killNum 不幸运数字
 * */

private int liveNum(int total,int killNum){
String temp="";
for(int i=0;i<total;i++){
temp+=""+(char)(i+30000);
}
String tt=temp;
while(temp.length()!=1){
int ss=(killNum-1)%temp.length();
temp=ss==0?temp.substring(1):temp.substring(ss+1)+temp.substring(0,ss);
}
return tt.indexOf(temp);
}}

Answer 7

楼上 Good idea ！！
比用List子集，String的剪切来得更方便！更快捷！！

Answer 8

java编程当真不需要考虑效率吗?
对这种简单的问题也动用封装好的库.
字符的连接操作导致了多少字符的移位,被拷贝,有没有考虑过.

Answer 9

public Person out() {
int count = 0;   // 喊吧while(array.size()>1) {
for(int i=0;i<array.size();i++) {
Person p = (Person)array.get(i);
count = p.callNum(count);// 喊道7,出局  计数从新开始
if(count == 7) {
array.remove(i);
count = 0;   // 计数归0
}
}
这个不对,for结束时不一定是刚好喊到7,并且每次while判断后,都是第一个人从1喊,不符合lz要求的

Answer 10

这样才是对的:
public class Person {
String name;public Person(String name) {
this.name = name;
}public int callNum(int a) {
return ++a;
}
}
//----------------------------------------------
import java.util.ArrayList;public class GetOut {ArrayList <Person> array; // 队列public GetOut(int NUM) {
array = new ArrayList<Person>();// 人类初始化,加入队列中
for(int i=0;i<NUM;i++) 
array.add(new Person("a" + i));
}public Person out() {
int count = 0;   // 喊吧while(array.size()>1) {
int beginNum=0;
  for(int i=beginNum;i<array.size();i++) {
Person p =array.get(i);
count = p.callNum(count);// 喊道7,出局  计数从新开始
if(count == 7) {
array.remove(i);
count = 0;   // 计数归0
}  }
  beginNum=array.size()/7+1;}// 唯一的幸存者
return array.get(0);
}public static void main(String [] args) {
int NUM = 100;GetOut go = new GetOut(NUM);
Person p = go.out();
System.out.println("My name is " + p.name + "!");
}}

Answer 11

count是一直传递的，开始元素有100个，当到第7个人时，出局，array移除这个元素，而这个时候，array的size只有99了（ArrayList以数组方式存储数据，它允许直接按序号索引元素，但插入或删除元素涉及到数组元素的移动的内存操作，这个是它性能上的差距，比起前面几位兄弟的算法，要消耗资源)。这时，可能array的次序已经被打乱，因为第7个元素被删除了，第8个元素现在在第7个元素的位置上。但person类的name是不会变的。count归0，for循环并没有结束，继续.....当到完成99次比较，我们的count相对于这些类始终是保持“同步”，因为上一次报数，会被传给下一个即将报数者。虽然每次while循环都是从第一个人开始喊，但count是同步的，这个第一个只是你个人的感觉，报数的规则并没有被破坏.....我不认为算法有问题，如果有意见，你得拿出足够的理由说服我！只要我们的array的size大于1，循环就不会结束。

Answer 12

while(array.size()>1) {
　　int beginNum=0;
　　for(int i=beginNum;i<array.size();i++) {
　　　　Person p =array.get(i);
　　　　count = p.callNum(count);　　　　// 喊道7,出局  计数从新开始
　　　　if(count == 7) {
　　　　　　array.remove(i);
　　　　　　count = 0;   // 计数归0
　　　　}
　　}
　　beginNum=array.size()/7+1;
}你不觉得for循环结束后，虽然beginNum被赋值了，但在下一次while循环开始，int beginNum = 0又将它的值改为了0。这个地方的“beginNum=array.size()/7+1;”没有任何意义！！不信可以输出一下。

Answer 13

说一下我的思路：就是计算最后活下来那个人的位置一个for循环计算出每次出局人的位置，描述如下
begin = 0
for(i=1; i<n; i++) {
    kill[i] = (begin+7)%n;
    begin = (kill[i]+1)%n;
}
最后留下来的那个人位置肯定是0，那么逆着计算他的位置：
pos = 0
for(i=n-1; i>=1; i--) {
    if(kill[i]<=pos)
         pos += 1
}
这样就计算出那个人的位置了

Answer 14

sniperhuangwei() ( ) 信誉：99  2007-9-14 10:59:37  得分: 0  
 
 
   
java编程当真不需要考虑效率吗?
对这种简单的问题也动用封装好的库.
字符的连接操作导致了多少字符的移位,被拷贝,有没有考虑过. -------------------------------------------------------------没有考虑!我只考虑编程要的是思想,要灵活,我只是提供另外的思路而已.对于使用封装好的库而言,我觉得没有什么大不了的,有就用嘛,不然他封装了是放在那里好看的?没有必要为每一个功能自己去开发更多的类啊...[杀鸡就要用牛刀,打蚊子就喜欢用大炮]
我只是菜鸟,我追求的是随便找几只虫吃饱就好! 
 

Answer 15

#define nmax 50
main()
{
  int i,k,m,n,num[nmax],*p;
  printf("please input the total of numbers:");
  scanf("%d",&n);
  p=num;
  for(i=0;i<n;i++)
     *(p+i)=i+1;
  i=0;
  k=0;
  m=0;
  while(m<n-1)
  {
     if(*(p+i)!=0) k++;
     if(k==3)
       { *(p+i)=0;
         k=0;
         m++;
       }
    i++;
    if(i==n) i=0;
  }
 while(*p==0) p++;
  printf("%d is left\n",*p);
}
顶一下

Answer 16

今天找到高人的算法了!int fun(int n, int m) {
    int i, r = 0;
    for (i = 2; i <= n; i++)
        r = (r + m) % i;
    return r+1;
}不过我看不明白,但是运行结果没有问题.

Answer 17

对于数2出列的可以看下这个方法。
int ju(int n)
{
return (n == 1 ? 1 : (n%2 == 0 ? 2*ju(n/2)-1 : 2*ju(n/2)+1) );
}