Bonjour à tous.
J'ai un exercice contenant 5 questions mais je n'arrive pas à comprendre 2 de leurs.
Voici le problème et les 2 questions auxquelles je cherche la solution :
On considère le problème suivant qu’on appellera 3SumSet :
Input : A, B et C des ensembles d’entiers (positifs ou n´egatif )
Question : Existe-t-il trois valeurs a ∈ A, b ∈ B et c ∈ C telles que a + b = c.
La taille d’une instance est la somme des cardinalités des trois ensembles de départ.
1. Donnez une instance de taille 9 du problème 3SumSet qui a une solution puis une instance de taille 5 qui n’a pas de solution.
2. Montrer que pour toute instance I de ce problème , il existe une instance I' de même taille ne contenant que des entiers positifs telle que I a une solution si et seulement si I' a une solution.
Si quelqu'un a une solution à me proposer j'en suis preneur.
Merci d'avance!!!
Partager