Réduire un tableau en un entier en utilisant l'opération donnée, implémentée en C++

Étant donné une variable entière Nombre en entrée. Considérons un tableau contenant des éléments compris entre 1 et Number. L'ordre des éléments peut être arbitraire. Si nous effectuons les opérations numéro 1 sur le tableau, l'opération est la suivante :

• Nous sélectionnons deux éléments A et B du tableau

• Supprimons A et B du tableau

• Remplacez A et B La somme des carrés est ajoutée au tableau

Finalement, nous obtenons une seule valeur entière ; le but est de trouver la valeur maximale possible pour cet élément.

Utiliser la file d'attente prioritaire

• Pour maximiser le résultat final, nous devons choisir A et B pour les rendre aussi grands que possible.

• Pour trouver les plus grands A et B, nous utiliserons une file d'attente prioritaire pour y stocker les valeurs des éléments.

• La file d'attente prioritaire stocke les éléments par ordre décroissant.

• L'élément le plus haut a la plus grande valeur, et ainsi de suite. Ainsi, après avoir fait apparaître les deux éléments, nous placerons à nouveau leurs carrés dans la file d'attente.

• Popera et poussera le numéro 1 fois pour obtenir le résultat souhaité.

Exemple

Entrée - Nombre=2

Sortie - Élément unique après réduction du tableau : 5

Explication - Supposons que les éléments du tableau sont [1 2]

Après l'insertion dans la file d'attente prioritaire : 2 1

A=5, B=4 : A²+B²=1+4=5

Le dernier élément : 5

Entrée - Numéro=5

Sortie - Élément unique après réduction du tableau : 5

Explication- Supposons que les éléments du tableau sont [5 1 2 4 3]

Après insertion dans la file d'attente prioritaire : 5 4 3 2 1

A=5 , B=4 : A ²+B²=25+16=41 : 41 3 2 1

A=41, B=3 : A²+B²=1681+9=1690 : 1690 2 1

A=1690, B=2 : A²+B²=1681+4=2856104 : 2856104 1

A=2856104 , B=1 : A²+B² =1187163712+1= 1187163713 : 1187163713

Dernier élément : 1187163713

La méthode utilisée dans le programme ci-dessous est la suivante

Dans cette méthode, nous définissons la file d'attente prioritaire pour stocker les éléments du tableau par ordre décroissant. Pop les deux plus grands éléments et repoussez la somme de leurs carrés dans la file d'attente jusqu'à ce qu'il ne reste qu'une seule valeur.

• Obtenez la variable d'entrée Numéro.

• Définissez le type de données du résultat sur long long integer - lli

• La fonction réduireArray(int Num) accepte le nombre d'entrée et renvoie le plus grand entier calculé à l'aide de l'opération ci-dessus.

• Utilisez une file d'attente prioritaire pQueue.

• Utilisez une boucle while pour remplir les nombres 1 à N dans pQueue.

• Quand i

• Maintenant, pQueue stocke les entiers 1 à N par ordre décroissant, avec la taille N.

• Utilisez une boucle while pour parcourir pQueue jusqu'à ce que sa taille >= 1.

• Définissez la valeur maximale sur var1=pQueue.top() et affichez-la.

• Définissez la valeur maximale suivante sur var2=pQueue.top() et affichez-la.

• Réglez var1 sur son carré et définissez var2 sur son carré.

• Poussez à nouveau var1+var2 dans pQueue.

• À la fin de la boucle while, renvoyez l'élément supérieur.

• Imprimez le résultat dans la fonction principale.

Exemple

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
int reduceArray(int Num){
   priority_queue<lli> pQueue;
   int i=1;
   while(i<=Num){
      pQueue.push(i);
      i=i+1;
   }
   while (pQueue.size() > 1) {
      lli var1 = pQueue.top();
      pQueue.pop();
      lli var2 = pQueue.top();
      pQueue.pop();
      var1=var1*var1;
      var2=var2*var2;
      pQueue.push(var1+var2);
   }
   return pQueue.top();
}
int main(){
   int Number = 5;
   cout<<"Single element after array reduction: "<<reduceArray(Number);
   return 0;
}

Output

Si nous exécutons le code ci-dessus, la sortie suivante sera générée

Single element after array reduction: 1187163713

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!