ПОМЕРАЈТЕ СКАЛУ НАИЗМЕНИЧНО ПОД ДАТИМ ОГРАНИЧЕЊИМА

Дате скалу пондера и низ различитих позитивних тежина где имамо бесконачну понуду сваке тежине. Наш задатак је да ставимо тегове на леву и десну тегове један по један на начин да се тегови померају на ону страну где се ставља тежина, односно сваки пут када се тегови померају на наизменичне стране.

Дато нам је још једно целобројно време „корака“ које нам је потребно да извршимо ову операцију.
Друго ограничење је да не можемо да стављамо исту тежину узастопно, тј. ако се узме тежина в, онда у следећем кораку док стављамо тежину на супротну посуду не можемо поново узети в.

Примери:

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.

Овај проблем се може решити тако што ћете ДФС међу државама обима.

Прелазимо између различитих ДФС стања за решење где ће свако ДФС стање одговарати стварној вредности разлике између левог и десног померања и тренутног броја корака.
Уместо да чувамо тежине обе посуде, ми само чувамо вредност остатка разлике и сваки пут изабрана вредност тежине треба да буде већа од ове разлике и не би требало да буде једнака претходно одабраној вредности тежине.
Ако јесте, онда позивамо ДФС метод рекурзивно са новом вредношћу разлике и још једним кораком.

Молимо погледајте код испод за боље разумевање

C++

// C++ program to print weights for alternating // the weighting scale #include    using namespace std; // DFS method to traverse among states of weighting scales 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 residueand 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; } // method prints weights for alternating scale and if // not possible prints 'not possible' void printWeightsOnScale(int arr[] int N int steps) {  int wt[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++)  cout << wt[i] << ' ';  cout << endl;  }  else  cout << 'Not possiblen'; } // Driver code to test above methods int main() {  int arr[] = {2 3 5 6};  int N = sizeof(arr) / sizeof(int);  int steps = 10;  printWeightsOnScale(arr N steps);  return 0; }

Java

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

# 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);  }  } }

JavaScript

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

Излаз:

2 3 2 3 5 6 5 3 2 3

Креирај квиз

TechCodeview

Померајте скалу наизменично под датим ограничењима