2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Закономерность в столбце матрицы
Сообщение03.02.2013, 22:44 
Имеем большую матрицу $m \times m$, в строках есть простая закономерность - 1-ца появляется через столбец, потом через 2 (для следующей строки), и т.д.

$\begin{vmatrix}
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & ...\\
0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & ...\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & ...\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & ...\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & ...\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & ...\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & ...\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & ...\\
...
\end{vmatrix}$

Можно ли быстро посчитать сумму произвольного столбца, например, для 1-го - 0, для 2-го - 1, для 3-го -1, для 4-го - 2, и т.д?

В голову пришел приблизительно такой алгоритм:
1. Получаем формулу (получил) для $i$-той строки, до $j$-того столбца, т.е. $f(i,j)$, например$ f(1,2) = 1$, $f(1,3) = 10$, $f(1,4) = 101$, и т.д.
2. Получаем формулу $g(i,j)$ (не могу получить) последней цифры $f(i,j)$, например $g(1,2) = 1$, $g(1,3) = 0$, $g(1,4) = 1$
3. Суммируем $g(i,j)$ до $i$-ой строки для $j$-того столбца, $h(j) = \sum\limits_{k=1}^{j-1} g(k,j)$, и надеемся, что эта сумма свернется в функцию без суммы.

Подскажите пожалуйста можно ли получить формулу для пункта 2? Или существует ли другая стратегия решения задачи?

 
 
 
 Posted automatically
Сообщение03.02.2013, 23:06 
Аватара пользователя
 i  Тема перемещена из форума «Математика (общие вопросы)» в форум «Помогите решить / разобраться (М)»

 
 
 
 Re: Закономерность в столбце матрицы
Сообщение04.02.2013, 12:30 
Сумма элементов $j-$ого столбца равна числу делителей числа $j$ минус 1.Например, $j=8$, делители: 1,2,4,8. Всего 4 штуки. Сумма элементов $4-1=3$.

 
 
 
 Re: Закономерность в столбце матрицы
Сообщение04.02.2013, 23:36 
2 mihiv: Т.е алгоритмическая сложность Вашего алгоритма, приблизительно будет $O(j^ \frac {1} {3})$, а быстрее можно, как Вы думаете мой алгоритм, имеет право на существование?

 
 
 
 Re: Закономерность в столбце матрицы
Сообщение05.02.2013, 00:31 
Аватара пользователя
Ваш алгоритм содержит слово "надеемся", т.е. относится к алгоритмам с божественным вмешательством. Тут напрямую сравнивать вообще нельзя.
Впрочем, конечно, сумма свернётся в функцию без суммы. Какая будет функция - тут два варианта: либо такая же, либо неправильная.

 
 
 [ Сообщений: 5 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group