Statyczne drzewo binarne i najdłuższy nieprzerwany ciąg
Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?
Zarejestruj się!

Statyczne drzewo binarne i najdłuższy nieprzerwany ciąg

AutorWiadomość
Temat założony przez niniejszego użytkownika
Statyczne drzewo binarne i najdłuższy nieprzerwany ciąg
» 2018-03-05 21:35:13
Witam, czy ktoś z tu obecnych byłby w stanie mi wytłumaczyć na czym dokładniej miałaby polegać metoda zapamiętywania najdłuższego nieprzerwanego ciągu od lewej i od prawej dla danego przedziału?
Więcej w zadaniu: https://main2.edu.pl/c/konkurs-podstaw-algorytmiki/p/zer3/
Nie umiem sobie wyobrazić jak ma to działać.
P-169798
» 2018-03-05 22:46:27
Olej podpowiedź. Po prostu wykonaj zadanie. Treść jest jasna. Jedyne co w tym zadaniu trzeba zrobić to napisać funkcję, która dla podanej tablicy wejściowej (np. 000100) wypisze ile najwięcej zer znalazłeś, które występują obok siebie. Reszta to formalność.
P-169803
» 2018-03-05 23:02:00
Chyba chodziło o wykonanie zadania szybciej niż naiwnie. Z drugiej strony, nie podali limitu czasu..

Nie umiem sobie wyobrazić jak ma to działać.
A umiesz sobie wyobrazić, co ma robić ten program?
P-169804
Temat założony przez niniejszego użytkownika
» 2018-03-06 07:45:56
Tak ale ja właśnie skupiam się na podpowiedzi bo w wyższych węzłach mam problem z podliczeniem np dla 0001 będzie 3 a dla 0010 bd 2 i twraz pojawia się problem jak go rozróżnić albo wydedukować na bazie samych informacji jaki jest najdłuższy ciąg od lewej i prawej, chyba ze rzeczywiście powinienem się skupić na innym rozwiązaniu
P-169806
» 2018-03-06 08:45:08
1.
za bardzo sie skupiasz nad jakimś szczególnym przypadkiem :)
wyobraź sobie inny przypadek
np.

20 10
01000100001000001000
.... // 10 kolejnych zmian

a następnie jakiś jeszcze inny
np.
100 50
0100010000100000100001000100001000001000010001000010000010000100010000100000100001000100001000001000
.... // 50 kolejnych zmian


2.
zadanie można zrealizować dla dowolnego kontenera
np. tablica, ciąg znaków,  string, vector, ...

Frazy, które należy wpisać w wyszukiwarkę google:

http://www.if.uz.zgora.pl​/~mdudek/lab2_cz4.pdf

3.
napisz funkcje która liczy ilość kolejnych 0 w użytym kontenerze
np dla tablicy
int DlugoscCiagu(int tab[] , int wielkoscTablicy)
{
  ...
  }
  return maxDlugosc;
}

4.
Algorytm :
* wprowadzasz zmianę do kontenera przechowujacej ciąg
* wywołujesz ww funkcję
P-169807
Temat założony przez niniejszego użytkownika
» 2018-03-06 15:54:16
Niestety jest tak jak myślałem, naiwne sprawdzanie ciągu przekroczy limity czasu w sprawdzarce bo wtedy tak naprawdę jest to O(n*k)
Generalnie to zadanie dotyczy statycznych drzew binarnych z tego co mi wiadomo.

Czy ktoś ma jakiś pomysł jak Moznaby to rozwiązać za pomocą drzewa?
P-169808
» 2018-03-06 20:35:31
Czy ktoś ma jakiś pomysł jak Moznaby to rozwiązać za pomocą drzewa?
0100010000100000100001000100001000001000010001000010000010000100010000100000100001000100001000001000
Jak byś ten ciąg zapisał krócej, tak by dało się go potem odtworzyć? I jak byś określił wartość n-tego bitu w ciągu na podstawie skompresowanego zapisu, bez odtwarzania oryginału? Te podpowiedzi powinny ci wystarczyć. Nie próbuj tu jeszcze wciskać drzewa.
P-169817
Temat założony przez niniejszego użytkownika
» 2018-03-06 21:19:15
Ooo możnaby go skompresować i wtedy nie trzeba by przeszukiwać tych n elementów za każdym razem. Dobrze rozumiem?
P-169818
« 1 » 2
 Strona 1 z 2Następna strona