![Imprimez toutes les sous-séquences en diminuant d’abord puis en augmentant en sélectionnant N/2 éléments de [1, N]](https://geektechnique.net/wp-content/uploads/2021/09/Imprimez-toutes-les-sous-sequences-en-diminuant-dabord-puis-en-augmentant.png)
Étant donné un graphe complet ayant N nœuds et N*(N-1)/2 arêtes et un entier positif K, la tâche consiste à trouver le nombre de façons si vous commencez au nœud 1 et se terminent au même nœud si exactement K les bords doivent être traversés.
Saisir: N = 4, K = 3
Sortir: 6
Explication: Les voies possibles sont-
1→2→3→1
1→2→4→1
1→3→2→1
1→3→4→1
1→4→2→1
1→4→3→1
Saisir: N = 5, K = 3
Sortir: 12
Approche naïve : L’approche la plus simple pour résoudre ce problème consiste à traverser à partir de chaque arête à partir du sommet actuel, la solution sera un temps exponentiel.
Complexité temporelle : O(N^N)
Espace auxiliaire : O(N), en raison de l’espace de pile dans les fonction récursive appel.
Approche efficace : Ce problème a la propriété Overlapping Subproblems et la propriété Optimal Substructure. Ce problème peut donc être résolu en utilisant la programmation dynamique. Comme d’autres problèmes typiques de programmation dynamique (DP), le recalcul des mêmes sous-problèmes peut être évité en construisant un tableau temporaire qui stocke les résultats des sous-problèmes. Suivez les étapes ci-dessous pour résoudre le problème :
- Initialiser un dp[] tableau où dp[i] pour stocker le nombre de façons d’atteindre à avec nœud et initialiser dp[0] comme 1.
- Itérer dans la plage [1, K] en utilisant la variable je et effectuez les étapes suivantes :
- Initialiser une variable nombre de voies comme 0 à stocker le nombre de façons d’atteindre tous les nœuds.
- Itérer dans la plage [0, N-1] en utilisant la variable j, puis ajouter dp[j] dans numWays.
- Itérer dans la plage [0, N-1] en utilisant la variable j, puis mettre à jour la valeur de dp[j] au maximum de dp[j] et numWays – dp[j].
- Après avoir effectué les étapes ci-dessus, imprimez dp[0] comme réponse.
Vous trouverez ci-dessous la mise en œuvre de l’approche ci-dessus :
C++
|
#include en utilisant l’espace de noms std ; void numberOfWays(int n, int k) { dp int[1000]; pour (int i = 0; i < n; i++) { dp[i] = 0 ; } dp[0] = 1 ; pour (int i = 1; i <= k; i++) { int numVoies = 0; pour (int j = 0; j < n; j++) { numVoies += dp[j]; } pour (int j = 0; j < n; j++) { dp[j] = numVoies – dp[j]; } } cout << dp[0] << finl; } int main() { entier N = 5, K = 3; nombreDeVoies(N, K); renvoie 0 ; } |
Java
|
classe GFG{ static void numberOfWays(int n, int k) { entier[] dp = nouvel int[1000]; for(int i = 0; i < n; i++) { dp[i] = 0 ; } dp[0] = 1 ; for(int i = 1; i <= k; i++) { int numVoies = 0; for(int j = 0; j < n; j++) { numVoies += dp[j]; } for(int j = 0; j < n; j++) { dp[j] = numVoies – dp[j]; } } System.out.println(dp[0] + « n »); } public static void main(String args[]) { entier N = 5, K = 3; nombreDeVoies(N, K); } } |
Python3
|
def numberOfWays(n, k): dp = [0 for i in range(1000)] dp[0] = 1 pour i dans la plage (1, k + 1, 1) : numVoies = 0 pour j dans la plage (n): numVoies += dp[j] pour j dans la plage (n): dp[j] = numVoies – dp[j] imprimer (dp[0]) if __name__ == ‘__main__’ : N = 5 K = 3 nombre de voies (N, K) |
C#
|
en utilisant le système ; classe GFG{ static void numberOfWays(int n, int k) { entier[] dp = nouvel int[1000]; for(int i = 0; i < n; i++) { dp[i] = 0 ; } dp[0] = 1 ; for(int i = 1; i <= k; i++) { int numVoies = 0; for(int j = 0; j < n; j++) { numVoies += dp[j]; } for(int j = 0; j < n; j++) { dp[j] = numVoies – dp[j]; } } Console.Ecrire(dp[0]); } vide public statique Main () { entier N = 5, K = 3; nombreDeVoies(N, K); } } |
Javascript
Complexité temporelle : O(N×K)
Espace auxiliaire : AU)
Attention lecteur ! N’arrêtez pas d’apprendre maintenant. Obtenez tous les concepts importants de DSA avec le Cours auto-rythmé DSA à un prix adapté aux étudiants et devenez prêt pour l’industrie. Pour compléter votre préparation de l’apprentissage d’une langue à DS Algo et bien d’autres, veuillez vous référer Cours complet de préparation aux entretiens.
Au cas où vous souhaiteriez assister cours en direct avec des experts, veuillez vous référer Cours en direct DSA pour les professionnels en activité et Programmation compétitive en direct pour les étudiants.
![Imprimez toutes les sous-séquences en diminuant d’abord puis en augmentant en sélectionnant N/2 éléments de [1, N]](https://geektechnique.net/wp-content/uploads/2021/09/Imprimez-toutes-les-sous-sequences-en-diminuant-dabord-puis-en-augmentant-75x75.png)
