[C++] Array inhoud lezen

[martijn946]

Beste forummers,

Ik heb even probleempje met een opdracht, ik heb geen idee hoe ik er aan moet beginnen.

----
GEGEVEN:
Een tabel van maximaal 80 tekens (char), in te vullen door gebruiker

GEVRAAGD:
Toon twee gelijke tekens (geen spaties) uit de tabel die het verst van elkaar verwijderd zijn.

Bijvoorbeeld:
Dit is een voorbeeld van een saaie zin.
In dit geval is de i de letter die het verst uit elkaar staat.
----

Dit is geen script request, ben gewoon benieuwd hoe jullie het zouden doen.


Tot nu:

C++:

#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <cstring>
#include <conio.h>


using namespace std;

main ()
{
    //variabelen
    char tabel[80];
    int  max = 80;
    int  i = 0;
    int  totaal_letters;

    //vraag gebruiker om invoer
    cout << "Dit programma zoekt de 2 verst van elkaar verwijderde gelijke letters in de zelfde zin.\n"
         << "Voer een zin in :";

    //lees invoer van de gebruiker
    cin.getline(tabel,80);
    cout << "\nDe zin die je invoerde was \"" << tabel << "\"\n";

    //controleren hoeveel letters er in de zin zitten
    totaal_letters = strlen(tabel);

    cout << "In totaal bevat deze zin \"" << totaal_letters << "\" letters \n\n";

    //laat oputput zien van array
    for (i=0; i <=totaal_letters - 1; i++)
    {
        //laat de inhoud van de @rray zien
        // \a is een DOS PIEP :)
        cout << "tabel[" << i <<"] = " << tabel[i] << "\n";
    }

    //i op 0 zetten
    i = 0;

    //spelen
    while( tabel[i] <= tabel[totaal_letters -1]){

        if ( tabel[i] ==  tabel[totaal_letters -1]){
            cout << "Nummer " << i << " en nummer " << totaal_letters-1  << " zijn gelijk\n\n\a";
        }
        totaal_letters --;
    }

    return 0;
}

[ Voor 24% gewijzigd door martijn946 op 16-09-2004 22:25 ]

[NightCruiser]

das toevallig, tijdje terug voor een programma had ik ook deze functie nodig, alleen ik kon op geen manier uitvinden hoe, als iemand et weet ben ik erg geholpen

[LoBbY_1]

Ik ben dan wel geen echte C++ maar, wat als je nou de lengte van je array andersom laat tellen? Zoiets als:

code:

    for (i = 0; i==totaal_letters; i++)
    {
        if (tabel[i] == tabel[totaal_letters - i])
        {

        }
    }

[ Voor 42% gewijzigd door LoBbY_1 op 16-09-2004 22:13 ]

[schoene]

mijn eerste ingeving:

C++:

for (int j=totaal_letters-1; j > 0; --j)
{
  for (int k=0; k+j< totaal_letters; ++k)
  {
  if (tabel [k] != ' ' && tabel [k] == tabel [k+j])
    cout << "Nummer " << k << " en nummer " << k+j  << " zijn gelijk\n\n\a";
  }
}

[martijn946]

We gaan even testen

[LazySod]

C:

int l_Longest         = 1;
int l_StartLongest = 0;
int l_EndLongest   = 0;

for ( int i = 0, j = strlen(input); i < j; i++)
{
     char x = input[ i];

     for ( int m = i + 1; m < j; m++)
     {
          if ( input[ m]  == x && m - i + 1 > l_Longest)
          {
               l_Longest         = m - i + 1;
               l_StartLongest = i;
               l_EndLongest   = m;
          }
     }
}

zoiets? vooruit lopend door het array iedere keer door blijven bladeren tot het einde van de string en afstand blijven bepalen?

algorithme is orde(N*N) en dat is natuurlijk knap waardeloos overigens.

[martijn946]

Ja, dat is zo. We gaan ff kijken

[Sjaaky]

Als je alle tekens kent die in de string voor kunnen komen (en dat is heel makkelijk als het 8 bit chars zijn) maak je een tabel met de eerste keer dat je teken bent tegen gekomen. Iedere keer dat je een teken tegenkomt kijk je in de tabel, en vergelijkt het verschil met de max afstand. De max afstand update je indien nodig. Je hoeft dan slechts 1x de hele string door te lopen.
Je algoritme is dan O(n). En als je unicode strings in wil lezen moet je wel het een en ander aanpassen (een hashtabel om tegengekomen tekens in te stoppen oid).

@LazySod:
Als je in de binnenste lus achteraan de string begint met lezen kun je direct uit de loop springen (een while van maken) als je hetzelfde teken vindt.
Aangezien je hier slechts 80 tekens in een string hebt zitten is O(n*n) geen probleem.

[ Voor 33% gewijzigd door Sjaaky op 16-09-2004 22:50 . Reden: ff algoritme aangepast :O ]

[martijn946]

Zo dan!!! Dat is ff pittig stukje wat je verteld, ik ga er even naar kijken of ik dat kan bewerkstelligen.

[Opi]

Sjaaky schreef op 16 september 2004 @ 22:46:
Als je alle tekens kent die in de string voor kunnen komen (en dat is heel makkelijk als het 8 bit chars zijn) maak je een tabel met de eerste keer dat je teken bent tegen gekomen. Iedere keer dat je een teken tegenkomt kijk je in de tabel, en vergelijkt het verschil met de max afstand. De max afstand update je indien nodig. Je hoeft dan slechts 1x de hele string door te lopen.

Je moet dan toch wel elke keer de tabel met tekens doorlopen? Gezien het een string is die waarschijnlijk enkel uit letters en cijfers bestaat, is het algorithme inderdaad nog steeds niet O(n²).

[Sjaaky]

OpifexMaximus schreef op 16 september 2004 @ 23:14:
[...]
Je moet dan toch wel elke keer de tabel met tekens doorlopen? Gezien het een string is die waarschijnlijk enkel uit letters en cijfers bestaat, is het algorithme inderdaad nog steeds niet O(n²).

Elk ascii teken heeft een bepaalde waarde, de 'A' is bijvoorbeeld 65. Uiteraard gebruik je de waarde van het teken zelf als index in de tabel.

[LazySod]

Sjaaky schreef op 16 september 2004 @ 22:46:
@LazySod:
Als je in de binnenste lus achteraan de string begint met lezen kun je direct uit de loop springen (een while van maken) als je hetzelfde teken vindt.
Aangezien je hier slechts 80 tekens in een string hebt zitten is O(n*n) geen probleem.

Klopt ... Even niet verder bij nagedacht. Er zijn ook in de buitenste loop nog wat optimalisaties mogelijk - als de hoogst gemeten afstand groter/gelijk is aan de rest van het array (j-i) dan kun je er nog uit.

Maar zelfs die oplossing zorgt nog steeds voor een O(n*n) algorithme - in het worst case scenario staat ieder karakter maar 1 keer in de string.

De redenatie dat het array maar 80 posities groot is is geen reden om niet te zoeken voor een algorithme welk niet O(n*n) is. Daar heb ik tijdens mijn korte tijd aan de TU nog aardig wat woorden over gehad met een docent aldaar (en volledig terecht -- hij had gelijk). Want al is deze testcase slechts 80 posities lang - waarom zou je een dergelijk programma niet gebruiken voor 80.000.000 posities?

Kortom.. Je methode met een arraytje start posities is naar alle waarschijnlijkheid het beste.

[MSalters]

Het probleem met de char-waarde als index is dat het niet schaalt naar wchar_t. In linux is die dacht ik al 32 bits.

Overigens, het is int main() { /***/ }, strings gaan het makkelijkst met std::string, en <conio.h> is niet-standaard en niet gebruikt.

[ Voor 3% gewijzigd door MSalters op 17-09-2004 08:52 . Reden: ; verdwaald ]

[-=bas=-]

Uiteraard gebruik je de waarde van het teken zelf als index in de tabel.

Woooeeei Uni-code here I come.
Met 16 bits gaat dat toch in de papieren lopen.
Het is iets efficienter als je gewoon 2 arrays gebruikt, 1 voor de letter en 1 voor de begin pos.

Je kan het probleem ook iets anders aanpakken waardoor je geen N*N probleem hebt.
- scan de zin van links naar rechts
- voor elk teken bepaal je mbv een array of je het al een keer hebt gezien of dat het nieuwe is
- is het nieuw dan voeg je het toe aan je array voor letters en je voegt toe aan je array voor begin posities op welke positie je dit karakter voor het eerst tegen bent gekomen.
- is het karakter niet nieuw dan voeg je aan een array voor eindposities de huidige positie van het character toe. Het kan natuurlijk gebeuren dat het de 3de of 4de keer is dat je het character tegenkomt, maar dan overschrijf je gewoon de oude waarde. (afhankelijk van wat je precies wil)
- aan het eind doorloop je je arrays en bepaalt hoe ver de characters uit elkaar liggen en dan weet je ook meteen welke de grootste afstand heeft.


Karakters die maar 1x voorkomen hebben een eindpositie van 0 dus die kan je gelijk overslaan.
Hou verder rekening met :
- slechts 1x elk karakter in een zin
- wil je andere leestekens ook mee laten tellen?
- het gebruik van een array van structures of objecten {letter, begin_pos, eind_pos} is natuurlijk nog makkelijker om alles te doorlopen. =)

[ Voor 69% gewijzigd door -=bas=- op 17-09-2004 09:07 ]

[PrinsEdje80]

Misschien handige tip: gebruik de functie find_last_of() op een string. Loop door de zin van links naar rechts en zoek vervolgens het bijbehorende character op van rechts. Sla de afstand op en loop door totdat je door de gehele string bent. Orde O(n) zou ik denken....

[Robtimus]

PrinsEdje80 schreef op 17 september 2004 @ 09:05:
Misschien handige tip: gebruik de functie find_last_of() op een string. Loop door de zin van links naar rechts en zoek vervolgens het bijbehorende character op van rechts. Sla de afstand op en loop door totdat je door de gehele string bent. Orde O(n) zou ik denken....

Dat is dus precies wat LazySod deed (als hij achteraan begon). Je krijgt dan alsnog een loop (find_last_of()) binnenin een loop (loop door de string). Toch O(n^2) dus.

PS: het array voor eindwaarden is niet nodig. Je doorloopt de string 1x, en slaat de eerste voorkomens op. Vervolgens doorloop je de string nog een keer (vanaf achter), zoekt voor elk karakter de plek van het eerste voorkomen op, berekent het verschil en vergelijkt met het maximum verschil tot dan toe. O(2n) = O(n).

[ Voor 23% gewijzigd door Robtimus op 17-09-2004 09:48 ]

[SWfreak]

IceManX schreef op 17 september 2004 @ 09:45:
PS: het array voor eindwaarden is niet nodig. Je doorloopt de string 1x, en slaat de eerste voorkomens op. Vervolgens doorloop je de string nog een keer (vanaf achter), zoekt voor elk karakter de plek van het eerste voorkomen op, berekent het verschil en vergelijkt met het maximum verschil tot dan toe. O(2n) = O(n).

In het Unicode geval kost je dit echt meer dan constante tijd hoor...

Voor een nette analyse moet je toch goed onderscheid maken tussen het aantal ingevoerde tekens (n) en de range van de tekens (l). Als je weet dat l begrensd is door een (kleine) constante, bijvoorbeeld 256, dan werkt het eerder opgestelde algoritme met l buckets het best, nl. in tijd O(n+l).

Als l >> n (bij unicode wellicht), dan gaat dit algoritme toch wat te traag. Het beste is dan inderdaad om eerste voorkomens op te slaan. Om dit eenvoudig en snel te doen, kun je een binaire zoekboom gebruiken op de characters die voorkomen in je string en hun eerste voorkomens. In C++ kan dit met de STL-klasse map. Dit geeft een looptijd van O(n lg n).

Een andere oplossing, die ook een O(n lg n) looptijd heeft, maakt gebruik van in-place mergesort. Maak een tweede array ind (ook met n posities) en vul deze met de getallen 1...n. Deze array bevat nu indices naar de array met tekens. Gebruik nu in-place mergesort om de tekens te sorteren, en zorg dat bij iedere swap ook de betreffende posities in ind geswapt worden. Nu kun je gewoon van links naar rechts de array ind aflopen:

C:

int i = 0, j = 0;
while( i < n )
{
j = i;
while( tekens[ind[i]] == tekens[ind[j]] && j < n )
j++;
//maximale afstand tussen twee posities met teken tekens[ind[i]] 
//is nu ind[j] - ind[i]
}
i = j+1;

Het bijhouden van de grootste maximale afstand en bijbehorende teken is triviaal. Merk trouwens op dat deze dubbele while-loop lineaire tijd kost. Helaas kost de mergesort O(n lg n) tijd en dus is de totale tijd van dit algoritme ook O(n lg n).
_{Dit algoritme kan nog veranderd worden zdd de originele array met tekens niet veranderd wordt.}

Heb ik nu nog een mogelijke niet omega(n^2) oplossing gemist?

[Verwijderd]

Is het de bedoeling het probleem met C of C++ op te lossen ? De titel zegt C++, maar termen als "class" en "STL" zijn dun gezaaid in de replies.

[Robtimus]

Verwijderd schreef op 17 september 2004 @ 12:39:
Is het de bedoeling het probleem met C of C++ op te lossen ? De titel zegt C++, maar termen als "class" en "STL" zijn dun gezaaid in de replies.

Wat in C kan kan ook in C++. Classes zijn hier denk ik niet relevant, hooguit de STL. Denk dan aan de map van SWFreak.
Het probleem zelf is abstracter dan een taal op zich, dus dan kun je gewoon in abstracte termen (string, array, binaire boom, map) praten. Hoe die in de gebruikte taal is geimplementeerd is voor dit probleem zelf niet zo relevant, alleen voor een implementatie van de oplossing.

[Sjaaky]

Even voor alle mensen die mijn voorstel de grond in trappen in het geval van unicode strings, lees mijn eerste post. :-)

Ik schreef op 16 september 2004 @ 22:46:
En als je unicode strings in wil lezen moet je wel het een en ander aanpassen (een hashtabel om tegengekomen tekens in te stoppen oid).

Ik snap ook wel dat je geen 32 bits lookup table kunt maken omdat dat te veel geheugen inneemt. Maar zoals ik al zei kan je een hashtable gebruiken. Deze biedt O(1) lookup, dus blijft het algorithme O(n). (Ok, ok, niet helemaal vanwege collisions in de hashtable, maar het komt aardig in de buurt).

Verder is het slim om tegelijkertijd van voren en van achter naar het midden te lopen. Als de maxDistance dan groter is dan stringLength - beginToMidIterator kan je stoppen met zoeken. Deze optimalisatie helpt echter alleen als de grootste afstand tussen 2 dezelfde tekens groter is dan de helft van de lengte van de string.

[Verwijderd]

IceManX schreef op 17 september 2004 @ 12:52:
[...]
Wat in C kan kan ook in C++. Classes zijn hier denk ik niet relevant, hooguit de STL. Denk dan aan de map van SWFreak.
Het probleem zelf is abstracter dan een taal op zich, dus dan kun je gewoon in abstracte termen (string, array, binaire boom, map) praten. Hoe die in de gebruikte taal is geimplementeerd is voor dit probleem zelf niet zo relevant, alleen voor een implementatie van de oplossing.

Praten via abstracte termen begrijp ik. Voor mij zijn array en character echter geen abstracte begrippen. Wat daaraan nog ontbreekt is "pointer" en dan is het hele idee van C++ weg: programmeren in de gebruikte abstracte termen.

Momenteel ben ik in gevecht verwikkeld met lieden die verstokt vasthouden de moeilijkste dingen met buffertjes en pointers te doen. Omdat ze classes nieuwerwets en stom vinden. Ik ben niet helemaal onbevooroordeeld .

[Verwijderd]

Het kan simpel met 1 loop en strrchr in C (ik ben geen C++ programmeur )

Begin met eerste karakter van string.
loop
Vervang het karakter dat met strrchr wordt gevonden door '\0' en bepaal de strlen.
Indien strlen groter dan vorige strlen, liggen karakters verder uit elkaar; sla in dat geval karakter en nieuwe strlen op.
Zet karakter weer terug en doe volgende karakter.
loop_end

Extra tests:
1)
als resultaat van strrchr naar het eerste karakter wijst, geldt het niet
2)
stop als strlen van string vanaf karakter dat je test kleiner is dan grootste gevonden lengte omdat je in dat geval dit nooit kunt overschrijden.

[Verwijderd]

Verwijderd schreef op 17 september 2004 @ 15:18:
Het kan simpel met 1 loop en strrchr in C (ik ben geen C++ programmeur )
(...)

Hehe, slim. De functie strrchr loopt zelf ook nog es door de text. Dit programma levert denk ik tot dusver de minste code op, de orde van de berekening blijft echter n^2. Maar ja, voor 80 tekens boeit dat niet.

[Robtimus]

Verwijderd schreef op 17 september 2004 @ 13:43:
Praten via abstracte termen begrijp ik. Voor mij zijn array en character echter geen abstracte begrippen. Wat daaraan nog ontbreekt is "pointer" en dan is het hele idee van C++ weg: programmeren in de gebruikte abstracte termen.

Een array is toch wel een abstract begrip. Ik heb hier op de TU/e veel les gehad mbv GCL (abstracte programmeertaal), en ook daarin bestonden arrays. Misschien had Dijkstra die wel gebaseerd op een programmeertaal als C, maar dat neemt niet weg dat gezien de wijde verspreiding van arrays in programmeertalen het een abstract begrip is (geworden). Of zie je het abstracter als we hem vector noemen? En op die manier is een character ook niet taal-/implementatie specifiek.
Pointers daarentegen zie ik als te concreet (bevat een geheugenplaats).

Momenteel ben ik in gevecht verwikkeld met lieden die verstokt vasthouden de moeilijkste dingen met buffertjes en pointers te doen. Omdat ze classes nieuwerwets en stom vinden. Ik ben niet helemaal onbevooroordeeld .

Ik ben ook een voorstander van classes hoor, juist omdat het abstractie bevorderd.

[ Voor 4% gewijzigd door Robtimus op 17-09-2004 15:58 ]