• 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

VPS Starter Arubacloud
+1 głos
124 wizyt
pytanie zadane 25 stycznia 2023 w C i C++ przez diedassel Użytkownik (570 p.)
edycja 25 stycznia 2023 przez diedassel

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 26 stycznia 2023 przez Whistleroosh Maniak (56,900 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ź 25 stycznia 2023 przez reaktywny Nałogowiec (40,650 p.)
edycja 25 stycznia 2023 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 25 stycznia 2023 przez diedassel Użytkownik (570 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 25 stycznia 2023 przez reaktywny Nałogowiec (40,650 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 25 stycznia 2023 przez diedassel Użytkownik (570 p.)
a masz jakiś konkretny plan na zrobienie tego zadania dla trójek?
komentarz 25 stycznia 2023 przez reaktywny Nałogowiec (40,650 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ć.

 

1
komentarz 26 stycznia 2023 przez Whistleroosh Maniak (56,900 p.)

Podobne pytania

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

92,453 zapytań

141,262 odpowiedzi

319,088 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...