笔试编程题(2012.3.22笔试)

一个笔试题目：
 n个人围成一个圈，第一个人从1开始递增报数，凡是报到3的倍数(包括3)时，该人退出，随后的人接着再继续报数，直到最后只剩下一个人为止，求最后剩下的这个人在原对中的编号。
思路：
用数组存储n个人，开始数组元素全部初始化为1，表示所有的人都在队中，然后循环遍历数组，凡是遇到能整除3的位置的元素就将该元素的值设为0; 同时记录队中1个数的count变量减一。重复上面的步骤，知道队中只有1个1时，循环退出，最后在遍历一次数组，找出值为1的这个元素所在的位置，就是最后剩下的这个人的原始编号。
实现：

/*
    时间：2012年3月22日 23:41:01
    功能：笔试题：n个人围城一圈，第一个人从1开始递增报数，凡是报到3的倍数(包括3)时，该人退出，随后的人接着再继续报数，直到最后只剩下一个人为止，求最后剩下的这个人的编号。
    思路：用数组存储n个人，开始数组元素全部初始化为1，表示所有的人都在队中，然后循环遍历数组，凡是遇到能整除3的位置的元素就将该元素的值设为0; 同时记录队中1个数的count变量减一。重复上面的步骤，知道队中只有1个1时，循环退出，最后在遍历一次数组，找出值为1的这个元素所在的位置，就是最后剩下的这个人的原始编号。
*/

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

int find(int n)
{
    int i;
    int count = n; //count表示队中1的个数，开始1的个数与人数相等
    int num = 1;   //num记录是报数的数字，从1开始。
    int *a = (int *)malloc(n * sizeof(int)); //为数组分配空间,这里不能写成a[n],数组是静态的，其大小必须明确。
    if (NULL == a)
    {
        printf("内存分配失败,程序退出\n");
        exit(-1);
    }

    //将数组全部数据初始化为1,1代表人还在队中
    for(i = 0; i < n; i++)
    {
        a[i] = 1;
    }

    start:
    for(i = 0; i < n; i++)
    {
        if (a[i] == 1) //检查第i个位置的人是否还在对中
        {
            if (num % 3 == 0) //如果还在,在检查他报数是否能整除3
            {
                a[i] = 0;  //如果能,将他退出
                count--;  //队中人数减1
            }
            num++; //下一个报数
        }

        if (count == 1) //这里可以减少额外的循环
            break;
    }

    if (count != 1)
        goto start;

    for (i = 0; i < n; i++)
    {
        if (a[i] == 1)
            return i + 1;
    }

    free(a);  //最好释放动态分配的内存
    return 0;
}

int main()
{
    int n;
    printf("请输入人数: ");
    scanf("%d", &n);

    printf("最后剩下的是 %d 个位置的人。\n", find(n));
    return 0;
}

测试结果：

int main()
{
    int n;
    printf("请输入人数: ");
    scanf("%d", &n);

    printf("最后剩下的是 %d 个位置的人。\n", find(n));
    return 0;
}

/*
    在vc++6.0中输出的结果为：
    ------------------------------------
    请输入人数: 100
    最后剩下的是 91 个位置的人。
    -----------------------------------
    请输入人数: 5
    最后剩下的是 4 个位置的人。
    -----------------------------------
*/

另一种实现(不用goto)

/*第二种实现(不用goto)*/
int find2(int n)
{
    int * a = (int *)malloc(n * sizeof(int));
    if (NULL == a)
    {
        printf("内存分配失败,程序退出\n");
        exit(-1);
    }

    int i, j = 0;
    int count = n;
    int num = 1;

    for (i = 0; i < n; i++)
    {
        a[i] = 1;
    }

    while (1)
    {
        if(a[j] == 1)
        {
            if (num % 3 == 0)
            {
                a[j] = 0;
                count--;
            }
            num++;
        }

        if (count == 1)
            break;

        j++;

        if (j == n)
        {
            j = 0;
        }
    }

    for (i = 0; i < n; i++)
    {
        if (a[i])
        {
            return i + 1;
        }
    }

    free(a);
    return 0;
}