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.
Czy cyfry w tablicach mogą być tylko 0 albo 1?
W zasadzie powinny być możliwe trzy przypadki [0,1] [1,0] lub [1,1].
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]?
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.
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.
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.
No to wygeneruj wszystkie możliwości i policz sumę dla każdej z nich. Gdzie jest problem?
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.
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/generate-all-the-binary-strings-of-n-bits/
Ok dzięki wszystkim patrzę na to:)
class perm_test
{
public static void main (String[] args) throws java.lang.Exception
{
new permutation(5,2).showAll();
}
}
class permutation
{
private char[] value;
public String getValue() { return new String(value); }
public permutation(int Size,int Count)
{
if(Size>=Count) init(Size,Count);
else init(Count,Size);
}
private void init(int Size,int Count)
{
value=new char[Size];
int Where=Size-Count;
for(int i=0;i<Size;++i) value[i]=i<Where?'0':'1';
}
private void swap(int a,int b)
{
char tmp=value[a];
value[a]=value[b];
value[b]=tmp;
}
private void reverse(int first,int last)
{
while(first<(--last)) swap(first++,last);
}
private int breakorder(int first,int last)
{
while(value[--last]<=value[first]) {}
return last;
}
private boolean swapreverse(int pos,int last)
{
if(value[pos]>=value[pos+1]) return false;
swap(pos,breakorder(pos,last));
reverse(pos+1,last);
return true;
}
private boolean next()
{
int last=value.length,i=last;
if((--i)<=0) return false;
while(i>0) if(swapreverse(--i,last)) return true;
reverse(0,last);
return false;
}
public void show()
{
System.out.println(getValue());
}
public void showAll()
{
show();
while(next()) show();
}
}