Mit STL nach Anzahl der Faktoren sortieren

Das Sortieren von Vektoren mithilfe von STL ist ein Kinderspiel. Wir können die berühmte Funktion sort() verwenden, um diese Aufgabe zu erfüllen. Die eigentliche Herausforderung besteht darin, die Anzahl der Faktoren für jede Zahl zu zählen.

Ein Faktor ist eine Zahl, die eine andere Zahl vollständig dividiert, also mit einem Rest von Null.

Das Durchlaufen aller Zahlen zur Berechnung der Faktoren könnte eine Möglichkeit sein, aber wir werden in diesem Artikel versuchen, eine effiziente Lösung zu finden und zu optimieren.

Problemstellung

Sortieren Sie das angegebene Array in aufsteigender Reihenfolge basierend auf der Anzahl der Faktoren jeder Zahl. Daher sollte die Zahl mit der niedrigsten Anzahl an Faktoren am Anfang und die Zahl mit der höchsten Anzahl an Faktoren am Ende stehen. Zahlen mit der gleichen Anzahl von Faktoren sollten in der Reihenfolge des ursprünglichen Arrays angeordnet werden. Arrays können mit STL sortiert werden.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Input − Array a = [15,2,20,3,10,4]
Output − 3 2 4 10 15 20
pre class="just-code notranslate language-cpp" data-lang="cpp">
The number of factors of 15 − 4.
The number of factors of 2 −  2.
The number of factors of 20 − 6.
The number of factors of 3 −  2.
The number of factors of 10 − 4.
The number of factors of 4 −  3.

Nachdem wir die Zahlen in aufsteigender Reihenfolge nach ihren Faktoren sortiert haben, erhalten wir die Ausgabe: 3 2 4 10 15 20.

Input − Array a = [5,9,12,19,21]
Output − 19 5 9 21 12

Erklärung

The number of factors of 5 −  3.
The number of factors of 9 −  3.
The number of factors of 12 − 4.
The number of factors of 19 − 2.
The number of factors of 21 − 4.

Nachdem wir die Zahlen in aufsteigender Reihenfolge nach ihren Faktoren sortiert haben, erhalten wir die Ausgabe: 19 5 9 21 12

Methode

• Ermitteln Sie die Anzahl der Faktoren jeder Zahl.

• Erstellen Sie einen Vektor, der Zahlenpaare und ihre Faktoranzahlen speichert.

• Sortieren Sie den Vektor und geben Sie das Ergebnis zurück.

Ermitteln Sie die Anzahl der Faktoren einer Zahl

Die chinesische Übersetzung von

Brute Force

ist:

Brute Force

Ein naiver Ansatz wäre, alle Zahlen von 1 bis n zu durchlaufen und herauszufinden, ob sie n teilen. Auf diese Weise können wir die Anzahl der Faktoren für jede Zahl berechnen.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Das Folgende ist ein C++-Programm, das rohe Gewalt anwendet, um alle Teiler einer Zahl zu berechnen

#include <bits/stdc++.h>
using namespace std;
// function to count the divisors
int countDivisors(int n){
   int count = 0;
	for (int i = 1; i <= n; i++){
	   if (n % i == 0)
		   count++;
	} 
   return count;
}

int main(){
   int n = 55;
   //Function call
   int ans = countDivisors(n);
	cout <<"The number of divisors of 55 is: "<<ans<<endl;
	return 0;
}

Ausgabe

The number of divisors of 55 is: 4

Effiziente Methode

Die Faktoren einer Zahl existieren paarweise.

Zum Beispiel sind die Teiler von 12 1, 2, 3, 4, 6, 12.

Wir können sie uns jedoch so vorstellen: (1,12), (2,6), (3,4).

Wenn wir also einen Teiler finden, können wir auch einen anderen Teiler finden, ohne zu n zu wechseln.

Der effiziente Weg besteht also darin, einfach bis zur Quadratwurzel der Zahl zu iterieren und dann die Teiler paarweise zu berechnen.

Die chinesische Übersetzung von

Beispiel

lautet:

Beispiel

Das Folgende ist ein C++-Programm zur Berechnung des Teilers einer Zahl

#include <bits/stdc++.h>
using namespace std;
// Function to count the divisors of a number
int countDivisors(int n){
   int count = 0;
	for (int i=1; i<=sqrt(n); i++){
		if (n%i == 0){
			// If divisors are equal, count only one
			if (n/i == i)
				count++;
			else // Otherwise count both
				count += 2;
		}
	}
	return count;
}

int main(){
   int n = 55;
   int ans = countDivisors(n);
   cout <<"The number of divisors of 55 is: "<<ans<<endl;
   return 0;
}

Ausgabe

The number of divisors of 55 is: 4

Jetzt können wir den zweiten und dritten Schritt der oben besprochenen Methode befolgen.

Beispiel für ein C++-Programm zum Drucken sortierter Vektoren basierend auf der Anzahl der Faktoren

#include <bits/stdc++.h>
using namespace std;
// Function to count the divisors of a number
int countDivisors(int n){
	int count = 0;
	for (int i=1; i<=sqrt(n); i++){
		if (n%i == 0){
			// If divisors are equal, count only one
			if (n/i == i)
				count++;
			else // Otherwise count both
				count += 2;
		}
	}
	return count;
}
int main(){
   int n = 5;
   vector<int>vec;
   //Inserting input
   vec.push_back(5);
   vec.push_back(14);
   vec.push_back(18);
   vec.push_back(9);
   vec.push_back(10);
   //Vector of pairs to store the number and its factor count
   vector<pair<int,int>>count_data(n);
   for(int i=0;i<n;i++){
      //Storing the data in the vector
      count_data[i] = {countDivisors(vec[i]), vec[i]};
   }
   //Sort the vector according to the number of factors
   sort(count_data.begin(),count_data.end());
   //Printing the result
   cout<<"The sorted vector based on the number of factors is: \n";
   for(int i=0;i<n;i++){
      cout<<count_data[i].second<<" ";
   }
   return 0;
}

Ausgabe

The sorted vector based on the number of factors is: 
5 9 10 14 18 

Fazit

In diesem Beitrag haben wir einen Vektor basierend auf der Anzahl der Faktoren ganzer Zahlen sortiert.

Wir haben einige Beispiele besprochen und dann über Methoden gesprochen.

Der Kern dieses Problems besteht darin, die Anzahl der Teiler einer Zahl zu ermitteln. Es gibt zwei Möglichkeiten, dieses Problem zu lösen: die Brute-Force-Methode und die effiziente Methode. Wir haben uns beide Ansätze angesehen und dann den effizienten Ansatz verwendet, um das endgültige Programm zu schreiben.

Das obige ist der detaillierte Inhalt vonMit STL nach Anzahl der Faktoren sortieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!