0

I've designed a code to solve the Frobenuis coin problem.

#define _CRT_SECURE_NO_WARNINGS

int numberOfPences;
printf("Enter pences quantity: ");
scanf("%d", &numberOfPences);
int k=8;
int coins[8] = {1, 2, 5, 10, 20, 50, 100, 200};
printf("Start memory allocation with size %d.\n", sizeof(long long));
long long ** computed = (long long **)malloc((k+1)*sizeof(long long *) + (k+1)*(numberOfPences+1)*sizeof(long long ));
for(int i = 0; i <= k; ++i)
{
            computed[i] = (long long *)malloc((numberOfPences+1)*sizeof(long long));
}
free(computed);
for(int i=0; i<k+1; i++)
{
     for(int j=1; j<numberOfPences+1; j++)
     {
                computed[i][j]= 0LL;
     }
}
computed[0][1]=1LL;
long long s = number_of_dec(numberOfPences, coins, k, computed);
printf("Number of variants : %d.\n", s);
return(0);
}

I cannot understand why sometimes it works, and sometimes it crushes with "Segmentation fault (core dumped)" even without stepping into number_of_dec function. Can you please help me on what am I doing wrong? I think that the problem is with memory allocation, since the same algorithm on Python is working allright.

Andrey Novikov
  • 31
  • 2
  • Please provide stack trace too. – Dr. Andrey Belkin Apr 02 '20 at 11:47
  • To begin with please take some time to read [the help pages](http://stackoverflow.com/help), take the SO [tour], read [ask], as well as [this question checklist](https://codeblog.jonskeet.uk/2012/11/24/stack-overflow-question-checklist/). Lastly please learn how to create a [mcve] and how to [edit] your question to show it. – Some programmer dude Apr 02 '20 at 11:48
  • Enter pences quantity: 14 Start memory allocation with size 8. Segmentation fault (core dumped) – Andrey Novikov Apr 02 '20 at 11:49
  • 1
    Um... `free(computed);` ? That's... wrong. You allocate a pointer array, then allocate vectors for each pointer in the array, then `free` the pointer array (and orphan `k+1` vector allocations in the process), then enumerate the now-gone pointer array and invoke *undefined behavior* to dereference elements. – WhozCraig Apr 02 '20 at 11:50
  • 1
    You have `free(computed);` but continue to use `computed`. That leads to *undefined behaviour*. – Weather Vane Apr 02 '20 at 11:50
  • I replaced it to the end of the program. Still got the same problem. I do not understand the logic of why it is working SOMETIMES (when numberOfPences is rather small). This is very misleading, since I have expected that if something is THAT wrong, it should not work at all. – Andrey Novikov Apr 02 '20 at 11:58
  • This size calculation looks weird: `long long ** computed = (long long **)malloc((k+1)*sizeof(long long *) + (k+1)*(numberOfPences+1)*sizeof(long long ));` `computed` points to a pointer. Therefore I would not exprect any other size than `sizeof(long long*)` in the calculation. No `sizeof(long long)`. Also in C the result of `malloc` should not be cast. – Gerhardh Apr 02 '20 at 12:18
  • Operator `sizeof` evaluates to a value of type `size_t`. `%d` is not the correct format specifier to print this. Use `%zu` instead. – Gerhardh Apr 02 '20 at 12:26

0 Answers0