Avatar billede skalerbar Nybegynder
05. maj 2003 - 12:50 Der er 21 kommentarer og
2 løsninger

Antal muligheder

Hvis jeg har tre rutepar
A til E
B til D
C til A

Hvordan finder jeg ud af hvor mange muligheder der  er for at kombinere turene?
eneste krav er at efter turen er alle blevet kørt "hjem"
Så A-D-E-C-A-B duer feks. ikke

man skal både kunne køre:
feks.
A-B-C-E-D-A

og
A-E-B-C-D-A

osv.

Hvordan laves  fornuftig kode der kan beskrive/løse dette
Avatar billede disky Nybegynder
05. maj 2003 - 12:59 #1
Du laver en graf.
Avatar billede skalerbar Nybegynder
05. maj 2003 - 13:07 #2
?
Avatar billede roenving Novice
05. maj 2003 - 13:17 #3
Hvis du skal starte og slutte i A, og skal bruge destinationerne op, så har du (4 * 3 * 2 * 1) muligheder, altså som formel (n er antallet af første destinationer):

n!
Avatar billede arne_v Ekspert
05. maj 2003 - 13:26 #4
roenving>

Som jeg forstår opgaven, så skal der være en A før end en E,
en B før end en D og en C før end en A.
Avatar billede roenving Novice
05. maj 2003 - 13:47 #5
>Jamen så holder min formel også, blot er der kun 3 første-destinationer!
Avatar billede arne_v Ekspert
05. maj 2003 - 13:54 #6
Øh.

Så vidt jeg lige kan se, så er der med de specifikke ruter 12 muligheder.

Med andre ruter må der være færre.
Avatar billede roenving Novice
05. maj 2003 - 14:01 #7
Du har ret (skyd den mand) -- men der må være en generel metode til beregning!
Avatar billede arne_v Ekspert
05. maj 2003 - 14:14 #8
Sikkert.

Er der nogen Mat.Øk.'ere tilstede ?
Avatar billede skalerbar Nybegynder
05. maj 2003 - 14:28 #9
Jeg skulle mene, jeg havde sjusset mig frem til ca. 44
Avatar billede roenving Novice
05. maj 2003 - 14:37 #10
12 er rigtigt:

aebcda
aebdca
aecbda

abedca
abecda
abdeca
abdcea
abcdea
abceda

acebda
acbdea
acbeda
Avatar billede skalerbar Nybegynder
05. maj 2003 - 14:50 #11
fek.s

A-E-B-C-A-D


B-A-C-A-E-D

mfl.
Avatar billede roenving Novice
05. maj 2003 - 15:08 #12
OK, -- ikke start og slut samme sted (a)
Avatar billede arne_v Ekspert
05. maj 2003 - 15:14 #13
Se det bliver det jo absolut ikke nemmere af.
Avatar billede skalerbar Nybegynder
05. maj 2003 - 15:16 #14
hvem havde sagt det skulle være nemt :)
Bare "alle bliver kørt hjem" er jeg ligeglad hvordan
Avatar billede roenving Novice
05. maj 2003 - 15:22 #15
Een rute: 1 mulighed
To ruter: 6 muligheder
Tre ruter: -- hmm kompliceret:
Du starter på en rute, 3 muligheder,
derefter har du to ikke påbegyndte ruter, 6 muligheder
og afslutningen af din første rute, som kan placeres på 5 forskellige pladser, altså ialt 90 ruter.
Avatar billede segmose Nybegynder
05. maj 2003 - 15:26 #16
har du husket c-b-a-e-d?
Avatar billede segmose Nybegynder
05. maj 2003 - 15:35 #17
Hvor hjernen svigter brug brute force
for (char pos1 = 'A'; pos1 < 'F'; pos1++)
for (char pos2 = 'A'; pos1 < 'F'; pos2++)
for (char pos3 = 'A'; pos1 < 'F'; pos3++)
for (char pos4 = 'A'; pos1 < 'F'; pos4++)
for (char pos5 = 'A'; pos1 < 'F'; pos5++) {
  pos6 = ' ';
  if CheckOkCombi()
    ok++;
  for (char pos6 = 'A'; pos1 < 'F'; pos6++) {
    if CheckOkCombi()
      ok++;
  }
}
Avatar billede roenving Novice
05. maj 2003 - 17:31 #18
segmose, du har ret ...

men ellers

Hvis du skal beregne brutto-antallet af mulige ruter skal man for hver tilkommen rute gange med n*(2n-1), dvs. 3 ruter:

3*5*2*3*1*1 = 90

og så har vi den generelle formel (?);

men så har du det samme punkt to gange (en gang som start og en gang som slut) og det vil sige, at vi skal fjerne alle forekomster af slutpunkt a, som kommer efter startpunkt a efter c, samt forekomster hvor de i øvrigt er naboer ...

dvs.
1. startpunkt c = 6 muligheder
1. startpunkt a = 30 muligheder
1. startpunkt b, 2 forskellige:
  - c foran første forekomst af a = 4 muligheder
  - a foran første forekomst af c = 15 muligheder

Ialt 55 ruter

mvh
jes
Avatar billede segmose Nybegynder
06. maj 2003 - 08:55 #19
jes, problemet er at Skalerbar's problem er lidt flydende, jeg antager en masse og du også noget, vi ved ikke om det er begrændsninger i antal mellemstationer, vi antager at der ikke må være mere end 6 ialt, vi antager at der må være 5,
at unødvendige mellemstationer ikke må forekomme etc.

Derfor kan vi ikke sigde at nogle combier reelt er udelukket, umiddelbart ville der være et uendeligt antal combier ud fra den måde spørgsmålet er stillet, da der ikke er taget forbehold for at der ikke må være unødvendige mellemstop.
Avatar billede roenving Novice
06. maj 2003 - 08:58 #20
Næh,

men når han bruger ordet 'hjem' i sin beskrivelse, har vi jo taget udgangspunkt i, at det f.eks. kunne være en bil, som skulle samle nogen op og sætte dem af -- og så ville det være unaturligt ikke at stå af, første gang man har chancen ...
Avatar billede roenving Novice
06. maj 2003 - 09:05 #21
Forøvrigt behøver vi slet ikke at gå ud fra den slags for at få astronomiske tal, ved 4 ture er det 28*90 = 2520 teoretiske,
ved 5 ture 45*2520 = 113400 ture,
ved 6 ture 66*113400 = 7.484.400 ture
.
.
.
ved 10 ture 190*12504636144000 = 2.375.880.867.360.000

og vi er stadig ved den simpleste form for tur: eet start-punkt og eet slutpunkt !~|

:o)
Avatar billede skalerbar Nybegynder
06. maj 2003 - 11:31 #22
Segmose:
Den kode du hare skrevet, har du noget mod at skrive den for dummies ( med  alle parametre)
Avatar billede segmose Nybegynder
06. maj 2003 - 13:09 #23
Den er ikke lige sådan at ud fylde, men lav et

char
  pos[6];

og brug den til lykkerne altså

for (pos[0] = 'A'; pos[0] < 'F'; pos[0]++)

og

CheckOkCCombi(char *pos) {
  // chekc de 3 mulig ruter
  // A til E
  // find et A med et E bagefter
  if (!AtilE(pos))
    return ERROR;
  // B til D
  // find B med D efter
  if (!BtilD(pos))
    return ERROR;
  // C til A
  // find C med et A efter
  if (!CtilA(pos))
    return ERROR;

  // hvis ingen af disse er forkert må det være en og løsning
  return OK;
}
 
Resten må jeg overlade som en øvelse pga. tidsmangel, hvis du selv
udfylder det hele kan jeg evt. se på fejl.
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester