Réorganiser un tableau pour que la somme des produits de paires d'éléments consécutives soit minimale, écrit en C++

Nous avons un tableau de types entiers positifs, en supposant qu'il s'agit de arr[], de n'importe quelle taille. La tâche consiste à réorganiser le tableau de telle sorte que lorsque nous multiplions un élément avec ses éléments adjacents, puis ajoutons tous les éléments résultants, la plus petite somme soit renvoyée.

Regardons différentes situations d'entrée et de sortie :

Entrée - int arr[] = {2, 5, 1, 7, 5, 0, 1, 0}

Sortie - Réorganiser le tableau pour minimiser la somme, c'est-à-dire le produit d'une paire d'éléments consécutifs est : 7 0 5 0 5 1 2 1

Explication- Nous avons un tableau entier de taille 8. Nous allons maintenant réorganiser le tableau, c'est-à-dire 7 0 5 0 5 1 2 1. Nous vérifierons si la somme minimale est renvoyée, c'est-à-dire 7 * 0 + 5 * 0 + 5 * 1 + 2 * 1 = 0 + 0 + 5 + 2 = 7.

Entrée - int arr[] = {1, 3, 7, 2, 4, 3}

Sortie - Réorganiser le tableau pour minimiser la somme, c'est-à-dire que le produit d'une paire consécutive d'éléments est : 7 1 4 2 3 3

Explication- Nous avons un tableau d'entiers de taille 6. Nous allons maintenant réorganiser le tableau, c'est-à-dire 7 1 4 2 3 3. Nous vérifierons si la somme minimale est renvoyée, c'est-à-dire 7 * 1 + 4 * 2 + 3 * 3 = 7 + 8 + 9 = 24.

La méthode utilisée dans le programme suivant est la suivante :

• Saisissez un tableau de type entier et calculez la taille du tableau.

• Triez le tableau en utilisant la méthode de tri de C++ STL, en passant le tableau et la taille du tableau à la fonction de tri.

• Déclarez une variable entière et définissez-la comme valeur de retour de la fonction appelante.

Exemple

#include <bits/stdc++.h>
using namespace std;
int Rearrange_min_sum(int arr[], int size){
   vector<int> even, odd;
   int temp = 0;
   int total = 0;
   for(int i = 0; i < size; i++){
      if (i < size/2){
         odd.push_back(arr[i]);
      }
      else{
         even.push_back(arr[i]);
      }
   }
   sort(even.begin(), even.end(), greater<int>());
   for(int j = 0; j < even.size(); j++){
      arr[temp++] = even[j];
      arr[temp++] = odd[j];
      total += even[j] * odd[j];
   }
   return total;
}
int main(){
   int arr[] = { 2, 5, 1, 7, 5, 0, 1, 0};
   int size = sizeof(arr)/sizeof(arr[0]);
   //sort an array
   sort(arr, arr + size);
   //call function
   int total = Rearrange_min_sum(arr, size);
   cout<<"Rearrangement of an array to minimize sum i.e. "<<total<<" of product of consecutive pair elements is: ";
   for(int i = 0; i < size; i++){
      cout << arr[i] << " ";
   }
   return 0;
}

Sortie

Si nous exécutons le code ci-dessus, il générera la sortie suivante

Rearrangement of an array to minimize sum i.e. 7 of product of consecutive pair elements is: 7 0 5 0 5 1 2 1

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!