Muszę wymyślić algorytm, który wykonuje:

Powiedzmy, że masz tablicę dodatnich liczb (np. {X0}}) i wiesz wcześniej swoją sumę wynosi 20.

Chcesz abstrakcję pewnej średniej ilości od każdej liczby, tak że nowa suma byłaby mniej o 7.

Aby to zrobić, musisz śledzić te reguły :

  • Możesz odjąć tylko liczby całkowite
  • Uzyskana tablica nie może mieć żadnych wartości ujemnych
  • Nie możesz wprowadzić żadnych zmian w indeksy wiader.

Im bardziej równomiernie odejmowanie jest dystrybuowane nad tablicą, tym lepiej.

Oto moja próba algorytmu w JavaScript + podkreślenia (co prawdopodobnie sprawi, że n ^ 2):

function distributeSubtraction(array, goal){
    var sum = _.reduce(arr, function(x, y) { return x + y; }, 0);
    if(goal < sum){
      while(goal < sum && goal > 0){
         var less = ~~(goal / _.filter(arr, _.identity).length); //length of array without 0s
         arr = _.map(arr, function(val){ 
            if(less > 0){
                return (less < val) ? val - less : val; //not ideal, im skipping some! 
            } else {
                if(goal > 0){ //again not ideal. giving preference to start of array
                    if(val > 0) {
                        goal--;
                        return val - 1;
                    }
                } else {
                    return val;
                }
            }
         });
         if(goal > 0){
             var newSum = _.reduce(arr, function(x, y) { return x + y; }, 0);
             goal -= sum - newSum;
             sum = newSum;
         } else {
            return arr;
         }
      }
    } else if(goal == sum) {
      return _.map(arr, function(){ return 0; });
    } else {
      return arr;
    }
}
var goal = 7;
var arr = [1,3,7,0,0,9];
var newArray = distributeSubtraction(arr, goal);
//returned: [0, 1, 5, 0, 0, 7];

Cóż, to działa, ale musi być lepszy sposób! Wyobrażam sobie czas pracy tej rzeczy będzie straszny z większych tablic i większych numerów.

Edytuj : Chcę wyjaśnić, że to pytanie jest czysto akademickie. Pomyśl o tym jak pytanie wywiadu, w którym coś whiteboard, a ankieter pyta, jak twój algorytm zachowywałby się na innym typie zbioru danych.

1
mkoryak 22 wrzesień 2012, 05:27

2 odpowiedzi

Najlepsza odpowiedź

Brzmi to tak, jak chcesz odejść ważoną ilość z każdej liczby. To chcesz odjąć X/sum * amount_to_subtract z każdego elementu. Oczywiście, że będziesz musiał okrążyć kwotę odejmowania. Problemem jest, aby upewnić się, że odjęto całkowitą prawidłową kwotę. Ponadto zależy to również na twoim wejściu: Czy gwarantujesz, że kwota, którą chcesz odjąć może być odjęte Oto szorstki implementacja Pythona (myślę):

def uniform_array_reduction(inp, amount):
  total = sum(inp)
  if amount > total:
    raise RuntimeError('Can\'t remove more than there is')

  if amount == total: #special case
    return [0] * len(inp)

  removed = 0
  output = []
  for i in inp:
    if removed < amount:
      to_remove = int(round(float(i)/float(total)*float(amount)))
      output.append(i - to_remove)
      removed += to_remove
    else:
      output.append(i)
  # if we didn't remove enough, just remove 1 from
  # each element until we've hit our mark.
  # shouldn't require more than one pass
  while removed < amount:
    for i in range(len(output)):
      if output[i] > 0:
        output[i] -= 1
        removed += 1
        if removed == amount:
          break
  return output

Edytuj: Naprawiłem kilka błędów w kodzie.

1
dave mankoff 22 wrzesień 2012, 01:47
s = Sum(x) - required_sum
do:
    a = ceil( s/number_of_non_zeros(x) )
    For i=1 to length(x):
        v = min(a, x[i], s)
        x[i]-=v
        s-=v
while s>0

Ta wersja nie wymaga sortowania.

1
ElKamina 25 wrzesień 2012, 13:50