给定开始、结束和N个数字的数组。在每一步中，start与数组中的任何数字相乘，然后对100000进行mod操作以获得新的start。我们的任务是找到从一开始就可以达到目的的最小步骤。 例如：
null
输入： 开始=3结束=30A[]={2,5,7} 输出： 2. 第一步：3*2=6%100000=6 第二步：6*5=30%100000=30 输入： 开始=7结束=66175 a[]={3,4,65} 输出： 4. 第一步：7*3=21%100000=21 第二步：21*3=6%100000=63 第三步：63*65=4095%100000=4095 第四步：4095*65=266175%100000=66175
方法： 由于在上述问题中，给出的模数为100000，因此最大状态数为10 5. .所有状态都可以使用简单的 BFS .使用-1初始化ans[]数组，该数组标记尚未访问该状态。ans[i]存储从一开始达到i所采取的步骤数。首先将开始推送到队列，然后应用BFS。弹出顶部元素并检查它是否等于结束，如果是，则打印ans[end]。如果元素不等于最上面的元素，则将最上面的元素与数组中的每个元素相乘，并执行mod操作。如果之前没有访问过乘法元素状态，则将其推入队列。通过ans[top_element]+1初始化ans[push_element]。一旦访问了所有状态，并且无法通过执行所有可能的乘法来达到该状态，则打印-1。 以下是上述方法的实施情况：
C++
// C++ program to find the minimum steps // to reach end from start by performing // multiplications and mod operations with array elements #include <bits/stdc++.h> using namespace std; // Function that returns the minimum operations int minimumMulitplications( int start, int end, int a[], int n) { // array which stores the minimum steps // to reach i from start int ans[100001]; // -1 indicated the state has not been visited memset (ans, -1, sizeof (ans)); int mod = 100000; // queue to store all possible states queue< int > q; // initially push the start q.push(start % mod); // to reach start we require 0 steps ans[start] = 0; // till all states are visited while (!q.empty()) { // get the topmost element in the queue int top = q.front(); // pop the topmost element q.pop(); // if the topmost element is end if (top == end) return ans[end]; // perform multiplication with all array elements for ( int i = 0; i < n; i++) { int pushed = top * a[i]; pushed = pushed % mod; // if not visited, then push it to queue if (ans[pushed] == -1) { ans[pushed] = ans[top] + 1; q.push(pushed); } } } return -1; } // Driver Code int main() { int start = 7, end = 66175; int a[] = { 3, 4, 65 }; int n = sizeof (a) / sizeof (a[0]); // Calling function cout << minimumMulitplications(start, end, a, n); return 0; } |
JAVA
// Java program to find the minimum steps // to reach end from start by performing // multiplications and mod operations with array elements import java.util.Arrays; import java.util.LinkedList; import java.util.Queue; class GFG { // Function that returns the minimum operations static int minimumMulitplications( int start, int end, int a[], int n) { // array which stores the minimum steps // to reach i from start int ans[] = new int [ 100001 ]; // -1 indicated the state has not been visited Arrays.fill(ans, - 1 ); int mod = 100000 ; // queue to store all possible states Queue<Integer> q = new LinkedList<>(); // initially push the start q.add(start % mod); // to reach start we require 0 steps ans[start] = 0 ; // till all states are visited while (!q.isEmpty()) { // get the topmost element in the queue int top = q.peek(); // pop the topmost element q.remove(); // if the topmost element is end if (top == end) { return ans[end]; } // perform multiplication with all array elements for ( int i = 0 ; i < n; i++) { int pushed = top * a[i]; pushed = pushed % mod; // if not visited, then push it to queue if (ans[pushed] == - 1 ) { ans[pushed] = ans[top] + 1 ; q.add(pushed); } } } return - 1 ; } // Driver Code public static void main(String args[]) { int start = 7 , end = 66175 ; int a[] = { 3 , 4 , 65 }; int n = a.length; // Calling function System.out.println(minimumMulitplications(start, end, a, n)); } } // This code is contributed by PrinciRaj19992 |
Python3
# Python3 program to find the minimum steps # to reach end from start by performing # multiplications and mod operations with # array elements from collections import deque # Function that returns the minimum operations def minimumMulitplications(start, end, a, n): # array which stores the minimum # steps to reach i from start ans = [ - 1 for i in range ( 100001 )] # -1 indicated the state has # not been visited mod = 100000 q = deque() # queue to store all possible states # initially push the start q.append(start % mod) # to reach start we require 0 steps ans[start] = 0 # till all states are visited while ( len (q) > 0 ): # get the topmost element in the # queue, pop the topmost element top = q.popleft() # if the topmost element is end if (top = = end): return ans[end] # perform multiplication with # all array elements for i in range (n): pushed = top * a[i] pushed = pushed % mod # if not visited, then push it to queue if (ans[pushed] = = - 1 ): ans[pushed] = ans[top] + 1 q.append(pushed) return - 1 # Driver Code start = 7 end = 66175 a = [ 3 , 4 , 65 ] n = len (a) # Calling function print (minimumMulitplications(start, end, a, n)) # This code is contributed by mohit kumar |
C#
// C# program to find the minimum steps // to reach end from start by performing // multiplications and mod operations with array elements using System; using System.Collections.Generic; class GFG { // Function that returns the minimum operations static int minimumMulitplications( int start, int end, int []a, int n) { // array which stores the minimum steps // to reach i from start int []ans = new int [100001]; // -1 indicated the state has not been visited for ( int i = 0; i < ans.Length; i++) ans[i] = -1; int mod = 100000; // queue to store all possible states Queue< int > q = new Queue< int >(); // initially push the start q.Enqueue(start % mod); // to reach start we require 0 steps ans[start] = 0; // till all states are visited while (q.Count != 0) { // get the topmost element in the queue int top = q.Peek(); // pop the topmost element q.Dequeue(); // if the topmost element is end if (top == end) { return ans[end]; } // perform multiplication with all array elements for ( int i = 0; i < n; i++) { int pushed = top * a[i]; pushed = pushed % mod; // if not visited, then push it to queue if (ans[pushed] == -1) { ans[pushed] = ans[top] + 1; q.Enqueue(pushed); } } } return -1; } // Driver Code public static void Main(String []args) { int start = 7, end = 66175; int []a = {3, 4, 65}; int n = a.Length; // Calling function Console.WriteLine(minimumMulitplications(start, end, a, n)); } } /* This code contributed by PrinciRaj1992 */ |
Javascript
<script> // Javascript program to find the minimum steps // to reach end from start by performing // multiplications and mod operations with array elements // Function that returns the minimum operations function minimumMulitplications(start,end,a,n) { // array which stores the minimum steps // to reach i from start let ans = new Array(100001); // -1 indicated the state has not been visited for (let i=0;i<ans.length;i++) { ans[i]=-1; } let mod = 100000; // queue to store all possible states let q = []; // initially push the start q.push(start % mod); // to reach start we require 0 steps ans[start] = 0; // till all states are visited while (q.length!=0) { // get the topmost element in the queue let top = q[0]; // pop the topmost element q.shift(); // if the topmost element is end if (top == end) { return ans[end]; } // perform multiplication with all array elements for (let i = 0; i < n; i++) { let pushed = top * a[i]; pushed = pushed % mod; // if not visited, then push it to queue if (ans[pushed] == -1) { ans[pushed] = ans[top] + 1; q.push(pushed); } } } return -1; } // Driver Code let start = 7, end = 66175; let a=[3, 4, 65]; let n = a.length; // Calling function document.write(minimumMulitplications(start, end, a, n)); // This code is contributed by unknown2108 </script> |
输出：
4
时间复杂性： O（n）
辅助空间： O（n）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
