0

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

Вот код для основной и дополнительных диагоналей идущих сверху слева вниз направо:

    def finder(row,n):
       steck=[]
       for i in row:
          if not steck or steck==i:
             steck.append(i)
          else:
             if len(steck)>=n:
                break
             else:
                steck=[]
                steck.append(i)
       #print(len(steck)>=n)         
       return len(steck)>=n
    def horizontal(n,m):
       for row in m:
         if finder(row,n):
           return True
       return False
    def vertical(n,m):
       for col in zip(*m):
         if  finder(col,n):
            return True
       return False  
    def diagonal_dopoln_left(n,m):
       N=len(m)
       for counter in range(1,N):
          diag_len=N-counter
          list1=[m[i][i+counter] for i in range(diag_len)]
          print('list1',list1)
          list2=[m[i+counter][i] for i in range(diag_len)]
          print('list2',list2)      
          if finder(list1,n):
            return True
          if finder(list2,n):
            return True      
       return False 
    def diagonal_left(n,m):
       left_main_diag=[m[i][i] for i in range(len(m))]
       if finder(left_main_diag,n):
          return True 
       return False 
    def checkio(matrix):
      if diagonal_dopoln_left(4,matrix):
         return True
      return False




    if __name__ == '__main__':
       print(checkio([[11,12,14,17],
                      [14,15,16,10],
                      [10,18,12,11],
                      [10,81,12,11]
                ]))
       #Ответ:
       #list1 [14, 10]
       #list2 [10, 81]
       #list1 [17]
       #list2 [10]
       #False

Нашел дополнительные диагонали идущие сверху от основной которая идет справа сверху вниз таким кодом:

def finder(row,n):
    steck=[]
    for i in row:
        if not steck or steck==i:
            steck.append(i)
        else:
            if len(steck)>=n:
                break
            else:
                steck=[]
                steck.append(i)
    #print(len(steck)>=n)         
    return len(steck)>=n

def diagonal_right(n,m):
    left_main_diag=[m[i][-(i+1)] for i in range(len(m))]
    print('left_main_diag:',left_main_diag)
    if finder(left_main_diag,n):
        return True 
    return False 

def diagonal_dopoln_right(n,m):
    N=len(m)
    for counter in range(1,N):
        diag_len=N-counter
        list1=[m[i][-(i+counter)] for i in range(diag_len+1)]
        print('list1',list1)
        #list2=[m[i][-(i+1)] for i in range(diag_len+1)]
        #print('list2',list2)      
        #if finder(list1,n):
            #return True
        #if finder(list2,n):
            #return True      
    return False 


def checkio(matrix):
    n=4
    if diagonal_dopoln_right(n,matrix):
        return True
    return False

if __name__ == '__main__':
   print(checkio([[11,12,14,17],
                  [14,15,16,10],
                  [10,18,12,11],
                  [10,81,12,11]                               
                     ]))
   #Ответ:
   #list1 [17, 16, 18, 10]
   #list1 [14, 15, 10]
   #list1 [12, 14]
   #False 

Как найти такие диагонали снизу от основной, надо как-то правильно расставить индексы, пробовал по разному-return -1 )

2
  • При этом надо найти идущие строго подряд 4 и более элементов. - можете пояснить, что это значит? В диагонали среди элементов должны быть 4 или более последовательных числа?
    – user247581
    13 июн 2018 в 11:06
  • 1
    Да, в диагонали должны быть строго подряд идущие равные элементы(числа),у меня в коде это обеспечивает функция finder(),но мне нужно нижние диагонали от "правой основной" в списковую компановку list2 выделить. 13 июн 2018 в 15:24

1 ответ 1

0

Пусть есть произвольная матрица n x n. Рассмотрим, чему равны суммы индексов на диагоналях, идущих из левого нижнего угла в правый верхний (иначе говоря, на побочных диагоналях). На рисунке у меня n == 3, в клетках записаны суммы индексов элемента. matrix

Можно увидеть, что для элементов, находящихся на самой длинной побочной диагонали сумма индексов равна n-1; номера строк при этом (в которых встречаются элементы из этой диагонали) идут в диапазоне [0, n-1]. Для тех побочных диагоналей, что стоят выше неё, сумма индексов меньше: для соседней - меньше на единицу, для следующей - на двойку и т.д. (сумма = n-1 - distance); номера строк, содержащих элементы этой диагонили, пробегают значения [0, n-1-distance] (distance - расстояние от самой длинной побочной диагонали до рассматривоемой, причём расстояние между соседними диагоналями понимается равным единице). Для диагоналей снизу от самой длинной сумма индексов наоборот возрастает (сумма = n-1 + distance), а номера строк, в которых стоят элементы из этих диагоналей, меняются как [distance, n-1]. Теперь можно легко написать функцию, которая найдёт все побочные диагонали, пробегаясь по строкам, в которых есть элементы для данной диагонали, получая номер столбца из номера строки:

def checkio_2(matrix):
    n = len(matrix)    # размер квадратной матрицы
    all_diags = []     # здесь будут храниться все найденные
                       #     побочные диагонали
    for distance in range(1, n):    # distance - расстояние от главной диагонали
        sum_tl = n - 1 - distance    # сумма индексов (верхний-левый угол)
        sum_br = n - 1 + distance    # сумма индексов (нижний-правый угол)
        all_diags.extend([
            [matrix[i][sum_tl - i] for i in range(n - distance)], # верх-лев диаг
            [matrix[i][sum_br - i] for i in range(distance, n)]   # ниж-прав диаг
        ])
    return all_diags    # возвращаем все побочные диагонали

Теперь встаёт вопрос фильтрации полученных значений. Насколько я могу судить, Ваша функция finder плоховато для этого подходит:

def finder(row,n):
    steck=[]
    for i in row:
        if not steck or steck==i:    # steck==i - сравнивать список и число
                                     #     вряд ли хорошая идея;
                                     #     к тому же, на нулевой итерации
                                     #     попадём сюда, т.к. not steck == True
            steck.append(i)          # теперь steck == [i, ]
        else:                        # на второй итерации идём сюда
            if len(steck)>=n:        # len(steck) == 1
                break
            else:                    # поэтому
                steck=[]             # опустошаем steck
                steck.append(i)      # теперь steck == [i, ] снова
                                     # и ходим по этой ветке
    return len(steck)>=n             # вернём False, ведь len(steck) == 1

То есть, независимо от того, что в найденных диагоналях, возвращается False. Я бы предложил сделать иначе (для произвольного n, где n - нужная длина последовательности идущих подряд возрастающих или убывающих элементов). Если нужно, чтоб поиск происходил лишь среди последовательных элементов диагонали, можно написать так:

def finder_2(row, n=4):
    for idx in range(len(row)-(n-1)):
        n_increasing = 0    # столько раз следующий элемент больше предыдущего
        n_decreasing = 0    # а столько раз - наоборот
        for i in range(idx, idx+n-1):
            if row[i+1] - row[i] == 1:    # возрастание
                n_increasing += 1
            elif row[i] - row[i+1] == 1:  # убывание
                n_decreasing += 1
        if n-1 in [n_increasing, n_decreasing]: # если все возрастают
                                                # или все убывают
            return True
    return False    # если не найдено строго монотонной 
                    # последовательности нужной длины

Таким образом, можно проверить с помощью finder_2 все найденные в checkio_2 диагонали. Если нужно проверить, есть среди элементов диагонали четыре (или произвольное n) число последовательных чисел, не обязательно встречающихся в самой диагонали подряд, нужно в finder_2 передавать отсортированную диагональ.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.