• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Ilość n-elementowych malejących podciagów ciągu

Aruba Cloud PRO i VPS, Openstack, VMWare, MS Hyper-V
+1 głos
61 wizyt
pytanie zadane 1 dzień temu w C i C++ przez blackjajko Użytkownik (630 p.)
edycja 1 dzień temu przez blackjajko

Siemka,

mam trudność z wymyśleniem jakiegoś sensownego sposobu na znalezienie w dosyć szybki sposób (przynajmniej szybszy od O(n^2)) liczby wszystkich n-elementowych malejących podciagów ciągu. Dodatkowy haczyk polega na tym, że podciąg ten niekoniecznie musi się składać z kolejnych wartości oryginalnego ciągu.

Przykład:

ciąg: 2 7 8 9 8 8 1 2, n = 3

poprawna odpowiedź: 4

wyjasnienie:

  • 2 7 8 9 8 8 1 2
  • 2 7 8 9 8 8 1 2
  • 2 7 8 9 8 8 1 2
  • 2 7 8 9 8 8 1 2
komentarz 1 dzień temu przez Whistleroosh Nałogowiec (37,700 p.)
Łatwo da się chyba znaleźć liczbę wszystkich podciągów malejących. Znalezienie liczby podciągów dla konkretnego n będzie trudniejsze

1 odpowiedź

0 głosów
odpowiedź 1 dzień temu przez reaktywny Nałogowiec (30,230 p.)
edycja 1 dzień temu przez reaktywny

To jest zadanie klasy O(n) lub O(n * logn). Bardzo proste IMO. Chyba, ze czegoś nie rozmiem....

 

Piszesz o wszystkich n-elementowych malejących podciągach. Dlaczego wszystkie podciągi są tutaj 3-elementowe? A co z 2-elementowymi?

Masz oryginalną treść zadania i czy to "wyjaśnienie" to jest Twoje, czy dołączone do zadania?

 

komentarz 1 dzień temu przez blackjajko Użytkownik (630 p.)
masz rację, zakreśliłem tylko te 3-elementowe, i rzeczywiście zadanie polega na znalezieniu tych 3-elementowych (niedopatrzenie podczas kopiowania kawałka treści zadania), ale ja chciałem uogólnić tą treść i znaleźć rozwiązanie dla każdej wartości n.
komentarz 1 dzień temu przez reaktywny Nałogowiec (30,230 p.)
Dla trójelementowych to jest dużo prostsze niż dla n w ogólnym przypadku. Wtedy n będzie z przedziału <2, 10>.
komentarz 1 dzień temu przez blackjajko Użytkownik (630 p.)
a masz jakiś konkretny plan na zrobienie tego zadania dla trójek?
komentarz 1 dzień temu przez reaktywny Nałogowiec (30,230 p.)

Robiłem podobne zadanie, tylko trzeba było znaleźć jeden najdłuższy ciąg malejący czy rosnący. U ciebie może być wiele trójelementowych, więc to trochę inaczej wygląda, ale zastanowię się i może wrzucę kod, ale nie w C++ :)

Spodobał mi się ten przykład, spróbuję go zrobić.

 

komentarz 18 godziny temu przez Whistleroosh Nałogowiec (37,700 p.)

Podobne pytania

0 głosów
1 odpowiedź 1,438 wizyt
+2 głosów
2 odpowiedzi 83 wizyt
pytanie zadane 4 listopada 2022 w C# przez JoannS Początkujący (250 p.)
0 głosów
2 odpowiedzi 226 wizyt

90,295 zapytań

138,894 odpowiedzi

311,078 komentarzy

60,009 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Sklep oferujący ćwiczenia JavaScript, PHP, rozmowy rekrutacyjne dla programistów i inne materiały

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...