Awesome, awesome, awesome.

[Patrunjel]

Tocmai am terminat de rezolvat o problema care, dupa parerea mea, e cea mai misto din toate pe care le-am intalnit. Am scris deja ce aveam de scris pe dreamincode, dau direct copy-paste, e mult si pur si simplu nu are rost:

The variables, comments and everything is in romanian, just compile it

#include<iostream>
using namespace std;

bool a[4097][4097];
struct matrice{
    int x,y,l;
};

void divimp(matrice m){
    if(m.l==2){
        a[m.y][m.x]=1;
    }
    else{
        matrice m1,m2,m3,m4;
        //stabilesc m1(stanga-sus)
        m1.x=m.x;
        m1.y=m.y;
        m1.l=m.l/2;
        //stabilesc m2(stanga-jos)
        m2.y=m.y-m1.l;
        m2.x=m.x;
        m2.l=m1.l;
        //stabilesc m3(dreapta-sus)
        m3.y=m1.y;
        m3.l=m1.l;
        m3.x=m.x+m3.l;
        //stabilesc m4(dreapta-jos)
        m4.x=m3.x;
        m4.y=m2.y;
        m4.l=m1.l;
        /*Transform 0-urile in 1 in m1*/
        for(int i=0;i<m1.l;i++)
            for(int j=0;j<m1.l;j++){
                a[m1.y-i][m1.x+j]=1;
            }
        divimp(m2);divimp(m3);divimp(m4);divimp(m1);
    }
}

int main(){
    int n,i,j;
    matrice mat;
    cout<<"n=";cin>>n;
    mat.x=1;mat.y=n;mat.l=n;
    divimp(mat);
    for(i=mat.l;i>0;i--){
        for(j=1;j<=mat.l;j++)
            cout<<a[i][j];
        cout<<endl;
    }
    return 0;
}

You just have to give n values that look like this :2^k, whatever k is (an integer). For example, n=2;n=4;n=8;n=16;n=32.

For values larger that 128 (like 4096, that I'm waiting now to compute ) you compile and run, and right-click on the blue bar above the actual console, and click properties. From there you go to the "Font" tab and choose the smallest one, then you go to "Layout". There you will have to experiment with the Window Size values so that it will fit your monitor. Also, on the "Layout" tab,(and this is the most important, if you want to see all the shape!)set both the buffer size values to 5000 (you don't use all of it if you give n the value 4096, but your PC will probably take it without complaint). Then just click OK twice and done.

Now, awesome things that you should know: You have in front of you n*n 1s and 0s (for 4096 that's 16,777,216 digits!), and you will see triangles of k distinct sizes (k from the n=2^k input condition mentioned above). Again, for 4096 that's 10 triangle sizes.Also, if you would store the result of n=4096 in a text file, considering that you declared the array as an int (4bytes/int), the file will be 67,108,864 bytes large. (that's 64mb of 1s and 0s!). Also, the whole thing took approx 400seconds to be generated, on my computer. (only a fraction of that time, 0.422s was needed to actually compute the 4096x4096 array, the rest was used to put the information on the screen.) Computers are awesome!

So, go on, enjoy the power of fractals!

Daca e careva interesat de problema (sa o rezolve singur, sau mai stiu eu), sa spuna, si copii cerinta aici (n-am mai copiat-o acuma ca mi-e lene, trebuie sa copii din carte, nu pot da copy-paste )

[totti93]

Arata fain matricea... Nu stiu ce se cere sa faci mai exact, de aceea m-ar interesaza cerinta...

[cmiN]

Seamana cu taietura maxima sau cel mai mare dreptunghi, triunghi cuprins intre "gauri" ceva de genul.

[Patrunjel]

Problema suna cam asa:

Consideram o valoare naturala n, de forma 2^k. Sa se construiasca, in memorie, o matrice a patratica de ordin n, ale carei elemente apartin multimii {0,1}. In matrice, elementele egale cu 1 sunt cele situate in subtabloul stanga sus, de latura n div 2. Procesul se repeta pentru cele trei subtablouri ramase, pana la obtinerea unor subtablouri de latura 1.

Realizati un subprogram care construieste matricea a dupa regula descrisa.