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.

Rearrange_min_sum(arr, size)

À l'intérieur de la fonction Rearrange_min_sum(arr, size)

• Créez une variable, disons, de type « pair » et « impair » qui stocke des variables entières.

• Déclarez une variable comme temp et total et initialisez-la avec 0.

• Démarrez la boucle FOR de i à 0 jusqu'à ce que i soit inférieur à la taille. À l'intérieur de la boucle, vérifiez SI i est inférieur à size/2 puis appuyez sur arr[i] vers. vecteur impair ELSE, poussez arr[i] vers vecteur pair

• Appelez la méthode de tri en passant even.begin(), even.end() et Greater().

• Démarrez la boucle FOR à partir de i à 0 jusqu'à ce que je soit inférieur à even.size(). Dans la boucle, définissez arr[temp++] sur pair[j], arr[temp++] sur impair[j] et total sur total + pair[j] * impair[j]

• Retour total

Imprimez le résultat.

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!