B
BlackSonic
Gast
Also hier ist die Aufgabenstellung
Gegeben sind :
• ein n × n-Array a, das mit Zufallszahlen aus dem Bereich 0. . .9 gefüllt ist sowie
• eine positive ganze Zahl x
Gesucht ist die Anzahl der in a enthaltenen Rechtecke,
bei den die Summe der Zahlen von den 4 Kanten( Rand) des Rechtecks genau x ergibt.
Jedes Rechteck muss mindestens die Höhe 1 und Breite 1 haben, d.h., Rechtecke dürfen nicht zu
einer Strecke oder einem Punkt entarten.
Bsp :
8 2 1 8 4 7 5
3 0 0 0 4 9 3
7 0 3 8 7 1 8
3 2 7 8 8 0 9
5 5 2 5 3 3 4
2 8 4 6 4 7 4
0 3 9 6 8 4 2
x = 30
Ausgabe: 5
Ich habe scho ein Programm geschrieben, aber der Algo ist zu langsam. Weil wir haben die Vorraussetzung das er bei einem 250 * 250 Array unter 30 sec läuft.
Mein Programm tut das nicht, braucht 5 min oder so
Hier noch paar Werte
1 Zahl Array Länge
2 Zahl Gesuchter wert X
3 Zahl zufalls zahl für den Random
java Generator 7 30 123 data.dat -> Anzahl Rechtecke: 5
java Generator 7 30 147 data.dat -> Anzahl Rechtecke: 8
java Generator 10 30 555 data.dat -> Anzahl Rechtecke: 23
java Generator 50 150 555 data.dat -> Anzahl Rechtecke: 2922
java Generator 50 300 777 data.dat -> Anzahl Rechtecke: 3590
java Generator 100 300 975 data.dat -> Anzahl Rechtecke: 24007
java Generator 100 100 1 data.dat -> Anzahl Rechtecke: 10141
java Generator 150 500 234 data.dat -> Anzahl Rechtecke: 88949
java Generator 200 600 3434 data.dat -> Anzahl Rechtecke: 199734
java Generator 250 1000 22 data.dat -> Anzahl Rechtecke: 451879
Mein Programm :
Ich hab schon eine Idee wie man das noch beschleunigen könnte, aber mir fehlt die Idee wie ich das ins Java umsetzen soll.
Und zwar geht es darum, das man ja viel rechen leistung braucht um die Kanten zu berechnen.
Und ich berechne sie jedes mal neu.
Da aber diese Kante in späteren Schritten wieder vorkommt, könnte sie man ja speichern und dann wider aufrufen.
Somit müsste rechenleistung eingespart werden, da auslesen und speichern weniger Leistung verbraucht als neu berechnen. Aber ich hab ansatz wo ich sie speichern kann/soll und wie ich sie wider zu dem benötigten Zeit punkt auslese.
Wäre für Hilfe sehr dankbar
und für andere vorschläge
Gegeben sind :
• ein n × n-Array a, das mit Zufallszahlen aus dem Bereich 0. . .9 gefüllt ist sowie
• eine positive ganze Zahl x
Gesucht ist die Anzahl der in a enthaltenen Rechtecke,
bei den die Summe der Zahlen von den 4 Kanten( Rand) des Rechtecks genau x ergibt.
Jedes Rechteck muss mindestens die Höhe 1 und Breite 1 haben, d.h., Rechtecke dürfen nicht zu
einer Strecke oder einem Punkt entarten.
Bsp :
8 2 1 8 4 7 5
3 0 0 0 4 9 3
7 0 3 8 7 1 8
3 2 7 8 8 0 9
5 5 2 5 3 3 4
2 8 4 6 4 7 4
0 3 9 6 8 4 2
x = 30
Ausgabe: 5
Ich habe scho ein Programm geschrieben, aber der Algo ist zu langsam. Weil wir haben die Vorraussetzung das er bei einem 250 * 250 Array unter 30 sec läuft.
Mein Programm tut das nicht, braucht 5 min oder so
Hier noch paar Werte
1 Zahl Array Länge
2 Zahl Gesuchter wert X
3 Zahl zufalls zahl für den Random
java Generator 7 30 123 data.dat -> Anzahl Rechtecke: 5
java Generator 7 30 147 data.dat -> Anzahl Rechtecke: 8
java Generator 10 30 555 data.dat -> Anzahl Rechtecke: 23
java Generator 50 150 555 data.dat -> Anzahl Rechtecke: 2922
java Generator 50 300 777 data.dat -> Anzahl Rechtecke: 3590
java Generator 100 300 975 data.dat -> Anzahl Rechtecke: 24007
java Generator 100 100 1 data.dat -> Anzahl Rechtecke: 10141
java Generator 150 500 234 data.dat -> Anzahl Rechtecke: 88949
java Generator 200 600 3434 data.dat -> Anzahl Rechtecke: 199734
java Generator 250 1000 22 data.dat -> Anzahl Rechtecke: 451879
Mein Programm :
Code:
import java.io.*;
class Rectangles {
static int countRectangles(int a[][], int zahl) {
int summe = 0;
int laenge = a.length;
//Hier werden die Zahlen aus dem Array von hinten uebergeben.
// Sie laufen von hinten bis 1 durch.
for (int x = laenge; --x>0;)
for (int y = laenge; --y>0;)
summe += basistest(a, zahl,laenge, x, y);
return summe;
}
//_________________________________________________________________________________________
// Hier ist nur eine Überprüfung auf die 3 Grundelemete jedes möglichen vierecks
static int basistest (int a[][], int zahl, int laenge, int startx, int starty){
int basis =a[startx][starty]+a[startx][starty-1]+a[startx-1][starty];
if(basis > zahl)
return 0;
else
return countrectangles(a,zahl,laenge,startx,starty);
//return berechnen(a,zahl,laenge,startx,starty);
}
//_________________________________________________________________________________________
// Hier bestimme ich die Grenze bis wohin er rechnen sollte, bringt ein kleinen Geschwindigkeits vorteil
static int countrectangles (int a[][], int zahl, int laenge,int startx,int starty){
int tempx=0, tempy=0,j=0, i=0, count=0;
for(int zx = startx-1; --zx>=0;)
tempx +=a[zx][starty];
for(int zx = starty-1; --zx>=0;)
tempy +=a[startx][zx];
if(tempx > zahl || tempy > zahl){
if(tempx > zahl)
{
while(tempx > zahl)
{
tempx -=a[i][starty];
i++;
}
count +=berechnen(a,zahl,laenge,startx,starty,i,0);
}
else
if(tempy > zahl)
{
while(tempy > zahl)
{
tempy -=a[startx][j];
j++;
}
count +=berechnen(a,zahl,laenge,startx,starty,0,j);
}
}
else
count +=berechnen(a,zahl,laenge,startx,starty,0,0);
return count;
}
//__________________________________________________________________________________________
// die Erste Idee wie ich die Vierecke berechne
static int berechnen(int a[][], int zahl,int laenge, int startx, int starty, int endx,int endy){
int count=0;
for(int x=endx; x<startx; x++)
for(int y=endy; y<starty; y++){
int temp=0;
for(int zy=y; zy<=starty; zy++)
temp +=a[startx][zy];
for(int zy=y; zy<=starty; zy++)
temp +=a[x][zy];
if ((startx-x) > 1) {
for (int zx = x+1; zx < startx ; zx++)
temp +=a[zx][starty];
for (int zx = x+1; zx < startx; zx++)
temp +=a[zx][y];
}
if(temp == zahl)
count++;
}
return count;
}
//__________________________________________________________________________________________
// die zweite Idee , wie ich die Vierecke berechne, hat aber irgendwo ein logischen fehler, liefert falsche zahlen aus.
static int berechnenb(int a[][], int zahl,int laenge, int startx, int starty, int endx,int endy){
int temp=0;
if ((startx-endx) > 1) {
for (int zx = endx; zx < startx ; zx++)
temp +=a[zx][starty];
if(temp > zahl)
return 0;
for (int zx = endx; zx < startx; zx++)
temp +=a[zx][endy];
if(temp > zahl)
return 0;
for(int zy=endy; zy<=starty; zy++)
temp +=a[startx][zy];
if(temp > zahl)
return 0;
for(int zy=endy; zy<=starty; zy++)
temp +=a[endx][zy];
if(temp == zahl)
return 1;
else
return 0;
}else
{ for(int zy=endy; zy<=starty; zy++)
temp +=a[startx][zy];
if(temp > zahl)
return 0;
for(int zy=endy; zy<=starty; zy++)
temp +=a[endx][zy];
if(temp > zahl)
return 0;
if ((startx-endx) > 1) {
for (int zx = endx; zx < startx ; zx++)
temp +=a[zx][starty];
if(temp > zahl)
return 0;
for (int zx = endx; zx < startx; zx++)
temp +=a[zx][endy];
}
if(temp == zahl)
return 1;
else
return 0;
}
}
//__________________________________________________________________________________________
// Das Main Programm, liest aus einer Datei, Werte aus, und packt sie in das Array.
public static void main(String[] args) {
try {
DataInputStream dis = new DataInputStream(new FileInputStream(
args[0]));
int n = dis.readInt();
int x = dis.readInt();
int[][] a = new int[n][n];
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
a[i][j] = dis.readInt();
//Out.print(a[i][j] + " ");
}
//Out.println();
}
Out.println();
Out.println("Anzahl Rechtecke mit Kantensumme " + x + ": "
+ countRectangles(a, x));
} catch (ArrayIndexOutOfBoundsException e) {
Out.println("Aufruf: java Simplest Dateiname");
} catch (FileNotFoundException e) {
Out.println("Datei existiert nicht");
} catch (IOException e) {
Out.println("Fehlerhafte Datei");
}
}
}Ich hab schon eine Idee wie man das noch beschleunigen könnte, aber mir fehlt die Idee wie ich das ins Java umsetzen soll.
Und zwar geht es darum, das man ja viel rechen leistung braucht um die Kanten zu berechnen.
Und ich berechne sie jedes mal neu.
Da aber diese Kante in späteren Schritten wieder vorkommt, könnte sie man ja speichern und dann wider aufrufen.
Somit müsste rechenleistung eingespart werden, da auslesen und speichern weniger Leistung verbraucht als neu berechnen. Aber ich hab ansatz wo ich sie speichern kann/soll und wie ich sie wider zu dem benötigten Zeit punkt auslese.
Wäre für Hilfe sehr dankbar
und für andere vorschläge
