Cara yang berbeza untuk mewakili N sebagai K bukan sifar integer

Soalan "Cara berbeza untuk mewakili N sebagai K bukan sifar integer" mempunyai aplikasi dalam banyak kes penggunaan dunia sebenar.

Cryptography - Dalam kriptografi, kaedah penyulitan khusus direka bentuk menggunakan konsep pengekodan nombor N sebagai hasil tambah K bukan sifar integer.

Mewakili integer N sebagai jumlah K bukan sifar integer mungkin muncul dalam submasalah masalah pengoptimuman yang berbeza bagi kaedah pengoptimuman.

Pembelajaran Mesin− Dalam pembelajaran mesin, vektor ciri yang menerangkan pengagihan titik data boleh dibuat dengan menggunakan masalah mewakili integer N sebagai hasil tambah K bukan sifar integer.

Penjelasan

Penjelasan

Sekarang mari kita menyahkod masalah.

Andaikan kita mempunyai dua integer positif N dan K, kita perlu mencari integer bukan sifar K yang jumlahnya sama dengan N. Sebagai contoh, jika N=10 dan K=3, kita perlu mencari tiga integer bukan sifar yang jumlahnya sama dengan 10. Penyelesaian yang mungkin dalam kes ini ialah −

1 + 4 + 5
2 + 3 + 5
2 + 4 + 4

Perhatikan bahawa dalam penyelesaian ini kita mempunyai K=3 integer bukan sifar, yang menambah sehingga N=10.

Terdapat pelbagai cara untuk menyelesaikan masalah ini, mari kita bincangkan setiap satu.

Kaedah rekursif

Gunakan algoritma langkah demi langkah kaedah rekursif untuk mencari cara berbeza mewakili N dengan K bukan sifar integer.

• Masukkan nilai N dan K dalam fungsi utama.

• Buat fungsi f(N, K), yang mengembalikan jumlah bilangan cara N boleh dinyatakan sebagai K bukan sifar integer.

• Jika K = 1, kembalikan 1 apabila N melebihi 0, jika tidak kembalikan 0. (kes asas).

• Jika N == 0 atau K > (Keadaan asas).

• Buat kiraan pembolehubah untuk menyimpan keputusan.

• Tetapkan nilai kiraan pembolehubah kepada 0.

• Dari 1 hingga min(N-K+1, N-1) untuk setiap integer I

• Kira secara rekursif f (N-i, K-1).

• Tambahkan hasil pada kiraan.

• Kiraan pulangan.

Contoh

Pelaksanaan algoritma di atas

#include <iostream>
using namespace std;

int f(int N, int K) {
   if (K == 1) {
      return (N > 0) ? 1 : 0; // base case
   }
   if (N <= 0 || K > N) {
      return 0; // base case
   }
   int count = 0;
   for (int i = 1; i <= min(N-K+1, N-1); i++) {
      count += f(N-i, K-1);
   }
   return count;
}

int main() {
   int N = 5, K = 2;
   
   int ways = f(N, K);
   cout << "Number of ways to represent " << N << " as the sum of " << K << " non-zero integers: " << ways << endl;
   return 0;
}

Output

Number of ways to represent 5 as the sum of 2 non-zero integers: 4

Kerumitan

Kerumitan masa: O(N ^ K).

Kerumitan ruang: O(K)

Formula pekali binomial

Kaedah gabungan bintang dan jalur boleh digunakan untuk mendapatkan formula bagi cara integer positif N boleh dinyatakan sebagai hasil tambah K bukan sifar integer.

Bayangkan satu baris N bintang (*), yang mewakili N unit partition bagi integer tertentu. Anda boleh menggunakan bar menegak K-1 (|) untuk menyusun bintang ke dalam segmen K, mewakili integer bukan sifar K bagi partition.

Ambil pembahagian 10 kepada 3 integer bukan sifar sebagai contoh. Asterisk dan sengkang berikut boleh digunakan untuk mewakili proses ini −

* * |. * * * |

• Tolak 1 daripada N untuk mendapatkan N-1.

• Bahagikan N-1 kepada integer bukan negatif K-1.

• Tambah 1 kepada semua integer bukan negatif K-1 yang diperoleh dalam langkah 2 untuk mendapatkan integer bukan sifar K, dan jumlahnya ialah N.

• 1 + 1 + 1 + 3

• 1 + 1 + 2 + 2

• 1 + 1 + 3 + 1

• 1 + 2 + 1 + 2

• 1 + 2 + 2 + 1

• 1 + 3 + 1 + 1

• 2 + 1 + 1 + 2

• 2 + 1 + 2 + 1

• 2 + 2 + 1 + 1

• 3 + 1 + 1 + 1

• Masukkan nilai N dan K dalam fungsi utama.

• Kira bilangan kaedah menggunakan formula di atas.

• Cetak nilai cara berubah-ubah.

#include <iostream>
using namespace std;

int binomial(int n, int k) {
   int res = 1;
   if (k > n - k) {
      k = n - k;
   }
   for (int i = 0; i < k; ++i) {
      res *= (n - i);
      res /= (i + 1);
   }
   return res;
}

int main() {
   int N = 7, K = 2;
   
   int ways = binomial(N - 1, K - 1);
   cout << "Number of ways to represent " << N << " as the sum of " << K << " non-zero integers: " << ways << endl;
   return 0;
}

Number of ways to represent 7 as the sum of 2 non-zero integers: 6

Salin selepas log masuk

Kerumitan

Kerumitan masa: O( K).

Kerumitan ruang: O(1)

Atas ialah kandungan terperinci Cara yang berbeza untuk mewakili N sebagai K bukan sifar integer. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!