https://bbs.bccn.net/thread-339180-1-1.html

这里面的那个报数程序 数一大就很慢 不过写的时候考虑的是省内存 后来又写了一个 发现效率真是不能比啊。。

原题目

m个人围成一圈,1,2,3循环报数，报到3的人退出，并将退出的序号依次存到数组p中，包括最后一个人的序号。到最后只余1人，输出最后留下的是第几号 （最初的序号，以1起始）。若m=6，则输出n=1<CR>  3 6 4 2 5 1；若m=10，则输出n=4<CR> 3 6 9 2 7 1 8 5 10 4；若m=100，则输出n=91<CR> 3 6 9……100 58 91。函数int fun(int n ,int *p)实现上述功能，返回n个人中最后余的1人的起始序号，并将退出的序号顺序写入p指向的数组中。

新程序包含了旧的 所以重新帖一遍罢。。

顺便问个问题 Code::Blocks 有人用么 感觉启动速度挺慢的 有没有办法优化下 谢谢。。

#include<stdio.h>
#include<string.h>
#include<time.h>

//#define FAST    /* for test */

#define M 100000

/* fast but use a buffer */
int baoshu_fast(int n,int *p)
{
    int buf[M] = {0};
    int pick = 1;
    int j = 0;
    int put = 0;

    while (put < n)
    {
        if (p[pick] != -1)
        {
            if (2 == j++)
            {
                buf[put++] = p[pick];
                p[pick] = -1;/* will not be picked */
                j = 0;
            }
        }

        pick++;

        if (pick > n)
        {
            pick = 1;
        }
    }

    memcpy((void *)&p[1],(void *)&buf[0],n*sizeof(int));

    return (p[n]);
}


int baoshu_savemem(int n,int *p)
{
    int i = 0;
    int pick = 1;
    int j = 0;

    for (; i<n-2; i++)
    {
        pick += 2;
        /* (n-i) nums */
        if (pick > (n-i))
        {
            pick -= (n-i);
        }
        p[n+1] = p[pick];    /* p[pick] == *(p+pick) */
        /* slow */
        /*
        for (j=pick; j<n+1; j++)
        {
            p[j] = p[j+1];
        }
        */
        /* faster */
        /* memcpy (void*, const void*, size_t); */
        memcpy((void *)&p[pick],(void *)&p[pick+1],(n-pick+1)*sizeof(int));
    }

    if (pick > (n-i))
    {
        pick -= (n-i);
    }

    /* 2 nums left */
    p[n+1] = p[pick];

    /*
    for (j=pick; j<n+1; j++)
    {
        p[j] = p[j+1];
    }
    */

    memcpy((void *)&p[pick],(void *)&p[pick+1],(n-pick+1)*sizeof(int));

    p[n+1] = p[1];

    /*
    for (j=1; j<n+1; j++)
    {
        p[j] = p[j+1];
    }
    */
    memcpy((void *)&p[1],(void *)&p[2],n*sizeof(int));

    return (p[n]);
}

int main(void)
{
    int m = 0;
    int a[M] = {'\0'};
    int i = 1;
    long start = 0l;
    long end = 0l;

    printf("Please input m(1<m<%d):",M-1);
    scanf("%d",&m);

    /* a[0] will not be used */
    for (i=1; i<=m; i++)
    {
        a[i] = i;
    }
    start = clock();
    #ifdef FAST
    printf("n=%d\n",baoshu_fast(m,a));
    #else
    printf("n=%d\n",baoshu_savemem(m,a));
    #endif
    end = clock();

    for (i=1; i<=m; i++)
    {
        printf("%3d ",a[i]);
    }

    printf("\n");

    printf("I use %ld ms.\n",end-start);

    return 0;
}

[ 本帖最后由 zklhp 于 2011-5-10 17:47 编辑 ]

自己顶

感觉要学的还很多啊。。

我喜欢快 呵呵