Fun-Soft - Programmierforum

Autor

Thread - Seiten: > 1 < [ 2 ]

000
03.06.2003, 16:59 Uhr
~guzi
Gast

hallo,
ich habe eine nette Programmieraufgabe:
auf dem Sender neun LIVE gibt es ein Spiel, wo man Punkte zu Quadrate verbinden muss. Es ist eine quadratische Matrix gegeben mit Punkten. Das Ziel ist nun alle Quadrate zu zählen die man bilden kann.

zb. (1=Punkt, 0= leer)

11000011
11111111
01000010
01011010
01011010
01000010
11111111
11000011

-> hier sind es 33!
viel Spass

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

001
03.06.2003, 17:54 Uhr
~0xdeadbeef
Gast

33 Rechtecke, aber nur 16 Quadrate. Mein Code dazu:

C++:

int count_squares(int **mat, int width, int height) {
    int ux, uy, lx, ret;
    ret = 0;
    for(ux = 0; ux < width; ++ux)
        for(uy = 0; uy < height; ++uy)
            for(lx = ux+1; lx < width; ++lx)
                if(uy+lx < height &&
                    mat[ux][uy]    &&
                    mat[lx][uy]    &&
                    mat[ux][uy+lx] &&
                    mat[lx][uy+lx]) ++ret;
    return ret;
}

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

002
03.06.2003, 17:59 Uhr
~0xdeadbeef
Gast

Ne, halt. Rechtecke gibts sogar 105:

C++:

int count_rectangles(int **mat, int width, int height) {
    int ux, uy, lx, ly, ret;
    ret = 0;
    for(ux = 0; ux < width; ++ux)
        for(uy = 0; uy < height; ++uy)
            for(lx = ux + 1; lx < width; ++lx)
                for(ly = uy + 1; ly < height; ++ly)
                    if (mat[ux][uy] &&
                        mat[lx][uy] &&
                        mat[ux][ly] &&
                        mat[lx][ly]) ++ret;
    return ret;
}

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

003
03.06.2003, 18:05 Uhr
ao

(Operator)

C++:

//#define _DEBUG

#include <assert.h>
#include <stdio.h>

#define MAX 8

int nM [MAX][MAX] =
{
    {  1,1,0,0,0,0,1,1}
    , {1,1,1,1,1,1,1,1}
    , {0,1,0,0,0,0,1,0}
    , {0,1,0,1,1,0,1,0}
    , {0,1,0,1,1,0,1,0}
    , {0,1,0,0,0,0,1,0}
    , {1,1,1,1,1,1,1,1}
    , {1,1,0,0,0,0,1,1}
};

// -------------------------------------
int Max (int nX, int nY)
{
    return (nX > nY) ? nX : nY;
}

// -------------------------------------
int MaxW (int nX, int nY)
{
    return MAX - Max (nX, nY);
}

// -------------------------------------
bool IsSquare (int nX, int nY, int nW)
{
    assert (nX>=0);
    assert (nY>=0);
    assert (nX+nW<MAX);
    assert (nY+nW<MAX);

    bool bResult = nM[nX][nY] && nM[nX][nY+nW] && nM[nX+nW][nY] && nM[nX+nW][nY+nW];

#ifdef _DEBUG
    printf ("\n  X = %d  Y = %d  W = %d   %c %c %c %c   %c",
            nX, nY, nW,
            nM[nX][nY] ? 'x' : ' ',
            nM[nX][nY+nW] ? 'x' : ' ',
            nM[nX+nW][nY] ? 'x' : ' ',
            nM[nX+nW][nY+nW] ? 'x' : ' ',
            bResult ? 'Q' : ' '
            );
#endif

    return bResult;
}

// -------------------------------------
int main (void)
{
    int nX;
    int nY;
    int nW;
    int nCount = 0;

    for (nX = 0; nX < MAX; nX++)
    {
        for (nY = 0; nY < MAX; nY++)
        {
            for (nW = 1; nW < MaxW (nX, nY); nW++)
            {
                if (IsSquare (nX, nY, nW))
                {
                    nCount++;
                }
            }

        }
    }

    printf ("\n %d \n", nCount);

    return 0;
}

Ich komme auf 23 Quadrate.

AO

Dieser Post wurde am 03.06.2003 um 18:06 Uhr von ao editiert.

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

004
03.06.2003, 18:54 Uhr
~guzi
Gast

so leid es mir tut, aber es sind 33 Quadrate. wieviele Rechtecke es sind, ist eine andere Frage.

Achtung das:
010
101
010
wäre auch eins!

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

005
04.06.2003, 08:58 Uhr
~urform
Gast

Soll das hier auch als Quadrat gelten?

C++:

01000
00001
00000
10000
00010

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

006
04.06.2003, 11:58 Uhr
~guzi
Gast

ja, alle Seiten sind gleich lang und wäre ein Zeichen hoch wie breit wäre der Winkel auch 90°.
wie will man sonst dem Computer die Realitiv beschreiben als mit 1 und 0?

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

007
04.06.2003, 13:17 Uhr
virtual
Sexiest Bit alive
(Operator)

Na, wenn sich sonst niemand weiter traut

C++:

#include <stdio.h>

char* quadrat[] =
{
"11000011",
"11111111",
"01000010",
"01011010",
"01011010",
"01000010",
"11111111",
"11000011"
};

int main()
{
    int breite = strlen(quadrat[0]);
    int hoehe = sizeof(quadrat)/sizeof(quadrat[0]);
    int x,y,dx,dy;
    int q = 0;

    printf("So sehen die Eingangsdaten aus:\n");
    for(y=0; y<hoehe; ++y)
        printf("%s\n", quadrat[y]);

    printf("Das sind die enthaltenen Quadrate (Links oben ist (0,0), rechts unten is (%d,%d):\n",
           breite-1, hoehe-1);
    for(x=0; x<breite; ++x)
        for(y=0; y<hoehe; ++y)
            if (quadrat[y][x]=='1')
            {
                for(dx=1; dx+x<breite; ++dx)
                    for(dy=0; dy+y<hoehe; ++dy)
                    {
                        if (y+dy>=hoehe || y+dy+dx>=hoehe || y+dx>=hoehe ||
                            x+dx>=breite || x+dx-dy>=breite || x+dx-dy<0 ||
                            x-dy<0)
                        {
                            break;
                        }
                        if (quadrat[y+dy][x+dx]=='1' &&
                            quadrat[y+dy+dx][x+dx-dy]=='1' &&
                            quadrat[y+dx][x-dy]=='1')
                        {
                            printf("Quadrat %d: (%d,%d), (%d,%d), (%d, %d), (%d,%d)\n",
                                    ++q,
                                    x, y,
                                    x+dx, y+dy,
                                    x+dx-dy, y+dy+dx,
                                    x-dy, y+dx);
                        }
                    }

            }

    printf("%d Quadrate gefunden.\n", q);
}

--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

008
04.06.2003, 13:27 Uhr
virtual
Sexiest Bit alive
(Operator)

Nachtrag:
1. Ich wußte garnicht, daß NeunLive Zuschauer hat.
2. Sollte jetzt irgendjemand mit Hilfe der obigen Lösung bei NeunLive abräumen, dann würde ich mich über eine Gewinnbeteiligung freuen. Ich würde sie sogar anstandshalber erwarten

3. Ich habe das Programm nicht in die Tiefe getestet, es brint einfach nur für die gegebenen Eingangsdaten das korrekte Resultat:

Code:

So sehen die Eingangsdaten aus:
11000011
11111111
01000010
01011010
01011010
01000010
11111111
11000011
Das sind die enthaltenen Quadrate (Links oben ist (0,0), rechts unten is (7,7):
Quadrat 1: (0,0), (1,0), (1, 1), (0,1)
Quadrat 2: (0,0), (6,0), (6, 6), (0,6)
Quadrat 3: (0,0), (7,0), (7, 7), (0,7)
Quadrat 4: (0,1), (5,1), (5, 6), (0,6)
Quadrat 5: (0,1), (6,1), (6, 7), (0,7)
Quadrat 6: (0,6), (1,6), (1, 7), (0,7)
Quadrat 7: (1,0), (2,1), (1, 2), (0,1)
Quadrat 8: (1,0), (6,0), (6, 5), (1,5)
Quadrat 9: (1,0), (7,0), (7, 6), (1,6)
Quadrat 10: (1,0), (7,1), (6, 7), (0,6)
Quadrat 11: (1,1), (3,1), (3, 3), (1,3)
Quadrat 12: (1,1), (4,1), (4, 4), (1,4)
Quadrat 13: (1,1), (6,1), (6, 6), (1,6)
Quadrat 14: (1,1), (7,1), (7, 7), (1,7)
Quadrat 15: (1,2), (6,2), (6, 7), (1,7)
Quadrat 16: (1,3), (4,3), (4, 6), (1,6)
Quadrat 17: (1,4), (3,4), (3, 6), (1,6)
Quadrat 18: (1,5), (2,6), (1, 7), (0,6)
Quadrat 19: (2,1), (6,2), (5, 6), (1,5)
Quadrat 20: (2,1), (7,1), (7, 6), (2,6)
Quadrat 21: (3,1), (6,1), (6, 4), (3,4)
Quadrat 22: (3,1), (6,3), (4, 6), (1,4)
Quadrat 23: (3,3), (4,3), (4, 4), (3,4)
Quadrat 24: (3,3), (6,3), (6, 6), (3,6)
Quadrat 25: (4,1), (6,1), (6, 3), (4,3)
Quadrat 26: (4,1), (6,4), (3, 6), (1,3)
Quadrat 27: (4,4), (6,4), (6, 6), (4,6)
Quadrat 28: (5,1), (6,5), (2, 6), (1,2)
Quadrat 29: (6,0), (7,0), (7, 1), (6,1)
Quadrat 30: (6,0), (7,1), (6, 2), (5,1)
Quadrat 31: (6,0), (7,6), (1, 7), (0,1)
Quadrat 32: (6,5), (7,6), (6, 7), (5,6)
Quadrat 33: (6,6), (7,6), (7, 7), (6,7)
33 Quadrate gefunden.

--
Gruß, virtual
Quote of the Month
Ich eß' nur was ein Gesicht hat (Creme 21)

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

009
04.06.2003, 14:16 Uhr
~guzi
Gast

NeunLive ist mein Lieblingssender (ab 24:00)

teste mal:
11111111
11111110
11111100
11111000
11110000
11100000
11000000
10000000

-> 66 Quadrate

Profil || Private Message || Suche

Download || Zitatantwort || Editieren || Löschen || IP

Seiten: > 1 < [ 2 ] [ Rätselecke ]

ThWBoard 2.73 FloSoft-Edition
© by Paul Baecher & Felix Gonschorek (www.thwboard.de)

Anpassungen des Forums
© by Flo-Soft (www.flo-soft.de)

Sie sind Besucher: