Wieviele Steine passen in eine Fläche?

CDW

CDW

0
Mitarbeiter
Eine Aufgabe von benwilliam:

Es soll ein Algorithmus entwickelt werden der die maximale Anzahl an Bausteinen bestimmt die in eine bestimmte Fläche passen.

z.B: ich gebe "ihm" eine Fläche von 2m x 2,5m vor und sage das ein Baustein 0,15m x 0.1m groß ist. Nun soll der Algorithmus die Bausteine so anordnen das die Große Fläche möglichst vollständig abgedeckt wird. und es so wenig wie möglich Lücken bleiben.
Die anzahl de genutzten Bausteine und wenn möglich die Form in der die Bausteine verlegt worden sind, sollen ausgegeben werden.
 
Sry ,aber ich glaub ich seh das Problem vom Problem irgendwie nicht :rolleyes:

0,15m * 0,1m = 0,015 qm ==> 333 * 0,015 qm = 4,995 qm < 5 qm

Also passen genau 333 Steine in die Fläche.
Der Algorithmus wäre einfach eine Schleife in der aufaddiert und gezählt wird ,bis zur Gesamtfläche.

Ist bestimmt am Problem vorbei ,weil viel zu einfach. Aber wie gesagt, ich seh's im Moment nicht.


Cagiv
 
naja, da du aber möglicherweise nicht alle steine auch reinlegen kannst sondern freiflächen bleiben kannst dir das glaube ich nicht so leicht machen. du weißt jetzt nur den optimalen wert aber nicht ob der auch möglich ist

nehmen wir ne 5 m? große fläche, die aber nur eine höhe von 5 cm hat. dann wirst du nicht einen einzigen stein mit der angegebenen größe platzieren können ;-)
 
@lightsaver

So wie ich das rauslesen konnte ,geht es aber darum eine Fläche und nicht ein Volumen zu füllen. Also hat die Höhe nichts mit der Berechnung zu tun.


Aber ich sehe ein ,dass wenn die Fläche vielleicht kreisförmig o.ä. ist ,das man dann nicht so einfach rechnen kann...


Cagiv
 
ja, sorry, hab nur das falsche wort benutzt, also nochmal zum verdeutlichen: 5 cm breite, 100 m länge. das wären dann auch 5 m? aber es würde kein einziger stein passen.
 
das müsste funktionieren:

abrunden(Breite_Feld / Breite_Stein) = B1
abrunden(Höhe_Feld / Höhe_Stein) = H1

abrunden(Breite_Feld / Höhe_Stein) = B2
abrunden(Höhe_Feld / Breite_Stein) = H2

P1 = B1*H1
P2 = B2*H2

Die Produkte entsprechen der Anzahl der Ziegelsteine die in die Fläche passen.

Für die restlichen drei Flächen muss die Überprüfung nochmal durchgeführt werden,
evt. können dann noch zusätzliche Steine in einer anderen Position in die Fläche gelegt werden.
 
Code: 
##############################################
#                                                                                                              #
#                         Aufgabe von benwilliam:                                                     #
#                                                                                                              #
#                        Es soll ein Algorithmus entwickelt werden,                           #
#                        der die maximale Anzahl an Bausteinen bestimmt,                   #
#                        die in eine bestimmte Fläche passen.                                    #
#                                                                                                             #
##############################################   
def feld (laenge, breite )   
    # bausteingröße festlegen in cm
    bausteinb = 150
    bausteinl  = 100
    # feldgröße festlegen in cm
    @breite    = breite
    @laenge   = laenge
    # wenn die Breite eines Bausteines breiter ist als die Breite des Feldes könnte man es ja noch quer hinlegen, sodass die Breite zur Länge wird ^^
    # also wenn Breite also größer ist als die Feldbreite UND Feldhöhe ist das Feld zu klein
    if bausteinb > @breite
        if bausteinb > @laenge
            puts "Feld ist zu klein"
            gets
    end
    # das selbe mit der Höhe ausprobieren
    elsif bausteinl > @laenge
        if bausteinl > @breite
            puts "Feld ist zu klein"
            gets
    end
    # falls das Feld nicht zu klein ist ausprobieren wie viele Steinchen darein passen
    else
    #Soviele Felder sind aus gefüllt ( noch keins )
        breitea   = 0
    laengea  = 0
    # natürlich hat ja jedes Steinchen auch eine Höhe die dann auch dazu addiert werden muss
    # wobei hier nach neuen erkentnissen nen dicker Denkfehler vorliegt
   
    # solange steinchen hinzufügen bis eins überstehen würde und dann die restlichen freien kästchen ausrechnen
    # falls man noch ein anderes länglich hineinlegen kann
        0.step(@breite, 150) do  |b|
    breitea += 150
    print breitea
    gets
end

    differenz = @breite - breitea
    # wenn der restliche platz noch groß genug ist um ein weiteres Teil längs hinzulegen
    # muss nur noch geprüft werden ob auch nach " oben " hin genug platz ist und dann
    # kann noch ein weiteres steinchen hinzugezählt werden
    if @differenz > bausteinl && bausteinl <= @laenge
        0.step(@differenz, bausteinl) do
        breitea   += 100
        laengea  += 150
        end
    end
    blub = @breite/bausteinb 
    end
end

puts "#{feld(250,100)}"
gets

als kleiner Gedankenanstoß ( sollte eigentlich verständlich sein, für jeden der programmiert hat ).
 
lol wie weinfach

Code: 
#include <iostream>
using namespace std;  
int main ()  
{     
 double a,b,c,d,e,f,g;     
 cout <<"flächenmase eingebn länge:"<<endl;      
cin >> a;     
 cout <<"breite:"<<endl;      
cin >> b;      c = a * b;     
cout <<endl;     
 cout <<"Steine Maße eingebn Länge:"<<endl;      
cin >>d;      
cout<<"Breite:"<<endl;      
cin>>e;      f = d * e;      g = f % c;     
 cout<<f/c<<"steine passen da rein"<<endl;     
 cout <<g<<"belibt übrig"<<endl;  
return 0;  
}
das müsste es eigentlich voll in c++ lösen ich versteh trozfdem nicht warum diese aufgabe auf dem schwierigkeits grad 3 läuft!
MfG MoE
 
1) gibt mal bei Dir Flächenmaße: 2x3
stein: 1x3
0.5 Steine passen da rein?

2) (nach dem Du die Formel korrigiert hast ;) ):
lies Dir bitte die Beiträge von lightsaver durch:
angenommen Du hast eine Fläche von 0.5x6 und Steingröße 0.6x1
Wieviele Steine kann man nun hineinlegen, ohne diese zu zerkleinern?
So ganz banal ist das Problem also doch nicht ;)
 
naja solange sowohl die Steine als auch die Fläche Rechteckig sind ist es trotzdem ziemlich einfach. Gibt es auch nicht rechteckige Steine / Flächen?
 
Ich hab das ganze mal schnell in C++ gecoded. Schwierigkeit 3 hat es meiner Meinung nach nicht verdient, da man sich den Algorithmus selbst ohne viel mathematisches Verständnis schnell zusammenreimen kann.

Code: 
#include <iostream>

using namespace std;

int main()
{
    int area_w, area_h, box_w, box_h;
    cout << "Feldbreite (z.B. \"200 250\"): ";
    cin >> area_w >> area_h;
    cout << "Kistenbreite (z.B. \"15 100\"): ";
    cin >> box_w >> box_h;

    if (area_w < area_h) {
        int tmp = area_h;
        area_h = area_w;
        area_w = tmp;
    }
    if (box_w < box_h) {
        int tmp = box_h;
        box_h = box_w;
        box_w = tmp;
    }

    int nBoxes = 0;

    // Erst alle in der einen Richtung
    nBoxes += (area_w / box_w) * (area_h / box_h);

    // Jetzt die Boxen "drehen" und gucken, was so noch passt
    nBoxes += ((area_w % box_w) / box_h) * (area_h / box_w);

    cout << "Bei einem Feld von " << area_w << "x" << area_h
         << " und einer Kistengröße von " << box_w << "x" << box_h
         << " passen genau " << nBoxes << " Kisten auf die Fläche." << endl;
}
 
Das Thema ist zwar schon älter aber ich muss auch^^

Code: 
puts "Willkommen zum Steinberechner!"
loop do
	puts "Bitte geben Sie die Breite der Flaeche ein:\n"
	breite = gets.to_f
	puts "Bitte geben Sie die Laenge der Flaeche ein:\n"
	laenge = gets.to_f
	puts "Bitte geben Sie die Breite der Steins ein:\n"
	bstein = gets.to_f
	puts "Bitte geben Sie die Laenge der Steine ein:\n"
	lstein = gets.to_f
	if bstein > breite && bstein > laenge
		puts "Passt nicht!!!\n"
	elsif lstein > breite && lstein > laenge
		puts "Passt nicht!!!\n"
	elsif bstein > breite && lstein > laenge
		puts "Passt nicht!!!\n"
	elsif lstein > breite && bstein > laenge
		puts "Passt nicht!!!\n"
	else
		flaeche = breite * laenge
		fstein = bstein * lstein
		zergebnis = fstein
		zaehler = 1
		while zergebnis < flaeche
			zaehler += 1
			zergebnis += fstein
		end
		puts "Es passen #{zaehler} Steine in die Flaeche.\n"
	end
	puts "Wollen Sie noch einen Versuch machen? (j/n)\n"
	auswahl = gets.chomp
	if auswahl != "j"
		break
	end
end
 
schmeißt nur errors aus :o
Sorry, mehr Infos
Also: Unter WinXP mit Konsole sagt es, dass bei "Passt nicht" in den Zeilen 12, 14, 16, 18, 28 ein kEND erwartet wird anstelle von tCONSTANT
und in Zeile 35 wird ein $end anstelle eines kEND erwartet.
Ich hab den Code 1 zu 1 in Scite übernommen und einfach gesichert.

edit2: Ich sehs, da fehlen 2 "n"s nach dem \ für den Zeilenumbruch in den Zeilen 5 und 9 ! Damit wird das Anführungszeichen escaped und der String nicht beendet !
 
Also, Jungs (bis auf mauralix und lightsaver):

Ihr macht Euch die Aufgabe zu einfach.
Auch wenn es nur um rechteckige Bausteine geht und auch wenn diese alle gleich aussehen, ist das Problem ein Optimierungsproblem.

Ihr könnte mit der einfachen Flächendivision einen Grenzwert bestimmen, der eventuell erreicht werden KANN.

Sofern die beiden Bedingungen "rechteckig" und "alle gleich" nicht auf die Bausteine und die auszulegende Fläche zutreffen, wird auf jeden Fall eine Aufgabe daraus, die exponentiellen Lösungsaufwand erfordert und bei der noch nicht mal feststeht, daß die Bausteine horizontal oder vertikal ausgerichtet eine optimale Flächendeckung ergeben.

MIT diesen beiden Bedingungen müßte man jedoch auch erstmal beweisen, daß die Flächennutzung bei horizontaler und vertikaler Ausrichtung optimal werden muß. Erst dann lohnt es sich, einen Algorithmus dafür zu schreiben.

Mal als Beispiel:

Baustein 3*5
Fläche 13*14

Grenzwert nach Flächendivision: 12, Rest 2
tatsächlich mögliche Auslastung: 11,
aber nur, wenn die Bausteine etwa (vom Prinzip her) SO angeordnet werden:

Code: 
1111122222bbb
1111122222bbb
1111122222bbb
3333344444bbb
3333344444bbb
3333344444
5555566666
5555566666
5555566666
777888999aaa 
777888999aaa
777888999aaa
777888999aaa
777888999aaa

geht man geringfügig anders ran, kann man eventuell nur noch 10 unterbringen.
GANZ so trivial ist die Aufgabe also nicht...

Falls die Annahme zutrifft, daß Optimalität erreiche werden kann, wenn man die Fläche damit auszulegen beginnt, daß man Bausteine einfach nur in einer Richtung ausgerichtet und in einer Ecke angesetzt erstmal bis auf die Reststreifen verteilt und dann jene zu füllen versucht, indem man die Bausteine 90° gedreht und wieder in einer verbleibenden Ecke angesetzt verteilt, müßt Ihr immer noch mindestens zwei Varianten davon probieren und die bessere auswählen!

Oder mit irgendwelchen Teilerverhältnis-Betrachtungen vorneweg die Optimallösung voraussagen.
 
Ich hab da mal was in Python gebastelt, um den Code klein zu halten vertraue ich mal darauf das die Eingaben Zaheln sind ;)

Code: 
#Autor :   BA2
#Link  :   http://www.abba-skript.de?seite=steine(Python)

#Flaeche festlegen
print 'Die Flaeche des Feldes wird in Millimeter eingegeben.\nEs sind nur ganze Zahlen erlaubt.'
feld_breite = input('Die Breite des Feldes in mm? ')
feld_laenge = input('Die Laenge des Feldes in mm? ')
feld_flaeche = feld_breite * feld_laenge
#bestimmen wieviele Stellen die Zahl hat
feld_zeichen = len(list(str(feld_flaeche))) + 4

#Steingroesse festlegen
print '\nDie Flaeche des Steines wird in Millimeter eingegeben.\nEs sind nur ganze Zahlen erlaubt.'
stein_breite = input('Die Breite des Steines in mm? ')
stein_laenge = input('Die Laenge des Steines in mm? ')
stein_flaeche = stein_breite * stein_laenge
#bestimmen wieviele Stellen die Zahl hat
stein_zeichen = len(list(str(stein_flaeche))) + 4

#Rechnungen
steine_insgesamt = feld_flaeche / stein_flaeche
steine_insgesamt_zeichen = len(list(str(steine_insgesamt))) + 7

#Gegebenheiten Ausgeben
print '\nGegeben:\n'
#Feld
print 'Feld Breite   = ',feld_breite,'mm'
print 'Feld Laenge   = ',feld_laenge,'mm'
#Stein
print 'Stein Breite  = ',stein_breite,'mm'
print 'Stein Laenge  = ',stein_laenge,'mm\n'

#Rechnung Ausgeben
print '\nRechnungen:\n'
#Rechnung Feld Flaeche
print 'Feld Flaeche = Feld Breite * Feld Laenge'
print 'Feld Flaeche =',feld_breite,'mm','*',feld_laenge,'mm'
print 'Feld Flaeche =',feld_flaeche,'mm2'
print ' '*14, '-'*feld_zeichen,'\n'

#Rechnung Stein Flaeche
print 'Stein Flaeche = Stein Breite * Stein Laenge'
print 'Stein Flaeche =',stein_breite,'mm','*',stein_laenge,'mm'
print 'Stein Flaeche =',stein_flaeche,'mm2'
print ' '*15, '-'*stein_zeichen,'\n'

#Rechnung wie viele Steine im Feld im Optimal fall passen
print 'Steine Insgesamt = Feld Flaeche / Stein Flaeche'
print 'Steine Insgesamt =',feld_flaeche,'mm2','/',stein_flaeche,'mm2'
print 'Steine Insgesamt =',steine_insgesamt,'Steine'
print ' '*18, '='*steine_insgesamt_zeichen,'\n'

mfg ba2
 
Hmm also wie ich das verstanden hab, soll man die Steine auch drehen,
um die optimale Fläche zu erhalten.

z.B:

Fläche 5x3
Stein: 2x2
Dann nicht nur einfach
[XX_]
[XX_]
[XX_]
[XX_]
[XX_]
(X= steinfeld, _=leer)
sondern
[XXO]
[XXO]
[XXO]
[XXO]
[XX_]
(O= gedrehter Stein)

Oder hab ich das nicht gecheckt?


Cya
 
Original von 0wnZ
schmeißt nur errors aus :o
Sorry, mehr Infos
Also: Unter WinXP mit Konsole sagt es, dass bei "Passt nicht" in den Zeilen 12, 14, 16, 18, 28 ein kEND erwartet wird anstelle von tCONSTANT
und in Zeile 35 wird ein $end anstelle eines kEND erwartet.
Ich hab den Code 1 zu 1 in Scite übernommen und einfach gesichert.

edit2: Ich sehs, da fehlen 2 "n"s nach dem \ für den Zeilenumbruch in den Zeilen 5 und 9 ! Damit wird das Anführungszeichen escaped und der String nicht beendet !
Zum Vergrößern anklicken....

Ja stimmt, ich hatte es schon bemerkt, dachte aber dass ich es schon richtig gepostet hätte

Ist verbessert
 
Hmmm, vielleicht solltet Ihr Euch erstmal untereinander klar werden, was Ihr überhaupt wollt? Bzw. was ihr meint?

Wenn Ihr von Problemen in 3 Dimensionen redet, solltet Ihr Euch ALLE darauf festlegen.
Wenn Ihr in zwei oder gar nur in einer Dimension denken wollt, natürlich dasselbe.
Sonst verhalten sich Eure Postings wie Socken zu Wackelpudding.

Ich vermute mal, daß das ursprünglich genannte Problem mitnichten darin besteht, zu beweisen, daß man simple Input- und Print-Operationen und Grundrechenarten in irgendeiner Programmiersprache beherrscht.

Aber vielleicht sagt der Aufgabensteller nochmal ein Wort dazu?

----

Ein paar weitere Gedanken:

Schon ein triviales Einstiegs-Beispiel zeigt, daß die Überlegungen zu Vereinfachungen allesamt Murks sind:

Man nehme längliche Bausteine 1*n und einen Kasten mit einer Seitenlänge von (n-1) * (2n-1). Senkrecht paßt nichts. Waagerecht paßt genau eine Reihe von n-1 Bausteinen, die aber ein riesiges Loch von (n-1)*(n-1) ungefüllt läßt. Dieses kann jedoch noch mit einer Menge von schräg liegenden Bausteinen gefüllt werden. Und eventuell wird der verbleibende Restplatz dadurch verringert, daß man sämtliche Bausteine von vornherein (und dann weniger schräg) einsetzt.

Nachdem ich jetzt zu dieser Erkenntnis gekommen bin, daß schräge Plazierung - falls sie vom Aufgabensteller nicht explizit ausgenommen wird - notwendig sein kann, halte ich die Aufgabe für überhaupt alles andere als trivial. Ideen zur bedingungslos und garantiert optimalen Lösung fehlen mir jedenfalls zur Zeit noch.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben