- sziku69: Fűzzük össze a szavakat :)
- D1Rect: Nagy "hülyétkapokazapróktól" topik
- sellerbuyer: Hogyan turbózd fel a NAS-od sebességét olcsón és egyszerűen?
- ubyegon2: Airfryer XL XXL forrólevegős sütő gyakorlati tanácsok, ötletek, receptek
- Sub-ZeRo: Euro Truck Simulator 2 & American Truck Simulator 1 (esetleg 2 majd, ha lesz) :)
- Luck Dragon: Asszociációs játék. :)
- sziku69: Szólánc.
- GoodSpeed: Perplexity Pro AI képszerkesztési limit -egy képgenerátor függő tapasztalatai
- Parci: Milyen mosógépet vegyek?
- sh4d0w: Én és a számítógép
Új hozzászólás Aktív témák
-
jattila48
aktív tag
válasz
Boryszka
#3095
üzenetére
Egy mohó algoritmust találtam ki a feladatodra, ami azért nem biztos, hogy optimális megoldást ad. Mintasorozatnak fogom nevezni az 1...N sorozatban bárhol megtalálható eltolt mintát. Tehát az pl. az 1,2,3,4,5,6,7,8 sorozatban az 1,3,4 mintának megfelelő mintasorozatok az 1,3,4; 2,4,5; 3,5,6; 4,6,7 és 5,7,8. Az elgondolás az, hogy a sorozatban megkeresem az első mintasorozatot, majd törlöm az egyik elemét. Ezzel elrontom az éppen aktuális mintasorozatot, és esetleg még másikakat is (legfeljebb annyit, amennyi a minta elemszáma, a példában ez 3). Azt az elemet fogom elhagyni, amelyik a legtöbb mintasorozatot rontja el. Ha több ilyen is van, akkor az elsőt veszem. Ezután az eljárást megismétlem. Megint veszem az első ép mintasorozatot (az elrontottak már nem lesznek tekintetbe véve), és megont elhagyom azt az elemét, amely a legtöbb mintasorozatot rontja el. És így tovább, egészen addig, amíg már nem lesz ép mintasorozat. Írtam is erre egy egyszerű kis programot. Felveszek egy sorozat nevű int tömböt, aminek az i. eleme (0-tól kezdődik az indexelés) kezdetben azt jelzi, hogy az i+1 szám hány mintasorozatban szerepel. A példában ez így néz ki:
1,1,2,3,3,2,2,1. A 4-es számnak megfelelő érték (3. indexű elem) 3, ami azt jelenti, hogy a 4 3 db mintasorozatban szerepel (1,3,4; 2,4,5; 4,6,7). Ezért az algoritmusnak megfelelően az első kihúzandó szám a 4 lesz. Az 5 is 3 mintasorozatban szerepel, azonban a 4 előbb van, ezért azt választjuk. Ezzel máris elrontottuk a felsorolt 3 mintasorozatot, a továbbiakban ezeket nem vesszük figyelembe. Most a sorozat tömb elemeit csökkenteni fogjuk, annak megfelelően, hogy az egyes számok a még megmaradt mintasorozatok közül hányban szerepelnek. Ezt az eljárást egészen addig ismételjük, amíg a sorozat tömb minden eleme 0 nem lesz.
A programkó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: ");
while(1){
int kihuzando,max=0;
//megkeressuk az elso, 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];
}
}
if(max==0)break;
printf("%d ",kihuzando+1);
//A kihuzott szam utan a sorozat tomb elemeit csokkentjuk, hogy tovabbra is azt jelezze, a megmaradt ep mintasorozzatok 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 && sorozat[k]>0){
--sorozat[k];
}
}
}
}
delete[] minta;
delete[] sorozat;
}Kissé off topic voltam, de ha már itt tetted fel a kérdést, itt válaszoltam. Nem vagyok biztos benne, hogy optimális megoldást ad az algoritmus, de biztosan mintamenteset, és szerintem közel optimálisat. Bár a mohó algoritmusok nem mindig jók. A program egyébként a példára azt fogja kiírni, hogy a 4-et és 5-öt hagyd el, ami jó és optimális is (legalább 2 elemet el kell hagyni). Mivel kezdetben N-mintaterjedelem+1 (mintaterjedelem a legnagyobb, vagyis utolsó mintaelem) mintasorozat van és egy elem kihúzásával legfeljebb nm (minta elemszáma) mintasorozatot rontunk el, ezért legalább (N-mintaterjedelem+1 )/nm felső egész része számú elem kihúzására van szükség. A példában ez 5/3=2, tehát legalább 2 elemet ki kell húzni.
-
válasz
Boryszka
#3091
üzenetére
"Ekkor a feladat az, hogy az (1,2,3,...,18,19,20) számokból (1-től 20-ig mindegyik) töröljünk minél kevesebbet úgy, hogy a megmaradt számok között ne forduljon elő a (2,3,6,8,13) minta és eltoltjai!"
Ne törölj semmit, probléma megoldva.
Következő kérdés?
Egyébként ez C vagy C++ házi?
(És hol adnak ilyen rettenetesen rosszul megírt feladatokat?) -
LordX
veterán
válasz
Boryszka
#3091
üzenetére
Ha letörlöd a minta első elemét az 1-20 listából, az nem oldja meg a problémát? 1 elem törlése, 2 sor:
std::vector<int> minta = ...;
std::vector<int> egytolhuszig = ...;
auto torlendo = std::find(begin(egytolhuszig), end(egytolhuszig), minta.front())
if (torlendo != end(egytolhuszig)) { egytolhuszig.erase(torlendo); } -
EQMontoya
veterán
-
jattila48
aktív tag
válasz
Boryszka
#2831
üzenetére
A matrix_base-től való öröklés szerintem felesleges, főleg private módon. A következő header jó kiindulás lehet:
template<typename T,int n,int m> class my_matrix{
public:
typedef T scalar_type;
/*
my_matrix(const my_matrix& mm){
int i,j;
for(int i=0;i<n;++i){
for(j=0j<m;++j){
matrix[i][j]=mm[i][j];
}
}
}
my_matrix &operator=(const my_matrix &mm){
}
*/
my_matrix(){
int i,j;
for(i=0;i<n;++i){
for(j=0;j<m;++j){
matrix[i][j]=T();
}
}
}
my_matrix & operator+=(const my_matrix &mm){
int i,j;
for(i=0;i<n;++i){
for(j=0;j<m;++j){
matrix[i][j]+=mm.matrix[i][j];
}
}
return *this;
}
my_matrix & operator*=(T c){
int i,j;
for(i=0;i<n;++i){
for(j=0;j<m;++j){
matrix[i][j]*=c;
}
}
return *this;
}
my_matrix operator+(const my_matrix &mm){
my_matrix t(*this);
int i,j;
for(i=0;i<n;++i){
for(j=0;j<m;++j){
t.matrix[i][j]+=mm.matrix[i][j];
}
}
return t;
}
my_matrix & operator=(const my_matrix &mm){
int i,j;
for(i=0;i<n;++i){
for(j=0;j<m;++j){
matrix[i][j]-=mm.matrix[i][j];
}
}
return *this;
}
const T & operator()(int i,int j) const{
assert(i<n && j<m);
return matrix[i][j];
}
T & operator()(int i,int j){
return const_cast<T &>(const_cast<const my_matrix *>(this)->operator()(i,j));
}
private:
my_matrix(const my_matrix &a,const my_matrix &b){
int i,j;
for(i=0;i<n;++i){
for(j=0;j<m;++j){
matrix[i][j]=a.matrix[i][j]+b.matrix[i][j];
}
}
}
T matrix[n][m];
};
/*
template<typename T> T operator+(T a, T b){
T c(a);
c+=a;
return c;
}
*/
template<typename T,int n,int m,int k> my_matrix<T,n,m> operator*(const my_matrix<T,n,k> &a,const my_matrix<T,k,m> &b){
my_matrix<T,n,m> c;
int i,j,l;
for(i=0;i<n;++i){
for(j=0;j<m;++j){
T s=T();
for(l=0;l<k;++l){
s+=a(i,l)*b(l,j);
}
c(i,j)=s;
}
}
return c;
}
template<typename T> T operator*(T A,typename T::scalar_type c){
T t(A);
t*=c;
return t;
}
template<typename T> T operator*(typename T::scalar_type c,T A){
return operator*(A,c);
}Copy ctor-t és értékadó operátort csak akkor kell írnod, ha a scalar_type (a mátrix elemeinek típusa) nem triviálisan másolható. Ezt pl. type trait-tal is ellenőrizheted. A + operator lehet tfv. is, ha nincs más típusról implicit konverzió. Különben free fv.-nek kell lenni. Én most nem írtam 1 paraméteres ctort, így nem lehet implicit konverzió (kivéve, ha más osztálynak van my_matrix-ra konverziós operátora).
Új hozzászólás Aktív témák
Hirdetés
● ha kódot szúrsz be, használd a PROGRAMKÓD formázási funkciót!
- Hálózati / IP kamera
- Foreo FAQ 202 – LED it be!
- Nők, nőügyek (18+)
- Kormányok / autós szimulátorok topikja
- exHWSW - Értünk mindenhez IS
- Meglepetés az iPhone Air hajlítópróbáján
- TCL LCD és LED TV-k
- Nyíregyháza és környéke adok-veszek-beszélgetek
- NVIDIA GeForce RTX 5080 / 5090 (GB203 / 202)
- Intel Core i5 / i7 / i9 "Alder Lake-Raptor Lake/Refresh" (LGA1700)
- További aktív témák...
- Oura Ring 4 Gold, Rose Gold (8,10-es méret) ÚJ ÁRA - 235.000 Ft
- Eladó: Teljesen Új Ooni Koda 2 Max Gázüzemű Pizzakemence Bontatlan, Gyári csomagolásban!
- Solana Mobile Seeker Web3 okostelefon
- Thinkpad X13 Gen5 13.3" FHD+ IPS Ultra 5 135U 16GB 512GB NVMe ujjlolv gar
- Eladó Juniper SRX300 tűzfal / router friss firmware-rel!
- Xiaomi Redmi 9AT 32GB, Kártyafüggetlen, 1 Év Garanciával
- Eladó karcmentes Apple iPhone 13 Pro 128GB Kék / 12 hó jótállás
- GYÖNYÖRŰ iPhone 13 128GB Starlight- 1 ÉV GARANCIA, Kártyafüggetlen,MS3435
- ÁRGARANCIA!Épített KomPhone Ryzen 7 9800X3D 32/64GB DDR5 RAM RTX 5070 12GB GAMER termékbeszámítással
- Xiaomi Redmi 12C 64GB, Kártyafüggetlen, 1 Év Garanciával
Állásajánlatok
Cég: CAMERA-PRO Hungary Kft.
Város: Budapest
Cég: PCMENTOR SZERVIZ KFT.
Város: Budapest