Autor Wątek: Wypełnianie tablicy liczbami o określonej sumie  (Przeczytany 2546 razy)

Offline LizarD

  • Użytkownik

# Kwiecień 23, 2014, 16:17:30
Witam!

Poszukuję jakiegoś algorytmu który załatwi taką sprawę, mam tablicę n elementową oraz pewną liczbę x, suma liczb w tablicy musi wynosić x, więc na chłopski rozum wystarczy podzielić x przez n oraz tą wartość powpisywać do każdego elementu tablicy, tylko jak zrobić żeby te liczby w tablicy nie były sobie równe ale zawsze ich suma wynosiła x, liczby mogą się powtarzać ale nie muszą. Można to zrobić tak:
int x = 100;
int n = 5;
int d = x/n;

for(int i = 0; i < n - 1; i++)
{
       int m = random(); // losowanie jakiejś liczby z przedziału np 0 - 5
       tablica[i] = d + m;
       tablica[i++] = d - m;
}
Tylko ten kod zawsze będzie generował liczbę w tablicy n+1 mniejszą niż element n, a jak temu zapobiec i mieć różnorodność ?

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline Xirdus

  • Redaktor

  • +1
# Kwiecień 23, 2014, 16:23:41
n = 5;
x = 100;
tab[n];
każdy element tab = x;
s = x * n;
while(s>x)
{
tab[rand()%n] -= 1;
s -= 1;
}

Offline ShadowDancer

  • Redaktor

  • +3
# Kwiecień 23, 2014, 19:22:49
Wpisz x do pierwszej komórki, a do reszty 0;


tab[0] = x;
for(int i = 1; i < tab_size; ++i)
{
   tab[i] = 0;
}

Offline Satirev

  • Użytkownik

# Kwiecień 23, 2014, 19:27:04
Można jeszcze tak:
Kod: (cpp) [Zaznacz]
std::random_device rd;
std::mt19937 gen(rd());

const int sum = 100;
const int n = 5;
int current_sum = 0;
int max_num = sum;
int min_num = 0;

std::array<int, n> nums;
for (int i = 0; i < n; ++i)
{
    max_num = std::min(max_num, sum - current_sum);
    min_num = std::min(max_num, std::max(min_num, sum - max_num * (n - i)));
    std::uniform_int_distribution<> dist(min_num, max_num);
    int num = dist(gen);
    nums[i] = num;
    current_sum += num;
}

std::shuffle(std::begin(nums), std::end(nums), gen);
std::copy(std::begin(nums), std::end(nums), std::ostream_iterator<int>(std::cout, " "));


Offline jorul

  • Użytkownik

# Kwiecień 23, 2014, 22:37:50
var oczekiwanaSuma = 15;
var skumulowanaSuma = 0;
var liczbaElementów = 20;

var tablica = [];

for ( var i = 0; i < liczbaElementów; i++ ) {
var wartość = Math.random()*1000;
tablica[i] = wartość;
skumulowanaSuma += wartość;
}

var współczynnik = skumulowanaSuma / oczekiwanaSuma;

for ( var i = 0; i < liczbaElementów; i++ ) {
tablica [i] /= współczynnik;
}

Offline Paweł

  • Użytkownik

# Kwiecień 25, 2014, 19:39:12
void f(int* a, int n, int desiredSum){
  int realSum=0;
  for  (int i = 0; i < n-1; ++i){
    a[i] = rand();
    realSum += a[i];
  }
  a[n-1] = desiredSum - realSum;
}

Offline LizarD

  • Użytkownik

# Maj 07, 2014, 07:12:39
Doba, a co jeżeli chciałbym mieć ustaloną jakąś liczbę minimalną ? Taką że w tablicy będzie ona zawsze najmniejszą liczbą ?

Offline Xirdus

  • Redaktor

# Maj 07, 2014, 08:37:11
W moim rozwiązaniu byłby to dodatkowy if sprawdzający czy dana liczba w tabeli jest już dostatecznie mała.

Offline _OskaR

  • Użytkownik

  • +1
# Maj 07, 2014, 22:01:57
@up
A nie lepiej najpierw wypełnić całą tablicę minimalnymi i potem tylko mniej razy losować indeks?

Offline LizarD

  • Użytkownik

# Maj 08, 2014, 15:59:51
@Up Ale że odwrotne rozwiązanie ? a co jeżeli chce mieć pewną kwotę maksymalną ? Też musi być if i na jedno wychodzi...

Offline Xirdus

  • Redaktor

# Maj 08, 2014, 16:06:42
W moim poście tablica jest już wypełniona maksymalnymi, więc ani porada _OskaRa, ani LizarDa nie pomoże. Po prostu moje rozwiązanie nie jest idealne.

Offline Xender

  • Użytkownik

# Maj 08, 2014, 16:38:37
STOP!

Przy tak niekompletnych założeniach nie można nawet zaczynać omawiać, która implementacja jest lepsza, a która gorsza.

W założeniach brak jakiejkolwiek informacji o tym, jaki ma być rozkład liczb w tablicy. A to kluczowa sprawa, ponieważ najprostsza implementacja:
int arr[n] = {desired_sum}; // Reszta jest wypełniona zerami w C++.Spełnia OBA warunki zadania: suma się zgadza, a "tylko jak zrobić żeby te liczby w tablicy nie były sobie równe ale zawsze ich suma wynosiła x, liczby mogą się powtarzać ale nie muszą" jest po prostu za mało precyzyjnym określeniem.

Więc jak OP ustali, o jaki rozkład mu chodzi (chociaż podejrzewam najprostszy, czyli liniowy. Pytanie teraz, z jakiego zakresu.), oraz czy mówimy o intach ze znakiem czy bez, to możemy wrócić do porównywania, które implementacja jest lepsza. Na razie chyba każda spełnia inne możliwe początkowe założenia.