Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Zagadnienie do matury rozszerzonej z informatyki: "rekurencyjnego tworzenia fraktali: drzewo binarne"

Ostatnio zmodyfikowano 2023-03-23 08:54
Autor Wiadomość
baziorek
Temat założony przez niniejszego użytkownika
Zagadnienie do matury rozszerzonej z informatyki: "rekurencyjnego tworzenia fraktali: drzewo binarne"
» 2023-03-16 20:59:03
Pomagam pewnej osobie w przygotowaniu do matury z informatyki rozszerzonej. Wśród zagadnień jest coś takiego jak w temacie. Raczej wątpię aby to miało być skomplikowane zagadnienie. Ale jak tam poszukałem to znalazłem:

Ten drugi przykład z pythona udało mi się jakoś uczytelnić w C++:
C/C++
#include <iostream>
#include <string>
#include <cmath>

using namespace std;

constexpr const char L = '/';
constexpr const char R = '\\';


string multipleString( string s, int howManyTimes )
{
   
auto returnText = s;
   
for( int i = 1; i < howManyTimes; ++i )
       
 returnText += s;
   
   
return returnText;
}

string centerText( const string & s, int width )
{
   
if( width < s.size() )
       
 return s;
   
   
auto spacesCount =( width - s.size() ) / 2.;
   
auto textLeft = string( floor( spacesCount ), ' ' );
   
auto textRight = string( ceil( spacesCount ), ' ' );
   
return textLeft + s + textRight;
}

void drawThree( int characters4Three )
{
   
for( int size = characters4Three, row = characters4Three; row > 1; row--, size /= size / row )
   
{
       
auto spacesBetweenSlashCount = size - row;
       
auto spaces = string( spacesBetweenSlashCount * 2, ' ' );
       
auto slashesPair = L + spaces + R;
       
auto slashesCentered = centerText( slashesPair, size * 2 );
       
auto slashPairCount = characters4Three / size;
       
auto multipleSlashes = multipleString( slashesCentered, slashPairCount );
       
cout << multipleSlashes << endl;
   
}
}

int main()
{
   
drawThree( 64 );
}
Jednak w pytaniu jest aby zrobić to rekurencyjnie. Stąd pytanie czy ktoś ma jakiś pomysł na tyle prosty aby był dla maturzystów?

Mi przychodzi do głowy aby zrobić przez macierz z "wymazywaniem", tak jak dywan Sierpińskiego.

W ogóle dziwi mnie, że jest takie zagadnienie do matury, którego nigdzie nie ma przykładu, nawet w innych językach programowania (chyba, że po rusku, bo w tym języku nie szukałem).
P-180057
pekfos
» 2023-03-16 22:14:51
Nigdzie nie jest napisane że to ma być w konsoli. Może system Lindenmayera? Chociaż jest prosty, to nie wyobrażam sobie że maturzysta go wyciągnie z rękawa. Twoje rozwiązanie mało przypomina fraktal, wygląda jak trójkąt Sierpińskiego, jakby usunąć z niego większość fraktala.

Jednak w pytaniu jest aby zrobić to rekurencyjnie. Stąd pytanie czy ktoś ma jakiś pomysł na tyle prosty aby był dla maturzystów?
Dodaj przestawianie kursora konsoli, albo generuj całość w tablicy i dopiero wypisuj. Chodzi żeby mieć rysowanie na X,Y. Drzewo na N+1 poziomów to dwa drzewa N poziomów i linie na połączenie ich. Pewnie nawet prościej to zrobić tak niż iteracyjne.

Zakodzone w 10 minut, więc dla maturzysty może 30? Powinno być wykonalne.
C/C++
#include <cstdio>
#include <cstring>

#define MAX 68

void drawTreeAt( char( * buf )[ MAX ], int level, int x, int y )
{
   
if( level > 0 )
   
{
       
int base = 1 << level;
       
       
for( int i = 0; i < base / 2; ++i )
       
{
           
buf[ y + i ][ x + base - i - 1 ] = '/';
           
buf[ y + i ][ x + base + i ] = '\\';
       
}
       
       
drawTreeAt( buf, level - 1, x, y + base / 2 );
       
drawTreeAt( buf, level - 1, x + base, y + base / 2 );
   
}
   
else
   
{
       
buf[ y ][ x ] = '/';
       
buf[ y ][ x + 1 ] = '\\';
   
}
}

int main()
{
   
char buf[ MAX ][ MAX ];
   
   
for( int level = 0, eh = MAX / 2; eh; ++level, eh >>= 1 )
   
{
       
memset( buf, ' ', sizeof buf );
       
drawTreeAt( buf, level, 0, 0 );
       
       
for( int y = 0; y < MAX; ++y )
       
{
           
buf[ y ][ MAX - 1 ] = 0;
           
if( char * end = strrchr( buf[ y ], '\\' ) )
               
 end[ 1 ] = 0;
           
else
               
 break;
           
           
puts( buf[ y ] );
       
}
       
       
puts( "" );
   
}
}

W ogóle dziwi mnie, że jest takie zagadnienie do matury, którego nigdzie nie ma przykładu, nawet w innych językach programowania
To byłoby dziwne gdyby maturzyści potrafili tylko reprodukować gotowce. Czy to dlatego przeportowałeś kod z pythona zamiast napisać go od początku samemu, mimo że "zadanie nie powinno być skomplikowane"? Ciężka sprawa jak nie można znaleźć w necie kodu który spełnia wszystkie parametry zadania :>
P-180058
baziorek
Temat założony przez niniejszego użytkownika
» 2023-03-17 07:01:38
Dodaj przestawianie kursora konsoli, albo generuj całość w tablicy i dopiero wypisuj. Chodzi żeby mieć rysowanie na X,Y. Drzewo na N+1 poziomów to dwa drzewa N poziomów i linie na połączenie ich. Pewnie nawet prościej to zrobić tak niż iteracyjne.
Bardzo dziękuję za sugestię! Oraz też dziękuję za przykładowy kod!
P-180059
tBane
» 2023-03-17 11:04:24
mnie się wydaję, że tu chodzi o sposob myślenia tzn problem z wymyslaniem, tworzeniem wzorow?

Jak drzewo binarne wyglada wiesz?

Poziom drzewa | wierzcholki
1 | 1
2 | 2
3 | 4
4 | 8
5 | 16

Teraz stworz wzór na ilość wierzcholkow... (jeśli nie wiesz.. to 2^(n-1)
Adekwatnie nalezy wymyślić wzór na pozycję x dla rysowania wierzcholka w danym poziomie...

jesli max 16 wierzcholkow to dla 5 poziomu rysujemy pierwszy wierzcholek w pozycji pozycja.pierwszyWierzcholek-16/2... a ostatni w pozycji pozycja.pierwszyWierzcholek+16/2
P-180060
baziorek
Temat założony przez niniejszego użytkownika
» 2023-03-23 08:54:08
mnie się wydaję, że tu chodzi o sposob myślenia tzn problem z wymyslaniem, tworzeniem wzorow?
Bardzo dziękuję za fajne rozpisanie matematycznie, faktycznie tak jest.

Jak drzewo binarne wyglada wiesz?
Wiem, nawet natrafiłem na bibliotekę, która je generuje, tam można podejrzeć:
https://github.com/YoussefRaafatNasry/bst-ascii-visualization
niestety to robi więcej niż potrzeba (bo nie tylko wizualizuje), przez co kod jest dość skomplikowany jak na maturzystę.

Jeszcze pomyślę nad tym, jak mi się uda to tutaj wrzucę dla potomnych.
P-180081
« 1 »
  Strona 1 z 1