Hallo zusammen,
ich hoffe hier hilfreiche Antworten zu bekommen, wofür ich mich im
Vorfeld herzlich bedanke!
Es geht um u.g. c-code: er muss mir alle Kombination ausgeben von m von
n zahlen " vorab 4 von 5 ", was bereits realisiert. jetzt muss ich die
ausgegeben Möglichkeiten anhand weitere Vorgabe auf Plausibilität.
Mir fehlt der Ansatz und wäre für jeden Tipp sehr dankbar!
1
#include< stdio.h >
2
#include< stdlib.h >
3
#include< string.h >
4
//#include "_generate.h"
5
6
intfak1(intwert1)
7
{
8
if(wert1==1)return1;
9
elsereturn(wert1*fak1(wert1-1));
10
}
11
12
intfak2(intwert2)
13
{
14
if(wert2==1)return1;
15
elsereturn(wert2*fak2(wert2-1));
16
}
17
18
voidprint_array(intk,intarray[])
19
{
20
staticintcount=0;
21
inti;
22
23
printf("%d. Moeglichkeit: (",++count);
24
for(i=0;i<k-1;i++)
25
printf("%d,",array[i]);
26
printf("%d ) \n",array[k-1]);
27
28
29
}
30
voidMoeglichkeiten(intn,intk,intarray[],intx)
31
{
32
inti;
33
intmax;
34
35
if(x<k)
36
{
37
max=x?array[x-1]:0;
38
39
for(i=max+1;i<=n-k+x+1;i++)
40
{
41
array[x]=i;
42
Moeglichkeiten(n,k,array,x+1);
43
}
44
}
45
else
46
print_array(k,array);
47
48
}
49
50
51
intmain(intargc,char*argv[])
52
{
53
intMoeglichkeit;
54
55
intn=5;
56
printf("Fakultaet der Gesamtanzahl % d ! = % d \n ",n,fak1(n));
57
58
intm=4;
59
printf("Fakultaet der Benutzten Anzahl % d ! = % d \n ",m,fak2(m));
60
61
62
Moeglichkeit=fak1(n)/(fak2(m)*(fak1(n)-fak2(m)));
63
64
printf(" Anzahl der Moeglichkeit= %d \n\n ",Moeglichkeit);
Anfaenger_2015 schrieb:> jetzt muss ich die> ausgegeben Möglichkeiten anhand weitere Vorgabe auf Plausibilität.>> Mir fehlt der Ansatz und wäre für jeden Tipp sehr dankbar!
und mir(uns) fehlt was du eigentlich willst.
Kannst du nicht lesen? Steht da doch eindeutig die Aufgabe:
"er muss mir alle Kombination ausgeben von m von
n zahlen " vorab 4 von 5 ", was bereits realisiert."
Was ist daran nicht zu verstehen?
;)
Danke für die schnellen Rückmeldungen!
Es werden wie bereits erwähnt alle Möglichkeiten ausgegeben: 1.2.3.4 &
1.2.3.5 & 1.2.4.5 $ 1.3.4.5 % 2.3.4.5.
Die Zahlen 1 bis 5 müssen Schneidmesser darstellen, die eine Breite x
haben und alle hintereinander auf einer Schiene positioniert.
jetzt muss ich eine 1800 mm lange Rolle an vier Stellen schneiden: 400,
700, 1000, und 1300.
Der Breite nach von den Messer wären nur 1.2.3.4 & 2.3.4.5 physikalisch
realisierbar.
Hat jdn vielleicht eine Idee wie ich vorgehen soll.
Vielen Dank
Ich verstehe leider nur Bahnhof, insbesondere das "nur 1.2.3.4 & 2.3.4.5
sind physikalisch realisierbar."
Du hast doch dein Problem schon selber gelöst, wenn alle möglichen
Kombinationen ausgegeben werden, oder?
Zur Not hier mal ein Link, wo andere Leute das Problem umgesetzt haben:
http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n
(Hoffe es ist okay hier auf andere Seiten zu verlinken)
Vielen Dank Hendrik w. für deine Antwort.
Um das Problem zu erklären: berücksichtigen Wir die 2. Möglichkeit
1.3.4.5.
dh. dass, die Messer_1, Messer_3, Messer_4, Messer_5 gesetzt werden
müssen. in der Rhein und Folge: Messer_5 schneidet an der Stelle
1300mm.
Messer_4 schneidet an der Stelle 1000mm.
Messer_3 schneidet an der Stelle 700mm.
Messer_2 ist inaktiv. muss aber positioniert
werden!
Messer_1 schneidet an der Stelle 400mm.
Nicht zu vergessen, Dass die Messer auf einer Schiene sind bzw. dass
alle Messer 200 mm breit sind. Sprich: Messer_2 kann nicht zwischen
Messer_3 und Messer_1 positioniert werden, weil der übrige Abstand
zwischen Messer_3 und Messer_1 nur 100 mm.
===> Die Möglichkeit kann physikalisch nicht realisiert werden.
Ich hoffe, dass mir jdn bei dem Lösungsanatz helfen kann.
Viele Grüße
Hallo Anfaenger_2015,
Ich versuche mal, dein Problem verständlicher zu formulieren:
Gegeben ist:
* ein 1800mm langes Werkstück (Rolle)
* 4 Stellen an denen die Rolle gleichzeitig durchgeschnitten werden soll
* 5 Messer mit unterschiedlicher Breite der Halterung
Gesucht sind alle Kombinationen von Messern mit denen die 4 Schnitte
gleichzeitig durchgeführt werden können.
Richtig?
Ich gehe davon aus, dass die Messerhalterungen unterschiedlich breit
sind, denn warum würdest du sonst alle Kombinationen durchgehen wollen?
Wenn die Messerhalterungen alle gleich breit sind, brauchst du nur die
Abstände zwischen den 4 Schneid-Stellen mit der Messerbreite zu
vergleichen.
Das mit den Kombinationen macht meiner Meinung nach sowieso wenig Sinn
wenn die Reihenfolge der Messer vorgegeben ist. Ist das eine
Übungsaufgabe? oder eine reale Aufgabe? Wenn dann müsste man alle
aufsteigenden Teilfolgen der Indexmenge 1,2,3,4...,m der größe n
bestimmen aber auch das wäre viel Aufwand wenn das nicht nur auf die
paar messer im beispiel beschränkt bleiben sollte. Ich würde mal für
eine andere Perspektive die Messer aneinander ordnen. Im Prinzip wäre
das ja in einem eigenen Koordinatensystem ein Dirac Kamm mit summe über
alle i der Indexmenge dirac(x-i*200+100) (um in den ursprung zu
verschieben). Wenn man (was aus der Aufgabe auch nicht ganz klar ist)
die Messer verschieben darf, dann kommt noch eine variable verzögerung
d_i für jedes messer rein.
summe über i der Indexmenge dirac(x-i*200+100-d_i), wobei die d_i
zwischen 0 (alle direkt aneinander) und einer max Grenze die aus der
Aufgabe aber auch nicht hervorgeht. Eigentlich müssten ja jetzt die
Schnittpunkte c_i = i*200-100+d_i erfüllen für alle i der Indexmenge und
d_i müssen exisieren.
Sieht irgendwie nach ILP aus? Nur eine Idee!
Ich gehe davon aus, dass die Messerhalterungen unterschiedlich breit
> sind, denn warum würdest du sonst alle Kombinationen durchgehen wollen?
die Messerhalterungen sind eben gleich breit " 200 mm ".
Damit du besser nachvollziehen kannst, warum nicht alle Möglichkeiten
realisierbar sind, Sieh dir bitte das Foto im Anhang an.
Ich habe mir das Bild vorhin schon mehrfach angesehen und sehe nicht was
das mit Kombinationen zu tun hat.
Was ich aber sehe ist, dass du es in 5 Posts noch immer nicht geschafft
hast, das Problem für andere verständlich zu beschreiben. Im ersten
Posting steht bis auf das Wort "Plausibilität" kein Wort zur
eigentlichen Aufgabenstellung.
Was genau willst du denn herausbekommen? Wenn es nur die physisch
möglichen Kombinationen bei gegebenen Schnittbreiten sind, musst du doch
nur die paar 4er-Kombinationen durchprobieren. Sobald eines der Messer
nicht "passt" (Mindestabstand unterschritten), scheidet die
entsprechende Kombination aus.
Klingt für mich nach einer Backtracking Aufgabe.
Messer n wird entweder benutzt oder nicht benutzt.
Wenn es benutzt wird, dann wird es so positioniert, dass es an der
gewünschten Stelle schneidet, wenn das geometrisch möglich ist.
Wenn es nicht benutzt wird, dann wird es einfach an das vorhergehende
Messer rangeschoben (bzw. auf 0).
Und dann: 'Backtracken'.
Man kann natürlich alle Kombinationen von 'benutzt/nicht benutzt'
bestimmen und dann nachsehen, welche davon gültig sind. Backtracking hat
halt den Charme, dass es während des Abarbeitens gleich viele
Kombinationen ausschliesst (was bei 5 Messern sicher nicht das grosse
Problem ist. Messer 1 auf 400 und Messer 3 auf 700 funktioniert nicht,
egal wie man Messer 4 oder 5 (oder wenn es noch mehr sind dann alle
weiteren) positioniert.
Wieso werden die Messer nicht einfach der Reihenfolge nach auf den
Schnitten positioniert? Dann müsste man ja nur die minimale
Schnittbreite von 200mm überwachen.
Karl Heinz schrieb:> Klingt für mich nach einer Backtracking Aufgabe.>> Messer n wird entweder benutzt oder nicht benutzt.> Wenn es benutzt wird, dann wird es so positioniert, dass es an der> gewünschten Stelle schneidet, wenn das geometrisch möglich ist.> Wenn es nicht benutzt wird, dann wird es einfach an das vorhergehende> Messer rangeschoben (bzw. auf 0).>> Und dann: 'Backtracken'.>> Man kann natürlich alle Kombinationen von 'benutzt/nicht benutzt'> bestimmen und dann nachsehen, welche davon gültig sind. Backtracking hat> halt den Charme, dass es während des Abarbeitens gleich viele> Kombinationen ausschliesst (was bei 5 Messern sicher nicht das grosse> Problem ist. Messer 1 auf 400 und Messer 3 auf 700 funktioniert nicht,> egal wie man Messer 4 oder 5 (oder wenn es noch mehr sind dann alle> weiteren) positioniert.
Lieber karl Heinz,
das hast du 100% richtig verstanden. bei 4 aus 5 Messer ist es einfach
zu lösung. Die Proleme hat man wie du richtig beschrieben hast, ab 4
Messer aus 6 Messer.
Tek schrieb:> Wieso werden die Messer nicht einfach der Reihenfolge nach auf den> Schnitten positioniert? Dann müsste man ja nur die minimale> Schnittbreite von 200mm überwachen.
lieber Tek, wdas würde gehen bei 4 aus 5 messer. Wenn du aber 6 , 7 oder
mehr Messer hast, davon aber logischerweise nur 4 verwenden kannst [ an
den Stellen ( 400,700,1000,1300)] dann kannst du die INAKTIVE Messer aus
Platzmangel nicht positionieren
Anfaenger_2015 schrieb:> Lieber karl Heinz,> das hast du 100% richtig verstanden. bei 4 aus 5 Messer ist es einfach> zu lösung. Die Proleme hat man wie du richtig beschrieben hast, ab 4> Messer aus 6 Messer.
Ja, gut. Macht ja nix.
Für eine Backtracking Lösung ist die Anzahl der Messer algorithmisch
recht irrelevant.
Tek schrieb:> Wieso werden die Messer nicht einfach der Reihenfolge nach auf den> Schnitten positioniert? Dann müsste man ja nur die minimale> Schnittbreite von 200mm überwachen.
Stell dir eine Komplettschnittbreite von 2000 vor und du sollst 1
Schnitt bei 1700 machen. Du hast 5 Messer auf der Schiene (jedes ist
200mm breit) und musst die so verschieben und aktiv/inaktiv machen, dass
du den gewünschten Schnitt bei 1700 hinkriegst ohne dass ein Messer von
der Schiene runtergenommen werden muss.
Du kannst dafür nicht einfach Messer 1 benutzen, denn alle weiteren
Messer sind ja rechts davon. Sitzt Messer 1 auf 1700, dann ist seine
rechte Kante bei 1800 und zwischen 1800 und 2000 passen die restlichen 4
Messer nicht mehr rein.
An dieser Stelle geht nur
* Lösung 1
Messer 1 ganz links, inaktiv
Messer 2 rechts neben 1, inaktiv
Messer 3 rechts neben 2, inaktiv
Messer 4 auf 1700 eingestellt, aktic
Messer 5 rechts neben 4, inaktiv
* Lösung 2
Messer 1 ganz links, inaktiv
Messer 2 rechts neben 1, inaktiv
Messer 3 rechts neben 2, inaktiv
Messer 4 rechts neben 3
Messer 5 auf 1700 eingestellt, aktiv
D.h. diese Aufgabe ist entweder mit Messer 4 oder mit Messer 5 lösbar.
Mit allen anderen funktioniert es nicht, weil sich sonst die inaktiven
Messer gegenseitig im Weg sind.
Alles in allem: eine schöne Backtracking Aufgabe. Ordne n Elemente so an
(Abstand + Aktivierung), dass gewisse Nebenbedingungen eingehalten
werden.
Wenn ich jetzt noch wüsste, ob das Ganze Hausaufgabe oder
Produktionscode ist.
> Wenn ich jetzt noch wüsste, ob das Ganze Hausaufgabe oder> Produktionscode ist.
Das ist eine Aufgabe, die mir Als Praktikant gegeben wurde.
int schnitte[] = {0,400, 700, 1000, 1300,1800};
Beispiel: { 3.4.5.6} im Fall 4 aus 6 Messern
Mein Problem ist wie ich die Formel/ if ( schnitte[b]-schnitte[b-1] <
(combination[b]-combination[b-1]) * mindestbreite ) verbessern kann,
dass die Möglichkeit als nicht realisierbar ausgegeben wird
Anfaenger_2015 schrieb:> Mein Problem ist
Hatte ich doch oben in dem Ruby Text angegeben:
cut_pos[k.index(b)] usw.
(Das mit dem index() ist eigentlich nicht schön da recht ineffizient,
aber mit fiel da so spontan nichts besseres ein...)
Du musst den Index des Messers auf dessen räumliche Position abbilden,
dann die Differenz benachbarter Messer berechnen und testen ob sie groß
genug ist. Aber für einen 16 jährigen Praktikanten, und dann noch in C,
ist das wirklich etwas unangenehm. Übrigens, mein Code oben funktioniert
wohl nicht, wenn alle Messer im Einsatz sind, dann ist
combination(disabled) undefiniert, man muss da eine Fallunterscheidung
einbauen. Na ja, vielleicht macht Dir Herr Buchegger das ja in C,
womöglich noch mit Backtracking. Das traurige ist aber eigentlich, dass
Du die Aufgabe anfangs auch nicht ansatzweise selbst beschreiben
konntest. Was mir übrigens nicht klar war, ist ob die gesamtlänge der
Rolle relevant ist. Ich hatte angenommen dass die nicht von Bedeutung
ist, aber womöglich kann ein Messer ja auch nicht ganz nah am Ende
positioniert werden?
Salewski, Stefan schrieb:> Anfaenger_2015 schrieb:>> Mein Problem ist>> Hatte ich doch oben in dem Ruby Text angegeben:>> cut_pos[k.index(b)] usw.>> (Das mit dem index() ist eigentlich nicht schön da recht ineffizient,> aber mit fiel da so spontan nichts besseres ein...)>> Du musst den Index des Messers auf dessen räumliche Position abbilden,> dann die Differenz benachbarter Messer berechnen und testen ob sie groß> genug ist. Aber für einen 16 jährigen Praktikanten, und dann noch in C,> ist das wirklich etwas unangenehm.
Ich bin ein Praktikant, aber kein 16 jähriger :). Praktikant der sich
während des Studium mit Prorammiersprachen halbwegs beschäftigen durfte.
Übrigens, mein Code oben funktioniert
> wohl nicht, wenn alle Messer im Einsatz sind, dann ist> combination(disabled) undefiniert, man muss da eine Fallunterscheidung> einbauen. Na ja, vielleicht macht Dir Herr Buchegger das ja in C,> womöglich noch mit Backtracking. Das traurige ist aber eigentlich, dass> Du die Aufgabe anfangs auch nicht ansatzweise selbst beschreiben> konntest. Was mir übrigens nicht klar war, ist ob die gesamtlänge der> Rolle relevant ist. Ich hatte angenommen dass die nicht von Bedeutung> ist, aber womöglich kann ein Messer ja auch nicht ganz nah am Ende> positioniert werden?
Viel dank für deine Aufklärung und verzeiht bitte alle zusammen, dass
ich ungenau mein Problem beschrieben habe. Das liegt an meine
Unerfahrenheit. Ich war der Meinung, dass ich mit den Angaben: Anzahl
der Messern + Schnittstellen+ wie die Messer auf einer Schiene
positioniert sind, meine Aufgabe vollständig beschrieben habe.