据说是微软面试题

qlks

原帖由 xxandxx 于 2006-12-5 20:31 发表
1952

int fun(int n)
{
    int first=1, last=n, i;
    int *b = (int *)malloc(2*n*sizeof(int));

    for (i = 1; i <= n; ++i)
        b = i;
   
    while(last-first != 1) {
     ...

如果fun(5)
为什么得到的是2？
不是第二次应该是4？

tyc611

原帖由 qlks 于 2006-12-6 17:48 发表


如果fun(5)
为什么得到的是2？
不是第二次应该是4？

你算错了

JColder

public class FindLeaveNum {



        /**

         * @param args

         */

        public static void main(String[] args) {

                // TODO Auto-generated method stub



                final int CAPABILITY = 2000;
                Vector v = new Vector(CAPABILITY );



                for (int i = 0; i < v.capacity(); i++) {

                        v.add(i, new Integer(i+1));

                }

                int i = 0;

                int beforeLast = Integer.parseInt(v.lastElement().toString());

                while (v.size()!= 1) {



                        for (int c = i; c < v.size(); c++) {

                                v.remove(c);

                        }

                       

                        System.out.print("剩下"+v.size()+"个： ");

                        for(int j=0;j<v.size();j++)

                        {

                                System.out.print(v.get(j)+" ");

                        }

                        System.out.println();

                       

                        int nowLast=Integer.parseInt(v.lastElement().toString());

                       

                        if(nowLast==beforeLast)

                        {

                                i=0;

                        }

                        else i=1;

                        beforeLast =nowLast;

                }



        }



}


结果是 1952

diabolo

typedef struct tagRingElement {
        tagRingElement * prev;
        tagRingElement * next;
        int data;
} RingElement_t;

const  int COUNT = 2000;

void main()
{
        RingElement_t * num = new RingElement_t[COUNT];

        RingElement_t * curdel, * nextdel, * prev, * next, * last;
       
        // num[0]
        num[0].data = 1;
        num[0].prev = num + COUNT - 1;
        num[0].next = num + 1;

        // num[1999]
        num[COUNT - 1].data = COUNT;
        num[COUNT - 1].prev = num + COUNT - 2;
        num[COUNT -1].next = num;

        for (int i = 1; i < COUNT - 1; i++)
        {
                num.prev = num + i - 1;
                num.next = num + i + 1;
                num.data = i + 1;
        }

        curdel = num;
        while (curdel->next != curdel->prev)
        {
                // store curdel->next->next;
                next = curdel->next;
                prev = curdel->prev;
                nextdel = next->next;

                // delete curdel
                next->prev = curdel->prev;
                prev->next = curdel->next;

                curdel = nextdel;
        }

        last = curdel->next;

        cout << last->data << endl;

        delete [] num;
}

忘了释放内存了，重贴一遍。

[ 本帖最后由 diabolo 于 2006-12-6 21:39 编辑 ]

zjbluefox

1952

1. 
   
2. import java.util.ArrayList;
   
3. import java.util.List;
   
4. 
   
5. /**
   
6. *
   
7. * @author Zhao
   
8. */
   
9. public class count {
   
10.    
    
11.     /** Creates a new instance of count */
    
12.     private static List<Integer> data = new ArrayList<Integer>();
    
13.     public static void main(String args[]) {
    
14.         for(int i=1;i<=2000;i++){
    
15.             data.add(i);
    
16.         }
    
17.         
    
18.         boolean FlagSize = false;
    
19.         
    
20.         while(data.size() > 1){
    
21.             int intSize = data.size();
    
22.             for(int i=0;i<intSize;i++){
    
23.                 if(i>=data.size()){
    
24.                     break;
    
25.                 }
    
26.                 if(FlagSize){
    
27.                     FlagSize = false ;
    
28.                     i++;
    
29.                 }
    
30.                 if(i==(data.size()-1)){
    
31.                     FlagSize =true;
    
32.                 }
    
33.                 data.remove(i);
    
34.             }
    
35.         }
    
36.         System.out.println(data.get(0));
    
37.         
    
38.     }
    
39.    
    
40. }
    

复制代码

[ 本帖最后由 zjbluefox 于 2006-12-7 10:50 编辑 ]

crspo

(2000循环左移1)-1=1952

2000: 11111010000
2000循环左移1:11110100001
2000循环左移1-1:11110100000=1952

tyc611

原帖由 crspo 于 2006-12-7 12:02 发表
(2000循环左移1)-1=1952

2000: 11111010000
2000循环左移1:11110100001
2000循环左移1-1:11110100000=1952

赞一个先！能说下为啥吗？

decwang

1953 用程序算出来的,为啥和上面不一样呢?

[ 本帖最后由 decwang 于 2006-12-7 14:31 编辑 ]

decwang

看错题了,呵呵

[ 本帖最后由 decwang 于 2006-12-7 14:59 编辑 ]

crspo

原帖由 tyc611 于 2006-12-7 12:19 发表


赞一个先！能说下为啥吗？

约瑟夫问题的小变体，可以参考concrete mathematics第一章