Aidez-moi s'il vous plaît avec la question ci-dessus. Un algorithme avec un exemple de travail sera apprécié. Aussi, s'il vous plaît gérer le cas lorsque ce qui précède n'est pas possible.
D'accord, ce que j'ai jusqu'à présent est ce qui suit:
Passez à travers l'ensemble de la matrice et obtenez la moyenne de toute une matrice. Au). Appelons ceci avg
Puis de cette moyenne peut obtenir la moyenne de l'ensemble de l'ensemble sauf Bien que quelqu'un me soit fourni une solution qui "fonctionne", je recherche la mise en œuvre la plus efficace. A [0] (la formule est: avg (A [1..n-1]) = (AVG (A [0..n-1]) * NA [0]) / (N-1) ). Ensuite, vous prenez cette nouvelle moyenne et comparez-la avec un [0]. S'ils ne sont pas égaux, vous passez à la valeur suivante, calculez les moyennes des moyennes de connaissances précédemment en utilisant la formule ci-dessus.
6 Réponses :
Une recherche rapide Google retournée Ce . Dans tous les cas, si vous ne recherchez pas de performance, Backtracking est toujours une option
ÉDITER: J'ai essayé d'appliquer en arrière. Ma solution n'est en aucun cas efficace. Bien entendu, vous pouvez remplacer les méthodes moyennes pour éviter un autre niveau de cyclisme. De plus, afin de montrer qu'il n'y a pas de solution, vous pouvez simplement compter le numéro des solutions. P>
import java.util.ArrayList;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
public class SOQuestion {
/**
* just prints a solution
*
* @param list
* @param indexes
*/
public static void printSolution(List list, HashSet indexes) {
Iterator iter = indexes.iterator();
while (iter.hasNext()) {
System.out.print(list.get((Integer) iter.next()) + " ");
}
System.out.println();
}
/**
* calculates the average of a list, but only taking into account the values
* of at the given indexes
*
* @param list
* @param indexes
* @return
*/
public static float avg(List list, HashSet indexes) {
Iterator iter = indexes.iterator();
float sum = 0;
while (iter.hasNext()) {
sum += (Integer) list.get((Integer) iter.next());
}
return sum / indexes.size();
}
/**
* calculates the average of a list, ignoring the values of at the given
* indexes
*
* @param list
* @param indexes
* @return
*/
public static float avg_e(List list, HashSet indexes) {
float sum = 0;
for (int i = 0; i < list.size(); i++) {
if (!indexes.contains(i)) {
sum += (Integer) list.get(i);
}
}
return sum / (list.size() - indexes.size());
}
public static void backtrack(List list, int start, HashSet indexes) {
for (int i = start; i < list.size(); i++) {
indexes.add(i);
if (avg(list, indexes) == avg_e(list, indexes)) {
System.out.println("Solution found!");
printSolution(list, indexes);
}
backtrack(list, i + 1, indexes);
indexes.remove(i);
}
}
public static void main(String[] args) {
List test = new ArrayList();
test.add(2);
test.add(1);
test.add(3);
backtrack(test, 0, new HashSet());
}
}
J'ai vérifié ces.Ils ne sont pas exacts. La plupart d'entre eux ne sont pas corrects
@Dstupid: Une bonne réponse doit être autonome et complète (si possible). Si vous avez juste un lien que vous avez googlé, faites-en un commentaire. Idem pour un seul rattrapage ( backtracking ). Pour en faire une réponse, expliquez comment résoudre le problème et poster ces liens comme des références.
@ Space_c0wb0y me donnant du temps pour développer la réponse aurait été belle. Mais merci pour la pointe, de toute façon. J'ai également pensé à donner des pointeurs rapides avant de donner la solution complète seraient utiles pour l'administrateur. Ma faute
Pouvez-vous me donner une solution efficace s'il vous plaît? Apprécie vraiment l'effort
@Programmer Je pense que je vous ai donné assez de pointeurs sur la manière d'améliorer la solution. Si vous cherchez quelqu'un pour faire votre travail pour vous, le bon endroit n'est pas le bon endroit.
Voici comment je l'ai fait:
1 - Total Array -> Si le numéro impair ne peut pas créer deux tableaux distincts. O (n)
2 - Diviser Total par 2.
3 - Array de tri (le plus élevé au plus bas) -> O (nlogn)
4 - Commencez avec le plus grand nombre et continuez à essayer d'obtenir le montant restant en allant au plus grand nombre. Si vous ne pouvez pas le faire, déplacez le numéro sur l'autre tableau. -> Je pense que le pire des cas est O (n ^ 2).
Permet de prendre cet exemple: 3, 19, 7, 4, 6, 40, 25, 8
Les deux liste sont donc [40,7,6,3] et [25,19,8,4]
Pourquoi ne pouvez-vous pas créer 2 tableaux si la matrice totale a une longueur étrange? Il n'est pas indiqué que les matrices résultantes doivent avoir la même longueur. Les moyennes doivent être identiques, et cela peut être fait pour [2,3,4,5,6] -> [2,4,6] + [3,5]
@RICHS Bonne explication avec l'exemple. Ce que vous avez fait est essentiellement montré comment résoudre le problème de la partition avec le recul. Ceci est (2 ^ N) dans le pire des cas cependant.
Essayez ce code ...
#include <QList>
#include <QDebug>
/****
We sort the array in the desending order. So the first two elemnts
are the biggest element of the array. These are put in split1 and the
split2 array. Note that we start from the biggest element the average
is going to be much higher than the final avarage. Next we start placing
the smaller elemnts from source to split1 or split2. To do this we make a
simple dicision. We look at the value to be added and then see if that will
increase/decrease the average of a given split. Accordingly we make our
decesion.
****/
static bool averageSplit(const QList<int>& source,
QList<int>& split1,
QList<int>& split2)
{
if (source.size() < 2) {
return false;
}
QList<int> list = source;
qSort(list.begin(), list.end(), qGreater<int>());
double sum = 0;
foreach(int elm, list) {
sum += elm;
}
const double totalAvg = sum / list.size();
double sum1 = list[0];
double sum2 = list[1];
split1.append(list[0]);
split2.append(list[1]);
for(int i = list.size() - 1; i >= 2; --i) {
double avg1 = sum1 / split1.size();
double avg2 = sum2 / split2.size();
int val = list[i];
if (avg1 < avg2) {
// Try to increase tha avg1 or decrease avg2.
if (val > split1.size()) {
split1.append(val);
sum1 += val;
}
else {
split2.append(val);
sum2 += val;
}
}
else {
// Try to increase tha avg2 or decrease avg1.
if (val > split2.size()) {
split2.append(val);
sum2 += val;
}
else {
split1.append(val);
sum1 += val;
}
}
}
qDebug() << "totalAvg " << totalAvg;
qDebug() << "Avg1 " << sum1 / split1.size();
qDebug() << "Avg2 " << sum2 / split2.size();
}
void testAverageSplit()
{
QList<int> list;
list << 100 << 20 << 13 << 12 << 12 << 10 << 9 << 8 << 6 << 3 << 2 << 0;
list << -1 << -1 << -4 << -100;
QList<int> split1;
QList<int> split2;
averageSplit(list, split1, split2);
qDebug() << "split1" << split1;
qDebug() << "split2" << split2;
}
Je pense que si la somme de tous les éléments de la matrice d'origine est étrange, la division en 2 tableaux n'est pas possible. Comment si SUM == Même, vous pouvez commencer à faire votre matrice de telle sorte d'éléments dans chaque == SUM / 2
#include<stdio.h>
void partitionEqualAvt(int *a, int n)
{
int i;
int sum=0, sSum=0, eSum, sAvg, eAvg;
for(i=0; i<n; i++)
sum+=a[i];
eSum=sum;
for(i=0; i<n-1; i++)
{
sAvg=0;
eAvg=0;
sSum+=a[i];
eSum=sum-sSum;
sAvg=sSum/(i+1);
eAvg=eSum/(n-i-1);
if(sAvg == eAvg)
{
printf("\nAverage = %d from [%d to %d] and [%d to %d]", sAvg, 0, i, i+1, n);
}
}
}
int main()
{
int a[]={1,1,1,1,1,1};
int n=sizeof(a)/sizeof(int);
partitionEqualAvt(a,n);
return 0;
}
Nous pouvons l'ajuster pour inclure des moyennes de flotteur.
Utilisation d'un algorithme gourmand Une approche du problème, imitant la façon dont les enfants choisissent des équipes pour une partie, est l'algorithme gourmand, qui itère à travers les chiffres de l'ordre décroissant, en attribuant à chacun d'eux au sous-ensemble ayant la somme inférieure. Cela fonctionne bien lorsque les chiffres de l'ensemble ont à peu près la même taille que sa cardinalité ou moins.
essayez ceci en python:
Si la moyenne existe alors, cette
S'il vous plaît poster le code que vous avez écrit jusqu'à présent. Les gens n'aiment généralement pas simplement écrire votre code pour vous. Comme c'est le cas, ceci est une description de travail, pas une question.
@Mitch: Je vous ai donné ma réponse. Pouvez-vous donner votre message maintenant?
La solution que vous proposez est
O (n) globalement, et je ne pense pas que cela puisse être apporté plus efficace que cela, simplement parce que vous devrez examiner chaque élément de la matrice une fois.N'est-ce pas un problème de partition? Un numéro de la liste d'origine peut être dans la liste1 ou non (dans ce cas c'est dans la liste2)
Devez-vous séparer le tableau en gauche / droit ou pouvez-vous réorganiser librement les éléments? Par exemple, si votre matrice est [1; 1; 2; 2], est [1; 2], [1; 2] valide ou est-il considéré comme irréalisable?