Isih mengikut bilangan faktor menggunakan STL

Mengisih vektor menggunakan STL adalah sekeping kek. Kita boleh menggunakan fungsi sort() yang terkenal untuk menyelesaikan tugas ini. Cabaran sebenar adalah mengira bilangan faktor untuk setiap nombor.

Faktor ialah nombor yang membahagikan nombor lain sepenuhnya, iaitu dengan baki sifar.

Memutar semua nombor untuk mengira faktor mungkin satu cara untuk pergi, tetapi kami akan cuba mengoptimumkan dan mencapai penyelesaian yang cekap dalam artikel ini.

Pernyataan Masalah

Isih tatasusunan yang diberikan dalam tertib menaik berdasarkan bilangan faktor setiap nombor. Oleh itu, nombor dengan bilangan faktor terkecil hendaklah pada permulaan dan nombor dengan bilangan faktor terbanyak hendaklah pada akhir. Nombor dengan bilangan faktor yang sama hendaklah disusun mengikut susunan tatasusunan asal. Tatasusunan boleh diisih menggunakan STL.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

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.

Jadi, selepas menyusun nombor dalam tertib menaik mengikut faktornya, kita mendapat output: 3 2 4 10 15 20.

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

Penjelasan

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.

Jadi, selepas menyusun nombor dalam tertib menaik mengikut faktornya, kita mendapat output: 19 5 9 21 12

Kaedah

• Cari bilangan faktor bagi setiap nombor.

• Buat vektor yang menyimpan pasangan nombor dan kiraan faktornya.

• Isih vektor dan kembalikan hasilnya.

Cari bilangan faktor bagi suatu nombor

Terjemahan bahasa Cina bagi

Brute Force

ialah:

Brute Force

Pendekatan naif adalah dengan mengulangi semua nombor dari 1 hingga n dan mengetahui sama ada ia membahagi n. Dengan cara ini, kita boleh mengira bilangan faktor bagi setiap nombor.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Berikut ialah program C++ yang menggunakan kekerasan untuk mengira semua pembahagi nombor

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

Output

The number of divisors of 55 is: 4

Kaedah yang cekap

Faktor nombor wujud secara berpasangan.

Sebagai contoh, pembahagi 12 ialah 1, 2, 3, 4, 6, 12.

Walau bagaimanapun, kita boleh menggambarkannya seperti ini: (1,12), (2,6), (3,4).

Jadi kalau jumpa pembahagi, kita juga boleh cari pembahagi lain tanpa melintasi ke n.

Jadi cara yang cekap ialah dengan hanya mengulang sehingga punca kuasa dua nombor dan kemudian mengira pembahagi secara berpasangan.

Terjemahan bahasa Cina bagi

Contoh

ialah:

Contoh

Berikut ialah program C++ untuk mengira pembahagi nombor

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

Output

The number of divisors of 55 is: 4

Kini, kita boleh ikut langkah kedua dan ketiga kaedah yang dibincangkan di atas.

Contoh program C++ untuk mencetak vektor yang diisih berdasarkan beberapa faktor

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

Output

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

Kesimpulan

Dalam siaran ini, kami mengisih vektor berdasarkan bilangan faktor integer.

Kami membincangkan beberapa contoh dan kemudian bercakap tentang kaedah.

Inti masalah ini ialah mencari bilangan pembahagi sesuatu nombor. Terdapat dua cara untuk menyelesaikan masalah ini: kaedah kekerasan dan kaedah cekap. Kami melihat kedua-dua pendekatan dan kemudian menggunakan pendekatan yang cekap untuk menulis program akhir.

Atas ialah kandungan terperinci Isih mengikut bilangan faktor menggunakan STL. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!