[C++] 2d array

[Verwijderd]

Achtergrondverhaal:

De Romeinen hadden een spelletje met muntjes, te weten sestertii.
Er staan een heleboel lege potjes op een rij en de eerste Romein
die langskomt gooit in elk potje een sestertius. Daarna komt de
tweede Romein die haalt uit alle even potjes het muntje. De
potjes zijn genummerd van 1 t/m n, waarbij n het laatste potje is.
De nummering is opeenvolgend. Dan komt de 3e romein en gaat alle
potjes die een veelvoud van drie zijn na, en als er een muntje
inligt dan pakt hij dat, en als er geen muntje inligt dan doet hij
er een in. Dus hij pakt het muntje uit potje 3 en doet dat in potje 6.
Daarna pakt hij het muntje uit potje 9 en doet dat in potje 12, enzovoort.
De vierde Romein doet hetzelfde voor alle potjes met als nummer een
viervoud. Nadat er n Romeinen zijn geweest, in hoeveel potjes ligt
er dan een muntje? Kan je ook een rij maken van X-en en O-en waarbij
een X staat voor wel een munt, en O voor geen munt?

Nu wil ik dat doen door een 2d array te maken(is nu nog van statische grootte, later breid ik dit uit zodat het van dynamische grootte wordt, maar is nu voorlopig niet van toepassing). Mn 2de array heb ik voorlopig al, die is gemaakt voor 6 potjes en 3 Romeinen die meedoen.

C++:

    unsigned int nP, nR;
    cout<<"Hoeveel potjes staan er?\n";
    cin>>nP;
    cout<<"Hoeveel Romeinen doen er mee?\n";
    cin>>nR;

    int Matrix[6+1][3+1];
    int counter=0;
    for(int i=0; i<(7); i++)
    {
        for(int j=0; j<(4); j++)
        {
                Matrix[i][j] = 0;
                cout<<Matrix[i][j]<<" ";
                counter++;
        }
    }
    
    cout<<endl<<counter<<endl;
    for(int r=1; r<=nR; r++)
    {
        for(int p=r; p<=nP; p += r)
        {
                if((Matrix[r-1][p]) == 0)
                {
                    cout<<"["<<r-1<<"]["<<p<<"] = "<<Matrix[r-1][p]<<endl;
                    (Matrix[r][p]) = 1;
                    cout<<"["<<r<<"]["<<p<<"] = "<<Matrix[r][p]<<endl;
                }
                else if((Matrix[r-1][p]) == 1)
                {
                    cout<<"["<<r-1<<"]["<<p<<"] = "<<Matrix[r-1][p]<<endl;
                    (Matrix[r][p]) = 0;
                    cout<<"["<<r<<"]["<<p<<"] = "<<Matrix[r][p]<<endl;
                }
                else
                cout<<"Er is iets foutgegaan\n";
                                    if(p == nP)
                {
                    for(int h=1; h<=nP; h++)
                    {
                        Matrix[r+1][h] = Matrix[r][h];
                    }
                }
        }
    }

Nu krijg ik steeds een verkeerd uitkomst, dus ik uit alle macht maar debuggen, ben ik erachter gekomen dat hij bij vanaf p=5 ipv dit

C++:

if((Matrix[r-1][p]) == 0)
{
   ...... 
}

dit

C++:

if((Matrix[r-1][p]) == 1)
{
   ...... 
}

doorloopt.

Als ik alle waarden van mn 2de array print krijg ik dit:

code:

[1][1] = 0 
[1][1] = 1
[1][2] = 0
[1][2] = 1
[1][3] = 0
[1][3] = 1
[1][4] = 0
[1][4] = 1
[1][5] = 0
[1][5] = 0
[1][6] = 0
[1][6] = 0

De eerste waarde is de waarde voordat de waarde verandert(moet worden) en de 2de waarde nadat het verandert is. Zoals je ziet verandert de waarde van [1][5] en [1][6] niet.

Mijn vraag is, waarom zegt hij dat [1][5] 0 is, en toch de verkeerde If() doorloopt?

[ Voor 31% gewijzigd door Verwijderd op 23-12-2003 14:47 ]

[whoami]

Het eerste element in een array, staat op index 0, en niet op index 1.

[.oisyn]

Hoe weet je dat ie de verkeerde if doorloopt? Je test of Matrix[r-1][p] == 0, en vervolgens assign je een waarde aan Matrix[r][p]. Dat is dus niet hetzelfde (je gebruikt eerst r-1, en daarna r)

Die haakjes steeds eromheen zijn trouwens niet nodig

[Verwijderd]

.oisyn schreef op 23 december 2003 @ 14:33:
Hoe weet je dat ie de verkeerde if doorloopt? Je test of Matrix[r-1][p] == 0, en vervolgens assign je een waarde aan Matrix[r][p]. Dat is dus niet hetzelfde (je gebruikt eerst r-1, en daarna r)

Die haakjes steeds eromheen zijn trouwens niet nodig

Dat zie ik in mijn debugger als ik de code steeds doorloop

@whoami

Dat weet ik wel, daarom maak ik een array met 1 element meer, zodat ik 0 gewoon kan negeren. Ik maak eerst van alle waarde in de matrix 0. Daarna kijk ik wat er een rij boven staat. Als er een rij boven(vandaar r-1) 0 is, moet de huidige waarde van [r,p] 1 worden, en als het 1 is moet het nul worden. (zie verhaaltje)

edit:
Ik heb het gevoel dat er iets mis gaat bij het kopieren van de huigige reeks naar de volgende rij. Dus hier:

C++:

if(p == nP)
{
    for(int h=1; h<=nP; h++)
    {
        Matrix[r+1][h] = Matrix[r][h];
        cout<<"["<<r<<"]["<<h<<"] = "<<Matrix[r][h]<<endl;
        cout<<"["<<r+1<<"]["<<h<<"] = "<<Matrix[r+1][p]<<endl;
    }
}

want hier krijg ik als uitvoer:

code:

[1][1] = 1
[2][1] = 0
[1][2] = 1
[2][2] = 0
[1][3] = 1
[2][3] = 0
[1][4] = 1
[2][4] = 0
[1][5] = 1
[2][5] = 0
[1][6] = 1
[2][6] = 1

wat erop wijst dat alleen de laatste element wordt gekopieerd van de eerste naar de 2de rij...
Ik snap alleen niet waarom

[ Voor 31% gewijzigd door Verwijderd op 23-12-2003 14:52 ]

[schoene]

Mag ik wel opmerken dat je een 2dimensionele
array declareert van dimensie 7x4, maar dat je
in je output blijbaar verder gaat dan 4 elementen
in het 2e deel?

[Verwijderd]

waaruit maak jij op dat ik verder ga dan
Want ik zie niet echt waar ik verder ga dan 4

nP krijgt de waarde 3

[ Voor 7% gewijzigd door Verwijderd op 23-12-2003 15:04 ]

[schoene]

Euh:

[1][1] = 1
[2][1] = 0
[1][2] = 1
[2][2] = 0
[1][3] = 1
[2][3] = 0
[1][4] = 1
[2][4] = 0
[1][5] = 1
[2][5] = 0
[1][6] = 1
[2][6] = 1

6 is groter dan 4

[Verwijderd]

ooow shit, ik heb die dingen net andersom. Thnx, nu heb ik het zo:

C++:

    int Matrix[3+1][6+1];
    int counter=0;
    for(int i=0; i<4; i++)
    {
        for(int j=0; j<7; j++)
        {
                Matrix[i][j] = 0;
                cout<<Matrix[i][j]<<" ";
                counter++;
        }
    }

Maar dan werkt het nog steeds niet helemaal naar behoren

/me start debugger maar weer

[schoene]

C++:

#define MAX_P 10
#define MAX_R 10

void DoIt ()
{
  unsigned int nP = 0, nR = 0;

  while (nP <=0 || nP > MAX_P)
  {
    cout<<"Hoeveel potjes staan er?\n";
    cin>>nP;
  }

  while (nR <=0 || nR > MAX_R)
  {
    cout<<"Hoeveel Romeinen doen er mee?\n";
    cin>>nR;
  }

  // Matrix [0][X] is voor de eerste romein passeert,
  // dan zijn alle potjes leeg
  int Matrix[MAX_R+1][MAX_P];

  for(int i=0; i<MAX_R+1; i++)
  {
    for(int j=0; j<MAX_P; j++)
    {
      Matrix[i][j] = 0;
    }
  }

  for(int r=1; r<=nR; r++)
  {
    for(int p=0; p<nP; p++)
    {
      if ((p+1)%r != 0)
        Matrix[r][p] = Matrix[r-1][p];
      else if(Matrix[r-1][p] == 0)
        Matrix[r][p] = 1;
      else if(Matrix[r-1][p] == 1)
        Matrix[r][p] = 0;
      else
        cout<<"Er is iets foutgegaan\n";
    }
  }


  for(int r=0; r<=nR; r++)
  {
    for(int p=0; p<nP; p++)
    {
      cout<<"["<<r<<"]["<<p+1<<"] = "<<Matrix[r][p]<<endl;
    }
  }
}

[ Voor 12% gewijzigd door schoene op 23-12-2003 15:33 ]

[Verwijderd]

Dit is mijn oplossing:

C++:

    int Matrix[3+1][6+1];
    int counter=0;
    for(int i=0; i<4; i++)
    {
        for(int j=0; j<7; j++)
        {
                Matrix[i][j] = 0;
                cout<<Matrix[i][j]<<" ";
                counter++;
        }
    }
    cout<<endl<<counter<<endl;
    for(int r=1; r<=nR; r++)
    {
        for(int p=r; p<=nP; p += r)
        {
                if((Matrix[r-1][p]) == 0)
                {
                    //cout<<"["<<r<<"]["<<p<<"] = "<<Matrix[r][p]<<endl;
                    (Matrix[r][p]) = 1;
                    //cout<<"["<<r<<"]["<<p<<"] = "<<Matrix[r][p]<<endl;
                }
                else if((Matrix[r-1][p]) == 1)
                {
                    //cout<<"["<<r<<"]["<<p<<"] = "<<Matrix[r][p]<<endl;
                    (Matrix[r][p]) = 0;
                    //cout<<"["<<r<<"]["<<p<<"] = "<<Matrix[r][p]<<endl;
                }
                else
                //cout<<"Er is iets foutgegaan\n";
                cout<<endl;
                if(p <= nP && r != nR)
                {
                    for(int h=1; h<=nP; h++)
                    {
                        Matrix[r+1][h] = Matrix[r][h];
                        //cout<<"["<<r<<"]["<<h<<"] = "<<Matrix[r][h]<<endl;
                        //cout<<"["<<r+1<<"]["<<h<<"] = "<<Matrix[r+1][p]<<endl;
                    }
                }
                //cout<<endl;
        }
    }

Dan staat in de laatste rij van de Matrix de uitkomst. Dat is verder geen punt.

[Soultaker]

Ik hoop trouwens dat je je er van bewust bent dat je oplossing niet schaalbaar is tot aan het in de oorspronkelijke opgave gestelde maximum aan de invoergrootte (2³⁰ potjes/romeinen); om die opgave op te lossen zul je dus iets slimmers moeten bedenken!

[schoene]

Je merkt toch zowiezo dat mijn oplossing optimaler is (nog verre van het optimaalst, maar kom): jij hebt 3 geneste lussen, terwijl ik er maar 2 heb.

Ook is het makkelijker te begrijpen voor een ander persoon: Ik vergelijk enkel met de vorige toestand, terwijl jij nog eens in bepaalde gevallen ook de toekomstige toestand zal goed zetten.

1 kleine opmerking nog:

Is het eigenlijk de bedoeling dat je de volledige historie bijhoudt (dus als je 5 romeinen hebt, dat je ook de toestand moet weten na de derde romein) ? Indien dit niet het geval is, is het volledig nutteloos van een 2 dimensionale array te gebruiken.

(ongetest, maar het is iets zoals hier)

C++:

  for(int r=1; r<=nR; r++)
  {
    for(int p=r-1; p<nP; p += r)
    {
      Matrix [p] = (Matrix [p] ==0 ? 1 : 0);
    }
  }  

[Verwijderd]

Nee heel de historie is niet nodig, maar ik ben al een beginner, en ik ben hier 2 dagen bezig mee geweest. Dit is wat ik nu heb: (met dynamische array)

http://www.rafb.net/paste/results/y2128074.html

Ik ga jullie tips opvolgen en kijken hoe ik het kan optimaliseren

edit:
Ik snap je code niet helemaal. Je moet je uitkomst vergelijken met wat de vorige Romein heeft gedaan. Dus als Romein ga je n potjes af.

code:

   nP  1  2  3  4  5  6
nR
1       X  X  X  X  X  X
2       X  O  X  O  X  O
3       X  O  O  O  X  X
4       X  O  O  X  X  X

Om bv te weten wat er moet gebeuren in potje 6 bij Romein 3 moet je eerst weten wat er gebeurd was in potje 6 bij Romein 2. Hoe kun je dat dan oplossen met een gewone array?

edit2:
How, gaat even te snel, ik ben een redelijke n00b zoals jullie het al vernomen hebben waarschijnlijk, maar waarom dit:

if(!(j % i)){ ...}

[ Voor 60% gewijzigd door Verwijderd op 23-12-2003 17:27 ]

[wacco]

Zoals schoene al zei, maar ik al aan het uitwerken was (mja... probeer dat maar eens te bewijzen )

C:

/* romeintjes.c @ 23/12/2003 Michael Meeuwisse
 * compile with: cc romeintjes.c -o romeintjes -O -Wall
 */

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv) {
  int p, r, i, j, *array;
  
  if(argc < 3) {
    printf("usage: ./romeintjes [aantal potjes] [aantal romeinen]\n");
    return -1;
  }  
  p = atoi(argv[1]); r = atoi(argv[2]);
  if((array = malloc(p * sizeof(int))) == NULL) {
    fprintf(stderr, "mallocing array failed");
    return -1;
  }
  for(i = 0; i <= p; i++)
    array[i] = 0;
    
  for(i = 1; i <= r; i++)
    for(j = 1; j <= p; j++) 
      if(!(j % i)) 
        array[j] = (array[j] == 0 ? 1 : 0);
  
  for(i = 1; i <= p; i++)
    printf("%d [%d]\n",i, array[i]);
  
  free(array);
  return 0;
}

Is dan wel c. Het hele nut van een 2D array was mij namelijk ook ontgaan.

Soultaker schreef op 23 december 2003 @ 16:36:
Ik hoop trouwens dat je je er van bewust bent dat je oplossing niet schaalbaar is tot aan het in de oorspronkelijke opgave gestelde maximum aan de invoergrootte (2³⁰ potjes/romeinen); om die opgave op te lossen zul je dus iets slimmers moeten bedenken!

waar heeft de Ts dat gemeld? Of ken je de opdracht? Ik weet niet of mijn code 2³⁰ aan potjes aan kan hoor (romeintjes moet wel lukken, duurt alleen even).

-edit- Deze manier van wisselen tussen true en false, is dat nou c of c++? M'n cc vreet het iig wel, maar die vreet volgens mij alles... (afgekeken van schoene dus )

[ Voor 13% gewijzigd door wacco op 23-12-2003 17:24 ]

[schoene]

Ik snap je code niet helemaal. Je moet je uitkomst vergelijken met wat de vorige Romein heeft gedaan. Dus als Romein ga je n potjes af.

Je kan eerst kijken wat de huidige waarde is, en nadien overschrijven.

C++:

  int *Matrix = new int [nP];

  for(int j=0; j<nP; j++)
  {
    Matrix [j] = 0;
  }

  for(int r=1; r<=nR; r++)
  {
    for(int p=r-1; p<nP; p += r)
    {
      Matrix [p] = (Matrix [p] == 0 ? 1 : 0);
    }
  }

  delete[] Matrix;

[Verwijderd]

schoene schreef op 23 december 2003 @ 17:27:
[...]


Je kan eerst kijken wat de huidige waarde is, en nadien overschrijven.

C++:

  int *Matrix = new int [nP];

  for(int j=0; j<nP; j++)
  {
    Matrix [j] = 0;
  }

  for(int r=1; r<=nR; r++)
  {
    for(int p=r-1; p<nP; p += r)
    {
      Matrix [p] = (Matrix [p] == 0 ? 1 : 0);
    }
  }

  delete[] Matrix;

ooow w8, wat heb ik het toch omslachtig gedaan nu snap ik wat jullie bedoelen. Maar moet het dan niet

for(int p=r; p<=nP; p += r) want waarom -1 dan dan klopt heel het verhaal niet meer

[schoene]

Neen, want een array begint bij 0, en niet bij 1.
Jij creeerde een extra item, om zo te kunnen beginnen bij 1, maar dit is totaal nutteloos, en 'a waste of resources' . Ik weet het, het is niet veel, maar het gaat om het principe: waarom geheugen alloceren dat je niet gebruikt?

[wacco]

Hmm das idd wel een klap sneller dan mijn !(i % j).
R - 1 is omdat je array op nul begint. Dus potje één is Matrix[0].

[Verwijderd]

ja maar waarom begin je dan r wel met 1, kan je daar ook net zo goed met 0 beginnen tog?

[schoene]

jah, maar dan moet je p met r+1 optellen, en r < nR ipv r <= nR:
(ik vind het op de andere manier duidelijker, maar dat is mijn mening)

Vergeet niet dat r hier niets te maken heeft met de array: we gebruiken nu een 1-demensionale array. r is gewoon een tellertje

C++:

  for(int r=0; r < nR; r++)
  {
    for(int p=r; p<nP; p += r+1)
    {
      Matrix [p] = (Matrix [p] == 0 ? 1 : 0);
    }
  } 

[ Voor 21% gewijzigd door schoene op 23-12-2003 17:44 ]

[Soultaker]

wacco schreef op 23 december 2003 @ 17:19:
waar heeft de Ts dat gemeld? Of ken je de opdracht? Ik weet niet of mijn code 2³⁰ aan potjes aan kan hoor (romeintjes moet wel lukken, duurt alleen even).

Het is een opgave van het Nederlands Kampioenschap Programmeren van dit jaar. Aangezien het de bedoeling is om in een paar seconden een oplossing te vinden moet je eigenlijk op zoek naar een algoritme met lineaire complexiteit (of hooguit iets van O(N log(N)) ), terwijl het nu gepresenteerde algoritme een kwadratische complexiteit heeft (O(N) operaties per Romein, maakt O(N²) operaties in totaal).

Overigens beperkt de oorspronkelijke opgave zich tot de situaties waarin het aantal potjes en het aantal Romeinen gelijk is (of dat noodzakelijk is voor de correcte oplossing herinner ik me niet meer).

[MSalters]

's Proberen. Om te beginnen jouw algo:

C++:

void foo( int potjes, int romeinen )
{
  std::vector<bool> array_potjes( potjes, true ); // romein 1 gehad
  for( int r = 1; r != romeinen; ++r ) // begin bij 0 behalve als je de eerste al hebt gehad
  {
    for( int p = r-1; p < potjes; p+=r ) // r-1 omdat het eerste potje #1 is, niet #0
    {
       array_potjes[p] = ( !array_potjes[p] ); // haakjes om verwarring met != te voorkomen
    }
  }
  for( int p = 0; p <= potjes; p+=r )
    std::cout << array_potjes[p] ? 'O' : 'X' ;
}

De eerste informatica truc is inderdaad p+=r, omdat ++p en een p%r test je kwadratisch gerdrag geeft.

Ik zit nog na te denken of het in O(N) kan. Het is duidelijk dat het eerste potje gevuld blijft. Geen enkele romein zit daaraan, want de Nde romein begint bij potje N. Het is duidelijk dat potje X gevuld is als ( het aantal delers van X kleiner dan het aantal romeinen ) even is. Ik weet geen mogeijkheid om in O(1) te bepalen hoeveel delers X+1 heeft, gegeven X, laat staan als je nog sommige delers eruit moet gooien. Neem nou 21,22,23,24,25 : De eerste is deelbar door {1,3,7,21 } [4], 22 -> { 1,2,11,22 } [4] , 23 -> {1,23 } [2], 24 -> {1,2,3,4,6,8,12,24 } [8] , 25 -> {1,5,25 } [3]. Vindt daar maar een logica in.

[wacco]

Well... d'r zit wel logica in.

code:

potjeQ = nul.
  Q
[deelbaar door 2?] y {dan potje = 1, uitkomst als Q recyclen}
  n
[deelbaar door 3?] y [zie deelbaar door 2, alleen dan met 3]
  n
{priemgetal, romein 1 vult, romein Q haalt leeg, is dus nul}

Dit kan volgens mij voor elk potje uniek uitrekenen of het gevult was of niet. Maar het werkt alleen als het aantal romeinen gelijk (of meer) is aan het aantal potjes. Erg aardig, zou lijken dat ik de goede kant op werk Dus;

C:

/* eerst even wat speciale situaties omzeilen */
if(np > 0) nm = 1; else nm = 0;
if(np >= 1) printf("[1]");
if(np >= 2) printf("[0]");
if(np >= 3) printf("[0]");

for(p = 4; p <= np; p++) {
  n = 0; q = p;
  while(q > 3) {
    if(!(q % 2)) {
      n = (n == 0 ? 1 : 0);
      q = q / 2;
    }
    else if(!(q % 3)) {
      n = (n == 0 ? 1 : 0);
      q = q / 3;
    }
    else {
      q = 0;
    }
  }
  printf("[%d]",n);
  if(n) nm++;
}
if(nm) printf("\n");
printf("number of coins in total: %d\n", nm);

untested, dat ga ik nu ff doen. Ben benieuwd of het werkt. If so, dan is dit algoritme iig degene die het zuinigste is met z'n geheugen

-edit- werkt. alleen is het resultaat niet hetzelfde Dus ergens zit het nog niet goed.

[ Voor 35% gewijzigd door wacco op 24-12-2003 02:54 ]

[RickN]

Uit het verhaal maak ik op dat er n potjes én n romeinen zijn en in dat geval is de snelste oplossing gewoon:

code:

return floor(sqrt(n));

Oftwel, het aantal kwadraten kleiner dan of gelijk aan n.
Uitleg, delers van een getal komen in paren en elk paar laat het aantal knikkers in een vaas ongewijzigd, behalve in het geval van een kwadraat, want daar zijn voor één paar delers de delers gelijk waardoor er dus een knikker overblijft.

Als het aantal romeinen ook kleiner dan het aantal potjes kan zijn moet je met gevalsonderscheid gaan werken, maar ik poneer dat een generieke O(1) oplossing mogelijk is.

[ Voor 32% gewijzigd door RickN op 24-12-2003 13:01 ]

[MSalters]

sqrt(n) is geen O(1) algoritme, en je uitleg komt niet overeen met je code. Afgezien daarvan heb je natuurlijk helemaal gelijk; return (sqrt(n)-floor(sqrt(n) == 0) geeft je het gewenste antwoord in O(log N) per potje, dat is dus ook O(N log N) voor het geheel.

Ik vraag me af of je snel kunt bepalen of X delers groter dan N heeft. Dan zou je namelijk ook snel kunnen bepalen of X een priemgetal is. Zoals bekend is dat geen O(1) probleem.

[schoene]

RickN gaat ervan uit dat je niet per potje moet zeggen of er een steentje in ligt, maar dat je enkel het aantal potjes met steentjes moet tonen. En daar heeft ie gelijk in als je de opgave correct leest. Wij hebben eigenlijk allemaal verkeerde info gekregen van Dr HenDre

Dan is de oplossing uiteraard wel O(log N) en niet O (NlogN).

[RickN]

MSalters schreef op 24 december 2003 @ 14:41:
sqrt(n) is geen O(1) algoritme

Dat hangt er maar net vanaf hoe je je atomaire operaties defineert. Op een proc met een sqrt instructie is het wel O(1). En een implementatie met een lookup tabel overigens ook.

, en je uitleg komt niet overeen met je code.

Jawel, het aantal kwadraten kleiner gelijk n is sqrt(n). De verdere uitleg had wellicht iets nauwkeuriger gekund.
Als en alleen als het nummer van een vaas een kwadraat is heeft dat nummer een oneven aantal unieke delers en zal er als alle romeinen zijn geweest een knikker in de bijbehorende vaas liggen.

Afgezien daarvan heb je natuurlijk helemaal gelijk; return (sqrt(n)-floor(sqrt(n) == 0) geeft je het gewenste antwoord in O(log N) per potje, dat is dus ook O(N log N) voor het geheel.

Ik twijfel er niet aan dat jij in minder dan O(N log N) een lijstje van kwadraten kleiner gelijk N kunt genereren.

Ik vraag me af of je snel kunt bepalen of X delers groter dan N heeft. Dan zou je namelijk ook snel kunnen bepalen of X een priemgetal is. Zoals bekend is dat geen O(1) probleem.

Wat hebben priemgetalen hiermee te maken.

[Verwijderd]

schoene schreef op 24 december 2003 @ 15:20:
RickN gaat ervan uit dat je niet per potje moet zeggen of er een steentje in ligt, maar dat je enkel het aantal potjes met steentjes moet tonen. En daar heeft ie gelijk in als je de opgave correct leest. Wij hebben eigenlijk allemaal verkeerde info gekregen van Dr HenDre

Dan is de oplossing uiteraard wel O(log N) en niet O (NlogN).

Jah maar zoals ik m heb verteld vond ik m boeiender dan gewoon aantal

[MSalters]

Precies, TS kwam blijkbaar met een ander probleem dan NK, en dat is O(NlogN). Ik blijf me nog steeds afvragen hoe je het handig aanpakt als Romeinen!=Potjes.

@RickN: Wat priemgetallen hiermee te maken hebben? Als jij in O(1) van een getal X kunt vertellen dat X geen delers kleiner dan sqrt(X) heeft, dan weet je dus in O(1) of X een priemgetal is. Volgens mij is dat nog steeds een gewild algoritme.

[Verwijderd]

Ik kan het allemaal niet meer volgen logaritme van N O(1)

[RickN]

MSalters schreef op 24 december 2003 @ 19:27:
Precies, TS kwam blijkbaar met een ander probleem dan NK, en dat is O(NlogN). Ik blijf me nog steeds afvragen hoe je het handig aanpakt als Romeinen!=Potjes.

Voor de situatie #Romeinen = #Potjes reduceert het probleem tot het bepalen van een reeks kwadraten.
Als je als output een reeks moet produceren die echt voor alle N potjes aangeeft of er een knikker in zit heb je natuurlijk al minimaal een O(N) algoritme. Verder moet je voor elke vaas bepalen of het nummer een kwadraat is. Ik kan een reeks kwadraten kleiner gelijk N genereren in O(sqrt(N)). De complexiteit van dit algoritme zou dan dus komen op O(N+sqrt(N)), maar dat is gewoon O(N). Let wel, dit algoritme gebruikt dus geen sqrt operatie meer, dus de complexiteit die je daarvoor hanteert doet er niet meer toe.

Voor #Romeinen != #Potjes wordt het wel lastiger, maar dan kom je met gevalsonderscheid nog een heel eind. Zo beweer ik b.v. dat voor

#R >= #P/2

het aantal potten met een knikker

2*sqrt(#R) + (#P-#R) - sqrt(#P)

is.

@RickN: Wat priemgetallen hiermee te maken hebben? Als jij in O(1) van een getal X kunt vertellen dat X geen delers kleiner dan sqrt(X) heeft, dan weet je dus in O(1) of X een priemgetal is. Volgens mij is dat nog steeds een gewild algoritme.

Mwa, priemtest zijn tegenwoordig al erg efficient. D.w.z. er kan van een getal met honderden decimalen betrekkelijk snel (minuten) bepaald worden of het priem is. Priemtesten heeft dus ook maar een polynomiale complexiteit. Natuurlijk zijn nog snellere algoritmes altijd welkom, maar ik denk niet dat iemand verwacht dat er ooit nog een O(1) priemtest ontdekt wordt.

@Dr HenDre: Dat O(1) en O(N) enzo, dat is een zogenaamde orde notatie. Het geeft geeft aan wat de asymptotische executietijd als functie van N is. Deze specifieke ordenotatie geeft een bovengrens, maar er zijn ook andere notaties die b.v. een ondergrens geven. O(1) betekent dat het programma een constante executie tijd heeft, die niet van N afhangt, dus voor grote of kleine N duurt het algoritme even lang. O(N) betekent dat het executie tijd linear met N stijgt, dus als N twee keer zo groot wordt duurt het b.v. ook twee keer zo lang voor je programma klaar is. En zo kun je verder gaan, O(N^2) betekent dan b.v. dat als N twee keer zo groot wordt, dat je programma dan ongeveer 2^2=4 keer zo lang duurt.
Het is een eenvoudige manier om aan te geven hoe efficient je algoritme is, maar het is absoluut niet zaligmakend. Zo heeft het quicksort algoritme (een zeer bekend sorteeralgoritme) een (worstcase) O(N^2) complexiteit, terwijl het in vrijwel alle gevallen sneller is dan andere sorteerroutines die officieel een O(N*log N) complexiteit hebben...

[Verwijderd]

maar hoe kun je uit een algotime opmaken wat de orde is. Dus hoe weet je dat een bepaalde algoritme O(N) is.

[.oisyn]

Dr Hendre: stel je hebt een verzameling van n elementen. Als je dan iets moet bepalen waarbij je alle elementen moet controleren, bijvoorbeeld het hoogste getal in de verzameling, dan is je algoritme dus van orde O(n). Als die verzameling nou van laag naar hoog gesorteerd was dan weet je dus altijd dat het hoogste getal achteraan staat. Je hoeft geen elementen te vergelijken, je kunt 'm er in een keer uitpakken. Dat is dus O(1), oftewel constante tijd.

En stel nou dat je in die verzameling moet zoeken naar 2 gelijke elementen. Een logisch (maar minder efficient) algoritme daarvoor is bijvoorbeeld door een genest loopje te doen. In de buitenste lus loop je alle elementen af, en in de binnenste lus ga je op zoek naar een equivalent element. De code ziet er dan bijvoorbeeld zo uit:

C++:

bool found = false;
for (int i = 0; !found && i < N; i++)
{
    for (int j = 0; j < N; j++)
    {
        if (i == j) // we hoeven natuurlijk niet hetzelfde element te vergelijken
            continue;
        if (element[i] == element[j])  // dubbele gevonden
        {
            found = true;
            break;
        }
    }
}

Het buitenste lusje is natuurlijk O(n), want je doorloopt n elementen. Alleen per iteratie doorloop je nog eens n elementen, waardoor het een kwadratische orde krijgt, dus O(n²)

Verder kun je hier en daar wat "sjoemelen" met factoren e.d.. Als je bijvoorbeeld 2x achter elkaar de hele verzameling doorloopt, dan zou je natuulijk zeggen dat het O(2n) is. Maar als je verzameling 2x zo groot wordt, dan duurt het algoritme nog steeds maar 2x langer, en dus vervalt de 2 in de O(2n), en wordt het dus gewoon O(n). Of als je een deel van je algoritme hebt dat O(n²) is, en een deel dat O(n) is, dan is het eindresultaat ook niet O(n² + n) maar gewoon O(n²), omdat bij hele grote n de n in het niet valt vergeleken met de n²