"Диагональная" нумерация матрицы

@Lesage · Регистрация: 24.02.2021

Студворк — интернет-сервис помощи студентам

Здравствуйте, у меня есть квадратная матрица размера n, и в этой матрице находятся числа от 1 до n^2, расположенные следующим образом:

1 3 4 10 11 21 22
2 5 9 12 20
6 8 13 19
7 14 18
15 17
16

И так далее.

Мне нужно, зная номер числа, узнать номер столбца и строки, в котором он находится.
Заранее спасибо за ответы.

@dondublon · 24.02.2021, 18:34

Это раздел форума по базам данных. Они тут ваще не при чём.

И да, для вашей задачи возможны различные решения. Я вижу три. 1. Нарисовать большой треугольник и тупо запомнить индексы. 2. Рисовать змейку, пока не дойдём до нужного числа, и 3. Аналитическое, но тут надо думать.

@dondublon · 24.02.2021, 19:04

Lesage, чтобы перенести тему - надо просить модератора.
Насчёт аналитического решения - ну тут явно номер "диагонали" (назовём так расстояние до начала отсчёта по диагонали) растёт квадратично. То есть надо составить квадратное уравнение и решить его.

@Lesage · 24.02.2021, 19:29 **[ТС]**

Да, я заметил некоторые особенности, более того, номера на крайней горизонтали и крайней вертикали соответствуют последовательностям
a(n) = if n mod 2 == 0 then n*(n+1)/2, otherwise (n-1)*n/2 + 1. -- горизонталь
a(n) = n*(n+1)/2 if n is odd, otherwise (n-1)*n/2 + 1. -- вертикаль

Но пока не понимаю, как это можно использовать.

@dondublon · 25.02.2021, 09:45

Пусть а - номер диагонали, которую оступаем, в направлении вправо-вниз. То, что направление чисел там чередуется, игнорируем, развернуть ряд чисел - это тривиально.
Пусть f(a) - маскимальное число на этой диагонали.
Тогда
f(1) = 1.
f(2) = 1+2.
f(3)=1+2+3.
f(a)=a(a+1)/2=a^2/2+a/2.

В диагонали ровно а чисел, поэтому минимальное = (а^2/2+a/2)-a+1 = a^2/2-a/2+1.
Ну вот вам и два квадратных неравенства.

@Lesage · 25.02.2021, 11:57 **[ТС]**

Я думаю, что решил эту проблему:

Кажется, у меня есть решение, вот код на питоне:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
num = int(input())
sum = 1
i = 1
while (num>sum):
    i += 1
    sum += i
diff = sum - num
if (i%2):
    Y = i - diff
    X = diff + 1
else:
    Y = diff + 1
    X = i - diff

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

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

@dondublon · 25.02.2021, 12:50

Lesage, это ж простой перебор. "Рисование".

@Lesage · 25.02.2021, 13:40 **[ТС]**

Ну не совсем перебор, мы же ищем конкретную диагональ, на которой лежит число, так что это скорее "метод научного тыка"))
К тому же скорость тут довольно приемлемая, при увеличении числа в 100 раз время выполнения программы увеличивается в 10 раз, то есть сложность sqrt(n)
Хотя безусловно можно быстрее

@Gdez · 25.02.2021, 14:23

Lesage,

т.к. размер числа может доходить до 10^18

@VistaSV30 · 25.02.2021, 17:03

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

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import numpy as np
d = 8 # размер матрицы
k = 9 # количество элементов
a = np.zeros((d, d)) # создание квадратной матрицы
x, y = [], []
for i in range(k+1): # опредляем индексы
    if i%2 == 0:
        x += reversed(range(i))
        y += range(i)
    else:
        x += range(i)
        y += reversed(range(i))
 
for i in range(k+1): # заполняем матрицу
    a[x[i], y[i]] = i
print(a)
 
# найти n-й элемент
n = 3
print(a[x[n], y[n]])

@Gdez · 25.02.2021, 18:01

Lesage,

Python
1
2
3
4
5
6
7
8
9
10
11
n = int(input())
a = int(((1+8*n)**0.5 - 1)/2) + 1
asta = (a-1)*a // 2 + 1
af = (a+1)*a // 2
if a%2:
    j = af - n
    i = n - asta
else:
    i = af - n
    j = n - asta
print(i, j)

@Du raker · 26.02.2021, 20:37

Господа, подскажите как заполнить матрицу таким способом.

@Du raker · 01.03.2021, 16:57

неужели ни кто не знает?

@VistaSV30 · 01.03.2021, 17:02

Du raker, а в чем проблема? Тут два варианта кода. Берите любой, вставляйте в Jupiter Notebook и запускайте!

@Lesage · 01.03.2021, 18:20 **[ТС]**

Du raker, У вас есть решение задачи как зная номер, понять расположение. Вам надо решить обратную задачу -- зная расположение, присвоить элементу соответствующий номер. В чём проблема?
Ну и залить это всё в цикл по всем элементам матрицы, конечно

@Du raker · 01.03.2021, 20:53

Сообщение от VistaSV30

import numpy as np
d = 8 # размер матрицы
k = 9 # количество элементов
a = np.zeros((d, d)) # создание квадратной матрицы
x, y = [], []
for i in range(k+1): # опредляем индексы
if i%2 == 0:
x += reversed(range(i))
y += range(i)
else:
x += range(i)
y += reversed(range(i))
for i in range(k+1): # заполняем матрицу
a[x[i], y[i]] = i
print(a)
# найти n-й элемент
n = 3
print(a[x[n], y[n]])

Этот код заполняет матрицу только до побочной диагонали.

@VistaSV30 · 01.03.2021, 21:02

После того, как заполнение проходит главную диагональ матрицы возникает ошибка. Поэтому, после этого нужно поменять условия в цикле. Пока не готов сказать, как именно.

@Gdez · 01.03.2021, 22:34

Du raker, Вывести матрицу змейкой

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@Lesage 0 / 0 / 0 Регистрация: 24.02.2021 Сообщений: 7

	"Диагональная" нумерация матрицы 24.02.2021, 13:29. Показов 9179. Ответов 17 Метки алгоритмы (Все метки) Здравствуйте, у меня есть квадратная матрица размера n, и в этой матрице находятся числа от 1 до n^2, расположенные следующим образом: 1 3 4 10 11 21 22 2 5 9 12 20 6 8 13 19 7 14 18 15 17 16 И так далее. Мне нужно, зная номер числа, узнать номер столбца и строки, в котором он находится. Заранее спасибо за ответы. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	24.02.2021, 18:34
	Это раздел форума по базам данных. Они тут ваще не при чём. И да, для вашей задачи возможны различные решения. Я вижу три. 1. Нарисовать большой треугольник и тупо запомнить индексы. 2. Рисовать змейку, пока не дойдём до нужного числа, и 3. Аналитическое, но тут надо думать. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	24.02.2021, 19:04
	Lesage, чтобы перенести тему - надо просить модератора. Насчёт аналитического решения - ну тут явно номер "диагонали" (назовём так расстояние до начала отсчёта по диагонали) растёт квадратично. То есть надо составить квадратное уравнение и решить его. 0

@Lesage 0 / 0 / 0 Регистрация: 24.02.2021 Сообщений: 7
	24.02.2021, 19:29 [ТС]
	Да, я заметил некоторые особенности, более того, номера на крайней горизонтали и крайней вертикали соответствуют последовательностям a(n) = if n mod 2 == 0 then n(n+1)/2, otherwise (n-1)n/2 + 1. -- горизонталь a(n) = n(n+1)/2 if n is odd, otherwise (n-1)n/2 + 1. -- вертикаль Но пока не понимаю, как это можно использовать. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	25.02.2021, 09:45
	Пусть а - номер диагонали, которую оступаем, в направлении вправо-вниз. То, что направление чисел там чередуется, игнорируем, развернуть ряд чисел - это тривиально. Пусть f(a) - маскимальное число на этой диагонали. Тогда f(1) = 1. f(2) = 1+2. f(3)=1+2+3. f(a)=a(a+1)/2=a^2/2+a/2. В диагонали ровно а чисел, поэтому минимальное = (а^2/2+a/2)-a+1 = a^2/2-a/2+1. Ну вот вам и два квадратных неравенства. 1

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	25.02.2021, 12:50
	Lesage, это ж простой перебор. "Рисование". 0

@Lesage 0 / 0 / 0 Регистрация: 24.02.2021 Сообщений: 7
	25.02.2021, 13:40 [ТС]
	Ну не совсем перебор, мы же ищем конкретную диагональ, на которой лежит число, так что это скорее "метод научного тыка")) К тому же скорость тут довольно приемлемая, при увеличении числа в 100 раз время выполнения программы увеличивается в 10 раз, то есть сложность sqrt(n) Хотя безусловно можно быстрее 0

@Du raker Заблокирован
	26.02.2021, 20:37
	Господа, подскажите как заполнить матрицу таким способом. 0

@Du raker Заблокирован
	01.03.2021, 16:57
	неужели ни кто не знает? 0

@VistaSV30 988 / 332 / 79 Регистрация: 10.04.2012 Сообщений: 1,242 Записей в блоге: 4
	01.03.2021, 17:02
	Du raker, а в чем проблема? Тут два варианта кода. Берите любой, вставляйте в Jupiter Notebook и запускайте! 0

@Lesage 0 / 0 / 0 Регистрация: 24.02.2021 Сообщений: 7
	01.03.2021, 18:20 [ТС]
	Du raker, У вас есть решение задачи как зная номер, понять расположение. Вам надо решить обратную задачу -- зная расположение, присвоить элементу соответствующий номер. В чём проблема? Ну и залить это всё в цикл по всем элементам матрицы, конечно 0

@VistaSV30 988 / 332 / 79 Регистрация: 10.04.2012 Сообщений: 1,242 Записей в блоге: 4
	01.03.2021, 21:02
	После того, как заполнение проходит главную диагональ матрицы возникает ошибка. Поэтому, после этого нужно поменять условия в цикле. Пока не готов сказать, как именно. 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,317
	01.03.2021, 22:34
	Du raker, Вывести матрицу змейкой 0

"Диагональная" нумерация матрицы

Решение