Mile widziana pomoc z zadaniem

0

Witajcie,

wziąłem się za programowanie. Jestem bardzo chętny do nauki, takie nowe zainteresowanie.

Przyjąłęm sobie pewne zadanie i nie daje mi spokoju jego rozwiązanie. Nie jestem w stanie skonstruować działającego kodu.

Oto zadanie:

Dane są dwa zbioryAiB ( n-elementowyim-elementowy) oelementach będących liczbami naturalnymi oraz zadana wartość (liczna naturalna).Elementy tych zbiorów dane są za pomocądwóch tablic uporządkowanych rosnąco.Skonstruuj algorytm wyznania liczbyelementów należących dozbioruA \B(różnicazbiorów A-B) ijednocześnie mniejszych od zadanej wartości. Np. A={1,2,3,5,8}, B={0,1,3,4,8,9,10} i zadana wartość to 3.A\B={2,5} ale istnieje jedenelement mniejszy od 3. Jest to wartość 2. Zalecana złożoność liniowa.

2

A czy chociaż rozumiesz, o co jesteś pytany i co masz zrobić? Nie wiesz, jak zapisać to w postaci kodu, ale czy wiesz jakbyś miał to zrobić sobie na kartce? Jakie czynności po kolei wykonać?

Bo jeśli tego też nie wiesz, to raczej nie tyle prosisz o pomoc, tylko o zrobienie tego za Ciebie. I teraz taka uwaga/przemyslenie - jeśli to do szkoły, to może ktoś Ci zrobi gotowca, natomiast jeśli rzeczywiście się sam uczysz, to może zacznij od podstaw, a potem zwiększaj poziom trudności.

2

Rozumiem na czym polega zadanie i jestem w stanie uporządkować potrzebne czynności do jego wykonania, lecz nie jestem w stanie przełożyć tego na kod. Mam tu do czynienia z funkcjami, które są dla mnie nowe mimo ich prostoty. Potrzebuje czegoś w stylu schematu kodu którym mógłbym się posłużyć o ile to jest wykonalne.

To wypisz "uporządkowane potrzebne czynności do wykonania zadania", a ktoś na pewno pomoże Ci w zbudowaniu z tym kodu. ;)

1

Próbowałem coś z działać sam z internetem

using namespace std; 

void findMissing(int tabn[], int tabm[], 
				int a, int b) 
{ 
	for (int i = 0; i < a; i++) 
	{ 
		int j; 
		for (j = 0; j < b; j++) 
			if (tabn[i] == tabm[j]) 
				break; 

		if (j == b) 
			cout << tabn[i] << " "; 
	} 
} 

int roznica() 
{ 
	int tabn[] = floor(m*rand(1,m); 
	int tabm[] = floor(m*rand(1,m); 
	int a = sizeof(tabn) / sizeof(tabn[0]); 
	int b = sizeof(tabm) / sizeof(tabm[1]); 
	findMissing(tabn, tabm, a, b); 
	return 0; 
}
1

Kierowałem się tymi krokami:
-stworzyć tabele
-porównać ich elementy
-wypisać te które są w pierwszej lecz nie w drugiej
-nadaną inną wartość porównać z wynikiem ^
-wypisać te które są mniejsze od nadanej wartości

3

Weź oddzielnie algorytm do wyznaczania róznicy, (dobra złozoność , liniowa):

#include <iostream>
#include <vector>
std::vector<int> difference(int arr[], int arr1[], int n, int m){   
    std::vector<int> v;
    int i = 0, j = 0; 
    while (i < n && j < m) { 
        if (arr[i] < arr1[j]) { 
            v.push_back(arr[i]); 
            i++; 
        } 
        else if (arr1[j] < arr[i]) {
            j++; 
        } 
        else{ 
            i++; 
            j++; 
        } 
    }
    return v; 
} 
void printVector(std::vector<int> v){
  for (auto &e : v)
    std::cout << e <<" ";
}
int main() {
     int arr1[] = {-2, 0, 5, 7, 13}; 
    int arr2[] = {0, 1, 4, 5, 14, 17}; 
    int n = sizeof(arr1)/sizeof(arr1[0]); 
    int m = sizeof(arr2)/sizeof(arr2[0]); 
    printVector( difference(arr1, arr2, n, m)); // -> -2 7 13
   std::cout <<"\n";
}

Znalezienie elementów wektora mniejszych od zadanej liczby będzie banalne.

0

Udało mi się skleić coś takiego ale coś robię źle wyciągając mniejsze wartości

#include<bits/stdc++.h> 
using namespace std; 

void brakujace(int a[], int b[], int n, int m) 
{ 
	for (int i = 0; i < n; i++) 
	{ 
		int j; 
		for (j = 0; j < m; j++) 
			if (a[i] == b[j]) 
				break; 

		if (j == m) 
			cout << a[i] << " "; 
	} 
} 

int main() 
{ 
	int a[] = { 1, 2, 6, 3, 4, 5 }; 
	int b[] = { 2, 4, 3, 1, 0 };
	int n = sizeof(a) / sizeof(a[0]); 
	int m = sizeof(b) / sizeof(b[1]); 
	brakujace(a, b, n, m);
	
    int x = 3;
    if (n<x)
    cout<<n;
    if (m<x)
    cout<<m;   
	
	return 0; 
}
0

I co?

0

Nie wyciąga mi mniejszych wartości od podanego x, chyba czegoś brakuje w kodzie

#include<bits/stdc++.h> 
using namespace std; 

void brakujace(int a[], int b[], int x, int n, int m) 
{ 
	for (int i = 0; i < n; i++) 
	{ 
		int j; 
		for (j = 0; j < m; j++) 
			if (a[i] == b[j]) 
				break; 

		if (j == m) 
			cout << a[i] << " "; 
	} 
	if (n<x)
    cout<<n;
    if (m<x)
    cout<<m;
} 

int main() 
{ 
	int a[] = { 1, 2, 6, 3, 4, 5 }; 
	int b[] = { 2, 4, 3, 1, 0 };
	int x = 3;
	int n = sizeof(a) / sizeof(a[0]); 
	int m = sizeof(b) / sizeof(b[1]); 
	brakujace(a, b, n, m, x);
	

	return 0; 
} 

teraz mi wyciąga liczbę 53 z jakiegoś powodu...

0

Spróbuj użyć mojej funkcji, jak się z jakiegoś powodu Brzydzisz std::vec, to można go łatwo podmienić tablicą.

0

A dałbyś radę może dokończyć mój kod?

1

Ale się Upierasz, czemu nie Wykorzystasz mojej funkcji. Jak tak Chcesz drukować wynik w metodzie, zamiast inteligentnie zwrócić strukturę, to można to, łatwo, przerobić na:

void solution(int arr[], int arr1[], int n, int m, int limit){   
    int * a = new int[n]; // difference arr - arr1
    int i = 0, j = 0, k = 0;
    while (i < n && j < m) { 
        if (arr[i] < arr1[j]) { 
            a[k] = arr[i]; 
            i++; 
            k++;
        } 
        else if (arr1[j] < arr[i]) {
            j++; 
        } 
        else{ 
            i++; 
            j++; 
        } 
    }
    for (int i = 0; i < k; ++i) {
		if (a[i] < limit)
			std::cout << a[i] << " ";
	}
        delete [] a;
	std::cout <<"\n";
} 

int main(){
    int arr1[] = {-2, 0, 5, 7, 13}; 
    int arr2[] = {0, 1, 4, 5, 14, 17}; 
    int n = sizeof(arr1)/sizeof(arr1[0]); 
    int m = sizeof(arr2)/sizeof(arr2[0]); 
    int limit = 10;
    solution(arr1, arr2, n, m, limit); // -> -2 7
	return 0;
}

Sporawdź sobie, że złożoność jest ~2n + m, korzystając z tego, że a jest posortowane, Mógłbyś (wyszukiwanie binarne) uprawnić to do ~n + m + logn; oczywiście obydwa sposoby (z usprawnieniem i bez) spełniają warunki zadania (złożoność liniowa).

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