1に到達するための最小ステップ

正の数 N が与えられると、最小ステップ数で 1 に到達する必要があります。ステップは、N を (N-1) に変換するか、N をその大きい約数の 1 つに変換するものとして定義されます。

形式的には、N にある場合は 1 ステップで (N - 1) に到達でき、N = u*v の場合は、u > 1 および v > 1 である max(u v) に到達できます。

例:

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)

幅優先探索を使用すると、この問題を解決できます。幅優先探索はレベルごとに機能するため、N の次のレベルに (N - 1) 以上の N の適切な因数が含まれる最小ステップ数で 1 に到達します。
完全な BFS 手順は次のとおりです。まず、ステップ 0 で N をデータキューにプッシュし、次に各レベルで、前のレベルの要素より 1 ステップ多い次のレベルの要素をプッシュします。このようにして、キューから 1 が取り出されるとき、そのキューには最小数のステップが含まれ、これが最終結果になります。
以下のコードでは、値と N からのステップを格納する「データ」タイプの構造のキューが使用されています。無限ループにつながる可能性がある同じ要素を複数回プッシュすることを避けるために、別の整数タイプのセットが使用されています。したがって、各ステップで、値が複数回アクセスされないように、値をキューにプッシュした後、セットに値をプッシュします。

よりよく理解するには、以下のコードを参照してください

Java文字列を整数に変換

C++

// C++ program to get minimum step to reach 1  // under given constraints #include    using namespace std; // structure represent one node in queue struct data {  int val;  int steps;  data(int val int steps) : val(val) steps(steps)  {} }; // method returns minimum step to reach one int minStepToReachOne(int N) {  queue<data> q;  q.push(data(N 0));  // set is used to visit numbers so that they  // won't be pushed in queue again  set<int> st;  // loop until we reach to 1  while (!q.empty())  {  data t = q.front(); q.pop();    // 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.find(t.val - 1) == st.end())  {  q.push(data(t.val - 1 t.steps + 1));  st.insert(t.val - 1);  }  // loop from 2 to 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.find(t.val / i) == st.end())  {  q.push(data(t.val / i t.steps + 1));  st.insert(t.val / i);  }  }  }  } // Driver code to test above methods int main() {  int N = 17;  cout << minStepToReachOne(N) << endl;  }

Java

// 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

# 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

JavaScript

<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>

出力：

クイズの作成