this.Partition1 = 2851 * 3; // which is 8553 and closest possible to 10000 this.Partition2 = 2 * 5 * 13;
6 Réponses :
puis passer par chaque nombre de 10 000 à 2. Pour chacun de ces éléments, testez pour voir si la factorisation principale du nombre est un sous-ensemble de la liste donnée. Si c'est le cas, nous avons trouvé la réponse.
voici le pseudocode: p> partition1 code> est les facteurs primordiaux du nombre. partition2 code> est simplement primenumbers - partition1 code>. p> for n=10000 to 2
factors = prime_factorization(n)
if( factors is subset primeNumbers ) {
partition1 = factors
partition2 = primeNumbers - factors
return (partition1,partition2)
}
Je pense que votre réponse est vraie, mais vous devriez le modifier pour clarifier, si vous le faites, je vais supprimer ma réponse, sinon je modifierai ma réponse :) En fait, vous devriez clarifier ce que vous entendez par la factorisation principale. En fait, cela ne devrait pas être la factorisation commune.
Je ne suis pas sûr de ce que tu veux dire. Comment la factorisation est-elle non claire? C'est un concept de niveau scolaire.
Et si "le plus proche de 10k" permet de plus de 10 000, avec 10001 étant plus proche de 9998, la boucle peut être exécutée "pour i = 0 à 10000: chèque (10000-i); vérifier (10000 + i)". Et si vous n'avez toujours pas trouvé partition1 après cela, tous les nombres premiers de l'entrée sont supérieurs à 20000, la solution est donc de prendre le plus petit.
Je comprends que ça marche mais ne serait-il pas trop lent? Calculer Prime, facteurs de chaque numéro de 10000 à 2 ?! Y a-t-il un meilleur algorithme performant?
@William: Non, l'affacturage de petits nombres est facile. Vous pouvez le faire par division d'essai dans O (sqrt (n)) heure.
Par exemple, vous avez {2 2851} dans vos primes, un facteur prime commun donne 2 ^ 13 aussi le plus proche possible, mais je pense que cela ne l'est pas, il veut juste que la multiplication principale actuelle ne soit pas la plus proche facteur. La factorisation n'est donc pas une factorisation normale.
Une liste de 13 twos n'est pas un subliste de {2 2851}. Je ne veux pas dire "ensemble" dans le sens mathématique strict du mot.
Je suppose que c'est des devoirs. La réponse est 2 * 4999 (9998), par inspection.
La technique de la force brute est (devrait être) évidente. Prenez une liste de tous les nombres premiers x tels que 0 <= x <= 5000 (puisque vous recherchez des facteurs ici, vous allez multiplier des chiffres ... et comme le plus petit prime est 2, vous n'avez pas besoin de vous inquiéter à propos de quelque chose de plus grand que 5000). Pour chaque élément Xin, la liste, itérale sur la liste examinant à nouveau chaque Y de la liste. Multipliez-les ensemble et enregistrez le delta entre le produit et 10000. Gardez le plus petit.
Une autre façon de le faire serait de commencer avec 10000 et de calculer ses principaux facteurs (le cas échéant).
http://mathworld.wolfram.com/primefactorization.html < p> http://mathworld.wolfram.com/primefactorizationalgorithms.html
Par exemple:
Bonne réponse, mais je crois que la question concerne «certains», pas «tous», nombres premiers. I.e. La méthode sera fournie une liste de nombres premiers - calculer le produit le plus proche de 10000 étant donné cette liste.
Cela ressemble à une reformulation de Problème de Knapsack . Bien que le vôtre soit multiplicatif, calculer le logarithme des primes et le numéro cible le transforme en un problème d'additif.
Mais même si le problème de Knapack général est dur , votre sous-ensemble de problèmes peut avoir une solution rapide.
Etant donné que 2 ^ 14 = 16384 , vous pouvez avoir au plus 13 facteurs premiers, dont au plus 5 peut être distinct (car 2 * 3 * 5 * 7 * 11 * 13 = 30030> 10000 ). La solution la plus simple consiste à parcourir toutes les combinaisons. Si vous voulez que l'un des produits soit le plus proche de 10 000, vous traversez tout. Si vous ne voulez qu'un dans lequel le produit des deux partitions est inférieur à 10 000, vous pouvez vous arrêter dès que vous avez une solution. Même sans optimisation du tout, cela ne devrait prendre qu'une fraction d'une seconde sur les machines d'aujourd'hui.
Comment écririez-vous la logique pour cela?
Étant donné que nous pouvons avoir au plus 5 facteurs premiers distincts, j'utiliserais 5 boucles imbriquées qui comptent jusqu'au nombre des occurrences de chaque facteur. Vous pouvez sauter tôt si le produit actuel est trop grand. Si vous avez moins de 5 facteurs distincts, j'utiliserais un facteur 1 avec un nombre de 1 pour garder les choses simples.
Ma solution est inférieure à
internal static void GetPartitionsClosestTo9999(List<long> primeFactors, out long partition1, out long partition2)
{
for (var index = 9999; index >= 2; index--)
{
var primeFactorsForCurrentIndex = GetPrimeFactors(index);
var isSubset = IsSubSet(primeFactorsForCurrentIndex, primeFactors); //!primeFactorsForCurrentIndex.Except(primeFactors).Any();
if (isSubset)
{
partition1 = index;
foreach (var primeFactorForCurrentIndex in primeFactorsForCurrentIndex)
{
primeFactors.Remove(primeFactorForCurrentIndex);
}
partition2 = GetProduct(primeFactors);
return;
}
}
throw new ApplicationException("No subset found.");
}
static bool IsSubSet<T>(ICollection<T> set, IEnumerable<T> toCheck)
{
return set.Count == (toCheck.Intersect(set)).Count();
}
Nice question et je me demande simplement où vous allez utiliser cette logique?
Je vais l'utiliser pour cette Stackoverflow.com/questions/7985725/...
@mekici lors d'une entrevue, bien sûr. Pourquoi demander quelque chose de pratique lors d'une interview? Au lieu de cela, demandez à [quelque chose d'inutile] << a href = "http://stackoverflow.com/questions/7985725/how-a-convert-2-restrillée-decimal-variables-a-a-third-variable-and-vice -Versa "title =" Comment convertir 2 variables décimales restreintes à une troisième variable et vice versa "> Stackoverflow.com/questions/7985725/... > - alors vous pouvez décider de ne pas embaucher Jon Skeet parce qu'il vous dit qu'il n'y a pas de solution.
Leur produit devrait être inférieur à 10000?