一道计算题
100个人做游戏，让100个人围成一个大圈，每个人分别报数，报数方式是从1开始到7结束，报到7的人退出游戏，余下的人继续报数，从推出的下一个人开始从新报1 ，报7的人退出，一次循环，找出最终获胜选手。
大家试一下！挺有意思！
[解决办法]
约瑟夫环问题，使用LinkedList实现即可。
记得LinkedList是循环链表的。
[解决办法]
两个类：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!
[解决办法]
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;
}
[解决办法]
http://community.csdn.net/Expert/topic/5738/5738951.xml?temp=7.319278E-02
[解决办法]
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要求的
[解决办法]
学习一下。
[解决办法]
好象学C的时候做过
[解决办法]
说一下我的思路：就是计算最后活下来那个人的位置
一个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
}
这样就计算出那个人的位置了
[解决办法]
这不约瑟夫环么？老掉牙的问题了，用链表来做吧
[解决办法]
#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);
}
顶一下
