Différentes manières de représenter N sous la forme de K entiers non nuls

La question « Différentes manières de représenter N par K des entiers non nuls » a des applications dans de nombreux cas d'utilisation réels.

Cryptographie - En cryptographie, des méthodes de cryptage spécifiques sont conçues en utilisant le concept d'encodage d'un nombre N comme somme de K entiers non nuls.

Représenter un entier N comme la somme de K entiers non nuls peut apparaître dans des sous-problèmes de différents problèmes d'optimisation de la méthode d'optimisation.

Machine Learning− Dans l'apprentissage automatique, des vecteurs de caractéristiques décrivant la distribution des points de données peuvent être créés en utilisant le problème de la représentation d'un entier N comme la somme de K entiers non nuls.

Explication

Explication

Décodeons maintenant le problème.

Supposons que nous ayons deux entiers positifs N et K, nous devons trouver K entiers non nuls dont la somme est égale à N. Par exemple, si N=10 et K=3, nous devons trouver trois entiers non nuls dont la somme est égale à 10. Les solutions possibles dans ce cas sont −

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

Notez que dans ces solutions, nous avons K=3 entiers non nuls, qui totalisent N=10.

Il existe différentes façons de résoudre ce problème, discutons de chacune d’elles.

Méthode récursive

Utilisez un algorithme étape par étape de la méthode récursive pour trouver différentes façons de représenter N avec K entiers non nuls.

• Entrez les valeurs de N et K dans la fonction principale.

• Créez la fonction f(N, K), qui renvoie le nombre total de façons dont N peut être exprimé sous forme de K entiers non nuls.

• Si K = 1, renvoie 1 lorsque N dépasse 0, sinon renvoie 0. (cas de base).

• Si N == 0 ou K > (Situation de base).

• Créez un nombre de variables pour stocker les résultats.

• Définissez la valeur du nombre de variables sur 0.

• De 1 à min(N-K+1, N-1) pour chaque entier I

• Calculez récursivement f (N-i, K-1).

• Ajoutez le résultat au décompte.

• Compte de retour.

Exemple

Implémentation de l'algorithme ci-dessus

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

Sortie

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

Complexité

Complexité temporelle : O(N ^ K).

Complexité spatiale : O(K)

Formule du coefficient binomial

La méthode de combinaison des étoiles et des rayures peut être utilisée pour obtenir une formule expliquant la manière dont un entier positif N peut être exprimé comme la somme de K entiers non nuls.

Imaginez une rangée de N étoiles (*), qui représentent N unités de partition d'un entier donné. Vous pouvez utiliser des barres verticales K-1 (|) pour disposer les étoiles en K segments, représentant K entiers non nuls de la partition.

Prenons comme exemple la division de 10 en 3 entiers non nuls. Les astérisques et tirets suivants peuvent être utilisés pour représenter ce processus −

* * |

• Soustrayez 1 de N pour obtenir N-1.

• Divisez N-1 en nombres entiers non négatifs K-1.

• Ajoutez 1 à tous les entiers non négatifs K-1 obtenus à l'étape 2 pour obtenir K entiers non nuls, et leur somme est 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

• Entrez les valeurs de N et K dans la fonction principale.

• Calculez le nombre de méthodes en utilisant la formule ci-dessus.

• Imprimez la valeur des voies variables.

#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

Copier après la connexion

Complexité

Complexité temporelle : O(K).

Complexité spatiale : O(1)

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!