Dodawanie 2 liczb binarnych

1

Siema!

Rozwiązuje zadanie na uczelnie gdzie trzeba dodać do siebie dwie liczby binarne, które mogą być różnej długości oraz w zapisie liczb nie ma zer wiodących, tzn. pierwszy bit każdej liczby jest równy 1, chyba że cała liczba jest równa 0 (jeden bit równy 0). Przykładowe wyjście:
Wejście:

2    // ilość zestawów (w każdym zestawie są 2 liczby binarne)
4   //  długość 1 liczby binarnej
1 0 0 1 // jej postać binarna
2  //długość 2 liczby binarnej
1 1 // jej postać binarna
// \/ dalej ten sam proces dla  kolejnych 2 liczb
4 
1 1 1 1
6
1 1 1 1 1 1

Wyjście:

1100
1001110

Ogólnie tu jest mój kod i niestety z powodu złej odpowiedzi uczelniany system go nie przepuszcza, a przy testowaniu różnych wariantów wychodzi poprawna odpowiedź.

#include <stdio.h
int main(){
int d; //liczba  zestawów
    scanf("%d", &d);
    int n, m, b1, b2;  // n = dlugosc pierwszej binarnej / m = dl. drugiej  / b1/b2 = postać binarna
    int sum[10000];
    int l;
    int carry; 
    int r;
    int d1[10000]; // tablica do przechowania binarnej, przesunięta o 1 indeks, np: zamiast 111111 było 0111111 - po to aby zrobić miejsce  na ewentualne dodatkowe 1.
    int d2[10000]; // tablica do przechowania binarnej, przesunięta o 1 indeks, np: zamiast 111111 było 0111111 - po to aby zrobić miejsce  na ewentualne dodatkowe 1.
    int p1[10000]; // tablica do przechowania binarnej
    int p2[10000]; // tablica do przechowania binarnej
    int f, g;
    for(int i = 0; i < d; i++){
        f = 0;
        g = 0;
        r = 0;
        carry = 0;
        scanf("%d", &n);
    //  int p1[10000];
        for(int j = 0; j < n; j++){
            scanf("%d", &b1);
            p1[j] = b1;
        }

        scanf("%d", &m);
    //  int p2[10000];
        for(int j = 0; j < m; j++){
            scanf("%d", &b2);
            p2[j] = b2;
        }
        if(n > m){

            d1[0] = 0;
            d2[0] = 0;

            f = n + 1;

                for(int j = 1; j <= m; j++)
                    d2[f - j] = p2[m - j];

                for(int k = 1; k <= f; k++)
                    d1[f - k] = p1[f - k - 1];

                for(int k = n; k > 0; k--){

                    if(d1[k]==0 && d2[k]==0 && carry==0){
                    sum[k] = 0;
                    carry = 0;
                    }
                    else if(d1[k]==0 && d2[k]==0 && carry==1){
                        sum[k] = 1;
                        carry = 0;
                    }
                    else if(((d1[k]==1 && d2[k]==0)||(d1[k]==0 && d2[k]==1)) && carry==0){
                        sum[k] = 1;
                        carry = 0;
                    }
                    else if(((d1[k]==1 && d2[k]==0)||(d1[k]==0 && d2[k]==1)) && carry==1){
                        sum[k] = 0;
                        carry = 1;
                    }
                    else if(d1[k]==1 && d2[k]==1 && carry==0){
                        sum[k] = 0;
                        carry = 1;
                    }
                    else if(d1[k]==1 && d2[k]==1 && carry==1){
                        sum[k] = 1;
                        carry = 1;
                    }

                    }
                if(carry == 0){
                    for(int j = 1; j <= n; j++)
                    printf("%d", sum[j]);
                    }   
                if(carry == 1){
                    sum[0] = 1;
                    for(int s = 0; s <= n; s++)
                        printf("%d", sum[s]);   
                    }
                for(int z = 0; z < m + 2; z++){
                    p1[z] = 0;
                    p2[z] = 0;
                    d1[z] = 0;
                    d2[z] = 0;
                    sum[z] = 0;
        }
    }
    //f = 0;
//  g = 0;
//  r = 0;
//  carry = 0;
        if(n < m){

            d1[0] = 0;
            d2[0] = 0;
            g = m + 1;
            for(int j = 1; j <= n; j++)
                d1[g - j] = p1[n - j];

            for(int k = 1; k <= g; k++)
                d2[g - k] = p2[g - k - 1];

            for(int k = m; k > 0; k--){

                    if(d1[k]==0 && d2[k]==0 && carry==0){
                    sum[k] = 0;
                    carry = 0;
                    }
                    else if(d1[k]==0 && d2[k]==0 && carry==1){
                        sum[k] = 1;
                        carry = 0;
                    }
                    else if(((d1[k]==1 && d2[k]==0)||(d1[k]==0 && d2[k]==1)) && carry==0){
                        sum[k] = 1;
                        carry = 0;
                    }
                    else if(((d1[k]==1 && d2[k]==0)||(d1[k]==0 && d2[k]==1)) && carry==1){
                        sum[k] = 0;
                        carry = 1;
                    }
                    else if(d1[k]==1 && d2[k]==1 && carry==0){
                        sum[k] = 0;
                        carry = 1;
                    }
                    else if(d1[k]==1 && d2[k]==1 && carry==1){
                        sum[k] = 1;
                        carry = 1;
                    }

                    }
            if(carry == 0){
                for(int j = 1; j <= m; j++)
                    printf("%i", sum[j]);
                    }   
            if(carry == 1){
                sum[0] = 1;
                for(int s = 0; s <= m; s++)
                    printf("%d", sum[s]);   
    }
            for(int z = 0; z < m + 2; z++){
                p1[z] = 0;
                p2[z] = 0;
                d1[z] = 0;
                d2[z] = 0;
                sum[z] = 0;
        }
    //f = 0;
    //g = 0;
//  r = 0;
    //carry = 0;
    }       
        if(n == m){ 
            d1[0] = 0;
            d2[0] = 0;
            r = m + 1;
            for(int j = 1; j <= n; j++){
                d1[r - j] = p1[n - j];
                d2[r - j] = p2[n - j];
        }
            for(int k = m; k > 0; k--){

                    if(d1[k]==0 && d2[k]==0 && carry==0){
                    sum[k] = 0;
                    carry = 0;
                    }
                    else if(d1[k]==0 && d2[k]==0 && carry==1){
                        sum[k] = 1;
                        carry = 0;
                    }
                    else if(((d1[k]==1 && d2[k]==0)||(d1[k]==0 && d2[k]==1)) && carry==0){
                        sum[k] = 1;
                        carry = 0;
                    }
                    else if(((d1[k]==1 && d2[k]==0)||(d1[k]==0 && d2[k]==1)) && carry==1){
                        sum[k] = 0;
                        carry = 1;
                    }
                    else if(d1[k]==1 && d2[k]==1 && carry==0){
                        sum[k] = 0;
                        carry = 1;
                    }
                    else if(d1[k]==1 && d2[k]==1 && carry==1){
                        sum[k] = 1;
                        carry = 1;
                    }

                    }
            if(carry == 0){
                for(int j = 1; j <= m; j++)
                    printf("%d", sum[j]);
                    }   
            if(carry == 1){
                sum[0] = 1;
                for(int s = 0; s <= m; s++)
                    printf("%d", sum[s]);
                }
            for(int z = 0; z < n + 2; z++){
                p1[z] = 0;
                p2[z] = 0;
                d1[z] = 0;
                d2[z] = 0;
                sum[z] = 0;
        }
    }
    //for(int z = 0; z < n + m; z++){
        //  p1[z] = 0;
        //  p2[z] = 0;
        //  d1[z] = 0;
        //  d2[z] = 0;
    //      sum[z] = 0;
    //  }   
}
}

Macie może jakiś pomysł jak to poprawić?

0

Na pewno zmniejszyć ilość ifów. Najlepiej napisać od początku.

0

Wrzuciłem Twój kod oraz dane wejściowe na https://ideone.com . W wyniku dostaje ~jedną cyfrę tzn pomiędzy poszczególnymi cyframi nie ma nowej linii. Nie mam kompilatora c++ pod ręką ale jeśli tak jest to Twój program wrzuca na Wyjście inne dane niż podałeś. Warto to sprawdzić.

1

Napisz to od początku. Napisz funkcję o prototypie

void add(int a[], int a_len, int b[], int b_len, int result[])

Funkcja ta będzie się zajmować wykonywaniem dodawania. Jak już ją uzyskasz, to możesz wykonać ją odpowiednio dużo razy w pętli.

Wzór na sumę jest ogólnie prosty:

result[i] = (a[i] + b[i] + carry) % 2;
if (a[i] + b[i] + carry >= 2) {
    carry = 1;
} else {
    carry = 0;
}

Jeśli teraz tylko powtórzysz tę operację odpowiednio dużo razy (pamiętając by iść od prawej strony tablic), to dostaniesz dodawanie liczb dowolnej długości.

1

Spróbuj z taką funkcją, dodającą dwie liczby binarne, jako tablice integerów:

int * bin_add(int a [], int b [], int len_a, int output []){
    a = reversed(a);
    b = reversed(b); 
    int carry_bit = 0;
    int i = 0;

    for (i = 0; i < len_a; i ++){
        output[i] = (a[i] + b[i] + carry_bit) % 2;
        carry_bit = (a[i] + b[i] + carry_bit) / 2;
    }

    if (carry_bit > 0)
        output[i + 1] = carry_bit;
    output = reversed(output);
    output = remove_trailing_zeroes(output);
    return output;
}

Tablice jakie funkcja przyjmuje musza być równe, krótsza musi być uzupełniona zerami na początku, trzeba przekazać rozmiar; tablica output o jeden większa od liczb. Jak nie Lubisz wskaźników, to może być void zmienający output.

0

@enedil
@lion137

#include <stdio.h>
int main(){
    int d;
    scanf("%d", &d);
    int n, m, b1, b2;
    int sum[10000];
    int l;
    int carry;
    int r;
    int d1[10000];
    int d2[10000];
    int f, g;
    for(int i = 0; i < d; i++){
        f = 0;
        g = 0;
        r = 0;
        carry = 0;
        scanf("%d", &n);
        int p1[10000];
        for(int j = 0; j < n; j++){
            scanf("%d", &b1);
            p1[j] = b1;
        }

        scanf("%d", &m);
        int p2[10000];
        for(int j = 0; j < m; j++){
            scanf("%d", &b2);
            p2[j] = b2;
        }
        if(n > m){

            d1[0] = 0;
            d2[0] = 0;

            f = n + 1;

                for(int j = 1; j <= m; j++)
                    d2[f - j] = p2[m - j];

                for(int k = 1; k <= f; k++)
                    d1[f - k] = p1[f - k - 1];

                for(int k = n; k > 0; k--){

                    sum[k] = (d1[k] + d2[k] + carry) % 2;
                    if (d1[k] + d2[k] + carry >= 2) {
                        carry = 1;
                    } else {
                    carry = 0;
                    }
                }

                if(carry == 0){
                    for(int j = 1; j <= n; j++)
                    printf("%d", sum[j]);
                    }   
                if(carry == 1){
                    sum[0] = 1;
                    for(int s = 0; s <= n; s++)
                        printf("%d", sum[s]);   
                    }
                printf("\n");

        }

        if(n < m){

            d1[0] = 0;
            d2[0] = 0;
            g = m + 1;
            for(int j = 1; j <= n; j++)
                d1[g - j] = p1[n - j];

            for(int k = 1; k <= g; k++)
                d2[g - k] = p2[g - k - 1];

            for(int k = m; k > 0; k--){

                sum[k] = (d1[k] + d2[k] + carry) % 2;
                if (d1[k] + d2[k] + carry >= 2) {
                    carry = 1;
                } else {
                    carry = 0;
                }

            }
            if(carry == 0){
                for(int j = 1; j <= m; j++)
                    printf("%i", sum[j]);
                    }   
            if(carry == 1){
                sum[0] = 1;
                for(int s = 0; s <= m; s++)
                    printf("%d", sum[s]);   
            printf("\n");
    }

    }       
        if(n == m){ 
            d1[0] = 0;
            d2[0] = 0;
            r = m + 1;
            for(int j = 1; j <= n; j++){
                d1[r - j] = p1[n - j];
                d2[r - j] = p2[n - j];
        }
            for(int k = m; k > 0; k--){

                sum[k] = (d1[k] + d2[k] + carry) % 2;
                if (d1[k] + d2[k] + carry >= 2) {
                    carry = 1;
                } else {
                    carry = 0;
                }

                    }
            if(carry == 0){
                for(int j = 1; j <= m; j++)
                    printf("%d", sum[j]);
                    }   
            if(carry == 1){
                sum[0] = 1;
                for(int s = 0; s <= m; s++)
                    printf("%d", sum[s]);
                }
            printf("\n");

    }

    for(int z = 0; z < n + m; z++){
            p1[z] = 0;
            p2[z] = 0;
            d1[z] = 0;
            d2[z] = 0;
            sum[z] = 0;
        }   

}
}

Zmieniłem na coś takiego wykorzystując dodawanie które dodałeś no ale niestety wciąż błedna odpowiedź wyskakuje na stronie uczelnianej gdy ładuje :/, aczkolwiek gdy robię dodawanie wygląda ok w devc++... ; /
W sumie to zamieszcze całą treść zadania
Dane są dwie liczby zapisane w postaci binarnej. Oblicz ich sumę, a wynik podaj również w postaci binarnej.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita d (1 <= d <= 100), która oznacza liczbę zestawów danych.
Każdy zestaw składa się z czterech linii. W pierwszej z nich znajduje się liczba bitów n (1<=n<=10000), na których zapisana jest pierwsza liczba.
Druga linia zawiera n oddzielonych spacjami cyfr: zer lub jedynek, tworzących reprezentację binarną pierwszej liczby.
W trzeciej linii znajduje się liczba bitów m (1<=m<=10000), na których zapisana jest druga liczba.
Czwarta linia zawiera m oddzielonych spacjami cyfr: zer lub jedynek, które tworzą reprezentację binarną drugiej liczby.
W zapisie liczb nie ma zer wiodących, tzn. pierwszy bit każdej liczby jest równy 1, chyba że cała liczba jest równa 0 (jeden bit równy 0).

Wyjście

Na wyjściu należy dla każdego zestawu danych wypisać ciąg zer i jedynek (bez spacji), będący zapisem binarnym sumy liczb podanych na wejściu.

0

Możesz jeszcze uprościć kod usuwając rozróżnienie pomiędzy n oraz m. Różnica długości liczb tak naprawdę nie ma znaczenia. Po tej operacji będzie prościej poprawić kod. Tip: pytanie czy liczba cyfr na maszynie na uczelni jest mniejsza niż 10000.

Edit: skoro liczby mają długość N cyfr to na wyjściu może być tych N+1.

0
#include <stdio.h>

int main(){
    int d;
    scanf("%d", &d);
    int n, m, b1, b2;
    int l;
    int carry;
    int f, g;
    for(int i = 0; i < d; i++){

        f = 0;
        g = 0;
        carry = 0;
        scanf("%d", &n);
        int p1[n];
        for(int j = 0; j < n; j++){
            scanf("%d", &b1);
            p1[j] = b1;
        }

        scanf("%d", &m);
        int p2[m];
        for(int j = 0; j < m; j++){
            scanf("%d", &b2);
            p2[j] = b2;
        }
        if(n > m){

            int d2[n];
            int sum[n + 1];

                for(int j = 1; j <= m; j++)
                    d2[n - j] = p2[m - j];
                for(int j = 0; j < n - m; j++)
                    d2[j] = 0;  

                l = n - 1;
                for(int k = l; k >= 0; k--){

                    sum[k + 1] = (p1[k] + d2[k] + carry) % 2;
                    if (p1[k] + d2[k] + carry >= 2) {
                        carry = 1;
                    } else {
                    carry = 0;
                    }
                }

                if(carry == 0){
                    for(int j = 1; j <= n; j++)
                    printf("%d", sum[j]);
                    }   
                if(carry == 1){
                    sum[0] = 1;
                    for(int s = 0; s <= n; s++)
                        printf("%d", sum[s]);   
                    }

                printf("\n");

        }
        if(n < m){

            int d2[m];
            int sum[m + 1];
            g = m - 1;

            for(int j = 1; j <= n; j++)
                    d2[m - j] = p1[n - j];
                for(int j = 0; j < m - n; j++)
                    d2[j] = 0;  

            for(int k = g; k >= 0; k--){

                sum[k + 1] = (d2[k] + p2[k] + carry) % 2;
                if (d2[k] + p2[k] + carry >= 2) {
                    carry = 1;
                } else {
                    carry = 0;
                }

            }
            if(carry == 0){
                for(int j = 1; j <= m; j++)
                    printf("%i", sum[j]);
                    }   
            if(carry == 1){
                sum[0] = 1;
                for(int s = 0; s <= m; s++)
                    printf("%d", sum[s]);   
        }

            printf("\n");
        }

    if(n == m){

            int sum[m + 1];
            g = m - 1;

            for(int k = g; k >= 0; k--){

                sum[k + 1] = (p1[k] + p2[k] + carry) % 2;
                if (p1[k] + p2[k] + carry >= 2) {
                    carry = 1;
                } else {
                    carry = 0;
                }

            }
            if(carry == 0){
                for(int j = 1; j <= m; j++)
                    printf("%i", sum[j]);
                    }   
            if(carry == 1){
                sum[0] = 1;
                for(int s = 0; s <= m; s++)
                    printf("%d", sum[s]);   
        }

            printf("\n");
        }

}
}

Okey Panowie dziękuje za pomoc, zrobiłem to w bardziej "dynamiczny sposób", kod wyżej przeszedl przez system :D

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