Kun annetaan positiivinen luku N, meidän on päästävä arvoon 1 minimimäärässä askeleita, joissa askel määritellään N:n muuntamiseksi (N-1) tai N muuntamiseksi yhdeksi suuremmista jakajista.
Muodollisesti, jos olemme N:ssä, voimme saavuttaa 1 askeleella arvoon (N - 1) tai jos N = u*v, voimme saavuttaa arvon max(u v), missä u > 1 ja v > 1.
Esimerkkejä:
Input : N = 17 Output : 4 We can reach to 1 in 4 steps as shown below 17 -> 16(from 17 - 1) -> 4(from 4 * 4) -> 2(from 2 * 2) -> 1(from 2 - 1) Input : N = 50 Output : 5 We can reach to 1 in 5 steps as shown below 50 -> 10(from 5 * 10) -> 5(from 2 * 5) -> 4(from 5 - 1) -> 2(from 2 *2) -> 1(from 2 - 1)
Voimme ratkaista tämän ongelman käyttämällä leveyshakua, koska se toimii taso kerrallaan, joten saavutamme 1:n vähimmäisaskelten määrässä, jossa N:n seuraava taso sisältää (N - 1) ja suuremmat oikeat tekijät N.
Täydellinen BFS-menettely on seuraava. Ensin työnnämme N:n vaiheilla 0 datajonoon, sitten jokaisella tasolla työnnämme niiden seuraavan tason elementit 1 askeleen enemmän kuin sen edellisen tason elementit. Tällä tavalla kun 1 ponnahtaa ulos jonosta, se sisältää minimimäärän vaiheita sen kanssa, mikä on lopputuloksemme.
Alla olevassa koodissa käytetään 'data'-tyyppistä rakennetta olevaa jonoa, joka tallentaa arvon ja askeleen N:stä siihen toista kokonaislukutyyppiä, jotta voimme säästää saman elementin työntämisestä useammin kuin kerran, mikä voi johtaa äärettömään silmukkaan. Joten jokaisessa vaiheessa työnnämme arvon joukkoon sen jälkeen, kun se on työnnetty jonoon, jotta arvoa ei käytetä useammin kuin kerran.
Katso alla oleva koodi ymmärtääksesi paremmin
C++// C++ program to get minimum step to reach 1 // under given constraints #include
// Java program to get minimum step to reach 1 // under given constraints import java.util.*; class GFG { // structure represent one node in queue static class data { int val; int steps; public data(int val int steps) { this.val = val; this.steps = steps; } }; // method returns minimum step to reach one static int minStepToReachOne(int N) { Queue<data> q = new LinkedList<>(); q.add(new data(N 0)); // set is used to visit numbers so that they // won't be pushed in queue again HashSet<Integer> st = new HashSet<Integer>(); // loop until we reach to 1 while (!q.isEmpty()) { data t = q.peek(); q.remove(); // if current data value is 1 return its // steps from N if (t.val == 1) return t.steps; // check curr - 1 only if it not visited yet if (!st.contains(t.val - 1)) { q.add(new data(t.val - 1 t.steps + 1)); st.add(t.val - 1); } // loop from 2 to Math.sqrt(value) for its divisors for (int i = 2; i*i <= t.val; i++) { // check divisor only if it is not visited yet // if i is divisor of val then val / i will // be its bigger divisor if (t.val % i == 0 && !st.contains(t.val / i) ) { q.add(new data(t.val / i t.steps + 1)); st.add(t.val / i); } } } return -1; } // Driver code public static void main(String[] args) { int N = 17; System.out.print(minStepToReachOne(N) +'n'); } } // This code is contributed by 29AjayKumar
# Python3 program to get minimum step # to reach 1 under given constraints # Structure represent one node in queue class data: def __init__(self val steps): self.val = val self.steps = steps # Method returns minimum step to reach one def minStepToReachOne(N): q = [] q.append(data(N 0)) # Set is used to visit numbers # so that they won't be pushed # in queue again st = set() # Loop until we reach to 1 while (len(q)): t = q.pop(0) # If current data value is 1 # return its steps from N if (t.val == 1): return t.steps # Check curr - 1 only if # it not visited yet if not (t.val - 1) in st: q.append(data(t.val - 1 t.steps + 1)) st.add(t.val - 1) # Loop from 2 to Math.sqrt(value) # for its divisors for i in range(2 int((t.val) ** 0.5) + 1): # Check divisor only if it is not # visited yet if i is divisor of val # then val / i will be its bigger divisor if (t.val % i == 0 and (t.val / i) not in st): q.append(data(t.val / i t.steps + 1)) st.add(t.val / i) return -1 # Driver code N = 17 print(minStepToReachOne(N)) # This code is contributed by phasing17
// C# program to get minimum step to reach 1 // under given constraints using System; using System.Collections.Generic; class GFG { // structure represent one node in queue class data { public int val; public int steps; public data(int val int steps) { this.val = val; this.steps = steps; } }; // method returns minimum step to reach one static int minStepToReachOne(int N) { Queue<data> q = new Queue<data>(); q.Enqueue(new data(N 0)); // set is used to visit numbers so that they // won't be pushed in queue again HashSet<int> st = new HashSet<int>(); // loop until we reach to 1 while (q.Count != 0) { data t = q.Peek(); q.Dequeue(); // if current data value is 1 return its // steps from N if (t.val == 1) return t.steps; // check curr - 1 only if it not visited yet if (!st.Contains(t.val - 1)) { q.Enqueue(new data(t.val - 1 t.steps + 1)); st.Add(t.val - 1); } // loop from 2 to Math.Sqrt(value) for its divisors for (int i = 2; i*i <= t.val; i++) { // check divisor only if it is not visited yet // if i is divisor of val then val / i will // be its bigger divisor if (t.val % i == 0 && !st.Contains(t.val / i) ) { q.Enqueue(new data(t.val / i t.steps + 1)); st.Add(t.val / i); } } } return -1; } // Driver code public static void Main(String[] args) { int N = 17; Console.Write(minStepToReachOne(N) +'n'); } } // This code is contributed by 29AjayKumar
<script> // Javascript program to get minimum step // to reach 1 under given constraints // Structure represent one node in queue class data { constructor(val steps) { this.val = val; this.steps = steps; } } // Method returns minimum step to reach one function minStepToReachOne(N) { let q = []; q.push(new data(N 0)); // Set is used to visit numbers // so that they won't be pushed // in queue again let st = new Set(); // Loop until we reach to 1 while (q.length != 0) { let t = q.shift(); // If current data value is 1 // return its steps from N if (t.val == 1) return t.steps; // Check curr - 1 only if // it not visited yet if (!st.has(t.val - 1)) { q.push(new data(t.val - 1 t.steps + 1)); st.add(t.val - 1); } // Loop from 2 to Math.sqrt(value) // for its divisors for(let i = 2; i*i <= t.val; i++) { // Check divisor only if it is not // visited yet if i is divisor of val // then val / i will be its bigger divisor if (t.val % i == 0 && !st.has(t.val / i)) { q.push(new data(t.val / i t.steps + 1)); st.add(t.val / i); } } } return -1; } // Driver code let N = 17; document.write(minStepToReachOne(N) + '
'); // This code is contributed by rag2127 </script>
Lähtö:
4