Diberi suatu nombor, jumlah jumlahnya dan nombor asal adalah sama dengan susunan nombor lain yang diberikan.

Dalam artikel ini, kita akan menyelidiki soalan menarik yang melibatkan nombor dan pilih atur: "Permutasi di mana jumlah nombor dan nombor asal adalah sama dengan nombor lain yang diberikan". Masalah ini menggabungkan teori nombor dan kombinatorik secara unik, menjadikannya satu cabaran yang menarik.

Untuk menjelaskan, diberi nombor asal dan nombor sasaran, kita perlu mencari pilih atur nombor asal supaya apabila kita menambah nombor asal dan pilih aturnya, kita mendapat nombor sasaran.

Memahami masalah

Pada asasnya, soalan ini menggabungkan konsep pilih atur nombor, penjumlahan dan semakan kesamaan. Cabarannya ialah untuk mencari pilih atur yang betul (atau penyusunan semula nombor) yang memenuhi syarat yang disediakan.

Penjelasan algoritma

Algoritma untuk menyelesaikan masalah ini adalah seperti berikut −

• Kira kekerapan setiap nombor dalam nombor asal dan nombor sasaran.

• Bandingkan frekuensi. Jika ia sepadan, ini bermakna terdapat pilih atur yang sah. Jika ia tidak sepadan, tiada pilih atur yang sah.

Contoh

Berikut ialah penyelesaian C++ menggunakan algoritma di atas -

#include<bits/stdc++.h>
using namespace std;

bool isPermutation(int original, int target) {
   vector<int> countOriginal(10, 0), countTarget(10, 0);
   
   while (original > 0) {
      countOriginal[original % 10]++;
      original /= 10;
   }
   
   while (target > 0) {
      countTarget[target % 10]++;
      target /= 10;
   }
   
   for (int i = 0; i < 10; i++) {
      if (countOriginal[i] != countTarget[i]) {
         return false;
      }
   }
   
   return true;
}

int main() {
   int original = 1234;
   int target = 2468;
   
   if (isPermutation(original, target - original)) {
      cout << "Yes, there is a permutation of the original number that satisfies the condition." << endl;
   } else {
      cout << "No, there is no permutation of the original number that satisfies the condition." << endl;
   }
   
   return 0;
}

Output

Yes, there is a permutation of the original number that satisfies the condition.

Dalam fungsi isPermutation, kami mula-mula memulakan dua vektor countOriginal dan countTarget untuk mengira kekerapan nombor dalam nombor asal dan nombor sasaran masing-masing. Kami kemudian melelang melalui setiap nombor dalam nombor asal dan nombor sasaran dan menambah kiraan yang sepadan. Akhirnya, kami membandingkan kiraan. Jika ia sepadan, kami kembalikan benar jika tidak, kami kembali palsu.

Fungsi utama menetapkan nombor asal dan nombor sasaran dan menyemak sama ada terdapat pilih atur yang sah bagi nombor asal yang memenuhi syarat.

Contoh kes ujian

Mari kita tetapkan nombor asal sebagai 1234 dan nombor sasaran sebagai 2468. Perbezaan antara nombor sasaran dan nombor asal ialah 1234. Oleh itu, kita perlu menyemak sama ada terdapat pilihatur sama dengan 1234 itu sendiri. Jelas sekali, nombor asal ialah pilih atur sendiri, jadi outputnya ialah "Ya, terdapat pilih atur nombor asal yang memenuhi syarat."

Kerumitan masa dan ruang

Kerumitan masa bagi algoritma ini ialah O(n), dengan n ialah bilangan digit dalam nombor yang diberikan. Ini kerana kita akan melalui setiap digit dalam kedua-dua nombor asal dan nombor sasaran.

Kerumitan ruang ialah O(1) kerana saiz vektor countOriginal dan countTarget adalah malar (10) tanpa mengira saiz input.

Kesimpulan

Dalam artikel ini, kami meneroka masalah menarik yang menggabungkan konsep pilih atur, penambahan dan kesamaan berangka. Kami melaksanakan penyelesaian C++ yang mengeksploitasi kekerapan nombor dalam nombor asal dan nombor sasaran.

Masalah ini memberikan cabaran unik dan cara terbaik untuk anda mempraktikkan kemahiran menyelesaikan masalah anda, terutamanya dalam teori nombor dan kombinatorik.

Atas ialah kandungan terperinci Diberi suatu nombor, jumlah jumlahnya dan nombor asal adalah sama dengan susunan nombor lain yang diberikan.. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!