据说是微软面试题

lauchee

这个问题不错,可以去研究一下.

franklmin

1024

第一次 拿走 1，3，5，7。。。。。。1999，剩下 2，4，6，8。。。。2000，下一次从 2 开始
第二次 拿走 2，6，10。。。。。。1998（拿走的数%2=0，%4=2）,剩下 4，8，12，16，20。。。。。。2000，下一次从4开始
第三次 拿走 4，12，20。。。2000（拿走的数%4=0，%8=4）,剩下8，16，24。。。1992

第 i 次拿走，剩下的数为 2^i ,2^(i+1).........[2^i<2000]

所以第十次拿走，剩下的数为1024

softsongs

我觉得答案是32。
循环次数                                 0                 1             2             3           4            ....
剩下数字的个数(第一个数)      2000(1)    1000(2)   500(4)    250( 8 )   125(16)       ....

循环4次后，还剩125个数，此时剩下的最小数为16， 16的下一个数为32， 因为已经出现奇数个数了，所以每次取完还是剩奇数个，32永远不会被取走（永远会被跳过，因为把32看成最后一个数，它总在偶数位，所以永远不会被选中），所以最后剩的数是32。

emacsnw

原帖由 franklmin 于 2006-12-4 20:54 发表
1024

第一次 拿走 1，3，5，7。。。。。。1999，剩下 2，4，6，8。。。。2000，下一次从 2 开始
第二次 拿走 2，6，10。。。。。。1998（拿走的数%2=0，%4=2）,剩下 4，8，12，16，20。。。。。。2000，下一次 ...

这2000个人围成一个圈，可以循环的。
查了一下这个问题叫Joseph's problem，网上有很多算法去解。

tyc611

我的想法有点笨，不过也说说，大家集思广益嘛
最初的序列为：1，2, 3, 4, ..., 1999, 2000（总数为偶数）
第一次取掉所有奇数，即剩下(2, 4, 6, ..., 1998, 2000) = 2 * ( 1, 2, 3, ..., 999, 1000)（仍为偶数）
第二次取掉剩下数中所有奇数，即剩下2 * (2, 4, 6, ..., 998, 1000) = 2^2 *(1, 2, 3, ..., 499, 500)（偶数）
第三次取掉剩下数中所有奇数，即剩下2^2 * (2, 4, 6, ..., 498, 500) = 2^3 * (1, 2, 3, ..., 249, 250)（偶数）
第四次取掉剩下数中所有奇数，即剩下2^3 * (2, 4, 6, ..., 248, 250) = 2^4 * (1, 2, 3, ..., 124, 125)（注意！为奇数了）
此时再取时，最后一个数2^4 * 125将被取掉，所以将第一个2放到最后，得：
第五次的结果：2^4 * (4, 6, 8, ..., 124, 2) = 2^5 * (2, 3, 4, ... , 62, 1)
为了简单，我们现在只对(2, 3, 4, ...., 62, 1) 取数，最后结果乘2^5即可。

先将(2, 3, 4, ..., 62, 1)序列映射为(1, 2, 3, ...., 61, 0)即原序列每个数减一，对新序列(1, 2, 3, ...., 61, 0)取数得：
第六次取数，得(2, 4, 6, ...., 60, 0) = 2 * (1, 2, 3, ..., 30, 0)（又是奇数了！）
（后面处理方法同上）
第七次取数，得 2 * (4, 6, 8, ..., 30, 2) = 2^2 * (2, 3, 4, ..., 15, 1)

再将(2, 3, 4, ..., 15, 1)映射为(1, 2, 3, ..., 14, 0)（原序列减一）
第八次取数，得 ( 4, 6, ..., 14, 2)……进行下去此序列得到最终值14

所以最终结果为  ((14+1)* 2^2+1)*2^5 = 1952

不知道算错没有，做得好麻烦啊

[ 本帖最后由 tyc611 于 2006-12-5 13:30 编辑 ]

jronald

原帖由 tyc611 于 2006-12-5 13:14 发表
我的想法有点笨，不过也说说，大家集思广益嘛
最初的序列为：1，2, 3, 4, ..., 1999, 2000（总数为偶数）
第一次取掉所有奇数，即剩下(2, 4, 6, ..., 1998, 2000) = 2 * ( 1, 2, 3, ..., 999, 1000)（ ...

1952正确

tyc611

原帖由 jronald 于 2006-12-5 13:26 发表


1952正确

写那么长花了我好长时间的，不过按那方法算越来也蛮快的，收敛速度还行

geel

为什么我直接模拟这个过程得出来的是1024？

1. <?php
   
2. for ($array = array(), $i=0; $i<2000; array_push($array, ++$i));
   
3. while (count($array)>1)
   
4. {
   
5.         unset($array[key($array)]);
   
6.         if(next($array) === false)          /* unset之后指针后移，一次next即可 */
   
7.                 reset($array);
   
8. }
   
9. print_r($array);
   
10. ?>
    
11. /* 结果是1024 */
    

复制代码

2006年12月6日更新：确实是1952，我上面的程序有bug

修正过的程序如下：

1. <?php
   
2. for ($array = array(), $i=0; $i<2000; array_push($array, ++$i));
   
3. while (count($array)>1)
   
4. {
   
5.         unset($array[key($array)]);
   
6.         if (!current($array))        /* 如果刚删除的是最后一个元素，从头开始的时候就要跳过一个 */
   
7.         {
   
8.                 reset($array);
   
9.                 next($array);
   
10.         }
    
11.         elseif(next($array) === false) /* 如果删除的是倒数第二个元素，从头开始 */
    
12.         {
    
13.                 reset($array);
    
14.         }
    
15. }
    
16. print_r($array);
    
17. 
    
18. /* 结果是 1952 */
    
19. ?>

复制代码

[ 本帖最后由 geel 于 2006-12-6 13:26 编辑 ]

franklmin

在vs2003上用笨笨的办法作了一下验证：

思路如下
（1）生成一个存有2000个节点的循环链表
（2）依次删除节点
（3）剩下最后一个数，打印


#include <stdlib.h>
#include <stdio.h>


//链表节点
struct circleListNode{
        int data;
        struct circleListNode *next;
    struct circleListNode *prev;
};



//生成一个不带头尾的循环链表

circleListNode* makelist(int maxnum)
{       
     circleListNode *tempHead,*currNode,*preNode;
         
        //tempHead用于保存开始的值，
         tempHead=new circleListNode;
         tempHead->data=0;
         tempHead->next=NULL;
         tempHead->prev=NULL;
       
        printf("Cirle list make Begin!\n");
       
        for(int i=0;i<maxnum;i++)
        {
                //初始情况       
                if(i==0)
                {
                        preNode=tempHead;
                }
       

        //一般情况
                currNode=new circleListNode;
                currNode->data=i+1;
                currNode->prev=preNode;
                preNode->next=currNode;
                preNode=currNode;
         

       //最后一个节点
                if(i==maxnum-1)
                {
                        currNode->next=tempHead->next;
                        tempHead->next->prev=currNode;
                        delete tempHead;
                       
                }
               
                printf("%d ",currNode->data);

        }

                printf("\nCirle list make completed!\n");

                currNode=currNode->next;//将指针放到第一个节点上

                return currNode;
       


}

//依次隔一个，删一个
void joblist(circleListNode* plist)
{
        circleListNode *curr,*prev,*next;
       
    curr=plist;
    prev=plist->prev;
        next=plist->next;
       
        while(curr)
        {       
                //删除当前节点
                printf("%d deleted\t",curr->data);
                delete curr;

                //将前一个节点与后面的节点连接。
                prev->next=next;
                next->prev=prev;
       
                //删除一个元素后各指针值

                curr=next->next;//跳过下一个节点
                next=curr->next;
                prev=curr->prev;

                //如果只剩下一个，就退出
        if(curr->next==curr)
                break;

        }

        printf("\nThe data remained is %d\n",curr->data);


}


int main()
{
    circleListNode *p=makelist(2000);

    joblist(p);

        system("pause");
        return 0;

}



结果是 1952！

[ 本帖最后由 franklmin 于 2006-12-5 15:56 编辑 ]

geel

楼上的，结果是？