[C++] Ekstrema w ciągu


(Lol600000065) #1

Witam,

mam do rozwiazania nastepujace zadanie:

O co chodzi z tą liczbą minimów i maksimów ? Co ma do rzeczy też to że a nie jest równe a[i+1] ?

pozdrawiam.


(Sawyer47) #2

Niezbyt jasno sformułowane zadanie. Moja interpretacja jest taka, że można te punkty połączyć łamaną i traktować jako wykres funkcji ciągłej i być może chodzi o policzenie ekstremów lokalnych?


(Johny) #3

Minimum,najmniejsza liczba w ciągu,Maximum największa liczba w ciągu

Minimum lokalne w przedzale (a,b) najmniejsza liczba w przedziale (a,b)

Maximum lokalne w przedziale (a,b) największa liczba w przedzale (a,b)

Extremum to minimum lum maximum na wykresach funkcji


(system) #4

Nie znam się na programowaniu, ale mogę zaproponować algorytm:

1/ Posortuj ciąg (metoda do wyboru, ale do różnych zbiorów danych stosuje się różne metody sortowania)

2/ Zlicz powtarzające się wyrazy od początku ciągu (to będą minima)

3/ Zlicz powtarzające się wyrazy od końca ciągu (to będą maksima)

-- Dodane So, 2011/06/25, 16.20 --

Żeby nieco wyjaśnić przykład ciągu spełniającego wymagania zadania:

1, 2, 3, 2, 1, 2, 3

Posortowany: 1, 1, 2, 2, 2, 3, 3

2 minima 1 i 2 maksima 3


(Lol600000065) #5

To to nie jest za proste :?: Wystarczy użyć max_element i min_element z ...

EDIT:

Aha rozumiem, dzięki =D>


(Ryan) #6

IMO nie o to chodzi, a o minima i maksima w ogóle (lokalne i globalne).

600px-Extrema_example_original.svg.png

Maksima lokalne znajdują się w ciągu w pozycjach o indeksie i, takich że (a[i-1] a a[i+1] a__). Dla minimów zmienia się kierunek nierówności. Dlaczego tak sądzę? Warunek mówiący o tym, że sąsiednie wartości nie są równe upraszcza algorytm i likwiduje z niego niejednoznaczności (czy ciąg 1221 ma jedno maksimum, czy dwa?).

Ogólnie jednak zadanie jest niejasne i autor zadania powinien doprecyzować treść.


(Lol600000065) #7

Czyli ogólnie rzecz biorąc mam pozliczać tylko wystąpienia (a[i-1] < a && a[i+1] < a__) oraz (a[i-1] > a && a[i+1] > a__) :?: No i zaprzestać iteracji na przedostatnim elemencie tablicy skoro tam jest i+1...


(Ryan) #8

Nie, ogólniej mówiąc masz spytać autora zadania co miał na myśli.


(Lol600000065) #9

Niestety nie mam takiej możliwości - ok moja wina, że nie spytałem wykładowcy zaraz po rozdaniu zadań.

Ale jeśli założyć, że Ty masz rację Ryan to moje rozumowanie jest dobre z tym zliczaniem :?:


(Ryan) #10

Wyjaśnij proszę dlaczego łamiesz punkt 2.16?


([alex]) #11

To zadanie można zrozumieć na dwa sposoby.

  1. (założenia Ryan'a są słuszne, bardzo prawdopodobne ponieważ warunek n jest co najmniej 3, nic nie daje dla wariantu drugiego, to samo dotyczy warunku a [nie jest rowne a[i+1])

w pętle od 2 do n-2 zliczasz wystąpienia:

(a[i-1]

(a[i-1]>a__)&&(a[i+1]>a__) // min

2. (założenia Ryan'a NIE są słuszne, mało prawdopodobne)

Pierwszym przebiegiem znajdujesz min i max.

Drugim przebiegiem znajdujesz ile razy wystąpił min oraz ile razy wystąpił max.


(system) #12

Dla n=2 istnieje 1 minimum i 1 maksimum. Bez wykonywania jakichkolwiek operacji.


([alex]) #13

iSalt0 , w zadaniu jasne napisano n>2