经典的两个面试题，作出来你“牛”！

1.将正整数1到N(N>1)排成一排，然后从第一个数开始取走数字，每间隔M(M>1)个取一个(譬如M=3,那么第一个取1,第二个取4,第三个取7...),一遍完成后再取第二遍，问取L遍(L<M)后,剩下哪些数字?


2.从一个有序数组中(从小到大)使用二分法查找一个给定的数的位置?



以上两题可用JAVA或javascript来完成。

评论

11 楼 chinabrle 2009-06-02  

第1题的JAVA代码：

public class Func {
    public static void f(int N,int M,int L){
        for(int i=1;i<=N;i++)
        {
            int j=i%M;
            if(j == 0)
                j=M；
            if(j > L)
                System.out.print(i+" ");
        }
    }

    public static void main(String[] args)
    {
        f(12,4,3);
    }
}

//输出：
//4 8 12

10 楼 zhanger 2009-04-16  

貌似没那么难吧?
第一个就是一个简单的模拟,第二个就是二分查找啊

9 楼 King_MrGao 2009-04-03  

这题就是解方程，找规律
public static void main(String [] args){
getN(30,3,3);
}

        /**
         * @param N 给定数范围
         * @param M 间隔
         * @param L 提取次数
        */
public static void getN(int N,int M,int L){
//计算次范围、提取次数、间隔下，最总剩余几个数字
int r_length = (N-1)/(int)Math.pow(M,L);
System.out.println("r_length:"+r_length);

for(int i=0;i<=r_length;i++){
System.out.println(i*(int)Math.pow(M,L)+1);
}
}
希望大侠们多给提意见！

8 楼 diaodou 2009-03-27  

diaodou 写道

diaodou 写道

cuiran 写道

1.将正整数1到N(N>1)排成一排，然后从第一个数开始取走数字，每间隔M(M>1)个取一个(譬如M=3,那么第一个取1,第二个取4,第三个取7...),一遍完成后再取第二遍，问取L遍(L<M)后,剩下哪些数字?


2.从一个有序数组中(从小到大)使用二分法查找一个给定的数的位置?



以上两题可用JAVA或javascript来完成。

1. 假设数字N是被第f(N, M)次取到，比如，f(1,3)=f(4,3)=f(7,3)=1,f(2,3)=2，那么，归纳一下，有下面公式：
if ((N+M-1) % M ==0) f(N, M) = 1
else f(N, M) = f(N-(N+M-1)/M, M) + 1
按此，可以得出，所有f(N, M) > L的N就是剩下的数字。

我解释下好了,以N=11,M=3作为例子，f(N, M)表示N这个数字被第f(N,M)次取到，可以得出
M=3
N: 1,2,3,4,5,6,7,8,9,10,11,
f: 1,2,3,1,4,2,1,5,3,1, 2,
L=3，剩下的就是5，8。

怎么求出f(N, M)呢？
N: 1,2,3,4,5,6,7,8,9,10,11,
第一次取数字以后，变为
N':2,3,5,6,8,9,11
可以看到，如果N+M-1被M整除，就是1,4,7这些，已经被删掉了，那么f=1
而剩下的数字，往前排，重新标号以后，有公式: N => N-(N+M-1)/M，不如，11=> 7
那么，可以知道，f(N, M) = f(N-(N+M-1)/M, M) + 1

这个公式怎么用呢？
我们先知道，
f(1, M) = 1
f(2, M) = 2, ...
f(M, 0) = M,
在根据公式f(N, M) = f(N-(N+M-1)/M, M) + 1，递推，可以把所有f(N, M)求出来

或者可以推导出一个表达式来。。。

7 楼 diaodou 2009-03-27  

diaodou 写道

cuiran 写道

1.将正整数1到N(N>1)排成一排，然后从第一个数开始取走数字，每间隔M(M>1)个取一个(譬如M=3,那么第一个取1,第二个取4,第三个取7...),一遍完成后再取第二遍，问取L遍(L<M)后,剩下哪些数字?


2.从一个有序数组中(从小到大)使用二分法查找一个给定的数的位置?



以上两题可用JAVA或javascript来完成。

1. 假设数字N是被第f(N, M)次取到，比如，f(1,3)=f(4,3)=f(7,3)=1,f(2,3)=2，那么，归纳一下，有下面公式：
if ((N+M-1) % M ==0) f(N, M) = 1
else f(N, M) = f(N-(N+M-1)/M, M) + 1
按此，可以得出，所有f(N, M) > L的N就是剩下的数字。

我解释下好了,以N=11,M=3作为例子，f(N, M)表示N这个数字被第f(N,M)次取到，可以得出
M=3
N: 1,2,3,4,5,6,7,8,9,10,11,
f: 1,2,3,1,4,2,1,5,3,1, 2,
L=3，剩下的就是5，8。

怎么求出f(N, M)呢？
N: 1,2,3,4,5,6,7,8,9,10,11,
第一次取数字以后，变为
N':2,3,5,6,8,9,11
可以看到，如果N+M-1被M整除，就是1,4,7这些，已经被删掉了，那么f=1
而剩下的数字，往前排，重新标号以后，有公式: N => N-(N+M-1)/M，不如，11=> 7
那么，可以知道，f(N, M) = f(N-(N+M-1)/M, M) + 1

这个公式怎么用呢？
我们先知道，
f(1, M) = 1
f(2, M) = 2, ...
f(M, 0) = M,
在根据公式f(N, M) = f(N-(N+M-1)/M, M) + 1，递推，可以把所有f(N, M)求出来

6 楼 bonny 2009-03-26  

cuiran 写道

bonny 写道

第一个问题

任何一个数字x经n轮挑选后，如果还存在，那么其值是
f（x） = x- n（|x/m|+1）
且 f(x)%m !=1

解此方程
N：数列长度
m：。。
n：遍历次数
    public static void f(int N, int m, int n) {
        boolean left = true;
        for (int i = 1; i <= N; i++) {
            left = true;
            for (int j = 0; j < +n; j++) {
                if ((i - j * (Math.abs(i / m) + 1)) % m == 1) left = false;
            }
            if (left)
                System.out.println(i);
        }

    }

你的思路很好，但有个问题：如果这样调用f(10, 4, 1);结果为:
2
3
4
6
7
8
10
那这样调用f(10, 4, 1)应该是：
3
4
6
8
10
而你的是：
3
4
6
10

我的分析错了，红色的部分应该是“位置”,即位置
设x在n次遍历后的位置为
f(x,n) = f(x,n-1) - ((|(f(x,n-1)-1)/m|+1)
f(x,0) = x
f(x,n)%m != 1

    public static void f(int N,int m,int n){
        boolean left;
       for(int i=1;i<N+1;i++){
           left = true;
           for(int j=0;j<n;j++){
              if(position(i,m,j)%m == 1) left = false;
           }
           if(left)
           System.out.println(i);
       }
    }


    public static int position(int x,int m,int n){
        if(n==0)
            return x;
        else
            return position(x,m,n-1) - Math.abs((position(x,m,n-1)-1)/m) -1;
    }

5 楼 叩舷而歌 2009-03-26  

基础的数据结构题……初学数据结构的时候就拿来练手，算不得牛。

4 楼 cuiran 2009-03-26  

bonny 写道

第一个问题

任何一个数字x经n轮挑选后，如果还存在，那么其值是
f（x） = x- n（|x/m|+1）
且 f(x)%m !=1

解此方程
N：数列长度
m：。。
n：遍历次数
    public static void f(int N, int m, int n) {
        boolean left = true;
        for (int i = 1; i <= N; i++) {
            left = true;
            for (int j = 0; j < +n; j++) {
                if ((i - j * (Math.abs(i / m) + 1)) % m == 1) left = false;
            }
            if (left)
                System.out.println(i);
        }

    }

你的思路很好，但有个问题：如果这样调用f(10, 4, 1);结果为:
2
3
4
6
7
8
10
那这样调用f(10, 4, 1)应该是：
3
4
6
8
10
而你的是：
3
4
6
10

3 楼 bonny 2009-03-26  

第一个问题

任何一个数字x经n轮挑选后，如果还存在，那么其值是
f（x） = x- n（|x/m|+1）
且 f(x)%m !=1

解此方程
N：数列长度
m：。。
n：遍历次数
    public static void f(int N, int m, int n) {
        boolean left = true;
        for (int i = 1; i <= N; i++) {
            left = true;
            for (int j = 0; j < +n; j++) {
                if ((i - j * (Math.abs(i / m) + 1)) % m == 1) left = false;
            }
            if (left)
                System.out.println(i);
        }

    }

2 楼 cuiran 2009-03-26  

第二题解：

/**
*
* @param num 给定的数
*/
public static void woke2(int num){
int array[]=new int[]{1,2,3,4,5,6,7,8,9,10};
int length=array.length;
int middle_num=(length)/2-1;
while(true){
if(array[middle_num]==num){
System.out.println(num+"的位置是:"+middle_num);
break;
}else{
if(array[middle_num]>num){
System.out.println("你输入的数字比"+array[middle_num]+"小");
middle_num=middle_num-1;

}else{
System.out.println("你输入的数字比"+array[middle_num]+"大");
middle_num=middle_num+1;

}

}
}

}

1 楼 diaodou 2009-03-26  

cuiran 写道

1.将正整数1到N(N>1)排成一排，然后从第一个数开始取走数字，每间隔M(M>1)个取一个(譬如M=3,那么第一个取1,第二个取4,第三个取7...),一遍完成后再取第二遍，问取L遍(L<M)后,剩下哪些数字?


2.从一个有序数组中(从小到大)使用二分法查找一个给定的数的位置?



以上两题可用JAVA或javascript来完成。

1. 假设数字N是被第f(N, M)次取到，比如，f(1,3)=f(4,3)=f(7,3)=1,f(2,3)=2，那么，归纳一下，有下面公式：
if ((N+M-1) % M ==0) f(N, M) = 1
else f(N, M) = f(N-(N+M-1)/M, M) + 1
按此，可以得出，所有f(N, M) > L的N就是剩下的数字。