Исходник Практикум: палиндромы

[Irval]

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

Условие задания гораздо короче, чем в том же консольном календаре. Из введенной пользователем строки мы должны выделить максимальный и минимальный палиндром максимальной длины. Считается, что строка состоит только из цифр, но проверку на неверный формат данных сделать все же стоит. Выходные данные не обязательно должны содержать цифры в том же порядке, в котором они находятся в строке.
То есть, в стоке 1585 максимальным палиндромом максимальной длины будет 585, а минимальным - 515.

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

Исходный код моего решения

Спойлер

#include <iostream>
#include <string>
using namespace std;
int main() {
    setlocale(LC_CTYPE, "Russian");
    while (true) {
        system("cls");
        cout << "Введите строку: ";
        int mas[10] = {}, mas2[10] = {}, m[10] = {};
        char c;
        while (c = cin.get(), c != '\n')
            if ('0' <= c && c <= '9') {
                mas[c - '0']++;
                mas2[c - '0']++;
                m[c - '0']++;
            }
        if (!mas[0] && !mas[1] && !mas[2] && !mas[3] && !mas[4] && !mas[5] && !mas[6] && !mas[7] && !mas[8] && !mas[9]) {
            cout << "В строке нет цифр!" << endl << endl;
            system("pause");
        }
        else {
            int num[101] = {};
            int index = 0;
            bool hasCentre = false;
            while (1) {
                for (int i = 9; i >= 0; i--) {
                    if (mas[i] > 1) {
                        num[index] = i;
                        num[50 + (50 - index)] = i;
                        mas[i] -= 2;
                        index++;
                        break;
                    }
                    else if (i == 0) {
                        for (int j = 9; j >= 0; j--) {
                            if (mas[j] == 1) {
                                num[50] = j;
                                hasCentre = true;
                                mas[j]--;
                                break;
                            }
                        }
                        goto end;
                    }
                }
            }
        end:
            cout << "Максимальный палиндром максимальной длины: ";
            bool is1 = true;
            if (hasCentre && num[0] == 0)
                cout << num[50];
            else if (!num[50] && !num[0] && !num[49])
                cout << 0;
            else {
                for (int i = 0; i < 101; i++)
                    if (hasCentre && i == 50 || i < index && i < 50 || i > 100 - index && i > 50)
                        cout << num[i];
            }
            cout << endl;
            int num1[101] = {};
            int index1 = 0;
            bool hasCentre1 = false;
            while (1) {
                for (int i = 0; i <= 9; i++) {
                    if (index1 == 0 && i == 0)
                        continue;
                    if (mas2[i] > 1) {
                        num1[index1] = i;
                        num1[50 + (50 - index1)] = i;
                        mas2[i] -= 2;
                        index1++;
                        break;
                    }
                    else if (i == 9) {
                        for (int j = 0; j <= 9; j++) {
                            if (mas2[j] == 1) {
                                num1[50] = j;
                                hasCentre1 = true;
                                mas2[j]--;
                                break;
                            }
                        }
                        goto end2;
                    }
                }
            }
        end2:
            cout << "Минимальный палиндром максимальной длины: ";
            if (m[0] && hasCentre1 && num1[0] == 0)
                cout << 0 << endl << endl;
            else if (!num1[50] && !num1[0] && !num1[49])
                cout << 0 << endl << endl;
            else
            {
                for (int i = 0; i < 101; i++)
                    if (hasCentre1 && i == 50 || i < index1 && i < 50 || i > 100 - index1 && i > 50)
                        cout << num1[i];
                cout << endl << endl;
            }
            system("pause");
        }
    }
}

Спойлер: Скриншот работы

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

 

[PureBottle]

1. Код дублируется.
2. Временную сложность на глаз не прикинешь, но явно можно сделать меньше
3. !mas[0] && !mas[1] && !mas[2] && !mas[3] && !mas[4] && !mas[5] && !mas[6] && !mas[7] && !mas[8] && !mas[9]
4. goto

Почему не использовать функции? На них можно накинуть юнит-тестов в процессе разработки программы.

int get_max_palindrome(int num) { ... }
// ...
assert(get_max_palindrome(78787) == 87778);

Почему не использовать STL? В условии об этом ничего нет. Считать количество вхождений каждой цифры можно в unordered_map, проверять наличие, введено ли пользователем число, методом empty того самого unordered_map

unordered_map<int, int> digits;
char c;

while (c = cin.get(), c != '\n' )
  if (isdigit(c))
    ++digits[c - '0'];

if (digits.empty())
  cout << "Number is expected" << endl;

Да, ещё: что за магические числа 49, 50, и 100 встречаются в коде? Я не от злобы всё это пишу, просто удивлён увиденным.

 

[sove]

4. goto

Гото вполне юзабельные так-то, только не в этом случае

 

[PureBottle]

Гото вполне юзабельные так-то, только не в этом случае

goto затрудняет поддержку кода. Как по мне, лучше вообще о нём забыть до момента, когда без goto - ну вообще никак. И даже в таком случае стоит прежде попытаться выполнить декомпозицию кода.

 

[Irval]

Почему не использовать функции? На них можно накинуть юнит-тестов в процессе разработки программы.

Почему не использовать STL? В условии об этом ничего нет. Считать количество вхождений каждой цифры можно в unordered_map, проверять наличие, введено ли пользователем число, методом empty того самого unordered_map

Хорошая идея, но пользьзователь, обратившийся ко мне, написал "Короч сделай все по максмуму просто, ато препод запалит я сложное не сделал бы"

Временную сложность на глаз не прикинешь, но явно можно сделать меньше

Более оптимизированного варианта не придумал, можешь подредачить, если хочешь)

!mas[0] && !mas[1] && !mas[2] && !mas[3] && !mas[4] && !mas[5] && !mas[6] && !mas[7] && !mas[8] && !mas[9]

Можно было сравнить с int empty[10] = {}, спасибо

goto затрудняет поддержку кода. Как по мне, лучше вообще о нём забыть до момента, когда без goto - ну вообще никак. И даже в таком случае стоит прежде попытаться выполнить декомпозицию кода.

Тут дело каждого, лично мне читать код с goto ничуть не тяжело

 

[PureBottle]

пользьзователь, обратившийся ко мне, написал "Короч сделай все по максмуму просто, ато препод запалит я сложное не сделал бы"

В общем-то, так и подумал. Такой бред только в универах и задают х)