经典算法 看大家的基本功是否扎实

Question

这约瑟夫也能叫经典算法。。我觉得就一简单的数学分析
public static void main(String[] args) {
int n = 500, m = 3;
int index = 0;

for (int i = 2; i <= n; i++) {
index = (index + m) % i;
}

System.out.println(index + 1);
}

Answer 1

答案是第436个小孩

List<Integer> ch=new ArrayList<Integer>();   //用一个List来存放500个小孩
for(int i=1;i<=500;i++){
ch.add(i);
}
int temp=0;
for(int j=0;j<ch.size();j++){//遍历List
temp++;//代表数数
if(temp==3){   //如果是数到3则把这个小孩从List中移除 并从1开始数（temp=0)
ch.remove(j);
j--;
temp=0;
}
if(j==ch.size()-1)//如果遍历到最后一个则重新开始遍历  j=-1 因为j++ 所以是从j=0开始重新遍历
j=-1;
if(ch.size()==1)//最后List的大小为1  则只剩下最后一个小孩 打印出来 结束
{
System.out.println(ch.get(0));
break;
}
}

Answer 2

答案是第436个小孩
List<Integer> ch=new ArrayList<Integer>();   //用一个List来存放500个小孩
for(int i=1;i<=500;i++){
ch.add(i);
}
int temp=0;
for(int j=0;j<ch.size();j++){//遍历List
temp++;//代表数数
if(temp==3){   //如果是数到3则把这个小孩从List中移除 并从1开始数（temp=0)
ch.remove(j);
j--;
temp=0;
}
if(j==ch.size()-1)//如果遍历到最后一个则重新开始遍历  j=-1 因为j++ 所以是从j=0开始重新遍历
j=-1;
if(ch.size()==1)//最后List的大小为1  则只剩下最后一个小孩 打印出来 结束
{
System.out.println(ch.get(0));
break;
}
}

Answer 3

boolean[] result=new boolean[500];//被选过就是true
int count=0,have=500,i=0;count是数数，have是还有多少个,i是标有志位置
while(true){
if(!result[i]){//没有被选过
if(++count==3){//增加个数，如果够3个
if(--have==0){//如果已经剩下0个就是他.
System.out.print(++i);//计算机从0计算的，实际中+1
return;
}else{
count=0;//从0开始
result[i]=true;//被选中

}
}
}
if(i==499)
i=0;
else
i++;
}

Answer 4

/*
 * 500个小孩围成一圈，从第一个开始报数：
 * 1,2,3,1,2,3,1,2,3……每次报3的小孩退出
 * 问最后剩下的那个小孩，在以前500人里是第几个？
 */
import java.util.*;/* 用ArrayList解决小孩围圈问题 */
public class ChildrenCircleArrayList {    public static void main(final String[] args) {
        int numberOfChildren = 500; // 小孩总数
        int quitNo = 3; // 报quitNo的小孩退出
        System.out.println(
                numberOfChildren + "个小孩，报"
                + quitNo + "的退出，剩下的是第"
                + getCountOffResult(numberOfChildren, quitNo) + "个小孩");
    }    /**
     * 获得报数结果
     *
     * @param numberOfChildren 小孩总数
     * @param quitNo 报quitNo的小孩退出
     * @return 剩下的是第几个小孩
     */
    private static int getCountOffResult(int numberOfChildren, int quitNo) {
        // 入口参数检查
        if (numberOfChildren <= 0 || quitNo <= 0) {
            return 0;
        }        // 定义并生成小孩数组列表，编号从1到numberOfChildren
        ArrayList<Integer> children = new ArrayList<>(numberOfChildren);
        for (int ii = 1; ii <= numberOfChildren; ii++) {
            children.add(ii);
        }        // 报数处理开始
        int callRollIndex = 0;
        while (children.size() > 1) { // 当剩下的小孩数大于1时
            callRollIndex = (callRollIndex + quitNo - 1) % children.size();
            // 可以打开下面的注释，查看详细的执行过程
            // System.out.println("第" + children.get(callRollIndex) + "个小孩已经退出");
            children.remove(callRollIndex);
        }
        return children.get(0);
    }
}
执行结果：
500个小孩，报3的退出，剩下的是第436个小孩

Answer 5

static void Main(string[] args)
        {
            int iNum = GetLastChild(500, 3);
            Console.WriteLine("剩下的孩子编号为："+iNum);
            Console.ReadLine();
            
        }
        static private int GetLastChild(int nums, int no)
        {
            int iStart = 0;
            int iNo=1;  // 第几个退出的孩子            List<int> childs = new List<int>();            
            // 添加
            for (int i = 1; i <= nums; i++)
            {
                childs.Add(i);
            }
            // 循环剔除
            while (childs.Count>1)
            {
                
                iStart += no - 1;
                if (iStart >= childs.Count) iStart -= childs.Count; // 一圈结束了，开始新的一圈
                
                Console.WriteLine("第"+iNo+"个退出的孩子。编号："+childs[iStart]+"，为本轮的第"+iStart+"个。");
                childs.RemoveAt(iStart);
                iNo++;
                iStart++;            }
            return childs[0];
        }
=====================
我怎么算的是449？

Answer 6

刚才那个错了，应该是436.
static private int GetLastChild(int nums, int no)
        {
            int iStart = 0;
            int iNo=1;  // 第几个退出的孩子            List<int> childs = new List<int>();            
            // 添加
            for (int i = 1; i <= nums; i++)
            {
                childs.Add(i);
            }
            // 循环剔除
            while (childs.Count>1)
            {
                
                iStart += no - 1;
                while (iStart >= childs.Count) iStart -= childs.Count; // 一圈结束了，开始新的一圈
                
                Console.WriteLine("第"+iNo+"个退出的孩子。编号："+childs[iStart]+"，为本轮的第"+iStart+"个。");
                childs.RemoveAt(iStart);
                iNo++;
                //iStart++;            }
            return childs[0];
        }

Answer 7

再简化：
static private int GetLastChild(int nums, int no)
        {
            int iStart = 0;
            int iNo=1;  // 第几个退出的孩子            List<int> childs = new List<int>();            
            // 添加
            for (int i = 1; i <= nums; i++)
            {
                childs.Add(i);
            }
            // 循环剔除
            while (childs.Count>1)
            {
                iStart = (iStart + no - 1) % childs.Count;
                Console.WriteLine("第"+iNo+"个退出的孩子。编号："+childs[iStart]+"，为本轮的第"+iStart+"个。");
                childs.RemoveAt(iStart);
                iNo++;
                //iStart++;
            }
            return childs[0];
        }

Answer 8

LinkedList版/*
 * 500个小孩围成一圈，从第一个开始报数：
 * 1,2,3,1,2,3,1,2,3……每次报3的小孩退出
 * 问最后剩下的那个小孩，在以前500人里是第几个？
 */
import java.util.*;/* 用LinkedList解决小孩围圈问题 */
public class ChildrenCircleLinkedList {    public static void main(final String[] args) {
        int numberOfChildren = 500; // 小孩总数
        int quitNo = 3; // 报quitNo的小孩退出
        System.out.println(
                numberOfChildren + "个小孩，报"
                + quitNo + "的退出，剩下的是第"
                + getCountOffResult(numberOfChildren, quitNo) + "个小孩");
    }    /**
     * 获得报数结果
     *
     * @param numberOfChildren 小孩总数
     * @param quitNo 报quitNo的小孩退出
     * @return 剩下的是第几个小孩
     */
    private static int getCountOffResult(
            int numberOfChildren, int quitNo) {
        // 入口参数检查
        if (numberOfChildren <= 0 || quitNo <= 0) {
            return 0;
        }        // 定义并生成小孩数组列表，编号从1到numberOfChildren
        List<Integer> children = new LinkedList<>();
        for (int ii = 1; ii <= numberOfChildren; ii++) {
            children.add(ii);
        }        Iterator<Integer> childrenIterator = children.iterator();
        while (numberOfChildren > 1) {
            Integer childNo = 0;
            for (int ii = 0; ii < quitNo; ii++) {
                if (!childrenIterator.hasNext()) {
                    childrenIterator = children.iterator();
                }
                childNo = childrenIterator.next();
            }
            // 可以打开下面的注释，查看详细的执行过程
            // System.out.println("第" + childNo + "个小孩已经退出");            childrenIterator.remove();
            numberOfChildren--;
        }        childrenIterator = children.iterator();
        return childrenIterator.next();
    }
}

Answer 9

不会JAVA、PHP，只会ASP，用ASP编写一个类，大家看看。（ASP不区分大小写）
<%
dim child
set child=new childcountclass
child.children=500
child.quitno=3
response.Write "共有"&child.children&"个小朋友围成一圈，按1～"&child.quitno&"报数，报"&child.quitno&"的退下，最后剩余的是第"&child.getlast&"号"Class ChildCountClass
public child '小朋友总人数
public quit '退出序号

private quan '第几圈
private sheng '留下人数
private begin '从几开始
private num() '定义数组

public function getlast '获取最后一个小朋友号码的调用函数
getlast=shu(child,1)
end function

private sub class_initialize '初始化
child=500
quit=3
redim num(child)
for i=0 to child-1
num(i)=i+1
next
sheng=child
begin=1
quan=0
end sub

private function shu(nums,start) '按圈数数，两个参数，现有人数nums，从几开始数start；报3的下，将留下的序号记录到数组num()
quan=quan+1 '统计圈数
n=0 '统计留下人数
for i=0 to nums-1
no=(i+start) mod quit '每个人的报数，1、2留，0下
if no<>0 then '留下的人记录下来
num(n)=num(i)
n=n+1
response.Write num(i)&" "
else
response.Write "<font color=red>"&num(i)&"</font> "
end if
if i mod 10=9 then response.write "<br>"
next
response.write "<br>第"&quan&"圈，初始"&nums&"人，应下"&((nums+start-1)\quit)&"人，留"&(nums-(nums+start-1)\quit)&"人，余"&((nums+start-1) mod quit)&"人，实际剩"&n&"人,余"&no&"人<br><br><br>"
if n>1 then shu=shu(n,no+1) else shu=num(0)
end function

    public property let Children(shu)
        child = shu
    end property    public property get Children() 
        Children = child
    end property

    public property let QuitNo(no) 
        quit = no
    end property     public property get QuitNo()
        QuitNo = quit
    end property
End Class
%>

Answer 10

上面的代码，在类中有输出过程，不需要的把类中所有的reponse.write语句整行删除就行了。结果是436

Answer 11

package day525;import java.util.ArrayList;
import java.util.List;public class YueSeFu { public static void main(String[] args) {
CycleLink link = new CycleLink();
link.setLen(500);
link.setBaoshu(1);
link.setShushu(3);
link.creatLink();
link.showNodes();
link.play();
}}class Node {
int num;
Node nextNode; public Node(int num) {
this.num = num;
}
}class CycleLink {
int len;
Node firstNode = null;
Node temp = null;
int baoshu;
int shushu; public void setLen(int len) {
this.len = len;
} public void setBaoshu(int baoshu) {
this.baoshu = baoshu;
} public void setShushu(int shushu) {
this.shushu = shushu;
} public void play() {
// 找到报数的小孩
temp = firstNode;
for (int i = 1; i < baoshu; i++) {
temp = temp.nextNode;
}
// 一直報數
while (len != 1) {
// 开始报数
for (int j = 1; j < shushu; j++) {
temp = temp.nextNode;
}
// 报道数字的人退出
Node temp2 = temp;
while (temp2.nextNode != temp) {
for (int i = 0; i <= len; i++) {
temp2 = temp2.nextNode;
}
} temp2.nextNode = temp.nextNode;
temp = temp.nextNode;
len--;
}
System.out.println("最後節點=" + temp.num);
} public void creatLink() {
for (int i = 1; i <= len; i++) {
if (i == 1) {
Node node = new Node(i);
firstNode = node;
temp = node;
} else {
if (i != len) {
Node node = new Node(i);
temp.nextNode = node;
temp = node;
} else {
Node node = new Node(i);
temp.nextNode = node;
temp = node;
temp.nextNode = firstNode;
}
}
}
} public void showNodes() {
int i = 1;
Node temp = firstNode;
while (i <= len) {
i++; System.out.println(temp.num + " ");
temp = temp.nextNode; }
}
}

Answer 12

这是一个递推公式，基本思想如下：/*
(函数)index表示(变量)n个人玩游戏报(常量)m退出最后胜利者的编号.则有递推公式：
index(1) = 0;
index(n) = (index(n-1) + m)%n;   (n>1)
这个公式不是只考虑一种场景得出的结果，而是抽象出普遍的n得出的结论，我觉得不是一般人能想到的--至少我是想不到的。
*/
参考：
http://hi.baidu.com/isswangqing/item/297c9edb0c960e3ce3108fa3
http://blog.csdn.net/goal00001111/article/details/3439308这个方法求解释啊,验证是OK的方法,但是哥们能否好心贴个思路上来撒,学习学习

Answer 13

你理解了题意吗？？？
1 第几个是从1开始数的，而不是从0开始
2 退出之后，只要身后还有人，后面那个还是要数数字，围成一圈。你现在第一个人（你的0）永远数1
这个貌似是JXXXXXX的数学解法，没有错