Учитывая N-стороннюю квадратную матрицу, есть ли способ найти значение кольца для ячейки без использования циклов или условий? - PullRequest
Новая
       18

Учитывая N-стороннюю квадратную матрицу, есть ли способ найти значение кольца для ячейки без использования циклов или условий?

1 голос
/ 03 апреля 2019

Например, представьте, что у вас есть 6-сторонняя квадратная матрица. Это клетки декартовых индексов: 

(0,0) (0,1) (0,2) (0,3) (0,4) (0,5)
(1,0) (1,1) (1,2) (1,3) (1,4) (1,5)
(2,0) (2,1) (2,2) (2,3) (2,4) (2,5)
(3,0) (3,1) (3,2) (3,3) (3,4) (3,5)
(4,0) (4,1) (4,2) (4,3) (4,4) (4,5)
(5,0) (5,1) (5,2) (5,3) (5,4) (5,5)

6-сторонний квадрат имеет 3 кольца: a 

A A A A A A
A B B B B A
A B C C B A
A B C C B A
A B B B B A
A A A A A A

ВОПРОС : Какая функция берет координаты ячейки, стороны N квадрата и, соответственно, возвращает значение кольца? Пример: 

f(x = 1, y  2, N = 6) = B

A, B, C ... может быть любым числовым значением: 1,2,3 ... или 0,1,2 ... или любым другим. Важно то, что они равны для любого N. Например: 

N = 1   =>   A = 1
N = 2   =>   A = 1
N = 3   =>   A = 1, B = 2
N = 4   =>   A = 1, B = 2
N = 5   =>   A = 1, B = 2, C = 3
N = 6   =>   A = 1, B = 2, C = 3
N = 7   =>   A = 1, B = 2, C = 4, D = 4
...

Используя условия, проблема легко решается. Дана пара (x, y) и квадратная сторона N: 

# N//2 is the number of rings in a N-side square
for k in range(1,N//2+1):
    if x == 0+k-1 or y== 0+k-1 or x == N-k or y == N-1:
        return k

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

Ответы [ 3 ]

2 голосов
/ 03 апреля 2019

Похоже, математическая задача для решения. РЕДАКТИРОВАТЬ: Обновленная функция, должна быть лучше, чтобы обрабатывать четные и нечетные случаи после средней точки, я надеюсь. Однако, просьба ОП превратить это в математическое уравнение, я не уверен, как это сделать. 

import math


def ring_finder(x, y, N, outer_ring = 0):
    '''
    x and y are the coordinates of a cell, N is the length of the side of square
    Returns the correct ring count starting from outer_ring value (default, 0)
    '''
    if x >= N or y >= N:
        print("coordinates outside square, please check")
        return None
    no_of_squares = math.ceil(N/2)
    x = N - x - 1 if x >= no_of_squares else x
    y = N - y - 1 if y >= no_of_squares else y
    return min(x, y) + outer_ring

ring_finder (5, 5, 6) 

ring_finder(1, 2, 6)
1 голос
/ 05 апреля 2019

Значение кольца является дополнением к расстоянию до центра массива в смысле «нормы бесконечности». 

N/2 - max(|X - (N-1)/2|, |Y - (N-1)/2|).

Это присваивает значение 0 для A, 1 дляB и т. Д.

Чтобы избежать половины целых чисел, вы можете использовать 

(N - min(|2X - N + 1|, |2Y - N + 1|) / 2.

. Функции max и abs могут включать скрытые if, но вы не можете этого избежать.. 

def Ring(X, Y, N):
    return (N - max(abs(2 * X - N + 1), abs(2 * Y - N + 1))) // 2

for N in range(1, 8):
    for X in range(N):
        for Y in range(N):
            print(chr(Ring(X, Y, N) + 65), '', end= '')
        print()
    print()

A 

A A 
A A 

A A A 
A B A 
A A A 

A A A A 
A B B A 
A B B A 
A A A A 

A A A A A 
A B B B A 
A B C B A 
A B B B A 
A A A A A 

A A A A A A 
A B B B B A 
A B C C B A 
A B C C B A 
A B B B B A 
A A A A A A 

A A A A A A A 
A B B B B B A 
A B C C C B A 
A B C D C B A 
A B C C C B A 
A B B B B B A 
A A A A A A A
1 голос
/ 03 апреля 2019

Я думаю, что эта функция делает то, что вы хотите: 

def ring_id(n, i, j):
    even = n % 2 == 0
    n_2 = n // 2
    i = i - n_2
    if even and i >= 0:
        i += 1
    i = abs(i)
    j = j - n_2
    if even and j >= 0:
        j += 1
    j = abs(j)
    ring_id = i + max(j - i, 0)
    return n_2 - ring_id

Маленький тест с буквами: 

import string

def print_rings(n):
    ring_names = string.ascii_uppercase
    for i in range(n):
        for j in range(n):
            rid = ring_id(n, i, j)
            print(ring_names[rid], end=' ')
        print()

print_rings(6)
# A A A A A A
# A B B B B A
# A B C C B A
# A B C C B A
# A B B B B A
# A A A A A A
print_rings(7)
# A A A A A A A
# A B B B B B A
# A B C C C B A
# A B C D C B A
# A B C C C B A
# A B B B B B A
# A A A A A A A

РЕДАКТИРОВАТЬ: Если вы настаиваете на том, чтобы в вашем слове не было слова ifфункцию, вы можете (несколько неловко) переписать вышеупомянутую функцию следующим образом: 

def ring_id(n, i, j):
    even = 1 - n % 2
    n_2 = n // 2
    i = i - n_2
    i += even * (i >= 0)
    i = abs(i)
    j = j - n_2
    j += even * (j >= 0)
    j = abs(j)
    ring_id = i + max(j - i, 0)
    return n_2 - ring_id

Или, если вы хотите, чтобы она выглядела более «по формуле» (хотя и не читаемой и с более повторяющимися вычислениями): 

def ring_id(n, i, j):
    i2 = abs(i - (n // 2) + (1 - n % 2) * (i >= (n // 2)))
    j2 = abs(j - (n // 2) + (1 - n % 2) * (j >= (n // 2)))
    return (n // 2) - i2 + max(j2 - i2, 0)

Это не более или менее "математически", хотя, по сути, это та же логика.

...