Witam,
mam kompletne drzewo binarne o \(\displaystyle{ p}\) poziomach. I muszę odpowiedzieć, na którym poziomie leży element \(\displaystyle{ 229}\). Jest na to jakiś wzór czy trzeba sprawdzać po kolei każdy poziom. Pomocy, jutro mam klasówkę!
Na którym poziomie w drzewie leży element?
-
- Użytkownik
- Posty: 1
- Rejestracja: 15 lis 2021, o 09:12
- Płeć: Mężczyzna
- wiek: 31
- Lokalizacja: https://forexn.com/pl/brokers/
Na którym poziomie w drzewie leży element?
Ostatnio zmieniony 17 lis 2021, o 12:12 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości. Temat umieszczono w złym dziale.
Powód: Poprawa wiadomości. Temat umieszczono w złym dziale.
-
- Użytkownik
- Posty: 4
- Rejestracja: 12 lis 2021, o 22:51
- Płeć: Kobieta
- wiek: 28
- Podziękował: 1 raz
Re: Na którym poziomie w drzewie leży element?
Obczaiłam co to jest drzewo binarne kompletne. Skoro ten element na samej górze to jest poziom zero to wygląda to tak, że liczbę elementów na danym poziomie drzewa można policzyć ze wzoru \(\displaystyle{ 2^{p} }\) (o ile jest cały zapełniony).
A to mi wygląda na ciąg geometryczny, więc znalazłam sobie na necie wzór na sumę ciągu geometrycznego
\(\displaystyle{ S_{n} =a _{1} \cdot \frac{1- q^{n} }{1-q} }\)
ale w naszym ciągu trzeba doliczyć jeszcze ten element z poziomu zerowego (więc dodałam jedynkę na początku) i to będzie
\(\displaystyle{ S _{p} =1+2 \cdot \frac{1- 2^{p} }{1-2}}\)
i dalej liczę
\(\displaystyle{ 1+2 \cdot \frac{1- 2^{p} }{1-2}>229}\) ,gdzie \(\displaystyle{ p}\) dla nas oznacza numer poziomu, więc trzeba dodać że szukamy tylko najmniejszej liczby naturalnej spełniającej to równanie, nie wiem tylko jak to zapisać w sposób matematyczny
\(\displaystyle{ 1-2(1- 2^{p}) >229}\)
\(\displaystyle{ 1- 2^{p} <-114}\)
\(\displaystyle{ 2^{p}>115 }\)
\(\displaystyle{ 2^{7} >115> 2^{6} }\)
A więc element 229 leży na poziomie 7.
A to mi wygląda na ciąg geometryczny, więc znalazłam sobie na necie wzór na sumę ciągu geometrycznego
\(\displaystyle{ S_{n} =a _{1} \cdot \frac{1- q^{n} }{1-q} }\)
ale w naszym ciągu trzeba doliczyć jeszcze ten element z poziomu zerowego (więc dodałam jedynkę na początku) i to będzie
\(\displaystyle{ S _{p} =1+2 \cdot \frac{1- 2^{p} }{1-2}}\)
i dalej liczę
\(\displaystyle{ 1+2 \cdot \frac{1- 2^{p} }{1-2}>229}\) ,gdzie \(\displaystyle{ p}\) dla nas oznacza numer poziomu, więc trzeba dodać że szukamy tylko najmniejszej liczby naturalnej spełniającej to równanie, nie wiem tylko jak to zapisać w sposób matematyczny
\(\displaystyle{ 1-2(1- 2^{p}) >229}\)
\(\displaystyle{ 1- 2^{p} <-114}\)
\(\displaystyle{ 2^{p}>115 }\)
\(\displaystyle{ 2^{7} >115> 2^{6} }\)
A więc element 229 leży na poziomie 7.