• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

question-closed C++, przykład funkcji rekurencyjnej

VPS Starter Arubacloud
+1 głos
274 wizyt
pytanie zadane 18 lutego 2018 w C i C++ przez Jakub 0 Pasjonat (23,120 p.)
zamknięte 18 lutego 2018 przez Jakub 0

Witam, zaraz pokażę kod i wynik działania pewnej funkcji wykorzystującej rekursje. Ogólnie rozumiem zasadę jej działania ale mam problem ze zrozumieniem jednego szczegółu samego programu:

#include <iostream>	

const int Len = 66; //musi być podzielna przez 2 
const int Divs = 6; //poziomy

void subdivide(char ar[], int low, int hight, int level) {
	if (level == 0) return;

	int mid = (hight + low) / 2;
	ar[mid] = '|';

	subdivide(ar, low, mid, level - 1);
	subdivide(ar, mid, hight, level - 1);
}

int main(){
	char ruler[Len];
	int i;

	int max = Len - 2; //-2 bo -1 to NUL
	int min = 0;

	for (i = 1; i < max; i++) //mniej od Len-2 bo konec to NUL aprzed koncem jeszcze znak '|'
		ruler[i] = ' ';
	ruler[Len - 1] = '\0';

	ruler[min] = ruler[max] = '|';

	std::cout << ruler << std::endl;
	for (i = 1; i <= Divs; i++) {
		subdivide(ruler, min, max, i);
		std::cout << ruler << std::endl;

		for (int j = 1; j < max; j++)
			ruler[j] = ' ';
	}
	return 0;
}

Wynik działania jest następujący:

const int Len = 66;

Długość to myślę że sprawa zrozumiała, mamy 66 znaków w tym jeden na NUL a więc 65, czyli indeksy tej tablicy znaków są w zakresie od 0-64

const int Divs = 6; 

Poziomy, ilość wywołań rekurencyjnych by zapełnić cały łańcuch znakami '|'. Korzystamy z metody dziel i zwyciężaj więc ilość działających w tle wywołujących się funkcji rośnie geometrycznie. Mamy 6 poziomów a 2^6 wynosi 64 a więc jest to liczba potrzebna by zapełnić cały łańcuch tymi znakami. Tu jest problem, książka z której korzystam upiera się że mamy 64 pól do zapełnienia więc liczba 6 jest poprawna (i jest poprawna w działaniu). Jednak ja tu czegoś nie rozumiem:

Mamy łańcuch który mieści 65 znaków a nie 64 (66 - 1 na NUL = 65), według mnie to się nie zgadza. To fakt że 2 elementy tablicy są już z góry zapełnione, indeks zerowy i 64 a więc w sumie pozostaje nam 63 pola do zapełnienia. Teraz za to ta liczba wydaja się za mała...

Z góry dziękuje za pomoc, jestem dość słaby z matmy i to może mieć wpływ :/

komentarz zamknięcia: już znam wytłumaczenie

1 odpowiedź

0 głosów
odpowiedź 18 lutego 2018 przez Piotr Batko Stary wyjadacz (13,190 p.)
wybrane 18 lutego 2018 przez Jakub 0
 
Najlepsza

Tyle kresek co wrzuciłeś to za dużo na moją głowę. Zobacz na listing niżej, zmniejszyłem liczbę kresek i trochę mi się rozjaśniło :)

|               | <- start
|       |       | <- poziom 1.
|   |   |   |   | <- poziom 2.
| | | | | | | | | <- poziom 3.
0 1 2 3 4 5 6 7 8

Tablica do przechowania takiego stringa potrzebuje mieć rozmiar 10 (9 kresek + '\0'). Na starcie na pozycje min(0) i max(8 = 10 - 2) wpisywane są kreski (zobacz u siebie w kodzie linijka 27.).

(...) ilość działających w tle wywołujących się funkcji rośnie geometrycznie. Mamy 6 poziomów a 2^6 wynosi 64 (...)

  •  Gdy jesteśmy na poziomie 1 odpalamy 1 funkcję.
  •  Gdy jesteśmy na poziomie 2 odpalamy 2 kolejne funkcje (mamy już w sumie 3).
  •  Gdy jesteśmy na poziomie 3 odpalamy 4 kolejne funkcje (mamy już w sumie 7).

Więc na 3 poziomy rekurencji, a wywołaliśmy 7 funkcji. Można by to policzyć ze wzoru: 2^poziom - 1.

Podsumowując: tablica 10 elementów = 2 (min i max) + 7 (funkcje rekurencyjne) + 1 ('\0'). Mógłbyś rozmiar potrzebnej tablicy wyliczać tak:

const int Divs = 3; //poziomy
const int Len = 2 + pow(2, Divs)-1 + 1; //musi być podzielna przez 2
komentarz 18 lutego 2018 przez Jakub 0 Pasjonat (23,120 p.)
Dzięki, zwłaszcza za wzór. Przyda mi się :)

Podobne pytania

0 głosów
2 odpowiedzi 439 wizyt
pytanie zadane 17 grudnia 2017 w C i C++ przez corrot Nowicjusz (200 p.)
0 głosów
3 odpowiedzi 446 wizyt
pytanie zadane 3 września 2016 w C i C++ przez karmider013 Początkujący (340 p.)
0 głosów
2 odpowiedzi 181 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!

...