我被要求将这个伪代码翻译成C程序:
rep := 0
while A not empty:
B := []
for x in A, y in A:
if x != y: append absolute_value(x - y) to B
A := B
rep := rep + 1
我最终得到了这个:
int iterateIt(int a_count, int* a) {
unsigned long long i, j, k;
unsigned long long count = a_count;
for( i = 1 ; i < a_count ; i++ )
count *= count-1;
int *b = (int *) malloc(count * sizeof(int));
count = 0;
k = 0;
for( i = 0 ; i < a_count ; i++ ){
for( j = i ; j < a_count ; j++ ){
if(a[i] != a[j]){
b[k] = abs(a[i] - a[j]);
k++;
}
}
}
if( k > 0){
return 1 + iterateIt(k, b);
}
free(b);
return 1;
}
我使用递归来返回算法的迭代次数。实际上,我将A中任意两个不同对象之间的差异区分开来,并将绝对值放在B中,然后重复出现。对于简单的输入我得到了正确的结果,但我不明白为什么输入如:16
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768
或4
1 352 9483 50000
(第一个数字是A的元素数)
我收到了分段错误错误。
谢谢您的帮助
我认为你的count
是错误的。你的第二次迭代已经很糟糕了。
#include <stdio.h>
#include <stdlib.h>
size_t total_allocated = 0;
int iterateIt(int a_count, int* a) {
unsigned long long i, j, k;
unsigned long long count = a_count;
for( i = 1 ; i < a_count ; i++ )
count *= count-1;
size_t size = count * sizeof(int);
printf("Allocating %llu ints: %llu bytes\n", count, (unsigned long long)size);
total_allocated += size;
printf("Total allocated: %llu bytes\n", (unsigned long long)total_allocated);
int *b = (int *) malloc(count * sizeof(int));
count = 0;
k = 0;
for( i = 0 ; i < a_count ; i++ ){
for( j = i ; j < a_count ; j++ ){
if(a[i] != a[j]){
b[k] = abs(a[i] - a[j]);
k++;
}
}
}
if( k > 0){
return 1 + iterateIt(k, b);
}
free(b);
return 1;
}
int main (void)
{
iterateIt(4, (int[4]){1,352,9483,50000});
return 0;
}
结果:
Allocating 17292 ints: 69168 bytes
Total allocated: 69168 bytes
Allocating 12550317587327992670 ints: 13307782201892867448 bytes
Total allocated: 13307782201892936616 bytes
首先考虑这一行:
return 1 + iterateIt(k, b);
b
阵列永远不会在这个return
上被释放,但如果k
为零,那就确实如此。让我们重写一下这段代码来清理一下:
#include <stdio.h>
#include <stdlib.h>
unsigned iterateIt(size_t a_count, int *a) {
unsigned rep = 1;
int *b = calloc(a_count * a_count, sizeof(int));
size_t k = 0;
for (size_t i = 0; i < a_count; i++) {
for (size_t j = i + 1; j < a_count; j++) {
if (a[i] != a[j]) {
b[k++] = abs(a[i] - a[j]);
}
}
}
if (k > 0) {
rep += iterateIt(k, b);
}
free(b);
return rep;
}
int main() {
int x[] = {1, 324, 54};
printf("%u\n", iterateIt(sizeof(x) / sizeof(int), x));
return 0;
}
观察a_count
的值,该程序试图分配太多内存并失败。
UPDATE
由于矩阵的两半最终相同,我修复了上面的代码以执行OP所做的事情,只处理1/2矩阵,即j
从i + 1
开始,因为两半最终相同。我也忽略了对角线,因为它总是零。然后代码完成我的示例代码中的三个数字,但当我将数组增加到四个值时再次爆炸。
我相信OP解决方案的递归性质优雅而且没有问题,但只是要确认,这是一个无法执行的迭代解决方案,而不是由于缺少堆栈内存:
unsigned iterateIt(size_t a_count, int *a) {
unsigned rep = 1;
bool first_time = true;
while (true) {
int *b = calloc((a_count * a_count) / 2, sizeof(int));
if (b == NULL) {
perror("calloc failed!");
exit(1);
}
size_t b_count = 0;
for (size_t i = 0; i < a_count; i++) {
for (size_t j = i + 1; j < a_count; j++) {
if (a[i] != a[j]) {
b[b_count ++] = abs(a[i] - a[j]);
}
}
}
if (b_count == 0) {
free(b);
break;
}
if (first_time) {
first_time = false;
} else {
free(a);
}
a = b;
a_count = b_count;
rep++;
}
return rep;
}