Skocz do zawartości

  •  
  • Mini kompendium
  • MimeTeX
  • Regulamin

Zdjęcie

Działania na zbiorach - jak mogę zrozumieć zadanie.

STUDIA

  • Nie możesz napisać tematu
  • Zaloguj się aby odpowiedzieć
2 odpowiedzi w tym temacie

#1 dorll

dorll

    Nowicjusz

  • Użytkownik
  • 1 postów
0
Neutralny
  • Płeć:Mężczyzna

Napisano 11.12.2013 - 13:26

Witam wszystkich,

Mam problem ze zrozumieniem pewnego zadania. Dziewczyna dostała zadanie z programowania w którym trzeba napisać pewien algorytm do zadania poniżej. Algorytm mogę jej stworzyć, tylko mam problem jak to zadanie zrozumieć/zrobić matematycznie.

 

Jego treść:

Dane są dwie tablice liczb całkowitych A i B o elementach uporządkowanych niemalejąco.
Rozmiar tablicy A >= rozmiaru tablicy B. Sprawdzić ile czy tablica B zawiera się w całości w
tablicy A (bez naruszania kolejności elementów tablicy B). Wskazana złożoność liniowa.
Np. dla A={1,2,2,2,3,4,4,4,5,8,10}, B={2,2,3,4,4,} własność jest spełniona.

 

 

Byłbym bardzo wdzięczny za jakąś podpowiedź, albo jeżeli nie proszę o wiele to matematyczne rozwiązanie tego zadania, a ja potem przeniosę je do vb.

 

Pozdrawiam,

GD


  • 0

Afroman

    Kombinator

  • Użytkownik
3
  • Płeć:Kobieta

Napisano 25.09.2011 - 17:55

#2 Ereinion

Ereinion

    Mega Rozkminiacz z Marsa

  • $Jr Admin
  • 2104 postów
1007
Starszy Wykładowca I
  • Płeć:Mężczyzna

Napisano 11.12.2013 - 13:49

Wyobraź sobie, że Twoja dziewczyna stoi przy pierwszym elemencie ciągu B i mówi Ci jaka to jest liczba. Ty zaczynasz iść wzdłuż ciągu A i patrzysz kolejno czy któraś z mijanych liczb jest równa tej, którą podała Ci dziewczyna. W momencie, kiedy na taką trafisz, zatrzymujesz się, a dziewczyna przechodzi do kolejnego elementu ciągu B i mówi Ci jaka to liczba. Wtedy Ty kontynuujesz swoją wędrówkę wzdłuż ciągu A szukając teraz już innej liczby. Jak na nią trafisz, to zatrzymujesz się, dziewczyna przechodzi dalej itd. Jeśli dziewczyna przejdzie przez cały ciąg B wcześniej niż Ty przez A, to własność jest spełniona.

Złożoność czegoś takiego oczywiście jest liniowa ze wzgl na długość A.

Mam nadzieję, że opis jest dostatecznie jasny.


  • 2

#3 Jarekzulus

Jarekzulus

    Wielki Analityk

  • +Mods
  • Redaktor
  • 3508 postów
3091
Profesor
  • Płeć:Mężczyzna

Napisano 13.12.2013 - 03:11

Cóż, jak chcecie zbanujcie moją odpowiedz (mam tylko nadzieje ze nie dostanę minusa czy czegoś podobengo :) ale odpowiedz jest zaj....sta :)

 

pozdrawiam


  • 0

:wave: :wave: :wave: Jeśli rzuciłem choć promyczek światła na problem który postawiłeś - podziękuj. pre_1433974176__syg.jpgNad kreską