Я не знаю, как хранить большое количество больших чисел, представленных в виде строки - PullRequest
3 голосов
/ 31 марта 2020

Я делаю университетский проект по предмету алгоритмов и структур данных, в котором мне приходится работать с очень большими целыми числами и выполнять с ними операции. Я реализовал числа в виде строк, а затем я реализовал различные функции для операций. Проблема заключается в том, что когда количество входных данных слишком велико, чтобы приложение продолжало работать без каких-либо ошибок.

Я попытался понять причину, по которой это происходит, и я сделал небольшую магистраль, в которой я беру только большие числа в виде строк и сохраните их в динамическом массиве c, а затем распечатайте их, но даже они продолжают работать без остановки.

int main(int argc, const char * argv[]) {
    int numOfNumbers;
    int numbersAdded=0;
    string input;
    string * arrayStrings;

    cin>>numOfNumbers;
    arrayStrings = new string[numOfNumbers];

    while(numbersAdded<numOfNumbers){
        cin>>input;
        arrayStrings[numbersAdded]=input;
        numbersAdded++;
    }

    for( int i = 0;i<numOfNumbers;i++){
        cout<<arrayStrings[i]<<endl;
    }
    delete arrayStrings; 
    return 0;
}

Пример записи, которую вы поймали:

100
1755128662250792726817307299021171022405
31602321932429919472347573932692115431
268613145625556
250995805115735123
2899821022216164821112051434821414118992115
27037278211962523201109134711837128617
279861141430143181518313
2556629007151952158131140
1196912232195651587224241
25217152742925013174325932918818704
127821054
253383867323001191423791
12348974130864
244901178019747324332994326262233310788
18871141121893613802910810566
298051220827966
22834322993767274181806121073176276959
12172351826990186206862376618791364
265732764173081220829716267442977319643273552225
24918204792116219043248262793915692401
1305831542
30700176671024343283713253592324315123
9631
1804116485164091127419645307015708
29922293842728930729216901755925702294991697
312452939618283102002333813782
97001726910215
23089
2228413461326671224530389
50281073851141324619663888524356
205537847
4387273422883676941299220683242529040
1068826033659423960273693499146131576
2353678092237010742
567428219113142508327393933916217
17519165136816290383310
171663253627992516622113674
13381174435173157252769015538248512802226982
18939548432449863556502935431668
227241606761772096923316172751849825321
28694
261158777214625061325511618639
26145245508605217823270225534
9144465612451
402063232412328332621313454157147811593510403
2974732438266188181
1971018749
2608143554273201627901930612227
167113264813914100695502
239491554826951684320992306102348527205832624426
322822701797512490321722
1222658617674291042489030110130720373
1918462976913296498889758915077263829448
272293167524341951427352662028327883857012375
174729150
1883623593305601460321897187512426209633019
8429505540641879120482112152815831074
2911590820561533087024079274326803
231262255129369314921398
30218
6853262887099
2979341273197322453071355192052510086228731082
6438195802600523532253931662830115
21455231162900119942
1839328344472262818266
2268711331105532851514258226702715029956686
1381271732204670982604920683
1750956011825180313080759535309
18306484
16752289242081714613984029594732346411804
269183243217101651922759
131903520
229283615302493931
25763
364627483502384441528056209239724
354632628
3536258474331130602772228026
287381151832596
28131307231326253372981510017858241118521
169071469721153
7226251212711565303162629173113572719
258312380924193826615620250272436820120
160731153614188
2355415899121291505218690251982485
2945329191793126217
199711279824919481281127503728828878916664
1846726425647269211818
2465830451616236642298932066180323217722337
2429926243493098211362313209
165211048224556263776021
7241210514
225393969266532086311050200721609924062
2391931833136282025125495
2211530320
15811209652225412597
104015738152769143240341892186871702212318
101430481142326694
327164589132301399725305
606829769525
136531485572681027581483494522825242

Ответы [ 3 ]

1 голос
/ 31 марта 2020

Я бы предложил не использовать строку для хранения номера. В вашем контексте контекстные строки будут занимать больше места и будут работать медленно.

Допустим, вы хотите сохранить номер 12345678901234567890. Теперь, если вы хотите сохранить этот номер, используя строку, вам потребуется 20 байтов (8 бит чар используется). String s = "12345678901234567890";

Вместо этого вы можете использовать массив целых чисел без знака. В большинстве современных компиляторов и компьютерных архитектур целое число составляет 4 байта. поэтому они могут представлять числа до 4 294 967 295. Теперь давайте рассмотрим, что наибольшее число является десятичным (все цифры - девять), которое может быть представлено целым числом без знака - 999 999 999. Если вы сейчас используете массив целых чисел, вам понадобятся только 3 целых числа. что составляет 12 байтов. целое число без знака [] = {234567890, 345678901, 12};

Теперь рассмотрим простое арифметическое c добавление операции. целое число без знака1 [] = {123456789, 123456789}; целое число без знака2 [] = {987654321, 987654321}; теперь, если вы хотите добавить два числа выше, у вас будет всего 2 итерации, чтобы получить ответ.

вы можете еще больше сжать готовый отпечаток памяти, если вы получили на битовом уровне. Это будет немного утомительной работой, но вы получите лучшую производительность.

0 голосов
/ 31 марта 2020

Касательно и, как правило, не имеет отношения к вышесказанному: «и если вам нужно сохранить« что-нибудь »в виде строки», вы всегда можете использовать JSON, YAML или XML. Эти форматы являются переносимыми, самоописуемыми и легко доступны.

0 голосов
/ 31 марта 2020

Ваша конкретная проблема c:

Проблема, с которой вы сталкиваетесь, заключается в том, что при вводе числа, большего, чем может содержать целое число со знаком, cin вводится в ошибку штат. Это означает, что последующие вызовы cin не будут работать, пока вы не наберете cin.clear().

. Прочтите об этом здесь: http://www.cplusplus.com/reference/ios/ios/clear/

Чтобы исправить код, попробуйте добавив cin.clear() после вызовов к cin следующим образом:

#include <iostream>
#include <string>

using namespace std;

int main(int argc, const char * argv[]) {

int numOfNumbers;
int numbersAdded=0;
string input;

/* todo: use a vector<string> instead - which handles resizing and allocation for you */
string * arrayStrings;

if (!(cin >> numOfNumbers))
{
    cout << "Warning: cin failed, did you enter a number larger than an numOfNumbers can hold? Value stored: " << numOfNumbers << endl;

    /* todo: maybe stop execution here and report back? */

    /* this will reset cin and leave numOfNumbers holding the largest value it can */
    cin.clear();
}

arrayStrings = new string[numOfNumbers];
/* todo: check the allocation succeeded, otherwise stop and report the error */

while(numbersAdded<numOfNumbers){
    if (!(cin >> input))
    {
        cout << "Warning: input failed, you entered a valid string? Value stored: " << input << endl;

        /* this will reset cin and leave input holding the largest value it can */
        cin.clear();
    }

    arrayStrings[numbersAdded]=input;
    numbersAdded++;
}

for( int i = 0;i<numOfNumbers;i++){
    cout<<arrayStrings[i]<<endl;
}

/* todo: this only deletes the array of pointers, not the strings themselves. Use a vector instead to avoid having to do memory management. */
delete arrayStrings; 
return 0;
}

Запуск вышеуказанной программы даст следующий вывод при вводе большого числа:

99999999999999999999999999999
Предупреждение: cin не удалось, вы ввели число больше, чем может содержать numOfNumbers Сохраненное значение: 2147483647

Лучший подход:

Как указали другие в комментариях есть и другие вещи, которые нужно привести здесь в порядок, используя vectors et c. Вот альтернативная реализация, которая чище и имеет больше проверки:

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(int argc, const char * argv[]) 
{
    unsigned int numOfNumbers;
    vector<string> numberStrings;

    cout << "How many numbers would you like to enter?" << endl;
    if (cin >> numOfNumbers)
    {
        unsigned int i;

        /* input numbers from console */
        cout << endl << "Please enter " << numOfNumbers << " numbers:" << endl;
        for (i = 0; i < numOfNumbers; i++)
        {
            string input;
            cin >> input;
            numberStrings.push_back(input);
        }

        /* print numbers out */
        cout << endl << "You entered:" << endl;
        for (const auto& num: numberStrings)
        {
            cout << num << endl;
        }
    }
    else
    {
        cout << "Number of numbers must be a positive integer less than " << UINT_MAX << endl;
    }

    return 0;
} /* vector magically deallocates when it leaves scope */
...