Сообщение Красивые числа от 04.12.2021 18:47
Изменено 04.12.2021 19:00 avovana
Re: Красивые числа
Тестовое задание.
В данной задаче будут рассматриваться 13-ти значные числа в тринадцатиричной системе исчисления(цифры 0,1,2,3,4,5,6,7,8,9,A,B,C) с ведущими нулями.
Например, ABA98859978C0, 6789110551234, 0000007000000
Назовем число красивым, если сумма его первых шести цифр равна сумме шести последних цифр.
Пример:
Число 0055237050A00 — красивое, так как 0+0+5+5+2+3 = 0+5+0+A+0+0
Число 1234AB988BABA — некрасивое, так как 1+2+3+4+A+B != 8+8+B+A+B+A
Задача:
написать программу на С/С++ печатающую в стандартный вывод количество 13-ти значных красивых чисел с ведущими нулями в тринадцатиричной системе исчисления.
В качестве решения должен быть предоставлено:
1) ответ — количество таких чисел. Ответ должен быть представлен в десятичной системе исчисления.
2) исходный код программы.
Это задача на перестановки(permutation) с повторами. К примеру, есть пин код.
Может быть цифра 1-9 в любой из 4ёх позиций. Причём, не так, что раз 1 уже была, то её нельзя поставить в другую позицию. Может быть код и 1111.
Т.е. сами цифры могут повторяться.
Сделал. Ответ оказался неверным. Может, найдёте ошибку?
// pretty_numbers = 707972099625
#include <iostream>
#include <string>
#include <map>
using namespace std;
std::map<int, int> sum_numbers;
unsigned long long counter = 0;
void count_sums(const char str[], int sum, int n, int lenght) {
if (lenght == 1) {
for (int j = 0; j < n; j++) {
int current = str[j] - 48;
if(current >= 10)
current = current - 7;
sum_numbers[sum + current]++;
}
} else {
for (int i = 0; i < n; i++) {
int current = str[i] - 48;
if(current >= 10)
current = current - 7;
count_sums(str, sum + current, n, lenght - 1);
}
}
}
void permutations(int n, int lenght) {
if (lenght == 1) {
for (int j = 0; j < n; j++)
counter++;
} else {
for (int i = 0; i < n; i++)
permutations(n, lenght - 1);
}
}
int main() {
int lenght = 6;
char str[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C'};
int n = sizeof str;
count_sums(str, 0, n, lenght);
/*
for(auto [sum, unique_numbers] : sum_numbers)
cout << sum << ":" << unique_numbers << endl;
...
39:195042
40:187803
41:178878
...
*/
unsigned long long pretty_numbers = 0;
for(auto [sum, unique_numbers] : sum_numbers) {
permutations(unique_numbers, 2);
cout << "sum: " << sum << " : " << unique_numbers << " : " << counter << " : " << pretty_numbers << endl;
pretty_numbers += counter;
counter = 0;
}
pretty_numbers = pretty_numbers - 2;
cout << "pretty_numbers = " << pretty_numbers;
return 0;
}
/*
sum: 0 : 1 : 1 : 0
sum: 1 : 6 : 36 : 1
sum: 2 : 21 : 441 : 37
sum: 3 : 56 : 3136 : 478
sum: 4 : 126 : 15876 : 3614
sum: 5 : 252 : 63504 : 19490
sum: 6 : 462 : 213444 : 82994
sum: 7 : 792 : 627264 : 296438
sum: 8 : 1287 : 1656369 : 923702
sum: 9 : 2002 : 4008004 : 2580071
sum: 10 : 3003 : 9018009 : 6588075
sum: 11 : 4368 : 19079424 : 15606084
sum: 12 : 6188 : 38291344 : 34685508
sum: 13 : 8562 : 73307844 : 72976852
sum: 14 : 11592 : 134374464 : 146284696
sum: 15 : 15378 : 236482884 : 280659160
sum: 16 : 20013 : 400520169 : 517142044
sum: 17 : 25578 : 654234084 : 917662213
sum: 18 : 32137 : 1032786769 : 1571896297
sum: 19 : 39732 : 1578631824 : 2604683066
sum: 20 : 48378 : 2340430884 : 4183314890
sum: 21 : 58058 : 3370731364 : 6523745774
sum: 22 : 68718 : 4722163524 : 9894477138
sum: 23 : 80262 : 6441988644 : 14616640662
sum: 24 : 92547 : 8564947209 : 21058629306
sum: 25 : 105378 : 11104522884 : 29623576515
sum: 26 : 118518 : 14046516324 : 40728099399
sum: 27 : 131698 : 17344363204 : 54774615723
sum: 28 : 144627 : 20916969129 : 72118978927
sum: 29 : 157002 : 24649628004 : 93035948056
sum: 30 : 168518 : 28398316324 : 117685576060
sum: 31 : 178878 : 31997338884 : 146083892384
sum: 32 : 187803 : 35269966809 : 178081231268
sum: 33 : 195042 : 38041381764 : 213351198077
sum: 34 : 200382 : 40152945924 : 251392579841
sum: 35 : 203658 : 41476580964 : 291545525765
sum: 36 : 204763 : 41927886169 : 333022106729
sum: 37 : 203658 : 41476580964 : 374949992898
sum: 38 : 200382 : 40152945924 : 416426573862
sum: 39 : 195042 : 38041381764 : 456579519786
sum: 40 : 187803 : 35269966809 : 494620901550
sum: 41 : 178878 : 31997338884 : 529890868359
sum: 42 : 168518 : 28398316324 : 561888207243
sum: 43 : 157002 : 24649628004 : 590286523567
sum: 44 : 144627 : 20916969129 : 614936151571
sum: 45 : 131698 : 17344363204 : 635853120700
sum: 46 : 118518 : 14046516324 : 653197483904
sum: 47 : 105378 : 11104522884 : 667244000228
sum: 48 : 92547 : 8564947209 : 678348523112
sum: 49 : 80262 : 6441988644 : 686913470321
sum: 50 : 68718 : 4722163524 : 693355458965
sum: 51 : 58058 : 3370731364 : 698077622489
sum: 52 : 48378 : 2340430884 : 701448353853
sum: 53 : 39732 : 1578631824 : 703788784737
sum: 54 : 32137 : 1032786769 : 705367416561
sum: 55 : 25578 : 654234084 : 706400203330
sum: 56 : 20013 : 400520169 : 707054437414
sum: 57 : 15378 : 236482884 : 707454957583
sum: 58 : 11592 : 134374464 : 707691440467
sum: 59 : 8562 : 73307844 : 707825814931
sum: 60 : 6188 : 38291344 : 707899122775
sum: 61 : 4368 : 19079424 : 707937414119
sum: 62 : 3003 : 9018009 : 707956493543
sum: 63 : 2002 : 4008004 : 707965511552
sum: 64 : 1287 : 1656369 : 707969519556
sum: 65 : 792 : 627264 : 707971175925
sum: 66 : 462 : 213444 : 707971803189
sum: 67 : 252 : 63504 : 707972016633
sum: 68 : 126 : 15876 : 707972080137
sum: 69 : 56 : 3136 : 707972096013
sum: 70 : 21 : 441 : 707972099149
sum: 71 : 6 : 36 : 707972099590
sum: 72 : 1 : 1 : 707972099626
pretty_numbers = 707972099625
*/Ответ оказался
Красивые числа
Тестовое задание.
В данной задаче будут рассматриваться 13-ти значные числа в тринадцатиричной системе исчисления(цифры 0,1,2,3,4,5,6,7,8,9,A,B,C) с ведущими нулями.
Например, ABA98859978C0, 6789110551234, 0000007000000
Назовем число красивым, если сумма его первых шести цифр равна сумме шести последних цифр.
Пример:
Число 0055237050A00 — красивое, так как 0+0+5+5+2+3 = 0+5+0+A+0+0
Число 1234AB988BABA — некрасивое, так как 1+2+3+4+A+B != 8+8+B+A+B+A
Задача:
написать программу на С/С++ печатающую в стандартный вывод количество 13-ти значных красивых чисел с ведущими нулями в тринадцатиричной системе исчисления.
В качестве решения должен быть предоставлено:
1) ответ — количество таких чисел. Ответ должен быть представлен в десятичной системе исчисления.
2) исходный код программы.
Это задача на перестановки(permutation) с повторами. К примеру, есть пин код.
Может быть цифра 1-9 в любой из 4ёх позиций. Причём, не так, что раз 1 уже была, то её нельзя поставить в другую позицию. Может быть код и 1111.
Т.е. сами цифры могут повторяться.
Есть формула. Там учитывается:
1) кол-во возможных чисел. Здесь 13ть
2) кол-во мест для перестановки. Здесь 6
Шаги:
1. Находим для каждой суммы кол-во возможных комбинаций
2. Допустим, для суммы 39 есть 195042 возможных комбинаций цифр.
Это в левой части. И в правой, получается, тоже 195042.
К примеру, ССС000, 000ССС, 0С0С0С (если бы было всего 3 возможных сочетаний цифр, которые дают сумму 39)
Теперь нужно по каждой такой сумме найти кол-во сочетаний:
1 ССС000 = ССС000
2 ССС000 = 000ССС
3 ССС000 = 0С0С0С
4 000ССС = ССС000
5 000ССС = 000ССС
6 000ССС = 0С0С0С
7 0С0С0С = ССС000
8 0С0С0С = 000ССС
9 0С0С0С = 0С0С0С
Сейчас просто смотрим по той формуле, что есть цифра 3. 3 уникальных сочетания с каждой из 2ух сторон.
Сделал. Ответ оказался неверным. Может, найдёте ошибку?
// pretty_numbers = 707972099625
#include <iostream>
#include <string>
#include <map>
using namespace std;
std::map<int, int> sum_numbers;
unsigned long long counter = 0;
void count_sums(const char str[], int sum, int n, int lenght) {
if (lenght == 1) {
for (int j = 0; j < n; j++) {
int current = str[j] - 48;
if(current >= 10)
current = current - 7;
sum_numbers[sum + current]++;
}
} else {
for (int i = 0; i < n; i++) {
int current = str[i] - 48;
if(current >= 10)
current = current - 7;
count_sums(str, sum + current, n, lenght - 1);
}
}
}
void permutations(int n, int lenght) {
if (lenght == 1) {
for (int j = 0; j < n; j++)
counter++;
} else {
for (int i = 0; i < n; i++)
permutations(n, lenght - 1);
}
}
int main() {
int lenght = 6;
char str[] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C'};
int n = sizeof str;
count_sums(str, 0, n, lenght);
/*
for(auto [sum, unique_numbers] : sum_numbers)
cout << sum << ":" << unique_numbers << endl;
...
39:195042
40:187803
41:178878
...
*/
unsigned long long pretty_numbers = 0;
for(auto [sum, unique_numbers] : sum_numbers) {
permutations(unique_numbers, 2);
cout << "sum: " << sum << " : " << unique_numbers << " : " << counter << " : " << pretty_numbers << endl;
pretty_numbers += counter;
counter = 0;
}
pretty_numbers = pretty_numbers - 2;
cout << "pretty_numbers = " << pretty_numbers;
return 0;
}
/*
sum: 0 : 1 : 1 : 0
sum: 1 : 6 : 36 : 1
sum: 2 : 21 : 441 : 37
sum: 3 : 56 : 3136 : 478
sum: 4 : 126 : 15876 : 3614
sum: 5 : 252 : 63504 : 19490
sum: 6 : 462 : 213444 : 82994
sum: 7 : 792 : 627264 : 296438
sum: 8 : 1287 : 1656369 : 923702
sum: 9 : 2002 : 4008004 : 2580071
sum: 10 : 3003 : 9018009 : 6588075
sum: 11 : 4368 : 19079424 : 15606084
sum: 12 : 6188 : 38291344 : 34685508
sum: 13 : 8562 : 73307844 : 72976852
sum: 14 : 11592 : 134374464 : 146284696
sum: 15 : 15378 : 236482884 : 280659160
sum: 16 : 20013 : 400520169 : 517142044
sum: 17 : 25578 : 654234084 : 917662213
sum: 18 : 32137 : 1032786769 : 1571896297
sum: 19 : 39732 : 1578631824 : 2604683066
sum: 20 : 48378 : 2340430884 : 4183314890
sum: 21 : 58058 : 3370731364 : 6523745774
sum: 22 : 68718 : 4722163524 : 9894477138
sum: 23 : 80262 : 6441988644 : 14616640662
sum: 24 : 92547 : 8564947209 : 21058629306
sum: 25 : 105378 : 11104522884 : 29623576515
sum: 26 : 118518 : 14046516324 : 40728099399
sum: 27 : 131698 : 17344363204 : 54774615723
sum: 28 : 144627 : 20916969129 : 72118978927
sum: 29 : 157002 : 24649628004 : 93035948056
sum: 30 : 168518 : 28398316324 : 117685576060
sum: 31 : 178878 : 31997338884 : 146083892384
sum: 32 : 187803 : 35269966809 : 178081231268
sum: 33 : 195042 : 38041381764 : 213351198077
sum: 34 : 200382 : 40152945924 : 251392579841
sum: 35 : 203658 : 41476580964 : 291545525765
sum: 36 : 204763 : 41927886169 : 333022106729
sum: 37 : 203658 : 41476580964 : 374949992898
sum: 38 : 200382 : 40152945924 : 416426573862
sum: 39 : 195042 : 38041381764 : 456579519786
sum: 40 : 187803 : 35269966809 : 494620901550
sum: 41 : 178878 : 31997338884 : 529890868359
sum: 42 : 168518 : 28398316324 : 561888207243
sum: 43 : 157002 : 24649628004 : 590286523567
sum: 44 : 144627 : 20916969129 : 614936151571
sum: 45 : 131698 : 17344363204 : 635853120700
sum: 46 : 118518 : 14046516324 : 653197483904
sum: 47 : 105378 : 11104522884 : 667244000228
sum: 48 : 92547 : 8564947209 : 678348523112
sum: 49 : 80262 : 6441988644 : 686913470321
sum: 50 : 68718 : 4722163524 : 693355458965
sum: 51 : 58058 : 3370731364 : 698077622489
sum: 52 : 48378 : 2340430884 : 701448353853
sum: 53 : 39732 : 1578631824 : 703788784737
sum: 54 : 32137 : 1032786769 : 705367416561
sum: 55 : 25578 : 654234084 : 706400203330
sum: 56 : 20013 : 400520169 : 707054437414
sum: 57 : 15378 : 236482884 : 707454957583
sum: 58 : 11592 : 134374464 : 707691440467
sum: 59 : 8562 : 73307844 : 707825814931
sum: 60 : 6188 : 38291344 : 707899122775
sum: 61 : 4368 : 19079424 : 707937414119
sum: 62 : 3003 : 9018009 : 707956493543
sum: 63 : 2002 : 4008004 : 707965511552
sum: 64 : 1287 : 1656369 : 707969519556
sum: 65 : 792 : 627264 : 707971175925
sum: 66 : 462 : 213444 : 707971803189
sum: 67 : 252 : 63504 : 707972016633
sum: 68 : 126 : 15876 : 707972080137
sum: 69 : 56 : 3136 : 707972096013
sum: 70 : 21 : 441 : 707972099149
sum: 71 : 6 : 36 : 707972099590
sum: 72 : 1 : 1 : 707972099626
pretty_numbers = 707972099625
*/Ответ оказался