据说是微软面试题

xxandxx

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] = i;
   
    while(last-first != 1) {
        b[++last] = b[++first];
        ++first;
    }
    i = b[last];
    free(b);
    return i;
}

int main()
{
    printf("%d\n", fun(2000));
    getch();
    return 0;
}

[[i] 本帖最后由 xxandxx 于 2006-12-5 20:46 编辑 [/i]]

zwylinux

原帖由 jronald 于 2006-12-5 00:45 发表
圆圈上顺时针排列着1,2,3,....2000 这2000个数. 从1开始,顺时针隔一个拿走一个(1最先被拿走,下一个是3被拿走). 问最后剩下是哪一个数字.

这个和约瑟夫问题有什么区别没？

jronald

原帖由 zwylinux 于 2006-12-6 00:09 发表


这个和约瑟夫问题有什么区别没？

不知道约瑟夫问题啊

灰色骆驼

就是约瑟夫环

jronald

原帖由 灰色骆驼 于 2006-12-6 00:17 发表
就是约瑟夫环

知道那就没意思了

W.Z.T

找出规律:

1,3,5,...,2n-1,..,1999             1000/1000

2,6,10,..,2(2n-1),...,1998      500/500

4,12,.4(2n-1),1996,250/250

8,24,40,8(2n-1),125/125

16,48,80,16(2n-1),1984 63/62

32,96,160,32(2n-1),1952,(196 31/31

geel

大家正确，结果确实是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. ?>

复制代码

meilinxiaoxue

用数组来做,可以指定步长:

1. #include<stdio.h>
   
2. #include<stdbool.h>
   
3. 
   
4. int josephus(int * input, size_t count, unsigned int step)
   
5. {
   
6.         int i,n_step,result;
   
7.         bool flag = true;
   
8. 
   
9.         n_step = 0;
   
10.         result = input[0];
    
11. 
    
12.         while (flag)
    
13.         {
    
14.                 flag = false;
    
15. 
    
16.                 for (i=0; i<count; i++)
    
17.                 {
    
18.                         if (input[i])
    
19.                         {
    
20.                                 if (0 == n_step%step)
    
21.                                 {
    
22.                                         n_step = 1;
    
23.                                         input[i] = 0;
    
24.                                 }
    
25.                                 else
    
26.                                 {
    
27.                                         n_step++;
    
28.                                         result = input[i];
    
29.                                         flag = true;
    
30. #ifdef _DEBUG
    
31.                                         printf("mid:%d\n",result);
    
32. #endif
    
33.                                 }
    
34.                         }
    
35.                 }
    
36.         }
    
37. 
    
38.         return result;
    
39. }
    
40. 
    
41. void main(void)
    
42. {
    
43.         int test[2000];
    
44.         int i,j;
    
45. 
    
46.         for (i=0; i<2000; i++)
    
47.         {
    
48.                 test[i] = i+1;
    
49.         }
    
50. 
    
51.         j = josephus(test, 2000, 2);
    
52.         printf("result:%d\n", j);
    
53. }
    

复制代码

shxliang

原帖由 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) {
     ...

这种算法我没想到过，呵呵，牛.........学习了

jronald

原帖由 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) {
     ...

有创意