найти симметричный ряд из списка

Question

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

Ввод:

12 -16 -7 -18 -5 -3 2 8 9 -14 -18 -9 11 -7 -3 4 -10 4 -3 -7 11 -12 -14 5 -11 -7 7 13 2 19 12 11

вывод:

12 9

второй пример,

ввод:

-4 -12 17 18 -8 7

вывод:

3 1

третий пример:

2 2 2 2 2 2 2 2

вывод:

0 8

Answer 1

Я попробовал решить задачку, у меня получился алгоритм, который нормально работает для цепочек с "нечетной длинной" - или, другими словами, в последнем тесте он выдаёт ответ 0 7

Пока не смог придумать, как его обобщить на цепочки четной длины.

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

Еще один недостаток - это не совсем питон :-) Но если Вы напишете в комментариях - я переведу на питончик.

Может, к тому времении и придумаю, как на четную длинну цепочек обобщить.

И еще - алгоритму в самом начале файла надо подсовывать число элементов в списке ("ну, это же убогий C++, он сам посчитать не может :-)")

То есть, первый тест теперь выглядит так:

    32
    12 -16 -7 -18 -5 -3 2 8 9 -14 -18 -9 11 -7 -3 4 -10 4 -3 -7 11 -12 -14 5 -11 -7 7 13 2 19 12 11

А сама программа - так:

    #include <iostream>
    #include <fstream>
    #include <vector>

    using namespace std;

    int main(){
        ifstream inp("input_simm.txt");
        int N;
        inp >> N;
        int x;
        vector<int> mass;
        for(int i=0; i<N; ++i) {
            inp >> x;
            mass.push_back(x);
        }
        // пытаемся найти симметричную цепочку
        int max_lengtn_central_index=-1;
        int max_lengtn=-1;
        for(int i=0; i<N;++i){
            int d=0;
            while( i-d-1>=0 && i+d+1<N ){
                d++;
                if ( mass[i-d]!=mass[i+d] ){
                    d--;
                    break;
                }
            }
            if ( d>max_lengtn ){
                max_lengtn=d;
                max_lengtn_central_index=i;
            }
        }
        if ( max_lengtn < 1 ){
            // симметричных цепочек нет. нужно вывести максимальный элемент
            auto max_iter=max_element(mass.begin(), mass.end());
            auto max_element_index = distance(mass.begin(), max_iter);
            auto max_element=mass[max_element_index];
            cout << max_element_index << " 1" << endl;
        }
        else
            cout << max_lengtn_central_index-max_lengtn << " " << max_lengtn*2+1 << endl;
        return 0;
    }

Answer 2

как-то так:

data = [12, -16, -7, -18, -5, -3, 2, 8, 9, -14, -18, -9, 11, -7, -3, 4, -10, 4, -3, -7, 11, -12, -14, 5, -11, -7, 7, 13, 2, 19, 12, 11]

pos_min = 0
size_max = 0

for pos in range(len(data)):
    for size in range(2, len(data) - pos + 1):
        if data[pos:pos+size] == list(reversed(data[pos:pos+size])) and size > size_max:
            size_max = size
            pos_min = pos

if size_max == 0:
    print(max(data), data.index(max(data)), 1)
else:
    print(pos_min, size_max)

но тему надо закрыть ибо нефиг школьные задачи спрашивать без приведения своего кода ;-)

P.S.

ну и для любителей однострочного разврата:

res = [(j, i) for i in range(len(data)) for j in range(2, len(data)-i+1) if data[i:i+j] == list(reversed(data[i:i+j]))]

if len(res) == 0:
    print(max(data), data.index(max(data)), 1)
else:
    print(max(res)[1], max(res)[0])

P.P.S.

А вообще к черту эти reversed! Мы что не на питоне что ли кодим?!!!

res = [(j, i) for i in range(len(data)) for j in range(2, len(data)-i+1) if data[i:i+j] == data[i:i+j][::-1]]

еще -10 буковок к коду :)

БЛОГ НА HUSL

найти симметричный ряд из списка

Ответы (2 шт):