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

• #3123 jattila48 aktív tag jattila48 #3116

  Új Válasz 2016-01-11 10:38:16 #3123

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  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.

• #3117 jattila48 aktív tag jattila48 #3116

  Új Válasz 2016-01-11 00:06:06 #3117

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  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