Hackerboard Wiki HaboBlog
Hackerboard bei Facebook Hackerboard bei Google+ Hackerboard bei Twitter

[HaBo]

 
Programmieraufgaben Hier wird regelmäßig eine neue Programmieraufgabe gestellt, die dann gelöst werden soll und in Zusammenarbeit mit den Moderatoren auch besprochen werden kann.

Wieviele Steine passen in eine Fläche?

Diskussion: Wieviele Steine passen in eine Fläche? im Forum Programmieraufgaben, in der Kategorie Code Kitchen; Anzeige Eine Aufgabe von benwilliam: Es soll ein Algorithmus entwickelt werden der die maximale Anzahl an Bausteinen bestimmt die in ...

Antwort
Alt 29.11.06, 18:15   #1 (permalink)
CDW
Moderator
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: Opteron
Likes: 202
Standard Wieviele Steine passen in eine Fläche?

Anzeige

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.

__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
CDW ist offline   Mit Zitat antworten
Alt 29.11.06, 22:13   #2 (permalink)
 
Benutzerbild von mauralix
 
Registriert seit: 17.04.06
mauralix Leistung: 8086
Likes: 3
Standard

Das ganze hört sich nach dem berühmten Rucksackproblem an

Nein, muss mich korrigieren...
Das Rucksackproblem war doch was anderes http://de.wikipedia.org/wiki/Rucksackproblem
mauralix ist offline   Mit Zitat antworten
   
HaBOT
 
- Anzeige -

Werbung ist gerade online    
Alt 04.12.06, 21:40   #3 (permalink)
 
Registriert seit: 03.06.06
cagiv Leistung: Facit NTK
Likes: 0
Standard

Sry ,aber ich glaub ich seh das Problem vom Problem irgendwie nicht

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
cagiv ist offline   Mit Zitat antworten
Alt 04.12.06, 22:50   #4 (permalink)
Moderator
 
Benutzerbild von lightsaver
 
Registriert seit: 19.06.06
lightsaver Leistung: Pentium Ilightsaver Leistung: Pentium Ilightsaver Leistung: Pentium I
Likes: 52
Standard

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 ist offline   Mit Zitat antworten
Alt 05.12.06, 06:19   #5 (permalink)
 
Registriert seit: 03.06.06
cagiv Leistung: Facit NTK
Likes: 0
Standard

@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
cagiv ist offline   Mit Zitat antworten
Alt 05.12.06, 07:27   #6 (permalink)
Moderator
 
Benutzerbild von lightsaver
 
Registriert seit: 19.06.06
lightsaver Leistung: Pentium Ilightsaver Leistung: Pentium Ilightsaver Leistung: Pentium I
Likes: 52
Standard

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.
lightsaver ist offline   Mit Zitat antworten
Alt 14.12.06, 21:10   #7 (permalink)
 
Registriert seit: 16.07.05
benwilliam Leistung: Facit NTK
benwilliam eine Nachricht über ICQ schicken
Likes: 0
Standard

@cagiv
außerdem hat ja auch iemand vom Volumen gesprochen ;-)
benwilliam ist offline   Mit Zitat antworten
Alt 14.12.06, 21:47   #8 (permalink)
 
Registriert seit: 23.10.06
raven88 Leistung: Facit NTK
Likes: 0
Standard

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.
raven88 ist offline   Mit Zitat antworten
Alt 14.12.06, 21:52   #9 (permalink)
 
Registriert seit: 25.06.06
0wnZ Leistung: Facit NTK
0wnZ eine Nachricht über ICQ schicken
Likes: 0
Standard

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 ).
0wnZ ist offline   Mit Zitat antworten
Alt 22.08.07, 01:34   #10 (permalink)
 
Registriert seit: 06.12.06
CrazyMoE Leistung: Facit NTK
CrazyMoE eine Nachricht über ICQ schicken
Likes: 0
Standard 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
CrazyMoE ist offline   Mit Zitat antworten
Alt 22.08.07, 01:56   #11 (permalink)
CDW
Moderator
Themenstarter
 
Benutzerbild von CDW
 
Registriert seit: 20.07.05
CDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: OpteronCDW Leistung: Opteron
Likes: 202
Standard

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
__________________
Noch mal, für alle Pseudo-Geeks: 1+1=0. -> 10 wäre Überlauf!
Selig, wer nichts zu sagen hat und trotzdem schweigt.
CDW ist offline   Mit Zitat antworten
Alt 22.08.07, 08:58   #12 (permalink)
Copykill
Guest
 
Likes:
Standard

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?
  Mit Zitat antworten
Alt 22.08.07, 18:16   #13 (permalink)
 
Benutzerbild von Eydeet
 
Registriert seit: 14.04.06
Eydeet Leistung: Facit NTK
Likes: 4
Standard

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.

matchingBoxes.cpp   
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;
}
Eydeet ist offline   Mit Zitat antworten
Alt 15.12.07, 18:22   #14 (permalink)
JTron
Guest
 
Likes:
Standard

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
  Mit Zitat antworten
Alt 15.12.07, 21:16   #15 (permalink)
 
Registriert seit: 25.06.06
0wnZ Leistung: Facit NTK
0wnZ eine Nachricht über ICQ schicken
Likes: 0
Standard

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 !
0wnZ ist offline   Mit Zitat antworten
Antwort
   
- Anzeige -

Werbung ist gerade online    

[HaBo] » Software Home » Code Kitchen » Programmieraufgaben » Wieviele Steine passen in eine Fläche?
Themen-Optionen
Ansicht

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks sind aus
Pingbacks sind aus
Refbacks sind aus


Ähnliche Themen
Thema Autor Forum Antworten Letzter Beitrag
5cm weiser Fläche sprudelgehirn (Web-) Design und webbasierte Sprachen 3 06.10.09 16:03
Wieviele Forumsmitglieder braucht man, um eine Glühbirne zu wechseln? ivegotmail Fun Section 22 16.09.07 21:14
Wieviele Telefonnummern q9fx7 Internet Allgemein 2 13.09.07 19:18
Wieviele Firmen haben eine Sicherheitspolitik? saftig (In)security allgemein 1 05.03.06 18:19
[JAVA] Tetris - Rotation der Steine Boar Code Kitchen 13 20.06.05 20:49


1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61