給定條件找最小值c語言程序
Problem statement:
問題陳述：
Given a number n, count minimum steps to minimize it to 1 performing the following operations:
給定數字n ，執行以下操作，計算最少的步驟以將其最小化為1：
Operation1: If n is divisible by 2 then we may reduce n to n/2.
運算1：如果n可被2整除，則可以將n減小為n / 2 。
Operation2: If n is divisible by 3 then you may reduce n to n/3.
運算2：如果n可被3整除，則可以將n減小為n / 3 。
Operation3: Decrement n by 1.
運算3：將n減1。
Input:
輸入：
Input is a single integer, n.
輸入是一個整數n 。
Output:
輸出：
Output the minimum number of steps to minimize the number performing only the above operations.
輸出最小步數以最小化僅執行上述操作的步數 。
Constraints:
限制條件：
1 <= N <= 10000
Example:
例：
Test case 1:
Input:
N=10
Output:
Minimum number of steps needed: 3
Test case 2:
Input:
N=6
Output:
Minimum number of steps needed: 2
Explanation:
說明：
For the above test case,
N=10
N is not divisible by 3, but by 2
So,
10->5
Now % is again neither divisible by 3 nor 2
So, only option is to decrement
Hence
5->4
4 can be decremented to 2 by dividing by 2
4->2
2->1
So,
The conversion path will be
10->5->4->2->1
Total 4 steps
But is this the optimal one?
Answer is no
The optimal will be
10 converted to 9 by decrementing
10->9
9->3->1
So, total of 3 steps which is the minimum number
Hence answer would be 3
Solution Approach:
解決方法：
The above problem is a classic recursion example.
上面的問題是一個經典的遞歸示例。
Like,
喜歡，
If n is divided by both 2 and 3
如果n除以2和3
Recur for possibilities
重復可能性
(n/3), (n/2), (n-1)
(n / 3)，(n / 2)，(n-1)
If n is divided by only 3 but not by 2 then
如果n僅除以3而不是2，則
Recur for possibilities
重復可能性
(n/3), (n-1)
(n / 3)，(n-1)
If n is divided by only 2 but not by 3 then
如果n僅被2除而不是3，則
Recur for possibilities
重復可能性
(n/2), (n-1)
(n / 2)，(n-1)
If n is divided by only 3 but not by 2 then
如果n僅除以3而不是2，則
Recur for possibilities
重復可能性
(n/3), (n-1)
(n / 3)，(n-1)
If n is not divisible by both 2 and 3
如果n不能被2和3整除
Then only recur for
然后只重復
(n-1)
(n-1)
We can write all this with help of recursive function,
我們可以借助遞歸函數來編寫所有這些代碼，
Let,
f(n) = the minimum number of steps to convert n to 1
If you draw the recursion tree for f(10) you will find many overlapping sub-problems. Hence, we need to store all the already computed sub-problems through memorization.
如果為f(10)繪制遞歸樹，則會發現許多重疊的子問題。 因此，我們需要通過記憶存儲所有已經計算出的子問題。
Function minimumSteps(n)
if(n==1)
return 0;
// memoization here, no need to compute if already computed
if(dp[n]!=-1)
return dp[n];
// store if not computed
if(n%3==0 && n%2==0)
dp[n]=1+min(minimumSteps(n-1),min(minimumSteps(n/3),minimumSteps(n/2)));
else if(n%3==0)
dp[n]=1+min(minimumSteps(n-1),minimumSteps(n/3));
else if(n%2==0)
dp[n]=1+min(minimumSteps(n-1),minimumSteps(n/2));
else
dp[n]=1+minimumSteps(n-1);
end if
return dp[n]
End Function
C++ Implementation:
C ++實現：
#include <bits/stdc++.h>
using namespace std;
int dp[10001];
int minimumSteps(int n)
{
if (n == 1)
return 0;
if (dp[n] != -1)
return dp[n];
if (n % 3 == 0 && n % 2 == 0) {
dp[n] = 1 + min(minimumSteps(n - 1), min(minimumSteps(n / 3), minimumSteps(n / 2)));
}
else if (n % 3 == 0) {
dp[n] = 1 + min(minimumSteps(n - 1), minimumSteps(n / 3));
}
else if (n % 2 == 0) {
dp[n] = 1 + min(minimumSteps(n - 1), minimumSteps(n / 2));
}
else
dp[n] = 1 + minimumSteps(n - 1);
return dp[n];
}
int main()
{
int n, item;
cout << "enter the initial number, n \n";
cin >> n;
for (int i = 0; i <= n; i++)
dp[i] = -1;
cout << "Minimum number of steps: " << minimumSteps(n) << endl;
return 0;
}
Output:
輸出：
RUN 1:
enter the initial number, n
15
Minimum number of steps: 4
RUN 2:
enter the initial number, n
7
Minimum number of steps: 3
翻譯自: https://www.includehelp.com/icp/minimum-steps-to-minimize-n-as-per-given-condition.aspx
給定條件找最小值c語言程序
)
