c - 学生储物柜问题(需要数组内交替)

Question

我必须解决这个问题:

A school has 100 lockers and 100 students. Student 1 opens all lockers. Student 2 toggles every 2nd locker starting from the first. Student 3 toggles every 3rd locker, starting from the back (the 100th). This goes all the way to the Nth student. (They alternate, starting from the back or front).

我必须在最后展示打开的储物柜。我似乎无法弄清楚如何使交替要求起作用。到目前为止，这是代码:

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

#define MAX_LOCKERS 100
#define MAX_STUDENTS 100

int main (void)
{
int i, n;
bool locker[MAX_LOCKERS + 1];

for ( i = 1; i <= 100; ++i )
    locker[i] = true;

for ( i = 2; i <= 100; ++i ) 
    for ( n = i; n <= 100; n += i )
        locker[n] = ! locker[n];
        if ( locker[i] )
            printf ("%i ", i);

printf ("\nThe open lockers are: ");

for ( i = 1; i <= 100; ++i )
    if ( locker[i] )
        printf ("%i ", i);

return 0;
}

Answer 1

这是一个有趣的问题，应该取决于奇数/偶数来确定是从开始到结束还是从结束到开始 em> 为所有学生打开储物柜门。

如果您将元素编号(例如for ( i = 1; i <= 100; ++i ))与数组索引(例如for (i = 0; i < 100; i++))混合在一起，您会感到非常困惑。始终最好记住数组在 C 中是零索引 并且在循环限制循环中保持一致 0 -> n-1而不是 1 -> n

(注意:两者当然都是合法的，但使用实际索引消除了因调整失败而off-by-one违反数组边界的可能性循环时的索引 1 -> n )

(edit-note:我在循环增量上差了一个——已修复)

打开所有储物柜后的基本方法是循环实际剩余的学生索引，循环1 -> n-1 .如果当前学生是奇数，则从头到尾切换储物柜。如果当前学生是偶数，则计算当前值的倍数可以达到的最后一个索引(例如 end = (100 / current) * current) 有意进行整数除法。(您可能需要 end = 100 - (current+1); 取决于您是否想要从学生 3 的末尾开始第 3 个，等等...)现在从 end 开始循环，同时大于或等于零切换储物柜。

如果您编写一个简单的切换储物柜函数，它可能有助于简化事情，例如

void toggle (int *locker, int idx)
{
    if (locker[idx])        /* if locker open */
        locker[idx] = 0;    /* close it */
    else                    /* otherwise */
        locker[idx] = 1;    /* open it */
}

然后避免在代码的主要逻辑中重复条件。您的代码使用 bool ，这很好，但我通常只使用 int反而。因此，对于您的主要逻辑，您可以使用类似于以下内容的内容:

    int i, j;
    int locker[MAX_LOCKERS + 1];

    for (i = 0; i < 100; i++)                   /* open all lockers */
        locker[i] = 1;

    for (i = 1; i < 100; i++) {                 /* loop all other students */
        if (i % 2 == 1)                         /* odd, from start */
            for (j = i; j < 100; j += (i+1))    /* loop j=i , j += (i+1) */
                toggle (locker, j);             /* toggle lockers at j */
        else {                                  /* if even index */
            int end = (100 / i) * i;            /* get end index by i */
            for (j = end; j >= 0; j -= (i+1))   /* from end, loop j -= (i+1) */
                toggle (locker, j);             /* toggle lockers at j */
        }
    }

总而言之，(让您用 MAX_STUDENTS 代替您在代码中对 100 的使用)，您可以执行类似以下操作:

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

#define MAX_LOCKERS 100
#define MAX_STUDENTS 100

void toggle (int *locker, int idx)
{
    if (locker[idx])        /* if locker open */
        locker[idx] = 0;    /* close it */
    else                    /* otherwise */
        locker[idx] = 1;    /* open it */
}

int main (void)
{
    int i, j;
    int locker[MAX_LOCKERS + 1];

    for (i = 0; i < 100; i++)                   /* open all lockers */
        locker[i] = 1;

    for (i = 1; i < 100; i++) {                 /* loop all other students */
        if (i % 2 == 1)                         /* odd, from start */
            for (j = i; j < 100; j += (i+1))    /* loop j=i , j += (i+1) */
                toggle (locker, j);             /* toggle lockers at j */
        else {                                  /* if even index */
            int end = (100 / i) * i;            /* get end index by i */
            for (j = end; j >= 0; j -= (i+1))   /* from end, loop j -= (i+1) */
                toggle (locker, j);             /* toggle lockers at j */
        }
    }

    for (i = 0; i < 100; i++) {     /* output results in grid form */
        if (i && i % 10 == 0)
            putchar ('\n');
        printf (" %s", locker[i] ? "[x]" : "[ ]");
    }
    putchar ('\n');

    return 0;
}

示例使用/输出

以网格形式输出储物柜的最终状态，(你可以做任何你喜欢的)

$ ../bin/openlockers2
 [ ] [ ] [x] [x] [ ] [ ] [ ] [x] [ ] [x]
 [x] [ ] [x] [ ] [ ] [x] [x] [ ] [ ] [ ]
 [ ] [ ] [ ] [x] [x] [x] [x] [x] [ ] [x]
 [x] [ ] [x] [x] [x] [x] [x] [ ] [ ] [ ]
 [ ] [ ] [x] [x] [ ] [x] [x] [x] [x] [ ]
 [ ] [x] [ ] [ ] [x] [ ] [x] [ ] [ ] [ ]
 [ ] [x] [x] [ ] [x] [x] [ ] [x] [x] [ ]
 [x] [ ] [x] [ ] [ ] [x] [ ] [x] [x] [ ]
 [ ] [x] [ ] [x] [ ] [x] [ ] [ ] [x] [x]
 [x] [ ] [x] [x] [x] [ ] [x] [x] [x] [x]

[x] - 储物柜打开。 (如果它对你更有意义，你可能想要交换它)

注意:这是为了展示一种方法来处理您的学生通过剩余学生数向前或向后学习。 我没有花时间验证逻辑是否正确......我怀疑它是(或非常接近)，但正确性的最终验证留给你。

如果使用 end 的替代定义到，例如从第 3 个学生开始切换到第 3 个，你将拥有:

            int end = 100 - (i+1);
            for (j = end; j >= 0; j -= (i+1))   /* from end, loop j -= (i+1) */
                toggle (locker, j);             /* toggle lockers at j */

因此:

$ ./bin/openlockers2
 [x] [x] [x] [ ] [ ] [ ] [ ] [x] [ ] [ ]
 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [x] [ ] [x]
 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [x] [ ]
 [ ] [x] [ ] [ ] [ ] [ ] [x] [ ] [ ] [ ]
 [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [x]
 [x] [x] [ ] [ ] [ ] [ ] [ ] [ ] [ ] [ ]
 [ ] [ ] [ ] [ ] [x] [ ] [ ] [ ] [x] [ ]
 [ ] [x] [ ] [ ] [ ] [x] [ ] [ ] [ ] [ ]
 [ ] [ ] [x] [ ] [x] [ ] [ ] [ ] [ ] [ ]
 [ ] [x] [x] [ ] [ ] [ ] [x] [x] [x] [x]

检查一下，如果您还有其他问题，请告诉我。