Przejdź do treści

Suma dwóch liczb

Opis problemu

Rozwiązanie naiwne

Implementacja

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h>

void sumOfTwoNaive(int n, int tab[], int sum) {
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (tab[i] + tab[j] == sum) {
              printf("%d, %d\n", tab[i], tab[j]);
                return;
            }
        }
    }

  printf("Not found\n");
}

int main() {
    int n = 10;
    int tab[10] = {1, 2, 4, 6, 8, 9, 10, 12, 13, 15};
    int sum = 18;

    sumOfTwoNaive(n, tab, sum);

    return 0;
}

Rozwiązanie optymalne

Implementacja

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <stdio.h>

void sumOfTwoOptimal(int n, int tab[], int sum) {
  int left = 0;
  int right = n - 1;

  while (left < right && tab[left] + tab[right] != sum) {
    if (tab[left] + tab[right] < sum) {
      left++;
    } else {
      right--;
    }
  }

  if (left < right) {
    printf("%d, %d\n", tab[left], tab[right]);
  } else {
    printf("Not found\n");
  }
}

int main() {
  int n = 10;
  int tab[10] = {1, 2, 4, 6, 8, 9, 10, 12, 13, 15};
  int sum = 18;

  sumOfTwoOptimal(n, tab, sum);

  return 0;
}