Statyczne drzewo binarne i najdłuższy nieprzerwany ciąg
Ostatnio zmodyfikowano 2018-03-07 12:39
Mati3k01 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ć. |
|
DejaVu |
» 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ść. |
|
pekfos |
» 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? |
|
Mati3k01 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 |
|
darko202 |
» 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, ... http://www.if.uz.zgora.pl/~mdudek/lab2_cz4.pdf3. 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ę |
|
Mati3k01 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? |
|
pekfos |
» 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. |
|
Mati3k01 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? |
|
« 1 » 2 |