Question

Les nombres dont les seuls facteurs premiers sont 2, 3 ou 5 sont appelés nombres laids.

Exemple:

1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...

1 peut être considéré comme 2^0.

Je travaille à trouver le nième numéro 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 laid ou non.Pour n > 500, c’est devenu super lent.J'ai essayé d'utiliser la mémorisation - observation :Ugly_number * 2, Ugly_number * 3, Ugly_number * 5 sont tous laids.Même avec ça, c'est lent.J'ai essayé d'utiliser certaines propriétés de log - car cela réduirait ce problème de la multiplication à l'addition - mais pas encore beaucoup de chance.J'ai pensé à partager cela avec vous tous.Des idées intéressantes ?

Utiliser un concept similaire à "Passoire d'Eratosthène" (merci Anon)

    for (int i(2), uglyCount(0); ; i++) {
            if (i % 2 == 0)
                    continue;
            if (i % 3 == 0)
                    continue;
            if (i % 5 == 0)
                    continue;
            uglyCount++;
            if (uglyCount == n - 1)
                    break;
    }

i est le nième nombre laid.

Même cela est assez lent.J'essaie de trouver le 1500ème numéro laid.

Était-ce utile?

La solution

Une solution simple et rapide en Java. Utilise l'approche décrite par Anon. .
Ici TreeSet est juste un conteneur capable de revenir plus petit élément en elle. (Pas de doublons stockés.) 

    int n = 20;
    SortedSet<Long> next = new TreeSet<Long>();
    next.add((long) 1);

    long cur = 0;
    for (int i = 0; i < n; ++i) {
        cur = next.first();
        System.out.println("number " + (i + 1) + ":   " + cur);

        next.add(cur * 2);
        next.add(cur * 3);
        next.add(cur * 5);
        next.remove(cur);
    }

Depuis 1000e numéro laid est 51200000, les stocker dans bool[] est pas vraiment une option.

modifier En tant que loisirs du travail (débogage Hibernate stupide), voici solution complètement linéaire. Merci à marcog idée! 

    int n = 1000;

    int last2 = 0;
    int last3 = 0;
    int last5 = 0;

    long[] result = new long[n];
    result[0] = 1;
    for (int i = 1; i < n; ++i) {
        long prev = result[i - 1];

        while (result[last2] * 2 <= prev) {
            ++last2;
        }
        while (result[last3] * 3 <= prev) {
            ++last3;
        }
        while (result[last5] * 5 <= prev) {
            ++last5;
        }

        long candidate1 = result[last2] * 2;
        long candidate2 = result[last3] * 3;
        long candidate3 = result[last5] * 5;

        result[i] = Math.min(candidate1, Math.min(candidate2, candidate3));
    }

    System.out.println(result[n - 1]);

L'idée est que pour calculer a[i], nous pouvons utiliser a[j]*2 pour certains j < i. Mais nous devons aussi veiller à ce que 1) a[j]*2 > a[i - 1] et 2) j est le plus petit possible.
Ensuite, a[i] = min(a[j]*2, a[k]*3, a[t]*5).

Autres conseils

Ma réponse se réfère à la bonne réponse donnée par Nikita Rybak . Alors que l'on pouvait 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é de 1ère approche de Nikita Rybak est que, au lieu d'ajouter les candidats suivants dans la structure de données unique, à savoir l'arbre ensemble, on peut ajouter chacun d'eux séparément dans 3 listes FIFO. De cette façon, chaque liste sera conservé triée tout le temps, et le prochain candidat moins doit toujours être à la tête d'un ou plusieurs de ces listes.

Si nous éliminons l'utilisation des trois listes ci-dessus, nous arrivons à la deuxième mise en œuvre Nikita Rybak réponse. Cela se fait en évaluant les candidats (à figurer dans trois listes) qu'en cas de besoin, de sorte qu'il n'y a pas besoin de les stocker.

Tout simplement :

  

Dans la première approche, nous mettons chaque nouveau candidat dans la structure de données unique, et c'est mauvais parce que trop de choses se mélangent imprudemment. Cette mauvaise stratégie entraîne inévitablement O (log (taille des arbres)) la complexité du temps chaque fois que nous faisons une requête à la structure. En les mettant en files d'attente séparées, cependant, vous verrez que chaque requête ne prend que O (1) et qui est la raison pour laquelle la performance globale réduit à O (n) !!! En effet, chacune des trois listes sont déjà triées, par lui-même.

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

Pour vous donner une idée, si vous simplifiez le problème pour permettre des facteurs de seulement 2 et 3, vous pouvez atteindre O (n ^ {1/2}) temps de démarrage en recherchant la puissance de deux plus petits qui est au moins aussi grand que le n-ième nombre laid, puis à générer une liste de O (n ^ {1/2}) candidats. Ce code devrait vous donner une idée comment le faire. Elle repose sur le fait que le nombre n-ième ne contenant que des puissances de 2 et 3 a une factorisation dont la somme des exposants est O (n ^ {1/2}). 

def 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 sorted(candidates)[n - (t - len(candidates))]

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

Basiquement la recherche pourrait être O (n):

Considérez que vous gardez une histoire partielle 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, l'ajouter à l'histoire, et déposer quelques chiffres de sorte que le plus petit de la liste multipliée par 5 serait plus grande que la le plus grand.

Il sera rapide, parce que la recherche du prochain numéro sera simple:
min (2 * plus grand, plus petit * 5, une à partir du milieu * 3), France qui est plus grand que le plus grand nombre dans la liste. Si elles sont scarse, la liste contient toujours quelques chiffres, de sorte que la recherche du nombre qui doivent être multipliés par 3 sera rapide.

Voici une bonne solution en ML. La fonction laid () retourne un flux (liste paresseux) des numéros de Hamming. La nième fonction peut être utilisée sur ce flux.

utilise la méthode Sieve, les éléments suivants ne sont calculés 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())));

Ce fut la première année de travail CS: -)

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

Trouver tous les numéros laids n plus petits dans l'ordre croissant se fait facilement à l'aide d'une file d'attente prioritaire dans O (n log n) et O (n) espace: Création d'une file d'attente prioritaire des numéros avec les plus petits nombres premiers, d'abord y compris tout le nombre 1. répétez ensuite n fois: Retirez le nombre x plus petit de la file d'attente prioritaire. Si x n'a pas été retirée avant, alors x est le prochain numéro laid plus grand, et nous ajoutons 2x, 3x et 5x à la file d'attente prioritaire. (Si quelqu'un ne connaît pas la file d'attente prioritaire terme, il est comme le tas dans l'algorithme de 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 de temps d'exécution: On extrait un nombre laid à partir des temps de file d'attente n. Nous avons d'abord un élément dans la file d'attente, et après l'extraction d'un nombre laid nous ajoutons trois éléments, ce qui augmente le nombre par 2. Ainsi, après un nombre n laides sont trouvé que nous avons au plus 2n + 1 éléments dans la file d'attente. Un élément peut extraire se faire dans le temps logarithmique. On extrait plus de chiffres que seulement les chiffres laid, mais au plus n nombres laid, plus 2n - 1 autres numéros (ceux qui auraient pu être dans le tamis après n-1 étapes). Ainsi, le temps total est inférieur à transfert de l'objet en temps logarithmique 3n = O (n log n), et l'espace total est d'au plus 2n + 1 éléments = O (n).

Beaucoup de bonnes réponses, mais j'avais du mal à comprendre ceux-ci, plus précisément comment ces réponses, y compris l'un accepté, maintenu l'axiome 2 papier original de Dijkstra :

  

Axiom 2. Si x est dans la séquence, est donc 2 * x, x 3 * et 5 * x.

Après quelques tableaux blancs, il est devenu clair que l'axiome 2 est pas un invariant à chaque itération de l'algorithme, mais en réalité l'objectif de l'algorithme lui-même. A chaque itération, nous essayons de restaurer l'état dans axiome 2. Si last est la dernière valeur dans la séquence de résultat S, axiome 2 peut simplement être reformulé comme:

  

Pour certains x à S, la valeur suivante dans S est le minimum de 2x,   3x et 5x, qui est supérieure à last. Appelons cet axiome 2' .

Ainsi, si nous pouvons trouver x, nous pouvons calculer le minimum de 2x, 3x et 5x en temps constant, et l'ajouter à S.

Mais comment pouvons-nous trouver x? Une approche est, nous ne sommes pas; à la place, chaque fois que nous ajoutons un nouveau e élément à S, on calcule 2e, 3e et 5e, et les ajouter à une file d'attente de priorité minimale. Étant donné que cette exploitation est garantie e en S, extraire simplement l'élément supérieur de l'axiome PQ satisfait 2' .

Cette approche fonctionne, mais le problème est que nous générons un tas de chiffres, nous ne pouvons pas mettre fin à l'aide. Voir cette répondre pour un exemple; si l'utilisateur veut que le 5ème élément S (5), le PQ à ce moment-là tient 6 6 8 9 10 10 12 15 15 20 25. Peut-on pas perdre cet espace?

fin de compte, nous pouvons faire mieux. Au lieu de stocker tous ces chiffres, nous maintenons simplement trois compteurs pour chacun des multiples, à savoir, 2i, 3j et 5k. Ce sont des candidats pour le prochain numéro de S. Quand nous prenons un d'entre eux, on incrémente que le compteur correspondant, et non les deux autres. Ce faisant, nous ne sommes pas générons avec impatience tous les multiples, résolvant ainsi le problème de l'espace avec la première approche.

Voyons voir une course sèche pour n = 8, à savoir le nombre 9. Nous commençons par 1, comme indiqué par axiome 1 dans le document de Dijkstra. 

+---------+---+---+---+----+----+----+-------------------+
| #       | i | j | k | 2i | 3j | 5k | S                 |
+---------+---+---+---+----+----+----+-------------------+
| initial | 1 | 1 | 1 | 2  | 3  | 5  | {1}               |
+---------+---+---+---+----+----+----+-------------------+
| 1       | 1 | 1 | 1 | 2  | 3  | 5  | {1,2}             |
+---------+---+---+---+----+----+----+-------------------+
| 2       | 2 | 1 | 1 | 4  | 3  | 5  | {1,2,3}           |
+---------+---+---+---+----+----+----+-------------------+
| 3       | 2 | 2 | 1 | 4  | 6  | 5  | {1,2,3,4}         |
+---------+---+---+---+----+----+----+-------------------+
| 4       | 3 | 2 | 1 | 6  | 6  | 5  | {1,2,3,4,5}       |
+---------+---+---+---+----+----+----+-------------------+
| 5       | 3 | 2 | 2 | 6  | 6  | 10 | {1,2,3,4,5,6}     |
+---------+---+---+---+----+----+----+-------------------+
| 6       | 4 | 2 | 2 | 8  | 6  | 10 | {1,2,3,4,5,6}     |
+---------+---+---+---+----+----+----+-------------------+
| 7       | 4 | 3 | 2 | 8  | 9  | 10 | {1,2,3,4,5,6,8}   |
+---------+---+---+---+----+----+----+-------------------+
| 8       | 5 | 3 | 2 | 10 | 9  | 10 | {1,2,3,4,5,6,8,9} |
+---------+---+---+---+----+----+----+-------------------+

Notez que S n'a pas grandi à l'itération 6, parce que le 6 minimum candidat avait déjà été ajouté précédemment. Pour éviter ce problème d'avoir à se souvenir de tous les éléments précédents, nous modifions notre algorithme pour incrémenter tous les compteurs chaque fois que les multiples correspondants sont égaux au candidat minimum. Cela nous amène à la mise en œuvre Scala suivant. 

def hamming(n: Int): Seq[BigInt] = {
  @tailrec
  def next(x: Int, factor: Int, xs: IndexedSeq[BigInt]): Int = {
    val leq = factor * xs(x) <= xs.last
    if (leq) next(x + 1, factor, xs)
    else x
  }

  @tailrec
  def loop(i: Int, j: Int, k: Int, xs: IndexedSeq[BigInt]): IndexedSeq[BigInt] = {
    if (xs.size < n) {
      val a = next(i, 2, xs)
      val b = next(j, 3, xs)
      val c = next(k, 5, xs)
      val m = Seq(2 * xs(a), 3 * xs(b), 5 * xs(c)).min

      val x = a + (if (2 * xs(a) == m) 1 else 0)
      val y = b + (if (3 * xs(b) == m) 1 else 0)
      val z = c + (if (5 * xs(c) == m) 1 else 0)

      loop(x, y, z, xs :+ m)
    } else xs
  }

  loop(0, 0, 0, IndexedSeq(BigInt(1)))
}

Je suppose que nous pouvons utiliser Programmation dynamique (DP) et calculer nième Nombre truand . L'explication complète est disponible à 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;
}

On peut voir que son assez rapide, il suffit de changer la valeur de MAX pour calculer plus Nombre truand

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 celui qu'il est un numéro laid. vous pouvez compter et même imprimer tous les numéros 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 résolu en O(1).

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

Maintenant, pour n’importe quel nombre x parmi les 22 nombres ci-dessus, il y aura un nombre x + 30 entre 31 et 60 qui est également moche.Ainsi, on peut trouver au moins 22 nombres entre 31 et 60.Désormais, pour chaque nombre laid compris entre 31 et 60, nous pouvons l’écrire sous la forme s + 30.Donc s sera aussi moche, puisque s + 30 est divisible par 2, 3 ou 5.Ainsi, il y aura exactement 22 nombres entre 31 et 60.Cette logique peut être répétée pour chaque bloc de 30 nombres par la suite.

Ainsi, il y aura 23 nombres dans les 30 premiers nombres, et 22 pour tous les 30 suivants.Autrement dit, les 23 premiers laids se produiront entre 1 et 30, 45 laids se produiront entre 1 et 60, 67 laids 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, j’aurai 6*22 + 1 = 133ème nombre laid à 180.J'aurai le 154ème numéro laid à 210.Je recherche donc le 4ème nombre laid (puisque 137 = 133 + 4) dans l'intervalle [2, 30], qui est 5.Le 137ème nombre laid est alors 180 + 5 = 185.

Un autre exemple:si je veux le 1500ème nombre laid, je compte 1500/22 = 68 blocs.Ainsi, j'aurai 22*68 + 1 = 1497ème moche à 30*68 = 2040.Les trois prochains laids du bloc [2, 30] sont 2, 3 et 4.Notre laid requis est donc à 2040 + 4 = 2044.

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

Voici une autre O (n) approche (solution Python) basée sur l'idée de fusionner les trois listes triées. Le défi est de trouver le prochain numéro laid dans l'ordre croissant. Par exemple, nous savons que les sept premiers chiffres sont laids [1,2,3,4,5,6,8]. Les chiffres laids sont en fait des trois listes suivantes:

  • Liste 1: 1 * 2, 2 * 2, * 3 2, 4 * 2, * 5 2, 6 2 *, 8 * 2 ... (multiplier chaque nombre laid par 2)
  • Liste 2: 1 * 3, 2 * 3, 3 * 3, * 4 3, 5 * 3, 6 * 3, * 3 8 ... (multiplier chaque nombre laid par 3)
  • Liste 3: 1 * 5, 2 * 5, 3 * 5, 4 * 5, 5 * 5, * 6 5, 8 * 5 ... (multiplier chaque nombre laid par 5)

Ainsi, le n-ième nombre laid est le nième nombre de la liste fusionnée des trois listes ci-dessus:

1, 1 * 2, * 3 1, 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        # multiply each number
        if next == ugly3: p3 += 1        # only once by each
        if next == ugly5: p5 += 1        # of the three factors
        uglynumber += [next]
    return uglynumber[-1]
  1. STEP I: calculer trois numéros laids suivants possibles des trois listes
    • ugly2, ugly3, ugly5 = uglynumber[p2]*2, uglynumber[p3]*3, uglynumber[p5]*5
  2. STEP II, trouver un prochain numéro laid comme le plus petit des trois ci-dessus:
    • next = min(ugly2, ugly3, ugly5)
  3. ÉTAPE III: déplacer le pointeur vers l'avant si son numéro laid était le prochain numéro laid
    • if next == ugly2: p2+=1
    • if next == ugly3: p3+=1
    • if next == ugly5: p5+=1
    • Note: pas à l'aide if avec elif ni else
  4. ÉTAPE IV: ajouter le numéro suivant laid dans la liste fusionnée uglynumber
    • uglynumber += [next]
Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top