Vzhledem k váhové stupnici a řadě různých kladných závaží, kde máme nekonečnou zásobu každé závaží. Naším úkolem je položit závaží na levou a pravou misku váhy jednu po druhé tak, aby se misky přesunuly na tu stranu, kde je závaží položeno, tj. pokaždé, když se misky váhy přesunou na alternativní strany.
- Jsou nám dány další celočíselné „kroky“ časy, které potřebujeme k provedení této operace.
- Dalším omezením je, že nemůžeme položit stejnou váhu po sobě, tj. pokud vezmeme váhu w, pak v dalším kroku při pokládání závaží na protější pánev nemůžeme znovu vzít w.
Příklady:
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.
Tento problém lze vyřešit tím, že uděláte DFS mezi státy měřítka.
- Procházíme mezi různými stavy DFS pro řešení, kde každý stav DFS bude odpovídat skutečné hodnotě rozdílu mezi levým a pravým panem a aktuálním počtem kroků.
- Namísto ukládání hmotností obou pánví pouze ukládáme rozdílovou zbytkovou hodnotu a každá zvolená hodnota hmotnosti by měla být větší než tento rozdíl a neměla by se rovnat dříve zvolené hodnotě hmotnosti.
- Pokud ano, zavoláme metodu DFS rekurzivně s novou hodnotou rozdílu a dalším krokem.
Pro lepší pochopení viz níže uvedený kód
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
výstup:
2 3 2 3 5 6 5 3 2 3
Vytvořit kvíz