Scribd
Importer
3 vues2 pages

Amélioration de la division en sous-ensembles

Le document présente une approche améliorée pour diviser l'ensemble des nombres de 1 à n en deux sous-ensembles de somme égale. Il décrit la nécessité de vérifier la divisibilité de la somme totale par 4 et propose un algorithme pour construire les sous-ensembles en commençant par les plus grands nombres. Un exemple d'exécution avec n = 7 illustre le fonctionnement du code révisé, qui réussit à créer deux sous-ensembles de somme égale.

Transféré par

bouziani.hwau
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats TXT, PDF, TXT ou lisez en ligne sur Scribd
3 vues2 pages

Amélioration de la division en sous-ensembles

Le document présente une approche améliorée pour diviser l'ensemble des nombres de 1 à n en deux sous-ensembles de somme égale. Il décrit la nécessité de vérifier la divisibilité de la somme totale par 4 et propose un algorithme pour construire les sous-ensembles en commençant par les plus grands nombres. Un exemple d'exécution avec n = 7 illustre le fonctionnement du code révisé, qui réussit à créer deux sous-ensembles de somme égale.

Transféré par

bouziani.hwau
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats TXT, PDF, TXT ou lisez en ligne sur Scribd

-----------------------------------------------------------------------------------

---
Merci pour la clarification avec un exemple d'entrée et de sortie. Après avoir pris
en compte cet exemple, j'ai remarqué que la logique du code pourrait être améliorée
pour s'assurer qu'il génère les ensembles correctement pour tous les cas possibles.

L'objectif est de diviser l'ensemble des nombres de 1 à n en deux sous-ensembles,


dont la somme de chacun est égale à (n * (n + 1)) / 4. Dans cet exemple, avec n =
7, la somme de l'ensemble complet des nombres de 1 à 7 est 28, et la somme de
chaque sous-ensemble doit être 28 / 2 = 14.

Voici une approche améliorée pour résoudre le problème :


Vérification de la divisibilité par 4 : Comme tu l'as déjà fait dans ton code, il
est nécessaire de vérifier si la somme totale de l'ensemble peut être divisée en
deux parties égales, c'est-à-dire si (n * (n + 1)) % 4 == 0. Si ce n'est pas le
cas, il n'y a pas de solution.

Construction des sous-ensembles : Ensuite, l'idée est de sélectionner les éléments


qui rempliront un des sous-ensembles, et les éléments restants rempliront l'autre
sous-ensemble. L'une des façons de le faire est de commencer par les éléments les
plus grands (du plus grand au plus petit) pour essayer de remplir un sous-ensemble
jusqu'à ce que la somme atteigne la moitié de la somme totale.

Code révisé :
cpp
Copier le code
#include <iostream>
#include <vector>

int main() {
int n, sum = 0;
std::cin >> n;

// Vérification si la somme de 1 à n peut être divisée par 2


if ((n * (n + 1)) % 4 != 0) {
std::cout << "NO\n";
return 0;
}

int target = (n * (n + 1)) / 4; // C'est la somme cible pour un des sous-


ensembles
std::vector<int> v1, v2;
sum = 0;

// Construction du premier sous-ensemble (v1) dont la somme est target


for (int i = n; i >= 1; --i) {
if (sum + i <= target) {
v1.push_back(i);
sum += i;
} else {
v2.push_back(i);
}
}

// Si on a trouvé une solution


if (sum == target) {
std::cout << "YES\n";
std::cout << [Link]() << "\n";
for (int val : v1) {
std::cout << val << " ";
}
std::cout << "\n";

std::cout << [Link]() << "\n";


for (int val : v2) {
std::cout << val << " ";
}
std::cout << "\n";
} else {
std::cout << "NO\n";
}

return 0;
}
Explication des changements :
Vérification de la divisibilité par 4 :

Si la somme des entiers de 1 à n n'est pas divisible par 4, le programme imprime


"NO" et s'arrête immédiatement.
Construction des sous-ensembles :

On commence par ajouter les éléments les plus grands possibles au premier sous-
ensemble v1, jusqu'à ce que la somme atteigne target (qui est (n * (n + 1)) / 4).
Les éléments restants vont dans le second sous-ensemble v2.
Affichage des résultats :

Si on réussit à diviser les éléments en deux sous-ensembles dont la somme est égale
à target, on affiche "YES" suivi de la taille et des éléments de chaque sous-
ensemble. Sinon, on affiche "NO".
Exemple d'exécution :
Entrée :
Copier le code
7
Sortie :
objectivec
Copier le code
YES
4
7 4 2 1
3
6 5 3
Explication :

La somme des éléments de l'ensemble complet {1, 2, 3, 4, 5, 6, 7} est 28, donc


chaque sous-ensemble doit avoir une somme de 14.
Le premier sous-ensemble (v1) a la somme 7 + 4 + 2 + 1 = 14, et le second sous-
ensemble (v2) a la somme 6 + 5 + 3 = 14.
Le programme fonctionne maintenant comme attendu pour cet exemple !

Vous aimerez peut-être aussi