Recherche d'une fonction mathématique

[tadaa9]

Bonjour,

J'ai codé un script qui me permet de générer des combinaisons de phrases. Celui-ci me génère par exemple 16 phrases et je souhaite ensuite les sélectionner dans un ordre particulier :
- la 1ère ;
- la dernière ;
- la 8ème (milieu) ;
- la 4ème ;
- la 12 ème, etc.

Formalisé autrement, je souhaite aboutir à une fonction mathématique qui me permettrait d'obtenir les résultats suivants en fonction d'une valeur en entrée (1, 2, 3...) et d'un nombre nbLignes :
1 -> 1
2 -> nbLignes

3 -> arrondiInferieur(nbLignes * 1 / 2)

4 -> arrondiInferieur(nbLignes * 1 / 4)
5 -> arrondiInferieur(nbLignes * 3 / 4)

6 -> arrondiInferieur(nbLignes * 1 / 8)
7 -> arrondiInferieur(nbLignes * 3 / 8)
8 -> arrondiInferieur(nbLignes * 5 / 8)
9 -> arrondiInferieur(nbLignes * 7 / 8)

...

Sauf que je ne suis pas capable d'écrire cette fonction !

Seriez-vous capable d'écrire une telle fonction ?

Merci !

[LB2]

Hello,

je pense que c'est très simple si le nombre de phrase total N est une puissance de 2.
Il suffit d'écrire N en base 2
et de découper les valeurs de [1,N] selon leur écriture en base 2.
(l'arithmétique en base 2 est assez simple pour ton opération)

Ou encore, utiliser un arbre binaire de recherche.
Ou encore, une approche récursive (coupage en 2 successifs)

Mathématiquement, tu cherches essentiellement à énumérer les rationnels dyadiques de [0,1]
https://en.wikipedia.org/wiki/Dyadic_rational

[tadaa9]

Bonjour LB2,

Merci pour tes pistes !

Non, malheureusement, je génère également un nombre de phrases impairs (des 10aines de milliers en réalité).

Ton lien est exactement ce que je cherche à exprimer ! Je vais donc creuser de ce côté.

J'avais également pensé à une approche récursive qui est plus proche de ma compétence. Peut-être retrouver mes cours sur les arbres binaires...

Merci !

[lyceen95]

Si le nombre de phrases est impair, c'est au contraire une bonne nouvelle.
Et si le nombre de phrases est de la forme 2^k+1, alors c'est une très bonne nouvelle.

Prenons un cas à problème, on a 13 phrases.
On veut quel ordre ?
1 13 7 4 10 ... et après ?
1 13 7 4 10 2 3 5 6 8 9 11 12 ? ou bien 1 13 7 4 10 2 5 8 11 3 6 9 12 ? ou même 1 13 7 4 10 2 5 9 12 3 6 8 11 ?

Si tu veux que le haut de l'arbre respecte au mieux ta règle, on va effectivement commencer par 1 13 7 4 10
Mais une autre option, c'est de privilégier le bas de l'arbre. L'énumération devra finir par 2 4 6 8 10 12.
Et il reste à définir une stratégie pour le début.

Dernier point. Le fait de commencer par la 1ere et la dernière ligne, ok, c'est un choix. Mais c'est en fait une exception.
On prend la 1ère et la dernière phrase, puis on a une démarche qui va être la même pour toutes les autres phrases (une dichotomie d'une certaine façon).

[fatal_error]

hi,

On peut s'en sortir à peu près (et de manière pas très jolie) avec une récurrence:
https://jsfiddle.net/0s5b21p6/

Code: Tout sélectionner

function buildLayers(left, right, n, depth, layers){
    if(n == left || n == right ){return null}
    let t = {}
    t.n = n;
    if(!layers[depth]){
        layers[depth]=[];
    }
    layers[depth].push(t.n);
    t.left = buildLayers(left, n, Math.floor((left + n)/2), depth+1, layers)
    t.right = buildLayers(n, right, Math.floor((right + n)/2), depth+1, layers)
    return t;
}
function specialBuild(N){
    let layers = [];
    let t2 = buildLayers(1, N, Math.floor((1+N)/2),0, layers);
    //your special case
    layers.unshift([1,N]);
    return layers;
}
function getBack(i, layers){
    let depth = 0;
    let layer = layers[depth];
    while(i >= layers[depth].length){
        i -= layers[depth].length;
        depth++;
    }
    return layers[depth][i];
}
function main(N){
    console.log('processing', N)
    let layers = specialBuild(N);
    for(let i = 0; i<N; ++i){
        console.log(i,'-->', getBack(i, layers)) 
    }   
}
main(12);
main(16);


on peut optimiser un peu sur getBack en remarquant que chaque layer est une puissance de 2 (sauf le tout premier et le dernier)