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

@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, Вывести матрицу змейкой

Новые блоги и статьи Все статьи Все блоги /
Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при изменении наименования справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере изменения наименования типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной. . .	модель ЗдравоСохранения 5. Меньше увольнений- больше дохода! anaschu 24.03.2026 Теперь система здравосохранения уменьшает количество увольнений. 9TO2GP2bpX4 a42b81fb172ffc12ca589c7898261ccb/ https:/ / rutube. ru/ video/ a42b81fb172ffc12ca589c7898261ccb/ Слева синяя линия -. . .	Midnight Chicago Blues kumehtar 24.03.2026 Такой Midnight Chicago Blues, знаешь?. . Когда вечерние улицы становятся ночными, а ты не можешь уснуть. Ты идёшь в любимый старый бар, и бармен наливает тебе виски. Ты смотришь на пролетающие. . .
SDL3 для Desktop (MinGW): Вывод текста со шрифтом TTF с помощью библиотеки SDL3_ttf на Си и C++ 8Observer8 24.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-text-sdl3-c. zip finish-text-sdl3-cpp. zip	Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере нетипового документа выдачи шин для спецтехники с табличной частью, разработанного в конфигурации КА2. Номеклатура. . .

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

	"Диагональная" нумерация матрицы 24.02.2021, 13:29. Показов 9165. Ответов 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 987 / 331 / 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 987 / 331 / 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

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

Решение