Trash value in a dynamic array in a structure. What am I doing wrong?

Question

Hello!

I do the calculation of factorial from 21 to 30. I use long arithmetic. The product of long and short numbers - wrote, works. I try to bring all this to mind with recursion, I compiled an algorithm, everything seems to be correct, but at the output I’m not getting the value, but the garbage. I do not understand what's wrong. Many questions arose while writing the program, but I was able to solve them all myself, although it was difficult, but here I have no idea how to solve them. Help me please. I suspect that the matter is in pointers, but I do not know how to fix it. I can not delay, I rummaged everything, I need to finish as quickly as possible, so I ask for help ... :(

I do it step by step, so for the time being I push off from the value of factorial 20 ( {0,0,0, 0,4,6, 6,7,1, 8,0,0, 2,0,9, 2,3,4, 2} ), and prescribed a multiplier for only 21 ( {1,2} ). I made factorial from 0 to 12 through int, factorial from 13 to 20 did through double, I thought then to combine it all, respectively, from 0 to 20 to do simple, and then through the product of long and short. Actually in this code just from 21 to 30 I do ...

#include "stdafx.h" #include <stdio.h> struct Result { int* res; int size; }; struct FResult { int* numb1; int* numb2; int size1; int size2; int number; }; Result multiply(int number1[], int number2[], int size_number1, int size_number2) { int length = size_number1 + size_number2 + 1; int* subresult = new int[length] {0, }, *result = new int[length] {0, }; int integer = 0, PlusSubResLen = 0; for (int j = 0; j < size_number2; j++) { for (int i = 0; i < size_number1; i++) { subresult[i + j] = (number1[i] * number2[j] + integer) % 10; //остаток integer = (number1[i] * number2[j] + integer) / 10; //целое, перенос } if (integer > 0) //последний знак { subresult[size_number1 + PlusSubResLen] = integer; //конечный символ в результе <--- сдвиг PlusSubResLen++; integer = 0; } for (int i = 0; i <= size_number1 + PlusSubResLen; i++) //сложение массивов { int temp = (result[i] + subresult[i] + integer) % 10; integer = (result[i] + subresult[i] + integer) / 10; result[i] = temp; subresult[i] = 0; } } int leadnull = -1; bool check = false; for (int i = 0; i < length; i++) //проверка на лидирующие нули { if (check == false) { if (result[i] == 0) { leadnull = i; check = true; } } else { if (result[i] != 0) { check = false; } } } length = leadnull; //перезадаю длинну, для очевидности int* finalresult = new int[length]; //создаю массив нужной длинны for (int i = 0; i < length; i++) //записываю данные во временный массив (по сути конечный) { finalresult[i] = result[i]; } Result final; final.res = new int[length]; final.res = finalresult; final.size = length; return final; } FResult factorial_21To30(FResult old_result) { FResult final; if (old_result.number == 20) { int number1[] = { 0, 0, 0, 0, 4, 6, 6, 7, 1, 8, 0, 0, 2, 0, 9, 2, 3, 4, 2 }; //20! int number2[] = { 0, 2 }; //20 final.numb1 = new int[19]; final.numb1 = number1; final.numb2 = new int[2]; final.numb2 = number2; final.size1 = 19; final.size2 = 2; final.number = 19; //предыдущий типо } else { int number2[] = { 1, 2 }; //времянка <------------------ Result subfinal; subfinal = multiply(old_result.numb1, number2, old_result.size1, 2); // большое число, малое число, размер большого, размер малого final.numb1 = new int[subfinal.size]; final.numb1 = subfinal.res; final.numb2 = new int[2]; final.numb2 = number2; //<--- final.size1 = subfinal.size; final.size2 = 2; //<---- final.number = old_result.number - 1; final = factorial_21To30(final); } return final; } int main() { FResult final; int number1[] = { 0, 0, 0, 0, 4, 6, 6, 7, 1, 8, 0, 0, 2, 0, 9, 2, 3, 4, 2 }; //20! число записано наоборот int number2[] = { 0, 2 }; //20 число записано наоборот final.numb1 = new int[19]; final.numb1 = number1; final.numb2 = new int[2]; final.numb2 = number2; final.size1 = 19; final.size2 = 2; final.number = 21; // если 20, то факториал 20, если 21, то рекурсия и выводит факториал 21 final = factorial_21To30(final); printf("Novaya stroka:\n"); for (int i = final.size1 - 1; i >= 0; i--) //вывод результата { printf("%d", final.numb1[i]); } int number2_2[] = { 1, 2 }; Result finalMult; finalMult = multiply(number1, number2_2, final.size1, final.size2); printf("\nNovaya stroka:\n"); for (int i = finalMult.size - 1; i >= 0; i--) //вывод результата { printf("%d", finalMult.res[i]); } int s; scanf("%d", &s); return 0; }

Result:

And if you slightly change the main (chose factorial 20, i.e. factorial 20 should be displayed, without calculations even without entering recursion):

 int main() { FResult final; int number1[] = { 0, 0, 0, 0, 4, 6, 6, 7, 1, 8, 0, 0, 2, 0, 9, 2, 3, 4, 2 }; //20! число записано наоборот int number2[] = { 0, 2 }; //20 число записано наоборот final.numb1 = new int[19]; final.numb1 = number1; final.numb2 = new int[2]; final.numb2 = number2; final.size1 = 19; final.size2 = 2; final.number = 20; // если 20, то факториал 20, если 21, то рекурсия и выводит факториал 21 FResult final2; final2 = factorial_21To30(final); printf("Novaya stroka:\n"); for (int i = final2.size1 - 1; i >= 0; i--) //вывод результата { final2.numb1[i] = factorial_21To30(final).numb1[i]; printf("%d", final2.numb1[i]); } printf("\nNovaya stroka:\n"); for (int i = final2.size1 - 1; i >= 0; i--) //вывод результата { printf("%d", final2.numb1[i]); } int s; scanf("%d", &s); return 0; }

Then I get the following result:

Those. in fact, I derive the same array twice, and I get a different result ...

And what are you doing in a row final.numb1 = new int[19]; final.numb1 = number1;
First I create the array final.numb1, then assign it the values of the array number1.
Have you ever wondered why in both cases there is a = sign?
The fact is that copying an array with the = sign does not occur at all.

Answer 1 · 2016-11-30T15:57:25

Garbage because UB is happening to you, at least here:

 int length = size_number1 + size_number2 + 1; int* subresult = new int[length] {0, }, *result = new int[length] {0, }; int integer = 0, PlusSubResLen = 0; for (int j = 0; j < size_number2; j++) { for (int i = 0; i < size_number1; i++) { subresult[i + j] = (number1[i] * number2[j] + integer) % 10; //остаток integer = (number1[i] * number2[j] + integer) / 10; //целое, перенос } // ниже по коду вы будете выходить за границы массивов // если окажется что size_number1 + PlusSubResLen >= lenght, // это может произойти если size_number1 < size_number2 // и если PlusSubResLen >= size_number2, то есть если // будет много переносов if (integer > 0) //последний знак { subresult[size_number1 + PlusSubResLen] = integer; //конечный символ в результе <--- сдвиг PlusSubResLen++; integer = 0; } for (int i = 0; i <= size_number1 + PlusSubResLen; i++) //сложение массивов { // здесь вы бужете выходить за границы массивов // если окажется что size_number1 + PlusSubResLen >= lenght // int temp = (result[i] + subresult[i] + integer) % 10; integer = (result[i] + subresult[i] + integer) / 10; result[i] = temp; subresult[i] = 0; } }

It seemed to me that with PlusSubResLen and the lengths of the arrays I took into account the right moments.
And when checking, in this function, works of long on short numbers - there were no problems.
Of course, I did not check everything, but I checked 20, 21, 23 and some small ones, Tipo 7 ..
Imagine that you have integer > 0 at each iteration, then if size_number1 <= size_number2 , it turns out that PlusSubResLen >= size_number1 .

VladD VladD 183k 16 gold signs 228 silver marks 434 bronze marks · Answer 2 · 2016-11-30T15:33:09

Look, since you are already writing in C ++, and not in C, it makes sense to switch to idiomatic data structures for C ++. It is necessary not to carry along pointers and lengths, it is better to use std::vector and not to look for errors in manual memory management. The result is this:

struct Result gone, instead of it will be a vector<int> .

struct FResult will look something like this:

 struct FResult { vector<int> numb1; vector<int> numb2; int number; };

Code

 int* finalresult = new int[length]; //создаю массив нужной длинны for (int i = 0; i < length; i++) //записываю данные во временный массив (по сути конечный) { finalresult[i] = result[i]; }

will turn into

 vector<int> finalresult(length); for (int i = 0; i < length; i++) { finalresult[i] = result[i]; }

etc.

In this case, most of the memory problems should go away. If there are still problems, it will most likely be algorithmic problems.

My brain was boiling for too long today, I can’t get together, to adequately perceive and understand something, tomorrow I will try to redo it according to your proposal.
And with the transfer of values through the function should not be a problem?
@IgRRR: Well, if you pass a vector by value, it will be copied.

Answer 3 · 2016-11-30T15:53:22

I can not say that this is the answer, but in addition to the above comments, if you really want to copy the values of one array into another, then you can cycle through assigning each element of the assigned array an element of another, identical in number.

Look carefully at the debug and create a breakpoint in this problematic line and you will see that the elements of the old_result.numb1 array in

subfinal = multiply(old_result.numb1, number2, old_result.size1, 2);

always equal to zero, even if I expose all elements in the array int number1[] other than zero. In addition, you allocate memory for arrays and do not use it.

there was such a thought, but how to be admissible, here: final = factorial_21To30 (final);

Trash value in a dynamic array in a structure. What am I doing wrong?

3 answers 3

More articles: