BlackBoard (http://www.black-board.net/index.php)
- Sonstiges (http://www.black-board.net/board.php?boardid=34)
-- Bildung (http://www.black-board.net/board.php?boardid=39)
--- eine mathematische frage... (http://www.black-board.net/thread.php?threadid=9939)
Geschrieben von scr!pTk!d am 22.01.2003 um 18:50:
eine mathematische frage...
an die mathematiker unter euch:
wir sollen von der schule aus innerhalb einer woche folgende aufgabe und ich wäre euch dankbar wenn ihr mir tips(oder vielleicht sogar eine lösund) geben könntet:
Wieviele Möglichkeiten gibt es n cent mit 5-, 2- und 1-cent stücken darzustellen?
ich habe keine ahnung wie das anpacken soll...
Geschrieben von zira am 22.01.2003 um 19:43:
Anzahl = f ( n ) ???
Gibt bestimmt irgend eine Lösung für diese Funktion.
Ich denke da vor allem an Serien und Permutationen.
Geschrieben von Black Star am 22.01.2003 um 19:55:
also mir mag dazu nur ein rekursiver algorithmus einfallen.
du brauchst halt alle permutationen, die n ergeben:
anzahl x cent
1: 1x1
2: 2x1; 1x2
3:....
......
11: 2x5+1x1; 1x5+3x2; 1x5+2x2+2x1;.........
daruas eine gleichnung für n abzuleiten könnte etwas heftig werden - gib mir ein wenig zeit
EDIT: darf modulo in der funktion drinstehen?
(modulo ist der rest beim teilen)
edit2:
funktioniert vermutlich mit binominalkoeffizienten (3 über 5) z.B.
resp. mit fakultät.
Geschrieben von Black Star am 22.01.2003 um 22:02:
wir ham was - hier eine unterhaltung asu dem irc-chan
| Zitat: |
<Black-Star> LX?
<chipdalf> na dann, bye und cu
<LX> Black-Star?
<-- chipdalf (~chip@euirc-f081494b.adsl.green.ch) has left #blackboard (Client Exiting)
<Black-Star> hast du den mathe-thread gelesen?
<LX> mit den Münzen?
<Black-Star> ja
<Black-Star> ist dir schon was eingefallen?
<Black-Star> ich hab hier drei mathebücher liegen, aber nichts passt
<LX> *g
<LX> na ich hab die Frage zuerst falsch gelesen
<Black-Star> das ist keine gewühnliche wahrscheinlichkeitsrechnung, weil die ganze scheisse zusammenaddiert n ergeben muss
<LX> wir hatten mal eine ala "Finde die Möglichkeit Betrag X mit so wenig wie möglich Münzen zu erreichen"... aber das ist billig
<Black-Star> jetzt ist die anzahl gefragt
<LX> eben
<-- Guest36776 (~ups@euirc-fd70b1f7.dip.t-dialin.net) has left #blackboard
<LX> so recht eingefallen ist mir nix, hab aber zugegebenermaßen auch net lange nachgedacht nachdem ich festgestellt hab, dass ich beinahe die falsche Frage beantwortet hab *g
<Black-Star> ich hab schon 5 zettelchen vollgekritzelt *g
<LX> kann ja mal bischel überlegen, aber ich hatte net soviel Mathe wie du 
<Black-Star> das ist kombinatorik, und zwar nich ohne
<LX> tscha, und mit Wahrscheinlichkeiten hatte ich nie viel am Hut... hab's nur im 2. Semester mal bischel anner FH gehabt, aber das war nicht gerade die höhere Stufe
<LX> ich hol mal eben Zettels
--> UPS_BB (~ups@euirc-112cf9da.dip.t-dialin.net) has joined #blackboard
--- ChanServ sets mode +a #blackboard UPS_BB
--- ChanServ gives channel operator status to UPS_BB
<LX> hat's geklappt mit dem zusenden?
<UPS_BB> ne
<Black-Star> LX: ich rechne mal die ersten 11 per hand, vl kann man ne formel sehen
<LX> ich hab die ersten 5 momentan
<LX> UPS_BB: aber wie kommst du dann jetzt rein?
<UPS_BB> ich hab Ksirc wieder
<Black-Star> LX: ich seh schon was mit modulo erkennen
<LX> Black-Star: 1 - 1; 2 - 2; 3 - 2; 4 - 3; 5 - 4
<LX> und da ist das PW gespeichert?
<Black-Star> 6-5 7-6 8-7 11-11 19-26
<Black-Star> das ist ne 100%ige rekursionsformel
<Black-Star> LX: für 2 ct und 1ct gibts n/2 + n%2 möglichkleiten....
<LX> aha
<LX> hab noch den Physik-Erstsemester auf die Aufgabe losgelassen *g
<LX> mal gucken, ob der im Laufe des Abends noch was rausfindet *g
<Black-Star> wen?
<LX> 'n Freund von mir
<Black-Star> es gibt glaubich zwei wege - einen informatiker-weg mit modulo und austesten, und einen ,athematiker-weg mit kombinatorik
<LX> ich versuche gerade noch die n%2 + n/2 nachzuvollziehen
<LX> aber ich glaub ich hab's gleich
<Black-Star> das ist ohne 5ct - ich mach grad das upgrade auf 5ct
<LX> jo, ich weiß
<Black-Star> ich glaub aber, das ist n/2 + 1
<Black-Star> ja n/2 + 1
<Black-Star> weil nur einsen gibts ja immer
<Black-Star> und das / ist immer abrunden
<Black-Star> wie div bei pascal
<LX> oder trunc bei SQL
* LX ist datenbankengeschädigt
<LX> aber wie kommste jetzt auf n/2?
<LX> +1
<Black-Star> guck mal bei 9....
<Black-Star> 4x2 + 1
<Black-Star> 3x2 + 3x1
<Black-Star> 2x2 + 5x1
<Black-Star> 1x2 + 7x1
<Black-Star> 9x1
<LX> hat bei 5 net hin
<LX> +u
<LX> bei 5 gibt's 4 Möglichkeiten
<Black-Star> weil 1x5
<LX> nach der Formel komme ich nur auf 3
<Black-Star> ja is ja noch nicht auf 5ct upgegradet
<LX> na ich denke das ist schon das Endergebnis?
<LX> d'oh *g
<Black-Star> neien nein
<Black-Star> ich arbeite an dem 5er upgrade
<Black-Star> ich hab hier die splits für 19 und 23 stehen
<LX> omannomann... also die Aufgabe ist mir ehrlich zu hoch *g
<LX> ich gesteh's mir selten ein, dass ich was net kann, aber hier bleibt mir momentan nix weiter übrig
<Black-Star> mich fuchst das blöde ding
<LX> ich würde also den Informatikerweg vorziehen *g
<Black-Star> das kann doch nicht so schwer sen
<Black-Star> +i
<Black-Star> auf dem befinde ich mich ja
<Black-Star> das müssen doch schüler rauskriegen können
<LX> tscha
<Black-Star> ich steh kurz vor ner lösung mit summenschreibweise
<LX> mmh, ich glaube ich hab hier auch was...
<Black-Star> erzähl
<LX> also wie gesagt bei 1ern und 2ern hat man immer n%2+1 Möglichkeit
<Black-Star> n/2 + 1
<Black-Star> nicht module
<Black-Star> -e +p
<Black-Star> -p +o
<LX> ups, meinte DIV
<LX> stimmt, % ist Modulo
<LX> also n DIV 2 + 1
<LX> denke mal bin auf demselben Weg wie du... ich addiere dann immer 1 + (n-1*5) * (n DIV 2 + 1)
<LX> + 2 + (n-2*5) * (n DIV 2 + 1)
<LX> usw.
<Black-Star> mmmh
<Black-Star> mein buffy-cron-job läuft
<LX> jetzt geht's eben nur darum, den letzten Teil in eine Summenformel zu kriegen
<Black-Star> ich arbeite dran
<Black-Star> ich hab eine - testing.....
<LX> hab auch eine, aber ob die stimmt
<Black-Star> bei 19 klappt meine
<Black-Star> ich geh buffy gucken - bis zum werbeblock
<LX> also mein Ergebnis: 1 + nDIV2 + SUMME von i=1 bis nDIV5 über (i + (n - i*5) * (1 + nDIV2)
<LX> und noch 'ne Klammer zu
<LX> ich teste auch mal ob das hinhauen würde
<andy`> schreibt man die programmiersprache assambler so?
<andy`> oder assembler...?
<LX> Assembler
<andy`> thx
<LX> Black-Star: nee, meine Formel haut net ganz hin, da fehlt noch ein bissel
<Black-Star> re
<Black-Star> testing.........
<LX> bei meiner Formel haut die Summe hinten noch net hin, kommen zu große Werte raus
<LX> ich muss noch was davon abziehen
<Black-Star> bis 7 passt meine
<Black-Star> bei 19 passt sie
<Black-Star> hast du zufällig den wert für eine durch 5 teibare
<Black-Star> +l
<LX> ja, für 5 *g
<Black-Star> ok ich mach für 15
<Black-Star> 18 kommt für 15 raus - testing....
<LX> hmm, bei 6 haut meine ausgebesserte net hin
<Black-Star> werbung is aus
<LX> ich hab jetzt (1 + nDIV2) + SUMME von i=1 bis nDIV2 über (n - 5i)*(1+(n-5i)DIV2))
<LX> möööö
<Black-Star> re
<Black-Star> meine scheint zu funzen
<Black-Star> 1 + n
<Black-Star> hups
<Black-Star> 1 + n/2 + Summe{[k=1 bis n/5] (n-5k) / 2 +1}
<LX> (1 + nDIV2) + SUMME[i=1 bis nDIV2](i+(n-5*i)DIV2)
<LX> die hab ich
<Black-Star> bis n div 5
<LX> ups, ja
<Black-Star> und 1 + ... statt i
<LX> bei mir net
<Black-Star> funzt bei 1-7, 11, 15, 19
<LX> aber ich hab sie noch net richtig testen können
<LX> ich grüble gerade, wie ich in Derive das DIV ausdrücke *g |
wie oben gesehen funzt die karre halbwegs.
ich schreibs noch mal schöner hin.
bis demnächst
Geschrieben von Compuholic am 22.01.2003 um 23:18:
@BlackStar:
Ich weiß ja nicht genau, was Du versuchst, aber ich denke, daß Du zu kompliziert denkst. Man muß doch einfach nur die maximal Möglichen Kombinationen herausfinden die 5 cent ergeben und das ganze dann auf dem Betrag hochrechnen.
5 cent lassen sich darstellen als
1x5
2x2 + 1x1
1x2 + 3x1
5x1
Gibt 4 Möglichkeiten für einen Betrag von 5 cent. Da wir jetzt aber einen Betrag von n Cent haben teilen wir das n durch 5 (keine Nachkommastellen). Wenn wir das Ergebnis mal m nennen ergeben sich allein daraus 4^m Möglichkeiten.
Das gleiche Spiel machen wir jetzt auch noch mit dem Verbleibenden Rest.
2 cent lassen sich mit 1x2 und 2x1 cent-stücken herstellen. Wir dividieren also den Rest durch 2 und zählen die hinzukommenden Permutationen zu den bereits existierenden hinzu. Sollte bei der Division immer noch ein Rest übrigbleiben kann man den sich hinters Knie binden, weil der Rest (sofern er existiert) in jedem Fall 1 ist und somit nur eine Möglichkeit in Frage kommt. Also braucht er nicht zu berücksichtigt werden.
Wenn ich jetzt den mathematischen Ausdruck für eine ganzzahlige Division kennen würde könnte ich ne Formel aufstellen (natürlich nur wenn ich grade keinen Denkfehler gemacht habe)
Ich unterstelle jetzt einfach mal das Zeichen "div"
4^(n div 5) + 2^(2 mod (n div 5))
[edit]
vergesst es so funktioniert die formel nicht. muß mal schauen, wo mein denkfehler liegt
[/edit]
Geschrieben von LX am 22.01.2003 um 23:18:
Okay, also Black Star postet gleich noch die Formel schön als Grafik, ich poste hier mal'n kleines C-Programm, wo die Formel eingebettet ist:
| code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
|
#include <stdio.h>
int main()
{
int n, Ergebnis, i;
while (n < 100)
{
printf("Bitte Zahl angeben: ");
scanf("%d",&n);
Ergebnis = (1 + n/2);
for (i = 0; i < n/5; i++)
{
Ergebnis += (1 + (n-5*(i+1))/2);
}
printf("%d\n",Ergebnis);
}
return(0);
} |
|
Ohne irgendwelche Abfragen. Beenden bei Eingabe einer Zahl größer gleich 100.
Geschrieben von Black Star am 22.01.2003 um 23:23:
so hier ist unsere formel als paint-gemälde
ich hab alles versucht, die summe zu zertrümmern, aber das wird beliebig kompliziert, weil das / ein echtes teilen ohne rest ist.
also klammern beachten, und immer ohne rest teilen.
die formel ist getestet bei 1-7,11,15,19 und 36, und rein logisch absolut logisch
Geschrieben von LX am 22.01.2003 um 23:47:
Wer ^das Gekrakel^ net lesen kann:
*duck*
Geschrieben von Exekutor am 23.01.2003 um 07:54:
Nur mal so als info, ich habe ja von dem ganzen Zeugs keine Ahnung.. habe ja Realabschluß, aber damit ihr wißt wieviel mühe die sich gemacht haben:
ich kam gestern frohen mutes, das ich mein system wieder zum laufen bekommen habe, also in den IRC-Channel, um ein wenig zu paudern, und was sah ich? wie sich 4, 5 leute mathematische formeln und funktionen um die ohren schlugen, und das nicht nur ein paar minuten, nein, nach einer stunde bin ich dann ins bett.. ich glaub da kamen sie so langsam ans ziel..
Ciao Exe
Geschrieben von LX am 23.01.2003 um 13:10:
4, 5 ist übertrieben. Eigentlich waren's nur Black Star und ich, und später kam noch Compuholic dazu, um uns zu verwirren *g
Aber da sieht man's mal wieder: IRC... da werden Sie geholfen
Geschrieben von Compuholic am 23.01.2003 um 22:02:
Hab mich grade nochmal mit der Sache beschäftigt. Ich habe jetzt den Denkfehler. Es werden nicht alle Kombinationen berücksichtigt (z.B. der Fall, das sich der Betrag vollständig aus 2c Münzen zusammensetzt). Außerdem dürfen keine Potenzen verwendet werden, sondern eine einfache Multiplikation.
Man muß das ganze genau andersrum angehen (von klein nach groß). Also erst einmal Prüfen wie viele Kombinationen sich durch den alleinigen Einsatz von 2c Stücken erreichen lassen. Wie viele dadurch sich durch 5c Kombinationen ersetzen lassen.
Dann kommt das raus, was Black-Star gepostet hat.
Geschrieben von scr!pTk!d am 24.01.2003 um 13:49:
hi also erstmal vielen dank für eure antworten!
(was ist denn k in eurer formel?)
...
jemand hat mir noch eine andere formel vorgelegt, aber ob sie stimmt weiß ich nicht... :
| Zitat: |
Lösung: r {0,1,2,3,4} sei der Rest der Division n:5, dann beträgt die gesuchte Anzahl:
1/20*[(n+4)²-(r-1)²+ 5/2*((-1)[sup]r[/sup] +(-1)[sup]n[/sup])]
|
stimmt diese formel auch?
mfg
scr!pTk!d
(erstaunlich wie 'schwierig' die lösung eines scheinbar einfachen problems ist hehe)
Geschrieben von LX am 24.01.2003 um 17:41:
| Zitat: |
Original von scr!pTk!d
(was ist denn k in eurer formel?) |
k ist der Zählindex der Summe.
| Zitat: |
jemand hat mir noch eine andere formel vorgelegt, aber ob sie stimmt weiß ich nicht... :
| Zitat: |
Lösung: r {0,1,2,3,4} sei der Rest der Division n:5, dann beträgt die gesuchte Anzahl:
1/20*[(n+4)²-(r-1)²+ 5/2*((-1)[sup]r[/sup] +(-1)[sup]n[/sup])]
|
stimmt diese formel auch? |
Ob sie stimmt, kann ich net sagen. Habe mal für 76 als n durchgerechnet. Bei unserer Formel kommt man auf 320 Möglichkeiten, bei der Formel da (wenn man mit Fließkommazahlen rechnet) auf 320,175
Das ist ziemlich nahe dran, dafür dass die beiden Formeln völlig unterschiedlich aussehen *g
Bin noch dabei, diese Formel auch in ein Progrämmchen einzubetten, um ein paar mehr Werte vergleichen zu können.
Geschrieben von scr!pTk!d am 24.01.2003 um 19:22:
sehr gut! danke
Forensoftware: Burning Board 2.3.6, entwickelt von WoltLab GmbH