Ņemot vērā svēršanas skalu un dažādu pozitīvo svaru masīvu, kur mums ir bezgalīgi daudz katra svara. Mūsu uzdevums ir uzlikt svarus uz kreiso un labo svaru pannas pa vienam tā, lai pannas virzītos uz to pusi, kur tiek likts svars, t.i., katru reizi, kad svari pārvietojas uz citām pusēm.
- Mums ir doti vēl viens vesels skaitļa “soļu” laiks, kas nepieciešams šīs darbības veikšanai.
- Vēl viens ierobežojums ir tāds, ka mēs nevaram secīgi uzlikt vienu un to pašu svaru, t.i., ja tiek ņemts svars w, tad nākamajā solī, liekot svaru uz pretējās pannas, mēs nevaram atkārtoti ņemt w.
Piemēri:
Let weight array is [7 11] and steps = 3 then 7 11 7 is the sequence in which weights should be kept in order to move scale alternatively. Let another weight array is [2 3 5 6] and steps = 10 then 3 2 3 5 6 5 3 2 3 is the sequence in which weights should be kept in order to move scale alternatively.
Šo problēmu var atrisināt, rīkojoties DFS starp mēroga stāvokļiem.
- Mēs šķērsojam dažādus DFS stāvokļus, lai atrastu risinājumu, kur katrs DFS stāvoklis atbildīs faktiskajai starpības vērtībai starp kreiso un labo panorāmu un pašreizējo soļu skaitu.
- Tā vietā, lai saglabātu abu pannu svaru, mēs tikai saglabājam starpības atlikuma vērtību, un katru reizi izvēlētajai svara vērtībai ir jābūt lielākai par šo starpību un tai nevajadzētu būt vienādai ar iepriekš izvēlēto svara vērtību.
- Ja tā ir, mēs rekursīvi izsaucam DFS metodi ar jaunu atšķirības vērtību un vēl vienu soli.
Lai labāk izprastu, lūdzu, skatiet tālāk norādīto kodu
C++// C++ program to print weights for alternating // the weighting scale #include
// Java program to print weights for alternating // the weighting scale class GFG { // DFS method to traverse among // states of weighting scales static boolean dfs(int residue int curStep int[] wt int[] arr int N int steps) { // If we reach to more than required steps // return true if (curStep >= steps) return true; // Try all possible weights and // choose one which returns 1 afterwards for (int i = 0; i < N; i++) { /* * Try this weight only if it is * greater than current residue * and not same as previous chosen weight */ if (curStep - 1 < 0 || (arr[i] > residue && arr[i] != wt[curStep - 1])) { // assign this weight to array and // recur for next state wt[curStep] = arr[i]; if (dfs(arr[i] - residue curStep + 1 wt arr N steps)) return true; } } // if any weight is not possible // return false return false; } // method prints weights for alternating scale // and if not possible prints 'not possible' static void printWeightOnScale(int[] arr int N int steps) { int[] wt = new int[steps]; // call dfs with current residue as 0 // and current steps as 0 if (dfs(0 0 wt arr N steps)) { for (int i = 0; i < steps; i++) System.out.print(wt[i] + ' '); System.out.println(); } else System.out.println('Not Possible'); } // Driver Code public static void main(String[] args) { int[] arr = { 2 3 5 6 }; int N = arr.length; int steps = 10; printWeightOnScale(arr N steps); } } // This code is contributed by // sanjeev2552
# Python3 program to print weights for # alternating the weighting scale # DFS method to traverse among states # of weighting scales def dfs(residue curStep wt arr N steps): # If we reach to more than required # steps return true if (curStep >= steps): return True # Try all possible weights and choose # one which returns 1 afterwards for i in range(N): # Try this weight only if it is greater # than current residueand not same as # previous chosen weight if (arr[i] > residue and arr[i] != wt[curStep - 1]): # assign this weight to array and # recur for next state wt[curStep] = arr[i] if (dfs(arr[i] - residue curStep + 1 wt arr N steps)): return True # if any weight is not possible # return false return False # method prints weights for alternating scale # and if not possible prints 'not possible' def printWeightsOnScale(arr N steps): wt = [0] * (steps) # call dfs with current residue as 0 # and current steps as 0 if (dfs(0 0 wt arr N steps)): for i in range(steps): print(wt[i] end = ' ') else: print('Not possible') # Driver Code if __name__ == '__main__': arr = [2 3 5 6] N = len(arr) steps = 10 printWeightsOnScale(arr N steps) # This code is contributed by PranchalK
// C# program to print weights for alternating // the weighting scale using System; namespace GFG { class Program { // DFS method to traverse among states of weighting scales static bool dfs(int residue int curStep int[] wt int[] arr int N int steps) { // If we reach to more than required steps return true if (curStep >= steps) return true; // Try all possible weights and choose one which returns 1 afterwards for (int i = 0; i < N; i++) { /* * Try this weight only if it is greater than current residue * and not same as previous chosen weight */ if (curStep - 1 < 0 || (arr[i] > residue && arr[i] != wt[curStep - 1])) { // assign this weight to array and recur for next state wt[curStep] = arr[i]; if (dfs(arr[i] - residue curStep + 1 wt arr N steps)) return true; } } // if any weight is not possible return false return false; } // method prints weights for alternating scale and // if not possible prints 'not possible' static void printWeightOnScale(int[] arr int N int steps) { int[] wt = new int[steps]; // call dfs with current residue as 0 and current steps as 0 if (dfs(0 0 wt arr N steps)) { for (int i = 0; i < steps; i++) Console.Write(wt[i] + ' '); Console.WriteLine(); } else Console.WriteLine('Not Possible'); } static void Main(string[] args) { int[] arr = { 2 3 5 6 }; int N = arr.Length; int steps = 10; printWeightOnScale(arr N steps); } } }
function dfs(residue curStep wt arr N steps) { // If we reach to more than required steps // return true if (curStep > steps) { return true; } // Try all possible weights and choose one which // returns 1 afterwards for (let i = 0; i < N; i++) { /* Try this weight only if it is greater than current residue and not same as previous chosen weight */ if (arr[i] > residue && arr[i] !== wt[curStep - 1]) { // assign this weight to array and recur for // next state wt[curStep] = arr[i]; if (dfs(arr[i] - residue curStep + 1 wt arr N steps)) { return true; } } } // if any weight is not possible return false return false; } function printWeightsOnScale(arr N steps) { const wt = new Array(steps); // call dfs with current residue as 0 and current // steps as 0 if (dfs(0 1 wt arr N steps)) { for (let i = 1; i <= steps; i++) { process.stdout.write(`${wt[i]} `); } console.log(); } else { console.log('Not possible'); } } const arr = [2 3 5 6]; const N = arr.length; const steps = 10; printWeightsOnScale(arr N steps); // This code is contributed by divyansh2212
Izvade:
2 3 2 3 5 6 5 3 2 3
Izveidojiet viktorīnu