为什么这个用于约瑟夫斯问题的算法在 c 中不起作用,而它在 python 中起作用?

Why isn't this algorithm for the Josephus problem working in c, when it works in python?

提问人:Vesal E.a 提问时间:11/9/2023 更新时间:11/10/2023 访问量:96

问:

因此,我需要解决约瑟夫斯问题的一个版本,在这个版本中,我们假设我们有 n 个机器人站成一个圆圈,所有这些机器人在开始时都处于开启状态。我们开始一轮一轮地关闭机器人。 1号机器人在第一轮中被关闭,然后我们计算打开的机器人,直到我们达到k号,然后我们关闭该机器人。 这个过程一直持续到一个机器人保持开启状态。

所以问题在于,我们应该编写一个算法,将 n 和 k 作为输入,并按顺序打印每轮关闭的机器人数组。 例如,如果 n = 13 且 k = 2,则答案为 1、3、5、7、9、11、13、4、8、12、6、2

我为这个问题写了一个 python 代码,打算之后将其转换为 C 下面是 python 代码,用于显示算法的一般思路:

n = int(input())
first = list(range(1 , n + 1)) 

k = int(input())

result = [] # with n - 1 segments

def removal(i):
    while i < len(first) - 1:
        first[i] = first[i + 1]
        i += 1
    first.pop() # n -= 1

i = 0
while len(first) > 1: # n > 1
    result.append(first[i])
    removal(i)
    i += k-1
    i %= len(first)

print(result)

这是 C 版本:

#include <stdio.h>

int main()
{
    int n , k;
    scanf("%d" , &n);
    scanf("%d" , &k);
    int len = n;
    int first[n + 1];
    
    int j = 0; //Taking array first as input
    while (j < n)
    {
        first[j] = j + 1;
        j++;
    }

    int result[n - 1];
    int i = 0;
    j = 0;

    while (n > 1)
    {
        result[j] = first[i]; 
        j++;

        while (i < n-1) //Removing the i th item of array first
        {
            first[i] = first[i + 1];
            i++;
        }
        n--;
        i += (k-1);
        i %= n;

    }
    
    j = 0;
    while (j < len-1)
    {
        printf("%d " , result[j]);
        j++;
    } 

    return 0;

}

例如,在我上面提到的情况下,当 n = 13 和 k = 2 时,C 代码打印: 1 3 4 5 6 7 8 9 10 11 12 13

正如我所说,python 代码有效,但它的 C 版本无效,我无法弄清楚为什么。 谁能解释一下我应该怎么做才能修复 c 中的代码?

蟒蛇 c 约瑟夫斯

评论

3赞 teapot418 11/9/2023
这是学习使用调试器的理想代码。试一试。
3赞 ikegami 11/9/2023
在 Python 程序中,有两个名为 .在 C 程序中,您只有一个用于这两种目的,因此包含垃圾。i
6赞 n. m. could be an AI 11/9/2023
Python代码有一个函数,C代码没有这样的功能。也许从使 C 代码更接近 Python 开始。removal(i)

答:

1赞 cTee 11/10/2023 #1

问题是 python 使用按值传递(请参阅按引用传递与按值传递有什么区别?),并且您的 C 程序在删除第 'th 元素时不会复制 的值,而是修改它。如果您将部分移除循环更改为:ii

int m = i;
while (m < n-1) //Removing the i th item of array first
{
    first[m] = first[m + 1];
    m++;
}

它应该像您预期的那样工作。这不是stackoverflow的问题,因为你可能已经从你得到的评论中猜到了。

评论

2赞 John Bollinger 11/10/2023
我没有看到你关于参数传递约定的观点。Python 和 C 都仅按值传递参数。在 Python 中,这些值都是引用,因为这是它唯一拥有的值,但最终无法将其与 C 在数值类型或列表/数组方面区分开来。
1赞 John Bollinger 11/10/2023
现在我仔细看了OP的C程序,我怀疑我知道你的意思了。然而,将传递价值带入其中只是令人困惑。
0赞 cTee 11/10/2023
我明白你的意思,但对我来说,了解这两个程序的区别至关重要,也许我应该以不同的方式表达。尽管如此,我认为 stackoverflow.com/users/775806/n-m-could-be-an-ai 的评论在这里就足够了。