Я застрял на этом словесном арифметическом алгоритме
Задана строка формата (11 символов, без пробела) в виде ABC + DEF = GHI, где A, B, C, D, E,
F, G, H, I представляют десятичную цифру (0, 1, 2, 3, 4, 5, 6, 7, 8, 9) «заполнители» (не обязательно различаются!),
разработать и внедрить алгоритм для нахождения трехзначных положительных чисел (ABC, DEF и GHI), которые
дать максимальный GHI в соответствии с данным равенством. Буквы (A, B, C, D, E, F, G, H, I) являются «заполнителями», поэтому у вас могут быть повторяющиеся цифры. Например, в формуле ABA + BBB = GGB все B представляют
та же десятичная цифра. Ваш алгоритм должен также проверить, если такие числа невозможно найти. Например,
для формулы AAB + AAB = AAB его невозможно удовлетворить десятичными цифрами. Ваша программа будет
скажите «Нет решения!». Возможно, существует более одного решения. В этом случае просто выведите первое, которое найдет ваш алгоритм. Продолжайте, пока пользователь не введет -1 для формулы, по которой ваша программа выйдет, сказав «Пока!».
Вот примерный прогон:
Введите формулу: AAB + AAB = AAB
Нет решения!
Введите формулу: AAA + BBB = AAA
999 + 000 = 999
Введите формулу: -1
До свидания!
Вот код, который я написал раньше:
#include<iostream>
#include<cmath>
#include<string>
using namespace std;
int main()
{
string str = "abcdefghi";
string num = "0123456789";
string formula;
int var1[3];
int var2[3];
int var3[3];
while (1)
{
cout << "Enter the formula: ";
cin >> formula;
if (formula == "-1")
{
cout << "Bye" << endl;
break;
}
else
{
for (int i = 0; i < str.length(); i++)
{
if (formula.at(0) == str.at(i))
{
var1[0] = i;
}
if (formula.at(1) == str.at(i))
{
var1[1] = i;
}
if (formula.at(2) == str.at(i))
{
var1[2] = i;
}
}
for (int i = 0; i < str.length(); i++)
{
if (formula.at(4) == str.at(i))
{
var2[0] = i;
}
if (formula.at(5) == str.at(i))
{
var2[1] = i;
}
if (formula.at(6) == str.at(i))
{
var2[2] = i;
}
}
for (int i = 0; i < str.length(); i++)
{
if (formula.at(8) == str.at(i))
{
var3[0] = i;
}
if (formula.at(9) == str.at(i))
{
var3[1] = i;
}
if (formula.at(10) == str.at(i))
{
var3[2] = i;
}
}
if (var1[0] + var2[0] == var3[0] && var1[1] + var2[1] == var3[1] && var1[2] + var2[2] == var3[2])
cout << var1[0] << var1[1] << var1[2] << "+" << var2[0] << var2[1] << var2[2] << "=" << var3[0] << var3[1] << var3[2] << endl << endl;
else
cout << "No Solution!" << endl << endl;
}
}
system("pause");
return 0;
}
Но это, похоже, не решает проблему точно. Как я могу изменить свой код, чтобы получить то, что хочет этот вопрос.
Решение
Ответ может быть найден грубой силой. Предположим, у вас есть массив или вектор из 10 цифр. С 10 возможными цифровыми значениями есть 10! = 3628800 возможных перестановок. Из каждой перестановки вы можете назначить первые 9 элементов каждой из 9 возможных букв, чтобы проверить, обеспечивает ли это новое максимальное значение.
Если ваши буквенные значения находятся в int letter_vals[10]; например, затем вы заполняете начальные значения:
std::iota(std::begin(letter_vals), std::end(letter_vals), 0);
Затем вы можете выполнить итерацию возможных назначений букв:
while (std::next_permutation(std::begin(letter_vals), std::end(letter_vals) )) {
Строка может быть преобразована в значение посредством перестановки, например,
val1 = letter_vals[(var1[0] - 'A')]*100;
val1 += letter_vals[(var1[1] - 'A')]*10;
val1 += letter_vals[(var1[2] - 'A')]*1;
Если разные буквы могут представлять одну и ту же цифру, то вы могли бы также применить грубую силу, но тогда у вас будет 10 возможных значений на букву и 9 букв для общего числа 10 ^ 9 возможных комбинаций. Возможно что-то вроде:
for(size_t i{0}; i <= 999999999; ++i) {
auto current_num{i};
for(auto& letter_val : letter_vals) {
letter_val = current_num % 10;
current_num /= 10;
}
std::reverse(std::begin(letter_vals), std::end(letter_vals));
Ответы различаются в зависимости от того, допускаются ли повторяющиеся цифры. Без повторяющихся цифр программа намного быстрее, с меньшим количеством ответов:
Оценка: AAC + BBF = GHI
New max answer found: 345
116+229=345
New max answer found: 346
117+229=346
New max answer found: 347
118+229=347
New max answer found: 450
112+338=450
New max answer found: 456
117+339=456
New max answer found: 457
118+339=457
New max answer found: 560
112+448=560
New max answer found: 562
113+449=562
New max answer found: 567
118+449=567
New max answer found: 670
112+558=670
New max answer found: 672
113+559=672
New max answer found: 673
114+559=673
New max answer found: 782
113+669=782
New max answer found: 783
114+669=783
New max answer found: 784
115+669=784
New max answer found: 890
114+776=890
New max answer found: 891
224+667=891
Maxval was: 891
224+667=891
С повторяющимися цифрами существует больше возможных комбинаций:
Evaluating: AAC+BBF=GHI
New max answer found: 1
000+001=001
New max answer found: 2
000+002=002
New max answer found: 3
000+003=003
New max answer found: 4
000+004=004
New max answer found: 5
000+005=005
New max answer found: 6
000+006=006
New max answer found: 7
000+007=007
New max answer found: 8
000+008=008
New max answer found: 9
000+009=009
New max answer found: 10
001+009=010
New max answer found: 11
002+009=011
New max answer found: 12
003+009=012
New max answer found: 13
004+009=013
New max answer found: 14
005+009=014
New max answer found: 15
006+009=015
New max answer found: 16
007+009=016
New max answer found: 17
008+009=017
New max answer found: 18
009+009=018
New max answer found: 110
000+110=110
New max answer found: 111
000+111=111
New max answer found: 112
000+112=112
New max answer found: 113
000+113=113
New max answer found: 114
000+114=114
New max answer found: 115
000+115=115
New max answer found: 116
000+116=116
New max answer found: 117
000+117=117
New max answer found: 118
000+118=118
New max answer found: 119
000+119=119
New max answer found: 120
001+119=120
New max answer found: 121
002+119=121
New max answer found: 122
003+119=122
New max answer found: 123
004+119=123
New max answer found: 124
005+119=124
New max answer found: 125
006+119=125
New max answer found: 126
007+119=126
New max answer found: 127
008+119=127
New max answer found: 128
009+119=128
New max answer found: 220
000+220=220
New max answer found: 221
000+221=221
New max answer found: 222
000+222=222
New max answer found: 223
000+223=223
New max answer found: 224
000+224=224
New max answer found: 225
000+225=225
New max answer found: 226
000+226=226
New max answer found: 227
000+227=227
New max answer found: 228
000+228=228
New max answer found: 229
000+229=229
New max answer found: 230
001+229=230
New max answer found: 231
002+229=231
New max answer found: 232
003+229=232
New max answer found: 233
004+229=233
New max answer found: 234
005+229=234
New max answer found: 235
006+229=235
New max answer found: 236
007+229=236
New max answer found: 237
008+229=237
New max answer found: 238
009+229=238
New max answer found: 330
000+330=330
New max answer found: 331
000+331=331
New max answer found: 332
000+332=332
New max answer found: 333
000+333=333
New max answer found: 334
000+334=334
New max answer found: 335
000+335=335
New max answer found: 336
000+336=336
New max answer found: 337
000+337=337
New max answer found: 338
000+338=338
New max answer found: 339
000+339=339
New max answer found: 340
001+339=340
New max answer found: 341
002+339=341
New max answer found: 342
003+339=342
New max answer found: 343
004+339=343
New max answer found: 344
005+339=344
New max answer found: 345
006+339=345
New max answer found: 346
007+339=346
New max answer found: 347
008+339=347
New max answer found: 348
009+339=348
New max answer found: 440
000+440=440
New max answer found: 441
000+441=441
New max answer found: 442
000+442=442
New max answer found: 443
000+443=443
New max answer found: 444
000+444=444
New max answer found: 445
000+445=445
New max answer found: 446
000+446=446
New max answer found: 447
000+447=447
New max answer found: 448
000+448=448
New max answer found: 449
000+449=449
New max answer found: 450
001+449=450
New max answer found: 451
002+449=451
New max answer found: 452
003+449=452
New max answer found: 453
004+449=453
New max answer found: 454
005+449=454
New max answer found: 455
006+449=455
New max answer found: 456
007+449=456
New max answer found: 457
008+449=457
New max answer found: 458
009+449=458
New max answer found: 550
000+550=550
New max answer found: 551
000+551=551
New max answer found: 552
000+552=552
New max answer found: 553
000+553=553
New max answer found: 554
000+554=554
New max answer found: 555
000+555=555
New max answer found: 556
000+556=556
New max answer found: 557
000+557=557
New max answer found: 558
000+558=558
New max answer found: 559
000+559=559
New max answer found: 560
001+559=560
New max answer found: 561
002+559=561
New max answer found: 562
003+559=562
New max answer found: 563
004+559=563
New max answer found: 564
005+559=564
New max answer found: 565
006+559=565
New max answer found: 566
007+559=566
New max answer found: 567
008+559=567
New max answer found: 568
009+559=568
New max answer found: 660
000+660=660
New max answer found: 661
000+661=661
New max answer found: 662
000+662=662
New max answer found: 663
000+663=663
New max answer found: 664
000+664=664
New max answer found: 665
000+665=665
New max answer found: 666
000+666=666
New max answer found: 667
000+667=667
New max answer found: 668
000+668=668
New max answer found: 669
000+669=669
New max answer found: 670
001+669=670
New max answer found: 671
002+669=671
New max answer found: 672
003+669=672
New max answer found: 673
004+669=673
New max answer found: 674
005+669=674
New max answer found: 675
006+669=675
New max answer found: 676
007+669=676
New max answer found: 677
008+669=677
New max answer found: 678
009+669=678
New max answer found: 770
000+770=770
New max answer found: 771
000+771=771
New max answer found: 772
000+772=772
New max answer found: 773
000+773=773
New max answer found: 774
000+774=774
New max answer found: 775
000+775=775
New max answer found: 776
000+776=776
New max answer found: 777
000+777=777
New max answer found: 778
000+778=778
New max answer found: 779
000+779=779
New max answer found: 780
001+779=780
New max answer found: 781
002+779=781
New max answer found: 782
003+779=782
New max answer found: 783
004+779=783
New max answer found: 784
005+779=784
New max answer found: 785
006+779=785
New max answer found: 786
007+779=786
New max answer found: 787
008+779=787
New max answer found: 788
009+779=788
New max answer found: 880
000+880=880
New max answer found: 881
000+881=881
New max answer found: 882
000+882=882
New max answer found: 883
000+883=883
New max answer found: 884
000+884=884
New max answer found: 885
000+885=885
New max answer found: 886
000+886=886
New max answer found: 887
000+887=887
New max answer found: 888
000+888=888
New max answer found: 889
000+889=889
New max answer found: 890
001+889=890
New max answer found: 891
002+889=891
New max answer found: 892
003+889=892
New max answer found: 893
004+889=893
New max answer found: 894
005+889=894
New max answer found: 895
006+889=895
New max answer found: 896
007+889=896
New max answer found: 897
008+889=897
New max answer found: 898
009+889=898
New max answer found: 990
000+990=990
New max answer found: 991
000+991=991
New max answer found: 992
000+992=992
New max answer found: 993
000+993=993
New max answer found: 994
000+994=994
New max answer found: 995
000+995=995
New max answer found: 996
000+996=996
New max answer found: 997
000+997=997
New max answer found: 998
000+998=998
New max answer found: 999
000+999=999
Maxval was: 999
000+999=999
Другие решения
Других решений пока нет …