fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. // Teil 1a: Maximale Dimensionen definieren
  5. #define NMAX 8
  6. #define MMAX 8
  7.  
  8. // Teil 1b: Struktur Feld
  9. typedef struct {
  10.     int iN;                      // Anzahl der Zeilen
  11.     int iM;                      // Anzahl der Spalten
  12.     char archFeld[NMAX][MMAX];   // Zweidimensionales Array
  13. } Feld;
  14.  
  15. // Teil 1c: Struktur Tile
  16. typedef struct {
  17.     unsigned char chFarbCode;    // Farbcode der Tiles
  18.     int iAnzFelder;             // Anzahl der elementaren Felder
  19.     int iAnzRotationen;         // Anzahl der gültigen Rotationen
  20.     Feld arstRotationen[4];     // Array für max. 4 Rotationen
  21. } Tile;
  22.  
  23. // Teil 3l: Struktur TileList für verkettete Liste
  24. typedef struct TileList {
  25.     char chTileIndex;           // Index der Tile
  26.     char chRotIndex;            // Index der Rotation
  27.     char chXPos;                // X-Position
  28.     char chYPos;                // Y-Position
  29.     struct TileList *pstPrev;   // Zeiger auf vorheriges Element
  30. } TileList;
  31.  
  32. // Globale Variable für die beste Tile-Liste
  33. static TileList *pstBestTileList = NULL;
  34.  
  35. // Teil 1e: Funktion zum Ausgeben aller Tiles
  36. void PrtTiles(Tile arstTiles[]) {
  37.     printf("Zur Verfuegung stehende Tiles:\n");
  38.  
  39.     // Für jeden Tile-Typ
  40.     for (int i = 0; i < 4; i++) {
  41.         printf("Tile %d -- Rotation(en): %d; Felder: %d\n", 
  42.                i + 1, arstTiles[i].iAnzRotationen, arstTiles[i].iAnzFelder);
  43.  
  44.         // Finde maximale Höhe über alle Rotationen
  45.         int maxHoehe = 0;
  46.         for (int rot = 0; rot < arstTiles[i].iAnzRotationen; rot++) {
  47.             if (arstTiles[i].arstRotationen[rot].iN > maxHoehe) {
  48.                 maxHoehe = arstTiles[i].arstRotationen[rot].iN;
  49.             }
  50.         }
  51.  
  52.         // Ausgabe zeilenweise
  53.         for (int z = 0; z < maxHoehe; z++) {
  54.             // Für jede Rotation
  55.             for (int rot = 0; rot < arstTiles[i].iAnzRotationen; rot++) {
  56.                 Feld *pstRot = &arstTiles[i].arstRotationen[rot];
  57.  
  58.                 // Wenn diese Zeile für diese Rotation existiert
  59.                 if (z < pstRot->iN) {
  60.                     for (int s = 0; s < pstRot->iM; s++) {
  61.                         if (pstRot->archFeld[z][s] != 0) {
  62.                             printf("%c%c", arstTiles[i].chFarbCode, arstTiles[i].chFarbCode);
  63.                         } else {
  64.                             printf("  ");
  65.                         }
  66.                     }
  67.                 } else {
  68.                     // Leere Zeile für diese Rotation
  69.                     for (int s = 0; s < pstRot->iM; s++) {
  70.                         printf("  ");
  71.                     }
  72.                 }
  73.  
  74.                 // 4 Leerzeichen zwischen Rotationen (außer nach der letzten)
  75.                 if (rot < arstTiles[i].iAnzRotationen - 1) {
  76.                     printf("    ");
  77.                 }
  78.             }
  79.             printf("\n");
  80.         }
  81.     }
  82. }
  83.  
  84. // Teil 1g: Funktion zum Ausgeben des Feldes
  85. void PrtFeld(Feld *pstAktFeld, Tile arstTiles[]) {
  86.     printf("\nZu partitionierende Flaeche:\n");
  87.  
  88.     // Obere Begrenzung
  89.     printf("\xDA"); // ┌
  90.     for (int i = 0; i < pstAktFeld->iM * 2; i++) {
  91.         printf("\xC4"); // ─
  92.     }
  93.     printf("\xBF\n"); // ┐
  94.  
  95.     // Inhalt
  96.     for (int z = 0; z < pstAktFeld->iN; z++) {
  97.         printf("\xB3"); // │
  98.  
  99.         for (int s = 0; s < pstAktFeld->iM; s++) {
  100.             char tileIndex = pstAktFeld->archFeld[z][s];
  101.             if (tileIndex == 0) {
  102.                 printf("  ");
  103.             } else {
  104.                 // Tile-Index auf Array-Index umrechnen (1-basiert zu 0-basiert)
  105.                 unsigned char farbCode = arstTiles[tileIndex - 1].chFarbCode;
  106.                 printf("%c%c", farbCode, farbCode);
  107.             }
  108.         }
  109.  
  110.         printf("\xB3\n"); // │
  111.     }
  112.  
  113.     // Untere Begrenzung
  114.     printf("\xC0"); // └
  115.     for (int i = 0; i < pstAktFeld->iM * 2; i++) {
  116.         printf("\xC4"); // ─
  117.     }
  118.     printf("\xD9\n"); // ┘
  119. }
  120.  
  121. // Teil 2i1: Funktion zum Zählen der Felder
  122. int AnzFelder(char archFeld[NMAX][MMAX]) {
  123.     int anzahl = 0;
  124.     for (int z = 0; z < NMAX; z++) {
  125.         for (int s = 0; s < MMAX; s++) {
  126.             if (archFeld[z][s] != 0) {
  127.                 anzahl++;
  128.             }
  129.         }
  130.     }
  131.     return anzahl;
  132. }
  133.  
  134. // Teil 2i2: ORIGINALE Tilify-Funktion (NICHT OPTIMIERT)
  135. void Tilify(Feld *pstAktFeld, Tile arstTiles[], int iAnzFelder, int iAnzTiles) {
  136.     static int iMinAnzTiles = 999999; // Große Zahl für Initialisierung
  137.  
  138.     // Basisfall: Alle Felder sind belegt
  139.     if (iAnzFelder <= 0) {
  140.         if (iAnzTiles < iMinAnzTiles) {
  141.             iMinAnzTiles = iAnzTiles;
  142.             printf("Neue beste Loesung mit %d Tiles gefunden!\n", iAnzTiles);
  143.         }
  144.         return;
  145.     }
  146.  
  147.     // Für alle Tiles
  148.     for (int t = 0; t < 4; t++) {
  149.         // Für alle Rotationen
  150.         for (int r = 0; r < arstTiles[t].iAnzRotationen; r++) {
  151.             Feld *pstRot = &arstTiles[t].arstRotationen[r];
  152.  
  153.             // Für alle Positionen im Feld
  154.             for (int z = 0; z <= pstAktFeld->iN - pstRot->iN; z++) {
  155.                 for (int s = 0; s <= pstAktFeld->iM - pstRot->iM; s++) {
  156.                     // Prüfe ob Tile passt
  157.                     int passt = 1;
  158.                     for (int tz = 0; tz < pstRot->iN && passt; tz++) {
  159.                         for (int ts = 0; ts < pstRot->iM && passt; ts++) {
  160.                             if (pstRot->archFeld[tz][ts] != 0 && 
  161.                                 pstAktFeld->archFeld[z + tz][s + ts] == 0) {
  162.                                 passt = 0;
  163.                             }
  164.                         }
  165.                     }
  166.  
  167.                     if (passt) {
  168.                         // Kopiere Feld
  169.                         Feld stFeldProc = *pstAktFeld;
  170.  
  171.                         // Setze Tile-Felder auf 0
  172.                         for (int tz = 0; tz < pstRot->iN; tz++) {
  173.                             for (int ts = 0; ts < pstRot->iM; ts++) {
  174.                                 if (pstRot->archFeld[tz][ts] != 0) {
  175.                                     stFeldProc.archFeld[z + tz][s + ts] = 0;
  176.                                 }
  177.                             }
  178.                         }
  179.  
  180.                         // Rekursiver Aufruf
  181.                         Tilify(&stFeldProc, arstTiles, 
  182.                                iAnzFelder - arstTiles[t].iAnzFelder, 
  183.                                iAnzTiles + 1);
  184.                     }
  185.                 }
  186.             }
  187.         }
  188.     }
  189. }
  190.  
  191. // Teil 3k: OPTIMIERTE Tilify_Opt-Funktion mit Speicherung
  192. TileList* Tilify_Opt(Feld *pstAktFeld, Tile arstTiles[], int iAnzFelder, int iAnzTiles, TileList *pstTileList) {
  193.     static int iMinAnzTiles = 999999; // Große Zahl für Initialisierung
  194.     static int bInitialized = 0;
  195.  
  196.     // Reset bei erstem Aufruf
  197.     if (!bInitialized) {
  198.         iMinAnzTiles = 999999;
  199.         pstBestTileList = NULL;
  200.         bInitialized = 1;
  201.     }
  202.  
  203.     // Basisfall: Alle Felder sind belegt
  204.     if (iAnzFelder <= 0) {
  205.         if (iAnzTiles < iMinAnzTiles) {
  206.             iMinAnzTiles = iAnzTiles;
  207.             pstBestTileList = pstTileList;
  208.             printf("Neue beste Loesung mit %d Tiles gefunden!\n", iAnzTiles);
  209.         }
  210.         return pstTileList;
  211.     }
  212.  
  213.     // Optimierung 1: Wenn aktuelle Anzahl bereits >= Minimum, abbrechen
  214.     if (iAnzTiles >= iMinAnzTiles) {
  215.         return pstTileList;
  216.     }
  217.  
  218.     // Optimierung 2: Finde erstes freies Feld (von oben links)
  219.     int firstZ = -1, firstS = -1;
  220.     for (int z = 0; z < pstAktFeld->iN && firstZ == -1; z++) {
  221.         for (int s = 0; s < pstAktFeld->iM && firstZ == -1; s++) {
  222.             if (pstAktFeld->archFeld[z][s] != 0) {
  223.                 firstZ = z;
  224.                 firstS = s;
  225.             }
  226.         }
  227.     }
  228.  
  229.     if (firstZ == -1) return pstTileList; // Kein freies Feld gefunden
  230.  
  231.     // Optimierung 3: Größere Tiles zuerst probieren
  232.     for (int t = 3; t >= 0; t--) {
  233.         // Für alle Rotationen
  234.         for (int r = 0; r < arstTiles[t].iAnzRotationen; r++) {
  235.             Feld *pstRot = &arstTiles[t].arstRotationen[r];
  236.  
  237.             // Prüfe alle Positionen, wo das erste Feld des Tiles das gefundene freie Feld überdecken könnte
  238.             for (int tz = 0; tz < pstRot->iN; tz++) {
  239.                 for (int ts = 0; ts < pstRot->iM; ts++) {
  240.                     if (pstRot->archFeld[tz][ts] == 0) continue; // Dieses Feld des Tiles ist leer
  241.  
  242.                     // Position wo das Tile platziert werden müsste
  243.                     int z = firstZ - tz;
  244.                     int s = firstS - ts;
  245.  
  246.                     // Prüfe ob Position gültig ist
  247.                     if (z < 0 || s < 0 || z + pstRot->iN > pstAktFeld->iN || s + pstRot->iM > pstAktFeld->iM) {
  248.                         continue;
  249.                     }
  250.  
  251.                     // Prüfe ob Tile passt
  252.                     int passt = 1;
  253.                     for (int pz = 0; pz < pstRot->iN && passt; pz++) {
  254.                         for (int ps = 0; ps < pstRot->iM && passt; ps++) {
  255.                             if (pstRot->archFeld[pz][ps] != 0 && 
  256.                                 pstAktFeld->archFeld[z + pz][s + ps] == 0) {
  257.                                 passt = 0;
  258.                             }
  259.                         }
  260.                     }
  261.  
  262.                     if (passt) {
  263.                         // Kopiere Feld
  264.                         Feld stFeldProc = *pstAktFeld;
  265.  
  266.                         // Setze Tile-Felder auf 0
  267.                         for (int pz = 0; pz < pstRot->iN; pz++) {
  268.                             for (int ps = 0; ps < pstRot->iM; ps++) {
  269.                                 if (pstRot->archFeld[pz][ps] != 0) {
  270.                                     stFeldProc.archFeld[z + pz][s + ps] = 0;
  271.                                 }
  272.                             }
  273.                         }
  274.  
  275.                         // Teil 3n: Neues Listenelement erstellen
  276.                         TileList *pstNewTile = (TileList*)malloc(sizeof(TileList));
  277.                         if (pstNewTile == NULL) {
  278.                             printf("Fehler bei Speicherallokation!\n");
  279.                             return pstBestTileList;
  280.                         }
  281.                         // n2: Member zuweisen
  282.                         pstNewTile->chTileIndex = t + 1; // 1-basiert speichern
  283.                         pstNewTile->chRotIndex = r;
  284.                         pstNewTile->chXPos = s;
  285.                         pstNewTile->chYPos = z;
  286.                         // n3: pstPrev auf bisherige Liste
  287.                         pstNewTile->pstPrev = pstTileList;
  288.  
  289.                         // Rekursiver Aufruf
  290.                         Tilify_Opt(&stFeldProc, arstTiles, 
  291.                                    iAnzFelder - arstTiles[t].iAnzFelder, 
  292.                                    iAnzTiles + 1, pstNewTile);
  293.                     }
  294.                 }
  295.             }
  296.         }
  297.     }
  298.  
  299.     return pstBestTileList;
  300. }
  301.  
  302. int main() {
  303.     // Teil 1d: Definition der Tiles mit Listeninitialisierung
  304.     Tile arstTiles[4] = {
  305.         // Tile 1: 1x1
  306.         {
  307.             .chFarbCode = 0xB0,  // ░
  308.             .iAnzFelder = 1,
  309.             .iAnzRotationen = 1,
  310.             .arstRotationen = {
  311.                 {
  312.                     .iN = 1, .iM = 1,
  313.                     .archFeld = {{1}}
  314.                 }
  315.             }
  316.         },
  317.         // Tile 2: L-Form mit 3 Feldern
  318.         {
  319.             .chFarbCode = 0xB1,  // ▒
  320.             .iAnzFelder = 3,
  321.             .iAnzRotationen = 4,
  322.             .arstRotationen = {
  323.                 { // Rotation 1
  324.                     .iN = 2, .iM = 2,
  325.                     .archFeld = {{1,1},{0,1}}
  326.                 },
  327.                 { // Rotation 2
  328.                     .iN = 2, .iM = 2,
  329.                     .archFeld = {{0,1},{1,1}}
  330.                 },
  331.                 { // Rotation 3
  332.                     .iN = 2, .iM = 2,
  333.                     .archFeld = {{1,0},{1,1}}
  334.                 },
  335.                 { // Rotation 4
  336.                     .iN = 2, .iM = 2,
  337.                     .archFeld = {{1,1},{1,0}}
  338.                 }
  339.             }
  340.         },
  341.         // Tile 3: 1x3 / 3x1
  342.         {
  343.             .chFarbCode = 0xB2,  // ▓
  344.             .iAnzFelder = 3,
  345.             .iAnzRotationen = 2,
  346.             .arstRotationen = {
  347.                 { // Horizontal
  348.                     .iN = 1, .iM = 3,
  349.                     .archFeld = {{1,1,1}}
  350.                 },
  351.                 { // Vertikal
  352.                     .iN = 3, .iM = 1,
  353.                     .archFeld = {{1},{1},{1}}
  354.                 }
  355.             }
  356.         },
  357.         // Tile 4: 2x2
  358.         {
  359.             .chFarbCode = 0xDB,  // █
  360.             .iAnzFelder = 4,
  361.             .iAnzRotationen = 1,
  362.             .arstRotationen = {
  363.                 {
  364.                     .iN = 2, .iM = 2,
  365.                     .archFeld = {{1,1},{1,1}}
  366.                 }
  367.             }
  368.         }
  369.     };
  370.  
  371.     // Teil 1f: Definition der zu parkettierenden Fläche
  372.     // Hinweis: Für Tests mit 4x4 NMAX und MMAX auf 4 setzen und diese Fläche verwenden:
  373.     /*
  374.     Feld stFeld = {
  375.         .iN = 4,
  376.         .iM = 4,
  377.         .archFeld = {
  378.             {1,1,0,0},  // Zeile 1: 2 Felder
  379.             {0,1,1,0},  // Zeile 2: 2 Felder  
  380.             {0,1,1,1},  // Zeile 3: 3 Felder
  381.             {1,1,1,1}   // Zeile 4: 4 Felder
  382.         }
  383.     };
  384.     */
  385.  
  386.     // Fläche aus Abbildung 4 (Ihre Fläche)
  387.     Feld stFeld = {
  388.         .iN = NMAX,
  389.         .iM = MMAX,
  390.         .archFeld = {
  391.             {0,0,0,0,0,0,0,0},  // Zeile 1: 0 Felder
  392.             {0,0,0,1,1,1,1,0},  // Zeile 2: 4 Felder (Spalten 4-7)
  393.             {0,1,1,1,1,1,0,1},  // Zeile 3: 6 Felder (Spalten 2-6 und 8)
  394.             {0,1,1,0,0,1,1,0},  // Zeile 4: 4 Felder (Spalten 2-3 und 6-7)
  395.             {0,1,1,1,1,1,1,0},  // Zeile 5: 6 Felder (Spalten 2-7)
  396.             {0,1,1,1,1,1,1,0},  // Zeile 6: 6 Felder (Spalten 2-7)
  397.             {0,0,0,1,1,0,0,0},  // Zeile 7: 2 Felder (Spalten 4-5)
  398.             {0,0,0,0,0,0,0,0}   // Zeile 8: 0 Felder
  399.         }
  400.     };
  401.  
  402.     // Ausgabe der Tiles
  403.     PrtTiles(arstTiles);
  404.  
  405.     // Ausgabe der initialen Fläche
  406.     PrtFeld(&stFeld, arstTiles);
  407.  
  408.     // Teil 3m: Initialisierung der Tile-Liste
  409.     TileList *pstTileList = NULL;
  410.  
  411.     // Anzahl der zu parkettierenden Felder
  412.     int anzFelder = AnzFelder(stFeld.archFeld);
  413.     printf("\nAnzahl zu parkettierender Felder: %d\n", anzFelder);
  414.  
  415.     // Teil 2i3: Aufruf der NICHT-optimierten Tilify für Teil 2
  416.     // Hinweis: Diese Funktion ist sehr langsam für große Flächen!
  417.     // Verwenden Sie die Testfläche 4x4 für diese Funktion
  418.     /*
  419.     printf("\nSuche mit nicht-optimierter Tilify-Funktion...\n");
  420.     Tilify(&stFeld, arstTiles, anzFelder, 0);
  421.     */
  422.  
  423.     // Teil 3: Optimale Parkettierung mit optimierter Funktion finden
  424.     printf("\nSuche optimale Parkettierung...\n");
  425.     printf("(Dies kann einen Moment dauern...)\n");
  426.  
  427.     // Teil 3n7: Erweiterte Funktion gibt Zeiger zurück
  428.     TileList *pstOptimalList = Tilify_Opt(&stFeld, arstTiles, anzFelder, 0, pstTileList);
  429.  
  430.     // Teil 3o: Optimale Parkettierung anwenden
  431.     if (pstBestTileList != NULL) {
  432.         // o1: Neue Fläche erstellen
  433.         Feld stOptFeld = stFeld;
  434.  
  435.         // o2: Tiles aus der Liste auf die Fläche legen
  436.         TileList *pstCurrent = pstBestTileList;
  437.         int tileCount = 0;
  438.  
  439.         // Sicherheitscheck
  440.         while (pstCurrent != NULL && pstCurrent != (TileList*)0xFFFFFFFFFFFFFFFF) {
  441.             // Weitere Sicherheitschecks
  442.             if ((void*)pstCurrent < (void*)0x1000) {
  443.                 printf("Fehler: Ungültiger Zeiger!\n");
  444.                 break;
  445.             }
  446.  
  447.             int tileIdx = pstCurrent->chTileIndex - 1; // Auf 0-basiert umrechnen
  448.             int rotIdx = pstCurrent->chRotIndex;
  449.             int xPos = pstCurrent->chXPos;
  450.             int yPos = pstCurrent->chYPos;
  451.  
  452.             // Validierung der Indizes
  453.             if (tileIdx < 0 || tileIdx >= 4 || rotIdx < 0 || rotIdx >= 4 ||
  454.                 xPos < 0 || xPos >= MMAX || yPos < 0 || yPos >= NMAX) {
  455.                 printf("Fehler: Ungültige Tile-Parameter!\n");
  456.                 break;
  457.             }
  458.  
  459.             Feld *pstRot = &arstTiles[tileIdx].arstRotationen[rotIdx];
  460.  
  461.             // Tile auf die Fläche setzen
  462.             for (int z = 0; z < pstRot->iN; z++) {
  463.                 for (int s = 0; s < pstRot->iM; s++) {
  464.                     if (pstRot->archFeld[z][s] != 0) {
  465.                         if (yPos + z < NMAX && xPos + s < MMAX) {
  466.                             stOptFeld.archFeld[yPos + z][xPos + s] = tileIdx + 1;
  467.                         }
  468.                     }
  469.                 }
  470.             }
  471.  
  472.             tileCount++;
  473.             pstCurrent = pstCurrent->pstPrev;
  474.  
  475.             // Endlosschleife verhindern
  476.             if (tileCount > 100) {
  477.                 printf("Fehler: Zu viele Tiles!\n");
  478.                 break;
  479.             }
  480.         }
  481.  
  482.         // o3: Optimale Parkettierung ausgeben
  483.         printf("\nOptimale Partitionierung (%d Tiles):\n", tileCount);
  484.  
  485.         // Ausgabe mit spezieller Überschrift
  486.         printf("\xDA"); // ┌
  487.         for (int i = 0; i < stOptFeld.iM * 2; i++) {
  488.             printf("\xC4"); // ─
  489.         }
  490.         printf("\xBF\n"); // ┐
  491.  
  492.         // Inhalt
  493.         for (int z = 0; z < stOptFeld.iN; z++) {
  494.             printf("\xB3"); // │
  495.  
  496.             for (int s = 0; s < stOptFeld.iM; s++) {
  497.                 char tileIndex = stOptFeld.archFeld[z][s];
  498.                 if (tileIndex == 0) {
  499.                     printf("  ");
  500.                 } else {
  501.                     unsigned char farbCode = arstTiles[tileIndex - 1].chFarbCode;
  502.                     printf("%c%c", farbCode, farbCode);
  503.                 }
  504.             }
  505.  
  506.             printf("\xB3\n"); // │
  507.         }
  508.  
  509.         // Untere Begrenzung
  510.         printf("\xC0"); // └
  511.         for (int i = 0; i < stOptFeld.iM * 2; i++) {
  512.             printf("\xC4"); // ─
  513.         }
  514.         printf("\xD9\n"); // ┘
  515.  
  516.         // Teil 1p: Antwort auf die Frage
  517.         printf("\nFuer die Parkettierung der Flaeche werden mindestens %d Tiles benoetigt.\n", tileCount);
  518.     } else {
  519.         printf("\nKeine Loesung gefunden!\n");
  520.     }
  521.  
  522.     // Teil 2h: Antwort auf die Frage zur Parameterübergabe
  523.     printf("\n== Antwort zu Aufgabe 2h ==\n");
  524.     printf("Die Ubergabe des Parameters arstTiles erfolgt als Array-Parameter.\n");
  525.     printf("In C werden Arrays immer als Zeiger auf das erste Element uebergeben.\n");
  526.     printf("Daher steht der gesetzte Wert auch in der aufrufenden Funktion zur Verfuegung.\n");
  527.  
  528.     // Teil 3j: Antwort zu Optimierungsmaßnahmen
  529.     printf("\n== Antwort zu Aufgabe 3j ==\n");
  530.     printf("Optimierungsmassnahmen:\n");
  531.     printf("1. Abbruch wenn aktuelle Anzahl >= bisheriges Minimum (Branch & Bound)\n");
  532.     printf("2. Immer das erste freie Feld abdecken (verhindert Lochbildung)\n");
  533.     printf("3. Groessere Tiles zuerst probieren (bessere Abdeckung)\n");
  534.  
  535.     return 0;
  536. }
Success #stdin #stdout 0.02s 5364KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Zur Verfuegung stehende Tiles:
Tile 1 -- Rotation(en): 1; Felder: 1
��
Tile 2 -- Rotation(en): 4; Felder: 3
����      ��    ��      ����
  ��    ����    ����    ��  
Tile 3 -- Rotation(en): 2; Felder: 3
������    ��
          ��
          ��
Tile 4 -- Rotation(en): 1; Felder: 4
����
����

Zu partitionierende Flaeche:
����������������Ŀ
�                �
�      ��������  �
�  ����������  ���
�  ����    ����  �
�  ������������  �
�  ������������  �
�      ����      �
�                �
������������������

Anzahl zu parkettierender Felder: 28

Suche optimale Parkettierung...
(Dies kann einen Moment dauern...)
Neue beste Loesung mit 12 Tiles gefunden!
Neue beste Loesung mit 10 Tiles gefunden!
Neue beste Loesung mit 9 Tiles gefunden!

Optimale Partitionierung (9 Tiles):
����������������Ŀ
�                �
�      ���۱���  �
�  �������۱�  ���
�  ����    ����  �
�  ������������  �
�  ������������  �
�      ����      �
�                �
������������������

Fuer die Parkettierung der Flaeche werden mindestens 9 Tiles benoetigt.

== Antwort zu Aufgabe 2h ==
Die Ubergabe des Parameters arstTiles erfolgt als Array-Parameter.
In C werden Arrays immer als Zeiger auf das erste Element uebergeben.
Daher steht der gesetzte Wert auch in der aufrufenden Funktion zur Verfuegung.

== Antwort zu Aufgabe 3j ==
Optimierungsmassnahmen:
1. Abbruch wenn aktuelle Anzahl >= bisheriges Minimum (Branch & Bound)
2. Immer das erste freie Feld abdecken (verhindert Lochbildung)
3. Groessere Tiles zuerst probieren (bessere Abdeckung)
https://ideone.com/vp7t4R
language:
C++14 (clang 8.0)
created:
7 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!