Dodawanie 2 liczb binarnych :: 4programmers.net

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

Dodawanie 2 liczb binarnych

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

Praca dla programistów

Forum dyskusyjne

Sprawy administracyjne

O nas

Skontaktuj się z nami