one-liners à la fin de cette réponse, explication suivante :-)
la co tableau efficace a: M éléments pour la première rangée (ligne 0, dans votre indexation), (M-1) pour le deuxième (ligne 1), et ainsi de suite, pour un total de M + (M-1) + & hellip; 1 = M (M + 1)/2 éléments. Il est un peu plus facile de travailler à partir de la fin, car le tableau de coefficients toujours a 1 élément pour la dernière rangée (rangée M-1), 2 éléments pour l'avant-dernière rangée (rangée M-2), 3 éléments pour la rangée M-3, et ainsi de suite.Les dernières rangées K occupent les dernières positions K (K + 1)/2 du tableau de coefficients.
Supposons maintenant que vous avez un index i dans le tableau de coefficients. Il y a M (M + 1)/2-1-i aux positions supérieures à i. Appelez ce numéro i '; vous voulez trouver le plus grand k tel que k (k + 1)/2 ≤ i '. La forme de ce problème est la source même de votre misère - pour autant que je puisse voir, vous ne pouvez pas éviter de prendre des racines carrées :-)
Eh bien faisons-le quand même: k (k + 1) ≤ 2i 'signifie (k + 1/2) - 1/4 ≤ 2i ', ou de manière équivalente k ≤ (sqrt (8i' + 1) -1)/2. Permettez-moi d'appeler le plus grand k tel que K, puis il y a K lignes qui sont plus tard (sur un total de M lignes), de sorte que le row_index (i, M) est M-1-K. Comme pour l'index de la colonne, K (K + 1)/2 éléments de l'i 'sont dans les rangées suivantes, donc il y a j' = i'-K (K + 1)/2 éléments plus tard dans cette rangée (qui a K + 1 éléments au total), donc l'index de la colonne est K-j '. [Ou de manière équivalente, cette ligne commence à (K + 1) (K + 2)/2 à partir de la fin, donc nous avons juste besoin de soustraire la position de départ de cette rangée de i: i- [M (M + 1)/2 - (K + 1) (K + 2)/2]. Il est encourageant de constater que les deux expressions donnent la même réponse]
(pseudo-) Code [en utilisant ii au lieu de i « que certaines langues ne permettent pas de variables avec des noms comme i » ;-)]:
row_index(i, M):
ii = M(M+1)/2-1-i
K = floor((sqrt(8ii+1)-1)/2)
return M-1-K
column_index(i, M):
ii = M(M+1)/2-1-i
K = floor((sqrt(8ii+1)-1)/2)
return i - M(M+1)/2 + (K+1)(K+2)/2
Bien sûr, vous pouvez les transformer en interligne en substituant les expressions de ii et K. Vous devrez peut-être faire attention aux erreurs de précision, mais il existe des moyens de trouver la racine carrée entière qui n'exigent pas de calcul en virgule flottante . En outre, pour citer Knuth: "Méfiez-vous des bugs dans le code ci-dessus, je l'ai seulement prouvé correct, pas essayé." Si je peux me permettre de faire une autre remarque: le simple fait de conserver toutes les valeurs dans un tableau M × M prendra au maximum deux fois la mémoire, et en fonction de votre problème, le facteur 2 pourrait être insignifiant par rapport aux améliorations algorithmiques , et pourrait valoir la peine d'échanger le calcul éventuellement coûteux de la racine carrée pour les expressions plus simples que vous aurez. [Edit: BTW, vous pouvez prouver ce plancher ((sqrt (8ii + 1) -1)/2) = (isqrt (8ii + 1) -1)/2 où isqrt (x) = plancher (sqrt (x)) est une racine carrée entière, et la division est une division entière (troncature, la valeur par défaut en C/C++/Java etc.) - donc si vous avez des soucis de précision, vous ne devez vous soucier de l'implémentation d'un nombre entier correct racine carrée.]
Pouvez-vous reformuler cela pour que les éléments du tableau soient des lettres plutôt que les nombres - il est difficile à 100% de comprendre exactement ce que vos fonctions sont censées faire lorsque vous utilisez à la fois des valeurs de rang/col basées sur zéro et des valeurs basées sur un seul dans le tableau lui-même. – Alnitak
@Alnitak: terminé. –
data [row * num_cols + column] est l'expression classique d'un tableau C 2D stocké en mémoire sous forme de tableau unique. –