黑马程序员技术交流社区
标题: 分享一道java基础面试题 [打印本页]
作者: 张辉2012 时间: 2012-12-15 21:35
标题: 分享一道java基础面试题
面试题是来自一个具有一定规模的IT公司面试题真题，现分享给大家，供大家学习交流，探讨解题思路！
题目：
现有50个数字，放在一个数组中，a[0],a[1],a[2],a[3]..............a[49]，将他们绕城一个圈排列，从1开始，每到第3个数字，即去除，这样循环往复，一直到最后，现在要求通过一段程序，来求出最后一个剩下的数字是多少?
作者: 邵天强 时间: 2012-12-15 22:36
这道题利用LinkedList比较方便
public class Test {
/**
* @param args
*/
public static void main(String[] args) {
Integer[]arr=new Integer[50];
for(int i=0;i<50;i++){
arr[i]=i+1;
}
System.out.println("最后一个剩余的位置："+test(arr,3));
}
public static int test(Integer[]arr,int k){
//然后把这个数组编程一个链表集合
LinkedList<Integer>list=new LinkedList<Integer>(Arrays.asList(arr));
//定义一个整形
int n=-1;
while(list.size()>1){
n=(n+k)%list.size();
list.remove(n--);
}
return list.get(0).intValue();
}
}
作者: 张海涛 时间: 2012-12-15 22:45
这个就是循环套循环，理清思路画画图应该能解出来！
作者: 张海涛 时间: 2012-12-15 22:45
这个就是循环套循环，理清思路画画图应该能解出来！
作者: 许晓华 时间: 2012-12-15 23:50
//此题为经典的约瑟夫环问题，没有用LinkedList
public class x
{
static int josephus(int N,int K)
{
int alive=0;//1个人的话，最后活下的编号是0号
for (int i=2;i<=N;i++)//从第2个人开始循环
alive=(alive+K)%i;
return alive;
}
public static void main(String []args)
{
Integer[]arr=new Integer[50];
for(int i=0;i<50;i++)
{
arr[i]=i+1;
}
System.out.println(arr[josephus(50,3)]);
}
}
作者: 许晓华 时间: 2012-12-15 23:51
针对你这个题，50个人，数到3退出，最后剩下编号为11号的人。即数组中第10号元素。
作者: 张辉2012 时间: 2012-12-16 12:57
许晓华 发表于 2012-12-15 23:51 
针对你这个题，50个人，数到3退出，最后剩下编号为11号的人。即数组中第10号元素。 ...
你的 josephus(int N,int K)方法能详细讲解下吗？
我想了半天真心没有看懂
for (int i=2;i<=N;i++)//从第2个人开始循环
alive=(alive+K)%i;
是在做什么呢？望解答:loveliness:
作者: 许晓华 时间: 2012-12-16 17:51
本帖最后由 许晓华 于 2012-12-16 17:55 编辑
张辉2012 发表于 2012-12-16 12:57 
你的 josephus(int N,int K)方法能详细讲解下吗？
我想了半天真心没有看懂
for (int i=2;i ...
约瑟夫环问题(Josephus)
•编号为0~N-1的N个人围成一个圈，从0开始数到k-1的被杀，求最后留下来的一个人的最初编号。
•设N个人的约瑟夫环问题的解是f(N)，即最后活下来的人的编号。以N=10，k=3为例
• 0 1 2 3 4 5 6 7 8 9
• 7 8 ☻ 0 1 2 3 4 5 6
•第一个数到k-1的人其编号(k-1)%N
•从编号为k%N的人开始，剩下的N-1个人又组成了一个新的f(N-1)的约瑟夫环问题：即
•f(N)=(f(N-1)+k%N)%N
•即f(N)=(f(N-1)+k)%N(递归表达式)
•已知f(1)=0
•根据递归表达式可知：
•f(2) =(f(1)+k)%2
•f(3) =(f(2)+k)%3
•f(4)=(f(3)+k)%4
•……
•可得出我程序中的递推公式
作者: 王进亮 时间: 2012-12-18 12:59
本帖最后由 Attacker_P 于 2012-12-18 13:07 编辑
java是面向对象的，为什么用面向对象呢.....
//面对对象，先不考虑算法，先考虑这个问题中有哪些类，类中有哪些属性和算法
//把每个数看成一个对象（Kid)，一个圈（双向链表，KidCircle）
public class Count3Quit2 {
public static void main(String args[]){
KidCircle kc=new KidCircle(50);
int countNum=0;
Kid k=kc.first;
while(kc.count>1){
countNum++;
if(countNum==3){
countNum=0;
kc.delete(k);
}
k=k.right;
}
System.out.println(kc.first.id);
}
}
class Kid{
int id;//每一个孩子给一个id
Kid left;//这个孩子的左边和右边那个孩子
Kid right;
}
class KidCircle{
int count=0;
Kid first,last;//开始的一个孩子，和结束的一个孩子
KidCircle(int n){//构建一个有n个数的圈
for(int i=0;i<n;i++){
add();
}
}
void add(){//添加一个孩子
Kid k=new Kid();
k.id=count;
if(count<=0){
first=k;
last=k;
k.left=k;
k.right=k;
}else {
last.right=k;//最后一个孩子右手等于新添加的孩子
k.left=last; //这个孩子的左手等最后那个孩子
k.right=first;//这个孩子的右手等第一个孩子
first.left=k;//第一个孩子 的左手等刚添加的这个孩子
last=k;//这个上孩子变成了最后一个孩子
}
count ++;
}
void delete(Kid k){//删除一个孩子
if(count <=0){
return;
}else if(count==1){
first=last=null;
}else{
k.left.right=k.right;//k左边这个孩子的右手拉住了k右边个人
k.right.left=k.left;//k右边个孩子的左手拉住了k左边这个人
if(k==first){//如果k为第一孩子
first=k.right;//K右边那孩子为变为第一个孩子
}else if(k==last){//如果K为最后一个人
last=k.left;//K左边那个孩子变为最后一个
}
}
count--;
}
}
作者: 熊永标 时间: 2012-12-25 11:34
张辉2012 发表于 2012-12-16 12:57
你的 josephus(int N,int K)方法能详细讲解下吗？
我想了半天真心没有看懂
for (int i=2;i ...
这是不是高数呀
作者: 张辉2012 时间: 2013-1-2 18:59
熊永标 发表于 2012-12-25 11:34
这是不是高数呀
呵呵 不太清楚啊 貌似上学的时候不记得高数中有约瑟夫环
作者: 穆爱明 时间: 2013-7-8 21:04
学习一下，感谢分享！
作者: 赵国刚 时间: 2013-8-12 20:31
这是我遇到的类似的题分享下
package com.itheima;
import java.util.*;
/**
* 第十题：有100个人围成一个圈，从1开始报数，报到14的这个人就要退出。
* 然后其他人重新开始，从1报数，到14退出。问：最后剩下的是100人中
* 的第几个人？
*/
public class Test10 {
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList first = new ArrayList(); //定义集合为first
int number = 14; //每次报数的点
for (int i=1;i<=100 ;i++ ) //在集合加入1~100
{
first.add(i);
}
sop(first);
sop(first.size());
Count(first,number); //开始计算
sop(first);
sop(first.size());
}
private static ArrayList Count(ArrayList arl,int num)
{
for (int x=arl.size(); x>=num; x--)//一次一次报数
{
arl.remove(num-1); //每到14时踢掉一个
ArrayList changeCollection = new ArrayList();//定义另一个集合用来装下first中的前13个数
for (int a = 0;a<num-1 ;a++ ) //把first中的前13个数装在changeCollection中，并且删掉first内部的前13个数
{
changeCollection.add(arl.get(0));
arl.remove(0);
}
for (int a =0;a<num-1 ; a++)//把changeCollection中的数重新放入first中，并且放在最后
{
arl.add(changeCollection.get(a));
}
}
return arl;
}
public static void sop(Object obj){
System.out.println(obj);
}
}
// 输出结果：
// [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21
// , 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
// 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58,
// 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77,
// 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96,
// 97, 98, 99, 100]
// 100
// [16, 29, 36, 39, 47, 55, 72, 74, 75, 80, 90, 91, 92]
// 13
// 最终剩下的人：16, 29, 36, 39, 47, 55, 72, 74, 75, 80, 90, 91, 92
作者: 路国强 时间: 2013-12-13 11:17
加油。好好奋斗。加油
作者: lovefmylgs 时间: 2014-5-2 08:31
考虑考虑考虑考虑考加减
作者: lovefmylgs 时间: 2014-5-2 08:32
public class x
{
static int josephus(int N,int K)
{
int alive=0;//1个人的话，最后活下的编号是0号
for (int i=2;i<=N;i++)//从第2个人开始循环
alive=(alive+K)%i;
return alive;
}
public static void main(String []args)
{
Integer[]arr=new Integer[50];
for(int i=0;i<50;i++)
{
arr[i]=i+1;
}
System.out.println(arr[josephus(50,3)]);
}
}
作者: 刘亚东 时间: 2014-7-9 00:39
在java面试宝典上看到过这个题。
作者: wujiemin 时间: 2014-10-7 23:13
呵呵 不太清楚啊 貌似上学的时候不记得高数中有约瑟夫环
作者: 王沙龙 时间: 2015-6-4 11:57
学习了，呵呵
| 欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) |
黑马程序员IT技术论坛 X3.2 |