Linux 3+1班的一道机试题

问题描述：有一个整型数组a，共有1000个元素，即int a[1000]={1, 2, 3, 4...1000},现在请设计一个算法，将每隔两个的数组元素删除，求最后的剩余一个元素的下标和值。如果到结尾的话，从头开始，循环删除。例如有十个数据时

a[10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

删除的顺序是3, 6, 9, 2, 7, 1, 8, 5, 10

剩余的一个元素是4，它的下标是3.

算法思想：用index来表示数组的下标，count表示已经删除的元素个数，如果count==N-1表示只剩下一个元素没有删除，这个时候退出循环。

具体实现：

#include <stdio.h>

#define N 1000

int main()
{
    int a[N], i, count, index;

    for(i = 0; i < N; i++) {
        a[i] = i+1;
    }
    
    index = 0;
    count = 0;
    while(1) {
        /*找到第一个不是0的index下标*/
        while(a[index] == 0) {
            index++;
            if(index == N) {
                index = 0;
            }
        }
        if(count == N-1) {
            i = index;
            break;
        }
        /*index下标加一，一直找到一个不为0的下标，表示空一个数字*/
        index++;
        if(index == N) {
            index = 0;
        }
        while(a[index] == 0) {
            index++;
            if(index == N) {
                index = 0;
            }
        }
        /*index下标加一，一直找到一个不为0的下标，表示空第二个数字*/
        index++;
        if(index == N) {
            index = 0;
        }
        while(a[index] == 0) {
            index++;
            if(index == N) {
                index = 0;
            }
        }
        a[index] = 0;
        count++;
    }

    printf("a[%d] = %d\n", i, a[i]);

    return 0;
}

 

结果：

a[603]=604