nième nombre laid

Je travaille à trouver le nième nombre laid. Notez que ces nombres sont extrêmement peu distribués à mesure que n devient grand.

J'ai écrit un programme trivial qui calcule si un nombre donné est moche ou non.

Cela ressemble à la mauvaise approche pour le problème que vous essayez de résoudre-c'est un peu un algorithme de shlemiel.

Connaissez - vous l'algorithme Seive D'Eratosthène pour trouver des nombres premiers? Quelque chose de similaire (exploiter la connaissance que chaque nombre laid est 2, 3 ou 5 fois un autre nombre laid) fonctionnerait probablement mieux pour résoudre cela.

Ma réponse fait référence à la bonne réponse donnée par Nikita Rybak. Pour que l'on puisse voir une transition de l'idée de la première approche à celle de la seconde.

from collections import deque
def hamming():
    h=1;next2,next3,next5=deque([]),deque([]),deque([])
    while True:
        yield h
        next2.append(2*h)
        next3.append(3*h)
        next5.append(5*h)
        h=min(next2[0],next3[0],next5[0])
        if h == next2[0]: next2.popleft()
        if h == next3[0]: next3.popleft()
        if h == next5[0]: next5.popleft()

Ce qui a changé par rapport à la 1ère approche de Nikita Rybak, c'est que, au lieu d'ajouter les candidats suivants dans une structure de données unique, C'est-à-dire un ensemble D'arbres, on peut ajouter chacun d'eux séparément dans 3 listes FIFO. De cette façon, chaque liste sera triée tout le temps, et le candidat le moins suivant doit toujours être à la tête d'une ou plusieurs de ces listes.

Si nous éliminons l'utilisation des trois listes ci-dessus, nous arrivons à la deuxième implémentation dans la réponse de Nikita Rybak. Cela se fait en évaluant ces candidats (à inclure dans trois listes) uniquement lorsque cela est nécessaire, de sorte qu'il n'est pas nécessaire de les stocker.

En termes simples :

Dans la première approche, nous mettons chaque nouveau candidat dans une structure de données unique, et c'est mauvais parce que trop de choses se mélangent jusqu'imprudemment. Cette mauvaise stratégie implique inévitablement une complexité temporelle o(log (tree size)) chaque fois que nous faisons une requête à la structure. En les mettant dans des files d'attente séparées, cependant, vous verrez que chaque requête ne prend que O (1) et c'est pourquoi la performance globale se réduit à O(n)!!! C'est parce que chacune des trois listes est déjà triée, par elle-même.

Fondamentalement, la recherche pourrait être faite O (n):

Considérez que vous gardez un historique partiel des nombres laids. Maintenant, à chaque étape, vous devez trouver la suivante. Il devrait être égal à un nombre de l'histoire multiplié par 2, 3 ou 5. Choisissez le plus petit d'entre eux, ajoutez-le à l'histoire et supprimez-en quelques chiffres pour que le plus petit de la liste multiplié par 5 soit plus grand que le plus grand.

Ce sera rapide, car la recherche du numéro suivant sera simple:
min(la plus grande * 2, plus petit * 5, un du milieu * 3),
c'est plus grand que le plus grand nombre de la liste. Si elles sont scarse, la liste contiendra toujours peu de nombres, de sorte que la recherche du nombre qui doit être multiplié par 3 sera rapide.

Je crois que vous pouvez résoudre ce problème en temps sous-linéaire, probablement O (N^{2/3}).

Pour vous donner l'idée, si vous simplifiez le problème pour autoriser des facteurs de seulement 2 et 3, vous pouvez obtenir le temps o(n^{1/2}) en commençant par chercher la plus petite puissance de deux qui est au moins aussi grande que le nième nombre laid, puis générer une liste de candidats O(N^{1/2}). Ce code devrait vous donner une idée de comment le faire. Il repose sur le fait que le nième nombre ne contenant que des puissances de 2 et 3 a un factorisation primaire dont la somme des exposants est O (N^{1/2}).

foo(n):
  p2 = 1 # current power of 2
  p3 = 1 # current power of 3
  e3 = 0 # exponent of current power of 3
  t = 1 # number less than or equal to the current power of 2
  while t < n:
    p2 *= 2
    if p3 * 3 < p2:
      p3 *= 3
      e3 += 1
    t += 1 + e3
  candidates = [p2]
  c = p2
  for i in range(e3):
    c /= 2
    c *= 3
    if c > p2: c /= 2
    candidates.append(c)
  return select(candidates, n - (t - candidates.length())) # linear time select

La même idée devrait fonctionner pour trois facteurs autorisés, mais le code devient plus complexe. La somme des pouvoirs de la factorisation tombe à O (N^{1/3}), mais vous devez considérer plus de candidats, O (N^{2/3}) pour être plus précis.

Voici une solution correcte en ML. La fonction ugly() retournera un flux (liste paresseuse) de nombres hamming. La fonction nth peut être utilisée sur ce flux.

Cela utilise la méthode tamis, les éléments suivants ne sont calculés qu'en cas de besoin.

datatype stream = Item of int * (unit->stream);
fun cons (x,xs) = Item(x, xs);
fun head (Item(i,xf)) = i;
fun tail (Item(i,xf)) = xf();
fun maps f xs = cons(f (head xs), fn()=> maps f (tail xs));

fun nth(s,1)=head(s)
  | nth(s,n)=nth(tail(s),n-1);

fun merge(xs,ys)=if (head xs=head ys) then
                   cons(head xs,fn()=>merge(tail xs,tail ys))
                 else if (head xs<head ys) then
                   cons(head xs,fn()=>merge(tail xs,ys))
                 else
                   cons(head ys,fn()=>merge(xs,tail ys));

fun double n=n*2;
fun triple n=n*3;

fun ij()=
    cons(1,fn()=>
      merge(maps double (ij()),maps triple (ij())));

fun quint n=n*5;

fun ugly()=
    cons(1,fn()=>
      merge((tail (ij())),maps quint (ugly())));

C'était la première année de travail CS: -)

Pour trouver le n-ième nombre laid dans O (N^(2/3)), l'algorithme de jonderry fonctionnera très bien. Notez que les nombres impliqués sont énormes donc tout algorithme essayant de vérifier si un nombre est laid ou non n'a aucune chance.

Trouver tous les N plus petits nombres laids dans l'ordre croissant se fait facilement en utilisant une file d'attente prioritaire dans le temps O (N log n) et L'espace O (N): créez une file d'attente prioritaire de nombres avec les plus petits nombres en premier, en incluant initialement juste le nombre 1. Puis répétez n temps: Supprimez le plus petit nombre x de la file d'attente prioritaire. Si x n'a pas été supprimé auparavant, alors x est le nombre laid suivant, et nous ajoutons 2x, 3x et 5x à la file d'attente prioritaire. (Si quelqu'un ne connaît pas le terme file d'attente prioritaire, c'est comme le tas dans l'algorithme heapsort). Voici le début de l'algorithme:

1 -> 2 3 5
1 2 -> 3 4 5 6 10
1 2 3 -> 4 5 6 6 9 10 15
1 2 3 4 -> 5 6 6 8 9 10 12 15 20
1 2 3 4 5 -> 6 6 8 9 10 10 12 15 15 20 25
1 2 3 4 5 6 -> 6 8 9 10 10 12 12 15 15 18 20 25 30
1 2 3 4 5 6 -> 8 9 10 10 12 12 15 15 18 20 25 30
1 2 3 4 5 6 8 -> 9 10 10 12 12 15 15 16 18 20 24 25 30 40

Preuve du temps d'exécution: nous extrayons un nombre laid de la file d'attente n fois. Nous avons d'abord un élément dans la file d'attente, et après avoir extrait un nombre laid, nous en ajoutons trois éléments, en augmentant le nombre de 2. Donc, après n nombres laids sont trouvés, nous avons au plus 2n + 1 éléments dans la file d'attente. L'extraction d'un élément peut se faire en temps logarithmique. Nous extrayons plus de nombres que les nombres laids mais au plus n nombres laids plus 2n - 1 autres nombres (ceux qui auraient pu être dans le tamis après n-1 étapes). Ainsi, le temps total est inférieur à 3N suppressions d'éléments dans le temps logarithmique = O (N log n), et l'espace total est au plus 2n + 1 éléments = O (N).

Je crois que l'on peut utiliser Programmation Dynamique (DP) et calculer nième Laid Nombre. Une explication complète peut être trouvée à http://www.geeksforgeeks.org/ugly-numbers/

#include <iostream>
#define MAX 1000

using namespace std;

// Find Minimum among three numbers
long int min(long int x, long int y, long int z) {

    if(x<=y) {
        if(x<=z) {
            return x;
        } else {
            return z;
        }
    } else {
        if(y<=z) {
            return y;
        } else {
            return z;
        }
    }   
}


// Actual Method that computes all Ugly Numbers till the required range
long int uglyNumber(int count) {

    long int arr[MAX], val;

    // index of last multiple of 2 --> i2
    // index of last multiple of 3 --> i3
    // index of last multiple of 5 --> i5
    int i2, i3, i5, lastIndex;

    arr[0] = 1;
    i2 = i3 = i5 = 0;
    lastIndex = 1;


    while(lastIndex<=count-1) {

        val = min(2*arr[i2], 3*arr[i3], 5*arr[i5]);

        arr[lastIndex] = val;
        lastIndex++;

        if(val == 2*arr[i2]) {
            i2++;
        }
        if(val == 3*arr[i3]) {
            i3++;
        }
        if(val == 5*arr[i5]) {
            i5++;
        }       
    }

    return arr[lastIndex-1];

}

// Starting point of program
int main() {

    long int num;
    int count;

    cout<<"Which Ugly Number : ";
    cin>>count;

    num = uglyNumber(count);

    cout<<endl<<num;    

    return 0;
}

Nous pouvons voir que c'est assez rapide, il suffit de changer la valeur de MAX pour calculer plus haut Nombre laid

Voici mon code , l'idée est de diviser le nombre par 2 (jusqu'à ce qu'il donne reste 0), puis 3 et 5 . Si enfin le nombre devient un, c'est un nombre laid. vous pouvez compter et même imprimer tous les nombres laids jusqu'à n.

int count = 0;
for (int i = 2; i <= n; i++) {
    int temp = i;
    while (temp % 2 == 0) temp=temp / 2;
    while (temp % 3 == 0) temp=temp / 3;
    while (temp % 5 == 0) temp=temp / 5;
    if (temp == 1) {
        cout << i << endl;
        count++;
    }

}

Ce problème peut être fait dans O (1).

Si nous enlevons 1 et regardons les nombres entre 2 et 30, nous remarquerons qu'il y a 22 nombres.

Maintenant, pour tout nombre x dans les 22 numéros ci-dessus, il y aura un nombre x + 30 entre 31 et 60 qui est aussi laid. Ainsi, nous pouvons trouver au moins 22 nombres entre 31 et 60. Maintenant, pour chaque nombre laid entre 31 et 60, nous pouvons l'écrire comme s + 30. Donc s sera moche, depuis s + 30 est divisible par 2, 3 ou 5. Ainsi, il y aura exactement 22 numéros entre 31 et 60. Cette logique peut être répétée pour chaque bloc de 30 nombres après cela.

Ainsi, il y aura 23 nombres dans les 30 premiers nombres, et 22 pour chaque 30 après cela. C'est-à-dire que les 23 premières uglies se produiront entre 1 et 30, 45 uglies se produiront entre 1 et 60, 67 uglies se produiront entre 1 et 30, etc.

Maintenant, si on me donne n, disons 137, je peux voir que 137/22 = 6.22. La réponse se situera entre 6 * 30 et 7 * 30 ou entre 180 et 210. À 180, je le ferai avoir 6*22 + 1 = 133e nombre laid à 180. Je vais avoir 154e numéro laid à 210. Donc, je cherche le 4ème Nombre laid (depuis 137 = 133 + 4 ) dans l'intervalle [2, 30], qui est 5. Le 137e nombre laid est alors 180 + 5 = 185.

Un autre exemple: si je veux le 1500E nombre laid, je compte 1500/22 = 68 blocs. Ainsi, j'aurai 22*68 + 1 = 1497e laid à 30 * 68 = 2040. Les trois uglies suivantes dans le bloc [2, 30] sont 2, 3 et 4. Donc, notre laid requis est à 2040 + 4 = 2044.

Le point il que je peux simplement construire une liste de nombres laids entre [2, 30] et simplement trouver la réponse en faisant des recherches dans O (1).

Voici une autre approche O (N) (solution Python) basée sur l'idée de fusionner trois listes triées. le vrai défi est de trouver le prochain-plus grand nombre laid? par exemple, nous savons que les cinq premiers nombres laids sont [1,2,3,4,5]. les nombres laids sont en fait des trois listes suivantes:

• liste 1: 1*2, 2*2, 3*2, 4*2, 5*2 ... ;
• liste 2: 1*3, 2*3, 3*3, 4*3, 5*3 ...;
• liste 3: 1*5, 2*5, 3*5, 4*5, 5*5 ... .

Donc le nième nombre laid sont le nième numéro de la liste fusionnée des trois listes ci-dessus:

1, 1*2, 1*3, 2*2, 1*5, 2*3 ...

def nthuglynumber(n):
    p2, p3, p5=0,0,0
    uglynumber=[1]
    while len(uglynumber)<n:
        ugly2, ugly3, ugly5= uglynumber[p2]*2, uglynumber[p3]*3, uglynumber[p5]*5
        next=min(ugly2, ugly3, ugly5)
        if next==ugly2: p2+=1
        if next==ugly3: p3+=1
        if next==ugly5: p5+=1
        uglynumber+=[next]
    return uglynumber[-1]

1. étape I: calcul des nombres laids actuels à partir des trois listes
   • ugly2, ugly3, ugly5=uglynumber[p2]*2,uglynumber[p3]*3,uglynumber[p5]*5
2. étape II, trouver le prochain-plus grand nombre laid:
   • suivant = min (ugly2, ugly3, ugly5)
3. étape III: déplacer le pointeur vers l'avant si son nombre laid est le nombre suivant
   • Si suivant = = ugly2: p2+ = 1
   • Si suivant = = ugly3: p3+ = 1
   • Si suivant = = ugly5: p5+ = 1
   • notez ici: ne pas utiliser if, elif et else
4. étape IV: ajout du nombre laid suivant dans la liste fusionnée unglynumber
   • uglynumber+=[suivant]