
On nous donne un nombre N et un tableau de M chiffres. Notre travail consiste à trouver n nombres
Un nombre divisible par 5 composé des M chiffres donnés.
Voyons quelques exemples pour comprendre l'entrée et la sortie du problème.
In -
1 2 3 | N = 2
M = 3
arr = {5, 6, 3}
|
Copier après la connexion
Out -
Copier après la connexion
Copier après la connexion
Il y a 2 N nombres 35 et 65 qui peuvent être divisibles également par 5. Regardons un autre exemple.
Entrée -
1 2 3 | N = 1
M = 7
arr = {2, 3, 4, 5, 6, 7, 8}
|
Copier après la connexion
Sortie -
Copier après la connexion
Seul 1 nombre à 1 chiffre dans le tableau donné est divisible par 5. Par conséquent, notre tâche est de trouver le nombre de nombres divisibles par 5 donnés N nombres. < /p>
Les nombres doivent se terminer par le chiffre 0 ou 5 pour être divisible par 5. Voyons l'algorithme
Algorithme
- vérifie 0 et 5 dans le tableau donné. 2. S’il y a à la fois 0 et 5, il existe deux façons de mettre le nombre à la place des uns. Sinon, il y aurait un moyen de placer les chiffres.
- Initialisez le compte à 2.
- Maintenant, les postes restants peuvent avoir m - 1, m - 2, m - 3, ... n façons de les pourvoir respectivement.
- Écrivez une boucle qui itère de 0 à n - 1.
- Réduisez le tableau.
- Multipliez-le avec le nombre.
- Si vous avez un seul chiffre 0 ou 5, il n'y a qu'une seule façon de mettre le numéro à la place des uns.
- Initialisez le compte à 2.
- Maintenant, les postes restants peuvent avoir m - 1, m - 2, m - 3, ... n façons de les pourvoir respectivement.
- Écrivez une boucle qui itère de 0 à n - 1.
- Réduisez le tableau.
- Multipliez-le avec le nombre.
- S'il n'y a pas de nombre 0 ou 5, alors nous pouvons former un nombre divisible par 5. Renvoie -1 à ce moment.
Implémentation
Ce qui suit est l'implémentation C++ de l'algorithme ci-dessus
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | # include <bits/stdc++.h>
using namespace std;
int numbers(int n, int m, int arr[]) {
bool isZeroPresent = false, isFivePresent = false;
int numbersCount = 0;
if (m < n) {
return -1;
}
for (int i = 0; i < m; i++) {
if (arr[i] == 0) {
isZeroPresent = true;
}
if (arr[i] == 5) {
isFivePresent = true;
}
}
if (isZeroPresent && isFivePresent) {
numbersCount = 2;
for (int i = 0; i < n - 1; i++) {
m--;
numbersCount = numbersCount * m;
}
} else if (isZeroPresent || isFivePresent) {
numbersCount = 1;
for (int i = 0; i < n - 1; i++) {
m--;
numbersCount = numbersCount * m;
}
} else {
return -1;
}
return numbersCount;
}
int main() {
int arr[] = {5, 6, 3};
cout << numbers(2, 3, arr) << endl;
return 0;
}
|
Copier après la connexion
Sortie
Si vous exécutez le code ci-dessus, vous obtiendrez les résultats suivants.
Copier après la connexion
Copier après la connexion
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!