Keresés

Új hozzászólás Aktív témák

  • jattila48

    aktív tag

    válasz jattila48 #3116 üzenetére

    Hát, ez az algoritmus nem valami jó. Ugye mindig olyan számot hagytam el a sorozatból (pontosabban az első ilyet), amivel a legtöbb még ép mintasorozatot rontom el. Most egy kicsit módosítottam az algoritmuson, és az első ép mintasorozatból hagyom el azt az elemet, ami a legtöbb mintasorozatot rontja el. Ennek megfelelően a módosított forráskód:
    #include <Windows.h>
    #include <stdio.h>

    int main(int argc,char *argv[])
    {
    if(argc<3){
    printf("Hasznalata: mintat_gyomlal <a gyomlalando sorozat hossza> <minta elemek 1... novekvoleg>");
    exit(1);
    }
    int mintahossz=argc-2,sorozathossz=atoi(argv[1]);
    auto minta=new int[mintahossz];
    for(int i=0;i<mintahossz;++i){
    minta[i]=atoi(argv[i+2]);
    }
    int minta_terjedelem=minta[mintahossz-1];
    auto sorozat=new int[sorozathossz];
    for(int i=0;i<sorozathossz;++i){
    sorozat[i]=0;
    }
    for(int i=0;i<=sorozathossz-minta_terjedelem;++i){
    for(int j=0;j<mintahossz;++j){
    ++sorozat[minta[j]+i-1]; //a tomb kezdeti feltotlese. az i.-edik elem azt jelzi, hogy az i+1 szam hany mintasorozatban szerepel
    }
    }
    printf("A sorozatbol kihuzando szamok: ");
    int nkihuzando=0;
    while(1){
    int kihuzando,max=0;
    /*
    //megkeressuk a legtobb mintasorozatban szereplo szamot, ez lesz a kihuzando+1 (a kihuzando indexu, mivel 0-val kezdodik az indexeles)
    for(int i=0;i<sorozathossz;++i){
    if(sorozat[i]>max){
    kihuzando=i;
    max=sorozat[i];
    }
    }
    */
    //modositas: az elso ep mintasorozatbol keressuk ki a legtobb mintasorozatot elronto elemet
    int i;
    for(i=0;i<sorozathossz && sorozat[i]==0;++i);
    if(i==sorozathossz)break;
    for(int j=0;j<mintahossz;++j){
    int n=i+minta[j]-1;
    if(sorozat[n]>max){
    kihuzando=n;
    max=sorozat[n];
    }
    }

    if(max==0)break;
    printf("%d ",kihuzando+1);
    ++nkihuzando;
    //A kihuzott szam utan a sorozat tomb elemeit csokkentjuk, hogy tovabbra is azt jelezze, a megmaradt ep mintasorozatok kozul hanyban szerepel az adott szam
    for(int i=0;i<mintahossz;++i){
    int n=kihuzando-minta[i];
    for(int j=0;j<mintahossz;++j){
    int k=minta[j]+n;
    if(k>=0 && k<sorozathossz && sorozat[k]>0){
    --sorozat[k];
    }
    }
    }
    }
    printf("\r\nOsszesen %d db.",nkihuzando);
    delete[] minta;
    delete[] sorozat;
    }

    A végén kiírom, hogy hány elemet hagytam el. Valamivel jobb eredményt ad mint az előző, de szerintem ez is távol áll az optimálistól.

  • jattila48

    aktív tag

    válasz jattila48 #3116 üzenetére

    A programkódban:
    if(k>=0 && sorozat[k]>0){
    --sorozat[k];
    }

    helyett helyesen:

    if(k>=0 && k<sorozathossz && sorozat[k]>0){
    --sorozat[k];
    }

Új hozzászólás Aktív témák