C中的循环数组和消元，如何return最后一个"living"元素索引？

Question

我正在尝试编写一个代码来模拟 circle 固定大小的人拥有一把剑。最接近当前index的“活人”将被淘汰，剑将传递给下一个活人（被杀的人之后）等等。

我想写成不用链表的

示例： 3人一组： arr[0] = 1, arr[1] = 1, arr[2] = 1

第一轮：

arr[0] KILLS arr[1] and the sword gets PASSED to arr[2]

第一圈后的元素值：

arr[0] = 1, arr[1] = 0, arr[2] = 1

第二轮：

arr[2] KILLS arr[0] and stays the last player

第二轮后的元素值：

arr[0] = 0, arr[1] = 0, arr[2] = 1

arr[2]'s index gets returned by the main function.

我想到的是：

数组
将所有元素的值设为1
每次传阅检查if (1 == arr[i])
设置一个标志来决定是杀死还是只把剑传给这家伙。
return 当前索引表示最后一个活着的玩家的索引。

例如，假设我们组中有 5 个人： [1] [1] [1] [1] [1]

第一轮:

give_sword = 0

i = 0不输入第一个if，因为give_sword不是1。它进入第二个 if，并使用函数 findClosestLivingPerson 找到最近的活着的人并获取他的索引并将他的值设置为 0（== 杀死最近的活着的人）。它将 give_sword 设置为 1.

减少 players_counter 并检查是否只剩下一名玩家。如果没有，继续循环。

这是我的代码：

#include <stdio.h>

int findClosestLivingPerson(int arr[], int index, int group_size);


int main (int argc, char *argv[])
{
    
    int group_size = 0, players_counter = 0;
    int i = 0, give_sword = 0;
    int arr[100] = {0};
    
    printf("Enter group size: \n");
    scanf("%d",&group_size);
    
    for (i = 0; i < group_size; i++)
    {
         arr[i] = 1;
    }
   
    players_counter = group_size;
    
        for (i = 0; i < group_size; (i+1) % group_size)
        {
            if (1 == arr[i])
            {
                if(1 == give_sword) /* should give sword, not to kill */
                {
                    give_sword = 0;
                }
                else /* should be killed */
                {
                    arr[findClosestLivingPerson(arr,i, group_size)] = 0;
                    give_sword = 1;
                    --players_counter;
                    if (players_counter == 1)
                    { 
                        break;
                    }
                }
            }
        }
    printf("Winner is %d ",i);
    return 0;
}

int findClosestLivingPerson(int arr[], int index, int group_size)
{
    for (; index < group_size; (index+1) % group_size)
    {
        if (arr[index] == 1)
        return index;
    }
    return 0;
}

编译器说：

In function ‘main’: last_man.c:23:43: warning: statement with no effect [-Wunused-value] 23 | for (i = 0; i < group_size; (i+1) % group_size)

last_man.c: In function ‘findClosestLivingPerson’: last_man.c:49:42: warning: statement with no effect [-Wunused-value] 49 | for (; index < group_size; (index+1) % group_size)

(index+1) % group_size就是要循环这个数组。

Answer 1

正如编译器所说，(i+1) % group_size 没有效果。它计算 i 和 1 之和的余数。之后，它对结果不做任何处理。

for 语句的第三部分只是一个被求值的表达式。它不会自动更新循环索引或做任何其他事情。如果你想让它更新 i，你必须写一个赋值，比如 i = (i+1) % group_size.

Answer 2

我认为您误解了 for 循环的工作原理。

格式应该是这样的：

for( initialization, condition, iteration )

示例：

for( int i = 0; i < size; i = i + 1 )

(i + 1) % group_size 不是迭代（它不是将结果分配给 i ），你真正想做的是

i = ( i + 1 ) % group_size;

同样适用于第二次警告。

Answer 3

我建议采用不同的方法。让我们以一种产生漂亮代码的方式来做到这一点。

struct actor {
    int label;
    struct actor *next;
};

使用这个结构，我们可以创建一个漂亮的链表并将其循环回去：

int n = 5;
int i;

struct actor *actors = calloc(n, sizeof *actors);
for (i = 0; i < n - 1; i++) {
    actors[i].label = i;
    actors[i].next = &actors[i+1];
}
actors[i].label = i;
actors[i].next = &actors[0];

好的，现在我们可以分配第一个杀手了：

struct actor *k = actors;

我们还需要一个kill函数：

struct actor *kill(struct actor *a)
{
    if (a->next != a) {
        printf("%d kills %d\n", a->label, a->next->label);
        a->next = a->next->next;
    } else {
        printf("%d is last man standing\n", a->label);
        a->next = NULL;
    }
    return a->next;
}

这是做什么的：它从循环链表中删除下一个人（因为那是被杀死的人）。下一个人的查找时间总是相同的。

一切就绪后，我们就可以开始狂欢了：

while (k) {
    k = kill(k);
}

这无论如何都不是完美的代码，但它是一个很好的例子，说明如果您在设置上付出一些努力，您可以如何使算法变得异常简单。

C中的循环数组和消元，如何return最后一个"living"元素索引？

Circular array and elimination in C, how to return the last "living" element index?

c

arrays

function

circular-reference

josephus