Question Étapes minimales pour un


Énoncé du problème:

Sur un entier positif, vous pouvez effectuer l'une des trois étapes suivantes.

  1. Soustrayez-en 1. (n = n - 1)
  2. Si c'est divisible par 2, divisez par 2. (si n% 2 == 0, alors n = n / 2)
  3. Si c'est divisible par 3, divisez par 3. (si n% 3 == 0, alors n = n / 3).

Maintenant, la question est, étant donné un entier positif n, trouver le nombre minimum d'étapes qui prend n à 1

par exemple:

  1. Pour n = 1, sortie: 0
  2. Pour n = 4, sortie: 2 (4/2 = 2/2 = 1)
  3. Pour n = 7, sortie: 3 (7 -1 = 6/3 = 2/2 = 1)

Je connais la solution en utilisant la programmation dynamique et avoir un tableau entier. voici le code.

    public int bottomup(int n) {
            //here i am defining an integer array
            //Exception is thrown here, if the n values is high.
            public int[] bu = new int[n+1];
            bu[0] = 0;
            bu[1] = 0;
            for(int i=2;i<=n;i++) {
                    int r = 1+bu[i-1];
                    if(i%2 == 0) r = Math.min(r,1+bu[i/2]);
                    if(i%3 == 0) r = Math.min(r,1+bu[i/3]);
                    bu[i] = r;
            }
            return bu[n];
    }

Mais je veux résoudre ceci en utilisant moins d'espace. Cette solution jette OutofMemoryError dans Java si n = 100000000.Je ne veux pas augmenter mon espace de tas. Quelqu'un at-il une solution utilisant moins d'espace?

S'il vous plaît noter que ce problème ne peut pas être résolu en utilisant algorthm gourmands.Utilisez une boucle while et vérifier divisible par 3 et divisible par 2 ne fonctionnera pas.Vous devez utiliser la programmation dynamique.S'il vous plaît suggérer si une solution utilise moins d'espace.

par exemple:

Pour n = 10, l'algo glouton est 10/2 = 5 -1 = 4/2 = 2/2 = 1, ce qui prend 4 pas. La solution devant être 10-1 = 9/3 = 3/3 = 1, 3 pas.

J'ai même essayé une solution de haut en bas.

    public int[] td = null;
    public int topdown(int n) {
            if(n <= 1) return 0;
            int r = 1+topdown(n-1);
            if(td[n] == 0) {
                    if(n%2 == 0) r = Math.min(r,1+topdown(n/2));
                    if(n%3 == 0) r = Math.min(r,1+topdown(n/3));
                    td[n] = r;
            }
            return td[n];
    }

il échoue à n = 10000.


12
2017-12-12 15:22


origine


Réponses:


Une idée est qu’à tout moment, vous n’avez besoin que des valeurs pour r/3 à r. Donc, vous pouvez continuer à jeter 1/3rd du tableau.

Je ne suis pas familier avec Java, mais avec C++ vous pouvez utiliser un double ended queue (deque):

Vous continuez à ajouter à la deque depuis l'arrière.
Quand i = 6, tu n'as pas besoin bu[0] et bu[1]. Donc, vous sortez deux éléments de l'avant de la file d'attente.

Accès aléatoire [ ] est supporté avec le récipient de deque.

EDIT: également comme suggéré dans les commentaires, vous devriez changer votre type de données à une taille plus petite puisque le nombre maximum d'étapes doit être de l'ordre de ( (log N) to base 2)

EDIT2: Comme Dukeling l'a fait remarquer, il semble qu'en Java, deque ne dispose d'aucune implémentation parfaitement adaptée qui ne compromettrait pas la complexité du temps. Vous pouvez penser à l'implémenter à votre manière comme le fait C ++ (j'ai entendu dire qu'il est implémenté comme un vecteur de vecteurs dont la taille des vecteurs internes est faible par rapport au nombre total d'éléments).


5
2017-12-12 15:48



MISE À JOUR: Voici le code mis à jour que j'ai en fait testé quelque peu et je crois que les réponses sont les mêmes pour n de 1 à 100 000. Je laisse la réponse originale ci-dessous pour référence. La faille était l'utilisation "intelligente" de MAX_INT. J'ai oublié qu'il y aurait des cas où j'ai sauté la possibilité -1 mais le nombre ne serait pas divisible par 2 ou 3. Cela résout ce problème en renvoyant null à "ce chemin est inutile à explorer plus avant".

public static int steps(int n) {
    return steps(n, 0);
}
private static Integer steps(int n, int consecutiveMinusOnes) {
    if (n <= 1) {
        return 0;
    }
    Integer minSteps = null;
    if (consecutiveMinusOnes < 2) {
        Integer subOne = steps(n - 1, consecutiveMinusOnes + 1);
        if (subOne != null) {
            minSteps = 1 + subOne;
        }
    }
    if (n % 2 == 0) {
        Integer div2 = steps(n / 2, 0);
        if (div2 != null) {
            if (minSteps == null) {
                minSteps = div2 + 1;
            } else {
                minSteps = Math.min(minSteps, 1 + div2);
            }
        }
    }
    if (n % 3 == 0) {
        Integer div3 = steps(n / 3, 0);
        if (div3 != null) {
            if (minSteps == null) {
                minSteps = div3 + 1;
            } else {
                minSteps = Math.min(minSteps, 1 + div3);
            }
        }
    }
    return minSteps;
}

Je crois que cela peut fonctionner, mais je ne l'ai pas prouvé. Cet algorithme est basé sur l'idée que la seule raison de soustraire par un est de vous rapprocher d'un nombre divisible par 2 ou 3. Pour cette raison, vous n'avez jamais vraiment besoin d'appliquer le soustrait par un pas plus de deux fois consécutivement, car si k% 3 == 2, alors k - 2% 3 == 0 et vous pouvez diviser par trois. La soustraction par une autre fois sera un effort inutile (vous aurez également passé au moins un nombre pair, de sorte que la meilleure opportunité en deux étapes apparaîtra). Cela signifie une approche descendante et récursive, et vous pouvez combiner certaines mémo si vous voulez:

public static int steps(n) {
    return steps(n, 0);
}
private static int steps(int n, int consecutiveMinusOnes) {
    if (n <= 1) {
        return 0;
    }
    int minSteps = Integer.MAX_VALUE;
    if (consecutiveMinusOnes < 2) {
        minSteps = 1 + steps(n - 1, consecutiveMinusOnes + 1);
    }
    if (n % 2 == 0) {
        minSteps = Math.min(minSteps, 1 + steps(n / 2, 0));
    }
    if (n % 3 == 0) {
        minSteps = Math.min(minSteps, 1 + steps(n / 3, 0));
    }
    return minSteps;
}

AVERTISSEMENT: Comme je l'ai dit ci-dessus, je n'ai pas prouvé que cette méthode fonctionne. Je n'ai pas non plus testé cette implémentation particulière. Je n'ai pas non plus fait la mémorisation juste parce que je suis paresseux. Quoi qu’il en soit, j’espère que même si cela ne fonctionne pas tout à fait, cela vous donne quelques idées sur la façon de modifier votre approche.


1
2017-12-12 15:56



Cela marche :)

import java.util.Scanner;
public class MinimumStepToOne {

 public static void main(String[] args){
    Scanner sscan = new Scanner(System.in);
    System.out.print("Give a no:" + " ");

    int n = sscan.nextInt();
    int count = 0;
    for(int i = 0; n > 1; i++){

        if(n%2 == 0){n /= 2; count++;}
        else if(n%3 == 0){ n /= 3; count++;}
        else { n -= 1; count++;}

    }
    System.out.println("your no is minimized to: " + n);
    System.out.println("The min no of steps: " + count);    
 }
}

0
2018-06-04 08:10