提问人:Vesal E.a 提问时间:11/9/2023 更新时间:11/10/2023 访问量:96
为什么这个用于约瑟夫斯问题的算法在 c 中不起作用,而它在 python 中起作用?
Why isn't this algorithm for the Josephus problem working in c, when it works in python?
问:
因此,我需要解决约瑟夫斯问题的一个版本,在这个版本中,我们假设我们有 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 中的代码?
答:
1赞
cTee
11/10/2023
#1
问题是 python 使用按值传递(请参阅按引用传递与按值传递有什么区别?),并且您的 C 程序在删除第 'th 元素时不会复制 的值,而是修改它。如果您将部分移除循环更改为:i
i
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 的评论在这里就足够了。
评论
i
removal(i)