kingbozz Gast |
Guten Tag,
Brauche eine Idee für ein Algorithmuss vielleicht kann mir ja jemand hier weiterhelfen....
Wenn ich ein Array der größe NxN habe ... und von den Array einfach paar rechtecke rauswählen ( die nicht der größe NxN sind)
will wie mache ich das am geschicktesten ?
danke im voraus....
LG
Hmm, also sowas wie
int xAnfang=..., yAnfang=..., xEnde=..., yEnde=...;
for( int i = yAnfang; i <= yEnde; ++i ){
for( int j = xAnfang; j <= xEnde; ++j ){
// do something with array[i][j]...
}
}
???Hat dir diese Antwort geholfen?
und von den Array einfach paar rechtecke rauswählen
Hat dir diese Antwort geholfen?
Hmm, also was richtig elegantes fällt mir dazu nicht ein. Probier doch erstmal so:
1. Nimm das erste Feld (1,1). Rechteck gefunden! Größe 1x1
2. Nimm das darunter liegende Feld dazu (1,2) Rechteck gefunden, Größe 1x2
3. Nimm immer das darunterliegende Feld dazu bis das Array zuende ist (1,3), (1,4) usw. Jeder Schritt ergibt ein Rechteck.
4. Nimm wieder das erste Feld
5. Nimm das rechts daneben dazu
6. Nimm die Felder eins unter den selektierten Feldern dazu
7. Widerhole 6. bis das Array unten zuende ist.
8. Wiederhole 5-7 bis das Array rechts und unten zuende ist.
9. Wiederhole 2-8 mit jedem Feld.
Ist recht länglich aber es gibt halt auch seeeehr viele Rechtecke selbst in einer recht kleinen Matrix (bei 2x2 gibt es bereits 9 Rechtecke!, bei 3x3 32)
Hat dir diese Antwort geholfen?
Ich probiers mal. Ein paar Anmerkungen vorweg
- Ich hab einfach mal sone Art C++ genommen
- Programm ist so sicherlicherlich nicht lauffaehig, ich hoffe aber, dass der Algorithmus an sich funktioniert
- Ich kann das gerade nicht testen, daher ohne Gewaehr 
sondern die kleinen rechtecke in der MATRIX !!!!!! 
kannst du ma den anfang machen // Fuer die Ergebnisse
class CResultEntry{
private:
int mStartingWidth; //x-Index
int mStartingHeight; //y-Index
int mWidth; //Breite des Eintags
int mHeight; //Hoehe des Eintrags
public:
CResultEntry::CResultEntry( int sw, int sh, int w, int h )
: mStartingWidth( sw ), mStartingHeight( sh ),
mWidth( w ), mHeight( h );
{};
}
typedef std::vector< CResultEntry > resultVec;
class CRectangleFinder{
private:
// Vorraussetzungen
int a[][] = ...;// das Array
int sum = ...; // die gesuchte Summe
int width = ...; // die Breite des Arrays
int height = ...; // die Hoehe des Arrys
resultVec results;
public:
CRectangleFinder::CRectangleFinder(){};
void CRectangleFinder::find()
{
// loop ueber alle Felder
for( int i = 0; i < height; ++i )
{
for( int j = 0; j < width; ++j )
{
checkHorizontal( i, j );
checkMulti( i, j );
}
}
}
private:
// check in x-Richtung mit Tiefe 1
void CRectangleFinder::checkHorizontal( int x, int y )
{
int tSum = a[x][y];
int tWidth = 0;
for int( k = x; k < width; ++k )
{
tSum += a[k][y];
tWidth++;
// Ergebnis gefunden -> speichern!
if( tSum == sum ) results.push_back( new CResultEntry( x, y, tWidth, 1 ) );
// Summe zu gross, verlasse Funktion
if( tSum > sum ) return;
}
}
// check in x-Richtung mit Tiefe n
void CRectangleFinder::checkMulti( int x, int y)
{
// letzte Zeile erreicht, Tiefe > 1 existiert nicht
if( y == height ) return;
for( int k = x; k < width; ++k )
{
int tSum = a[x][y];
int tWidth = 1 + k - x;
int tHeight = 1;
for( int l = y + 1; l < height; ++l )
{
tHeight++;
tSum = calculate( x, y, tWidth, tHeight );
//Summe schon zu gross, verlasse innere for-Schleife
if( tSum > sum ) break;
// Ergebnis gefunden -> speichern!
if( tSum == sum ) results.push_back( new CResultEntry( x, y, tWidth, tHeight ) );
}
}
}
// Berechne Summe
int CRectangleFinder::calculate( int x, int y, int w, int h )
{
int rval = 0;
for( int i = x; i < x + w; ++i )
{
for( int j = y; j < y + h; ++j )
{
rval =+ a[i][j];
}
}
return rval;
}
}
| « Programmieren | Physikgames » | ||
Liegt das Ausgangsmaterial nicht in zum Beispiel von Final C...
OldTimer's List-It (OTL) dient der Analyse / Diagnose Deines...
Tabellen erstellen in Word
Manchmal ist es sehr praktisch, anstatt einen Text zu erstellen, eine Tabelle oder gleich mehrere Ta...
Kann mich jemand aufklären was ein Array ist und was der bezweckt.In welcher Programmiersprache sin...
Hallo. Ich komme da in PHP nit so ganz weiter:Hab ne Textdatei, sieht etwa so aus:"abc",&q...
Win XP: Disk Array Verzweiflung need help!!Ich habe in meinem System eine Samsung Spinpoint IDE Festplatte. Wegen...
Hallo. Ich kenne mich bereits ein bisschen mit PHP aus, aber mit Arrays komme ich nicht klar. Ich ha...
hallo zusammenhab folgendes problem:Mein php file gibt schön alle werte als formular aus, das einer...
Hallo zusammen Ich möchte innerhalb einer "Do until File.AtEndOfStream"-Schlaufe einen We...
Hallo alle zusammen ... Ich bins wieder :D for(i=0; i<n; ++i){ for(k=0; k<n; ...
Hallo Leuts |Hab mal ein kleines Problem mit einer Array-Sortierung.Und zwar hab ich ein indiziertes...