[Algorytmy] Sumowanie nieparzystych kolumn, parzystych wiers

[kobi55]

Witam serdecznie,

piszę do Was ponieważ pokonało mnie zadanie z algorytmów.
Problem polega na sumowaniu w tablicy dwuelementowej (macierzy) liczb z nieparzystych kolumn i parzystych wierszy. Treść zadania brzmi tak:

Dana jest tablica A[1...m,1...n] wskaż sumę liczb znajdujących się w nieparzystych kolumnach i parzystych wierszach.

Nie wiem w jaki sposób to napisać, w związku z tym bardzo proszę o wsparcie drodzy forumowicze.

Pozdrawiam Serdecznie
Kobi55

[bartek118]

W pseudojęzyku można to tak zrobić:

Kod: Zaznacz cały

suma = 0;
for i:=1 to m do step 2
for j:=2 to n do step 2
suma := suma + A[i,j]

(zależy też trochę, który indeks traktujesz jako wiersz, a który jako kolumnę)

[kobi55]

Dzięki za odpowiedź,
problem w tym, że wykładowca powiedział mi, że tak nie może być, bo to jest źle. Powiedział, że tak łatwego zadania by nie dał. Masz może jakiś inny sposób na to?

Pozdrawiam

[bartek118]

Co ma być wynikiem? Bo nie jest to teraz dla mnie jasne. Suma wszystkich tych elementów? Czy sumy z wierszy i sumy z kolumn jako osobne liczby?
Tak, czy owak zadanie jest wysoce trywialne, więc owszem, dał tak łatwe zadanie.

[kobi55]

Wynikiem ma być suma wszystkich liczb ktore znajdują się we wskazanych lokacjach (kolumna nieparzysta, wiersz parzysty). Np. (1,2)+(1,4)+(1,n)+(3,2)... itd.

Oddałem mu zadanie dokładnie tak samo zrobione jak to co mi pokazałeś. Dowiedziałem się od niego, że to jest źle, nie powiedział dlaczego.

EDIT: Też myślałem, że jest takie łatwe. On stwierdził, że nie, ale nie chciał powiedzieć jak powinno być. Powiedział tylko, że tak prostego by nie dał.

[bartek118]

W takim razie to rozwiązanie jest poprawne.

[kobi55]

Dziękuję, takie rozwiązanie wyślę
Mógłbyś mi jeszcze pomóc z takim zadaniem:

Dana jest tablica A [1...n] zawiera liczby całkowite od 0 do n z wyjątkiem jednej liczby. Wyznacz brakującą liczbę. Liczby się nie powtarzają.

Pozdrawiam

[bartek118]

Mój pierwszy pomysł: posortuj i potem przejedź liniowo i znajdź miejsce 'skoku', albo takie, gdzie indeks się nie powtarza. Z dobrze zaimplementowanym sortowaniem - złożoność: \(\displaystyle{ O(n \log n)}\).
Można jeszcze szybciej - robisz tablicę bool przechodzisz po danej tablicy i w tablicy zaznaczasz true, przy danej liczbie. Potem przechodzisz drugi raz i znajdujesz gdzie zostało false. Złożoność: \(\displaystyle{ O(n)}\).

[kobi55]

Problem w tym że jestem totalnym laikiem
Mam zamiar uczyć się algorytmów, jednak z powodu choroby opuściłem czas od początku studiów...

Mógłbym prosić o napisanie tego? To jest jednorazowa prośba, musze po prostu nadrobić braki, a do wieczora nie zdąrze...

[bartek118]

Napiszę Ci pseudokod drugiego podejścia:

Kod: Zaznacz cały

boolean T[0..n]

for i:=0 to n do
T[i] = false;

for i:=1 to n do
T[A[i]] = true;

i:=0
while(T[i])
i:=i+1;

return i;

[kobi55]

To jest do tego

Można jeszcze szybciej - robisz tablicę bool przechodzisz po danej tablicy i w tablicy zaznaczasz true, przy danej liczbie. Potem przechodzisz drugi raz i znajdujesz gdzie zostało false. Złożoność: O(n).

Dobrze rozumiem?

[bartek118]

Zgadza się.

[kobi55]

A w tym miejscu:

Kod: Zaznacz cały

while(T[i])
i:=i+1;

return i;

Sprawdzan czy aktualne miejsce w tablicy ma wartość true.
Jeżeli tak to zwiększam zmienna i oraz sprawdzam ponownie.

W momencie w ktorym element tablicy ma wartosc false wychodze z petli i zwracam index tej liczby. Zgadza się?

[Vardamir]

Zgadza się?

Zgadza się, ale przecież można prościej

Suma od \(\displaystyle{ 0}\) do \(\displaystyle{ n}\) to \(\displaystyle{ \frac{n^2 + n}{2}}\).

Zatem wystarczy wysumować elementy tablicy i odjąć sumę wcześniej policzoną.

Kod: Zaznacz cały

suma=(n*n+n)/2
x=0

for i=1 to n
  x+=A[i]

return suma-x

[kobi55]

Dziękuję bardzo