Znalezienie wszystkich kombinacji [0,1] [0,1] [0,1] w zależności od podanej sumy

0

Witam,
Mam do rozwiązania taki problem. Podaję tablice dla np trzech przypadków [0.1][0,1][0,1] wszystkie kombinacje to 000, 001, 010, 011, 100, 101, 110 and 111. I teraz podaję sumę którą chcę znaleźć np. 2 czyli rozwiązanie to 011, 110 i 101.

Chodzi o to, że podaję ileś tam tablic [0.1][0,1][0,1][0.1][0,1][0,1] i podaję jakąś sumę np 4 i znalezienie wszystkich rozwiązań.

Może być też [1.1][0,1][0,1][1.1][0,1][1,1] i szukam rozwiązań dla podanej sumy.

0

Czy cyfry w tablicach mogą być tylko 0 albo 1?

0

W zasadzie powinny być możliwe trzy przypadki [0,1] [1,0] lub [1,1].

0

To rozumiem [0, 1][0, 1][0, 1] znaczy, że na trzech możliwych pozycjach, mogę mieć 0 lub 1, co daje ten zbiór potęgowy: 000, 001, ..., i tak dalej. A co zrobić z tym:
[1.1][0,1][0,1][1.1][0,1][1,1]?

0

Bo to chodzi o to, że jak podam dowolną ilość tych [0,1] i jakąś sumę to ma mi znaleźć ileś tam rozwiązań.

Czyli jak mamy: [1,1][0,1][0,1][1.1][0,1][1,1] i podaję sum=5 to ma wypisać wszystkie możliwe rozwiązania tak jak w poprzednim przypadku. czyli np. 111101 to jest jedno rozwiązanie albo 101111 drugie itd.

2

Zadanie zadaniem, ale umiejętność określenia problemu jest najważniejsza. Szczerze, ja dalej nie rozumiem jakie jest polecenie. Nie rozumiem twoich zapisów, mieszasz kropki z przecinkami.
I myślę, że nie jestem jedyny.

"Bo to chodzi o to" - no ale według Ciebie czy według polecenia?
Postaraj się nam opisać problem DOKŁADNIE z jasnym opisem oznaczeń, a wtedy postaramy Ci się pomóc.

0

Faktycznie w paru miejscach jest kropka ale wszędzie gdzie jest [] muszą być przecinki.
Jeszcze raz:
Tablica może przyjmować tylko wartości [0,1][1,0][1,1][0,0] np.

.Mam tablice [0,1][0,1][0,1] wszystkie możliwe kombinacje to 000, 001, 010, 011, 100, 101, 110 , 111. Podaję sumę sum=2 wtedy rozwiązanie to 011, 110 i 101 bo 0+1+1 = 2, 1+1+0 =2, 1+0+1=2 i to są rozwiązania.

Mogą być inne przypadki np: [1,1][0,1][1,0][1,1][0,0] i teraz chcę znaleźć wszystkie rozwiązania dla sum = 3. Czyli rozwiązanie to np. 11010 albo 10110.
Mam nadzieje, że trochę rozjaśniłem.

0

No to wygeneruj wszystkie możliwości i policz sumę dla każdej z nich. Gdzie jest problem?

1

Najprostsze rozwiązanie:
mamy przykładowo dane wejściowe [1,1][0,1][0,1][0,1] i suma = 2.
Ile jest wszystkich kombinacji do sprawdzenia? 16 . I teraz iterujesz od 0 do 16, w każdej iteracji zamieniasz index na jego wartość bitowa. To byłby index do tablic wejściowych np 5 = 0101 czyli z tablic wejściowych bierzesz 1 1 0 1 - sumujesz cyfry. Jeśli ich suma jest oczekiwana dodajesz ją do tablicy.

Da się to zrobić szybciej np zamiast liczenia wartości binarnej można ją generować przez tablice z przeniesieniem. Dodatkowo można od razu wykluczyć albo zawsze dodać tablice [0,0] [1,1]
one nigdy/ zawsze nie będą zmieniać sumy.

0

Tak jak Napisałeś, program wyświetla te kombinacje (nie zwraca) - dlatego to takie toporne:)

class Main {

  static void printTheArray(int arr[], int n) { 
    for (int i = 0; i < n; i++) { 
        System.out.print(arr[i]+" "); 
    } 
    System.out.println(); 
} 

static int sumOfArray(int arr[], int n) {
  int s = 0;
  for (int i = 0; i < n; i++) 
    s += arr[i];
  return s;
}

static void generateAllBinaryStringsGivenSum(int n,  
                            int arr[], int i, int s) { 
    if (i == n)  { 
        if (sumOfArray(arr, n) == 3)
          printTheArray(arr, n); 
        return; 
    } 

    arr[i] = 0; 
    generateAllBinaryStringsGivenSum(n, arr, i + 1, s); 

    arr[i] = 1; 
    generateAllBinaryStringsGivenSum(n, arr, i + 1, s); 
  } 

public static void main(String args[]) { 
    int n = 4; 

    int[] arr = new int[n]; 

    int sum = 3;

    generateAllBinaryStringsGivenSum(n, arr, 0, sum); 
  } 
} 

Źródło: https://www.geeksforgeeks.org[...]the-binary-strings-of-n-bits/

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0