encse,
így már értem, és bosszant, hogy nem tudok rá képletet adni :-)
De szerintem nincs rá lineráris rendű megoldó program, sőt gynús, hogy faktoriálisnál jobb rendű sincs... (Ugye a linerárist az eredeti sorozat hosszára gondoltad és nem a létrehozható sorozatok számával arányosra gondoltál.)
Arra gondolsz, hogy simán a különböző maszkokat összeszámoljuk, és így pont (2^szóhossz)-1 részsorozat van? Sejtettem, hogy kellene egy nem ilyen speciális példát is írnom. Tehát: a gondok akkor kezdődnek, ha több egyforma jel is van a szóban. Pl. abab esetén az ab részsorozat előáll az 1100, 0011, 1001 maszkok mellett is. (A maszk úgy értendő, hogy a nullás pozíciókat elhagyjuk, az egyeseket megtartjuk.) Így a különböző maszkok száma (2^4)-1=15 több, mint a részsorozatok száma.
A lehetséges részsorozatok itt:
a, b, ab, ba, aa, bb, aab, aba, abb, bab, abab
Ha nem hagytam ki semmit, akkor a D-bonyolultság csak 11.
Remélem így érthetőbb. Amúgy a sorrend cserét hogy érted? Csak elhagyjuk a betűket, és a maradék egy részsorozat.
encse,
valamit biztos nem értek, de ez a feladat nekem egyetlen hatványozásnak ill. faktoriális összegnek tűnik aszerint, hogy számít-e a sorrend. (Az utóbbi már O(n^2) rendű.)
A dolognak semmi gyakorlati haszna nincs szerintem, de azért jól el lehet szórakozni vele (nekem két napig tartott).
Adott egy szó mondjuk: 12345678. Keressük ennek D-bonyolultságát, azaz a különböző részsorozatainak számát (magyarul elhagyunk belőle néhány - esetleg 0 , de nem az összes - betűt, és az így kapott különböző részsorozatok számát szeretnénk meghatározni). Tehát pl. ennek részsorozatai lehetnek: 1, 12, 148, 12345678, stb. Hány ilyen van?
Adjunk olyan a szó hosszára nézve lineáris futásídejű és memóriaigényű algoritmust, amely tetszőleges szó D-bonyolultságát meg tudja határozni!
Igen érdekes vitának lehetünk tanúi, aminek lassan a felét a másik ismétlése teszi ki. (de ez nem ide tartozik)
Nem írna valaki megint feladványokat is?
Örülnék neki...
"Ha valaki hozzanyul a kodhoz, es megvaltoztatja a tipust (ami teljesen normalis dolog)" Nem, ez nem normális. Ha csak ennyit tesz, akkor vagy én rontottam el valamit vagy ő.
Merthogy?
A tipusok nem fluktuálnak egymásba.
Nem tudom mit ertesz fluktualason. De szvsz teljesen normalis dolog, hogy valami ma Editbox, holnap EdiboxWitThickBlackBorder, holnaputan EditWithHistory, stb. De akar szamoknal is miert ne lehetne egy mennyideg ma int, holnap Int, _int16, Number, Bugnumber, Rational, Complex, DbInteger vagy akarmi mas, ami hasonloan mukodik, de megis maskent.
Vagy egy kollekcio vector helyett list lesz, vagy singlelist, doublelist. Ha a std szerinti kollekciokat hasznalod az algotitmusokkal es iteratorokkal, a program tulnyomo resze eszre sem veszi a valtozast.
Hasonloan, a refactoring kereteben az egyed tipusok mukodese is jelentosen modosulhat, szetrakjuk, osszerakjuk, megvaltoztatjuk a kapcsolatokat, stb.
Az előfordulhat, hogy pl. egy hajdanában int32-nek tervezett mennyiségről kiderül hogy kicsi és át kell térni int64-re vagy stringre. Egy ilyen jellegű változás kezelése azonban nem merülhet ki változó típusváltásban vagy átnevezésben.
So what? Megint felrebeszelsz. Egy dolog, hogy egy valtozas metortenik-e, es egy masik, hogy pontosan hogyan. Te az utobbit kezdted berangatni a vitaba. Objection - irrelevant! :-)
Az adatmodell additív változásait is egy teljeskörű változástervezésnek kell megelőznie (és akkor nem fordul elő, hogy a copy contructor nem másolja az új adattagot, mint amire volt példám).
Err, hogy csinalja a copyctor hogy nem masolja a micsodat? Ha atirom egy objektum tipusat egy masikra (feltetelezve hogy az az osztaly korrekt modon viselkedik), a copyctor vagy magatol jo lesz, vagy nem fordul le a program. mindezt total magatol.
Mellesleg ugye egyetertunk, hogy a modern kornak megfelelo C++ kodban az autogen copyctorok uralkodnak, ujra. Es a fordito nem hibazza el.
(Ettol meg persze meg nem tekint el az ember a vizsgalattol, de ennek a feladatnak a tartalma messze leegyszerusodott.
Azt me gvégképp nem értem, hogy egy változó átnevezés mitől tud bugot okozni...
Attol, hogy az illeto, aki csinalja elbassza. Elgepeli, stb. Ismered az "ami nem hibas, azt ne javitsd" elvet? Eleg okos emberek talaltak ki. Es akik nem kovetik rendszeresen a verukkel fizetnek.
Node ideje lenne visszaterni a temahoz. Az egyetlen valamirevalo pozitivum amit felhoztal a tipus nevbe kodolasa mellett az volt, hogy akkor latod a tipust a nevbol. Ha mar ott vagy az osszes terveddel felvertezve, miert is van szukseged erre az infora? mire odaig jutsz, hogy latod a nevet, mar reg tudsz rola mindent, nem? Akkor meg minek faradni vele?
Irnal egy koherens peldat? :)
"A terv meg eleg ritkan szokta tartalmazni azokat a kivansagokat, melyek holnap pattannak ki a kedves megrendelo agyabol." Épp az a baj (és ez elég szignifikáns különbség kettönk 'világnézete' között), hogy a feladat módosulásait nem a kódban kell végrehajtani, hanem a véltozást kell megtervezni.
Nem tudom a kovetkeztetesedet milyen alapon szurted le. En egyszeruen nem beszeltem a temahoz nem tartozo dolgokrol, az nem jelenti hogy azok nem is leteznek.
Maradjunk az eletnel: az objektum-neveknek, melyekrol beszelunk, csak kis resze fog megjelenni a tervben. Azok, melyek a publikus interfeszben szerepelnek. A tobbi "detail" ami (keves kiveteltol eltekintve)nem tartozik a tervre.
Ráadásul így el lehet dönteni, hogy a kód átírása, hogy újraírása a megfelelőbb.
Valaki eldonti. So what? Szvsz mindenki tudja a 98%-os esetet: "Ezt ujra kene irni, de nem tehetjuk meg, mert .... Majd esetleg ha tuljutottunk az aktualis hataridon, utana." Az utana persze szinten a 2%-os eset.
De mindez megint irrelevans.
(Megjegyzés: tudom, hogy erre nagyon ritkán van példa. A kisebb módosítások többnyire nem is kerülnek be a specifikációba, a nagyobbak esetén jó esetben átírják a specifikációt, de a kódot csak módosítgatják.)
Es ez igy van rendjen. Amiota lehet "self-documenting" kodot irni, mar az elvarasokbol is kikerult a "tervezes" ilyen sizntje.
"Ha valaki hozzanyul a kodhoz, es megvaltoztatja a tipust (ami teljesen normalis dolog)" Nem, ez nem normális. Ha csak ennyit tesz, akkor vagy én rontottam el valamit vagy ő. A tipusok nem fluktuálnak egymásba. Az előfordulhat, hogy pl. egy hajdanában int32-nek tervezett mennyiségről kiderül hogy kicsi és át kell térni int64-re vagy stringre. Egy ilyen jellegű változás kezelése azonban nem merülhet ki változó típusváltásban vagy átnevezésben. Az adatmodell additív változásait is egy teljeskörű változástervezésnek kell megelőznie (és akkor nem fordul elő, hogy a copy contructor nem másolja az új adattagot, mint amire volt példám). A modell más jellegű változásait még alaposabban kell(ene) megtervezni a meglevő adatok, a meglevő funkcionalitás és a meglevő kód alapján.
Azt me gvégképp nem értem, hogy egy változó átnevezés mitől tud bugot okozni...
"Te szoktal ilyenekkel foglalkozni" Épp hibát javítok. A file fejlécben: "@created 0.1 1998.03.08"
"A terv meg eleg ritkan szokta tartalmazni azokat a kivansagokat, melyek holnap pattannak ki a kedves megrendelo agyabol." Épp az a baj (és ez elég szignifikáns különbség kettönk 'világnézete' között), hogy a feladat módosulásait nem a kódban kell végrehajtani, hanem a véltozást kell megtervezni. Ráadásul így el lehet dönteni, hogy a kód átírása, hogy újraírása a megfelelőbb. (Megjegyzés: tudom, hogy erre nagyon ritkán van példa. A kisebb módosítások többnyire nem is kerülnek be a specifikációba, a nagyobbak esetén jó esetben átírják a specifikációt, de a kódot csak módosítgatják.)
Szvsz a c++ egy teljesen korrekt nyelv. Es annak aki tud programozni, joval kenyelmesebb mint mondjuk a C.
A "csinaljunk egy egyszeruseitett C++-t" torekvesre kepzodott nyelvek (java, C#) mar tapasztalatok alapjan jol mutatjak, hogy nem leptek elore.
Teny, hogy lehet jol osszekavart dolgokat csinalni (foleg templatokkal), de ezek tobbsege akademikus, az eletben egyszeruen "te csinalj olyat" es kesz. Meg az a veszely sem fenyeget, hogy mas rak alad ilyen aknat.
Elmondanad, hogy neked mi tunik bonyolultnak a C++-ban?
>ha lehet, a strukturált programozás kapcsán semmilyen MS eredetű kódot ne emlegessünk fel, legfeljebb negatív példaként...
Ezt tamogatom. Es rogton tegyuk hozza, hogy a HN-t a M$ eroltette, es csak ok hasznaltak erdemben (plusz par csoka aki nem igazodott a fenti kijelenteshez.)
>Ha nincs tervezés (amelynek elég koari lépése lenne az adatbázis terv), akkor egyáltalán nincs értelme programozásról beszélni
Ezzel a kijelentessek egeytertek, csak megint nem illeszkedik a targyalt temahoz.
Te jottel azza, hogy a kodot T ido (pl. 5 ev) elmultaval elovesszuk. Miert is vesszuk elo? Gondolom nem azert, mert sok a szabad idonk, hanem mert at kell irni.
A terv meg eleg ritkan szokta tartalmazni azokat a kivansagokat, melyek holnap pattannak ki a kedves megrendelo agyabol.
A kod modosulasa az idovel teljesen termeszetes. Mar egesz uj tudomanyagak szovodnek e kore (lasd
"refactoring").
Tobbnyire van eger a kezem alatt. De nem letszukseglet. (Csak tudnam hogy jon ez ide.)
>Azért anyira nem borzasztó, ha egy változónévre ránézve tudod, hogy az egy cím, objektum vagy valami numerikus és egyből tudod, hogy mit lehet vele tenni.
Hogyne, az sem olyan borzaszto, ha 10 szep lany korulzsong, lesik a kivansagaimat, massziroznak, stb. Persze csak amig te fizeted a szamlat.
A valtozonevbe kodolt egyeb info addig hasznos, amig igaz. Ha valaki hozzanyul a kodhoz, es megvaltoztatja a tipust (ami teljesen normalis dolog) ket dolgot tehet: meghagyja a valtozo nevet vagy nem. A gyakorlatban ezt random modon csinaljak. Igy nagyon hamar eljut a program abba az allapotba, hogy a nevek egy resze hazudik, igy az altalad elkepzelt cel nem teljesul.
Ha pedig precizen uj nevet kap a valtozo, es vegig van konyvelve, az bizony jelentos plusz munka, es extra bugok bejutasi kapuja.
>Ilyen alapon az egész változónév redundancia, elég egy betű, úgysem használunk 26-nál több változót.
No ezt az okos kovetkeztetest igazan megindokolhatnad. Kezdjuk talan a "redundancia" szo jelentesevel.
>Egyébként meg dögöljön meg, aki 5 év múlva javítani akarja a kódodat.
Te szoktal ilyenekkel foglalkozni, vagy csak lip service? En ugyanis mar eleg sokszor kerultem pont ebbe a helyzetbe, hogy masok reg elfeledett ganyolmanyabol kell jol mukodo programot csinalni, tegnapra.
Na akkor még1*, miért tartom jobbnak az én megoldásomat:
A kód sokkal olvashatóbb. Nem az van, hogy mindenféle if-else meg switch szerkezeteken kell átjutnod, mire eljucc a lényegi kódig. Hanem látod a különböző hibás eseteket 1-1 if formájában, aztánmeg ott a kódod.
A hibát nem mindíg kell/lehet helyben lekezelni, SŐT általában ha megírsz egy függvényt, amit pl mások is használni fognak, akkor nem illik/lehet mindent helyben lekezelni. Mondjuk nem tud megnyitni egy filet, azzal te mit kezdesz? Terminálsz? Nem teheted (legalábbis nem illene). Inkább valami spec értéket adsz visszatérési értékként, amit a hívó lekezelhet. De nem mindíg van ilyen spec érték. Arról nem is beszélve, hogy mi van ha többféle hiba is előfordulhat, amit nem tudsz helyben lekezelni (hisz nem tudhatod, a függvényed használója mit akar majd kezdeni az egyes esetekben)? Azt már nem nagyon tudod spec értékekkel lekezelni. Mennyivel egyszerübb, ha megmondod, milyen kivételeket válthat ki a függvényed hívása, és ezeket lehet elkapdosni? Szerintem sokkal szebb, jobb, praktikusabb, ...
Amúgymeg ajánlom Stroustrup könyvecskéjét olvasgatni, abban van néhány elég jó kis érv.
C++ tényleg bonyolult, de talán érdemes megpróbálni. Ha nem is leszel igazi C++ programozó, sokmindent felhasználhatsz az előnyeiből, anélkül, hogy mélyebben belemerülnél a nyelv rejtelmeibe (szvsz Strousrtupon kívül nem sok ember tud igazán C++ -ul, nekem legalábbis nagyon bonyolult nyelvnek tűnik a Mester könyve alapján).
Gondolj bele pl, hogy a saját kivételedet konstruktorálhatod úgy, hogy tartalmazza a pontos hibát. De erre csak azert van szukseg, mert a hibakezelest eltavolitjuk a hiba fellepesetol... ha helyben kezeljuk, akkor eleve kezunkben vannak az adatok.
Sőt, ha több hasonló hibaellenörzés van, az a 2. esetben több * 2 sort jelent a "normális eset elött Mereseim szerint ha ket helyen lephet fel "ugyanaz a hiba", az altalaban megsem "ugyanaz" egy kicsit maskepp kell kezelni...
Persze az biztos, hogy a kod megduplazasat el kell kerulni... nagysagrendekkel nagyobb bun mint pl egy goto.
C++:
lehet hogy mar tul oreg vagyok hozza:-(
Bar egy elonye tenyleg van: lehet strukturakat 'kiterjeszteni' oroklessel, amit egyebkent csak beagyazott strukturaval (vagy preprocesszoros buveszkedessel) lehet megoldani...
Egoist,
ne kavard össze: az, hogy egy adatbázis mező milyen méretű/precizitású eldönthető (és eldöntendő!) a tervezés alatt, míg egy platformváltást kicsit nehezebb betervezni egy API-ba. (Mellesleg az egész int16-int32 átállás elég zavaros a Win32 API-ban, de nem esküszöm meg rá, hogy sokkal joban meg lehetett volna oldani anélkül, hogy teljesen új kifejezéshalmazt vezettek volna be.)
Végül, de nem utolsó sorban: ha lehet, a strukturált programozás kapcsán semmilyen MS eredetű kódot ne emlegessünk fel, legfeljebb negatív példaként...
A kivételkezelés azért SOKKAL töbre is képes, mint egy goto+label. Gondolj bele pl, hogy a saját kivételedet konstruktorálhatod úgy, hogy tartalmazza a pontos hibát. Grrrrr...
Magyarázat:
if (valami < 0) { //hibás érték
switch (valami) {
case -1: ...
case -2: ...
....
}
}
HA NEM TÖRTÉNT HIBA
helyett:
try {
if (valami < 0)
throw lessThanZero(valami);
HA NEM TÖRTÉNT HIBA
} catch (lessThanZero l) {
switch (l.getValue()) {
case -1: ...
case -2: ...
....
}
}
Szerintem sokkal célszerübb a 2. megoldás, mivel a speciális esetek külön vannak lekezelve, így a kódot sokkal egyszerübb olvasni. Sőt, ha több hasonló hibaellenörzés van, az a 2. esetben több * 2 sort jelent a "normális eset elött", az elsőben meg egy sok hibakezelő kód a "normális eset" kódja elött.
Jól elkülönített kommentekkel lehet javítani a helyzeten, de nekem akkoris a 2. megoldás teccik jobban.
C: továbbra is az egyik kedvenc nyelvem, de már nem nagyon látom a létjogosultságát a c++ melett (leszámítva a max néhány 100 soros progikat). Nemrég olvastam valahol (bár saját tapasztalatom nincsen), hogy talán az AS400-ok oprendszerének kernele is c++ -ban íródott, és jól megállja a helyét.
Azért ez nem egészen így van.
Tegnap megtaláltam 1-2 már korábban olvasott cikket az ügyben, és a felvetésedre a következő problémát írták az egyik helyen:
Visualéknál dívik a hun. not., és van olyan változójuk, ami w-vel kezdődik (nem emléxem konkrétan mejik változó szerepelt a példabeszédben, de gondolom több ilyen is van). Ez MS jelölés szerint azt jelenti, hogy word, azaz 16 bites. Nos ez a változó 32 bitesedés óta 32 bites, azaz dw kéne hogy az eleje legyen, de ugyebár nem szokás csak úgy megváltoztatni ilyen dolgokat, így maradt w. így viszont semmi értelme az egésznek, hisz nem a valóságot tükrözi a név, és így megtévesztő. Megváltoztatni a nevét pedig szintén problémás, hisz ha nem volna gond, akkor megtették volna.
Amúgy asszem még nem írta senki:
azért hungarian, mivel Charles Simonyi "vezette" be MS-éknél. Aki ugyebár magyar (1948-ban született Bp-en).
Ad 3. a throw-catch-et lehet goto-ként használni, de annál sokkal többre is. A java kivételkezelése, ahol a kivételek dobása is deklarált nagyon masszív hibakezelést tesz lehetővé, persze ehhez kell, hogy:
- ott dobjunk hibát, ahol valami fatális (azaz az adott szinten nem lekezelhető) történik,
- ott kapjuk el, ahol először kezelhető a hiba.
Pl. egy parser olvasó részében sokkal egyszerűbb, ha nem az összes apró olvasó rutin kezeli az input végét, hanem csak a fő eljárás fog meg egy kivételt. (Persze célszerű a publikus interfészre minél kevesebb throws-t rakni.)
Keversz:-)
Az adatbazis tervesekor eldontjuk, hogy a rekordnak lesz egy technikai kulcsa, de nyitva hagyjuk azt a kerdest, hogy az 10 szamjegybol, 5 betubol, vagy valami masbol fog-e allni...
Pl egy rendesen megcsinalt fejlesztesnel nem omlunk ossze ha kiderul, hogy a megrendelo kivansagara szemelyi szam (NUMBER(11)) helyett utlevelszammal (CHAR(8)) kell azonositanunk a dolgozokat.
Felreertesz... nem az a gond, hogy a hibakezeles bonyolult, hanem az hogy tul melyen van a sok if egymasba agyazva
Exception: ket okbol nem hasznalom:
1) C-ben nincs exception
2) az en tapasztalataim szerint a hibat ott kell kezelni ahol fellep, ha mar egyszer elhalasztjuk akkor elfelejtodik, osszecsapodik, osszekeverednek a kulonbozo hibaokok stb
3) a throw+catch nagyon hasonlit egy goto+label -re, csak eppen nehezebb megtalalni a parokat...
Egoist,
én általában ilyen kódot írok C++-ban, azzal a különbséggel, hogy a "csinálok valamit" rendszerint egy hibát vagy sikerességet visszaadó függvény/metódus, így az mélység kicsi marad.
Javaban pedig inkább a meghívott metódusok dobják a kivételt, az ilyen "rövid távú" kivételt inkább kerülöm (kivéve ha nagy a try blokk, de ekkor már nem "rövid távú" a kivétel).
NevemTeve,
"a valtozo neve ne utaljon a tipusra, mert az megvaltozhat fejlesztes kozben" Ha nincs tervezés (amelynek elég koari lépése lenne az adatbázis terv), akkor egyáltalán nincs értelme programozásról beszélni, csak kódfarigcsálásról, ez esetben viszont minek akarunk programozási elveket vagy szabályokat alkalmazni?!?
pasa_,
Te ugye egérrel "programozol"?
Azért anyira nem borzasztó, ha egy változónévre ránézve tudod, hogy az egy cím, objektum vagy valami numerikus és egyből tudod, hogy mit lehet vele tenni. Ilyen alapon az egész változónév redundancia, elég egy betű, úgysem használunk 26-nál több változót. Egyébként meg dögöljön meg, aki 5 év múlva javítani akarja a kódodat.
Igen, de épp az általad írt példában nem volt "csinalok valamit;" ill. "megvalamit csinalok;", azaz teljesen felesleges volt a return használata. Ezért írtam azt, amit.
Épp nemrég gondoltam nyitni egy programozási stílus topikot.
Hungaryan notation: Pozitív fogadtatást még sehol sem láttam. Linket nem tudok írni, de engem 2-3 kritika meggyőzött a szükségtelenségéről. Aki keres, az talál elég cikket erről. Az más kérdés, hogy VC-ben minden osztály C-vel kezdődik, a pointerek p-vel, a lokális változók (amik nem a függvény paraméterei) szintén valamilyen betűt tartalmaznak (talán l?) (ennyit MS-ék stílusáról. nem hiszem, hogy ha nyílvános lenne a win kódja, bárki is tudná értelmezni :) (persze most nem emiatt)). Ebből a p nekem teccik, hisz így 1értelmű, hogy mikor kell .-ot és mikor -> -t használni. Ezt a C critique is megírta, és teljesen 1etértek vele, hogy nincs sok értelme a kétféle jelölésnek, hiszen fordítási időben eldönthető, hogy mikor melyiknek kell ott lenni, és ha rosszat használsz, a fordító rád is szól.
Btw: Java és C++ esetén nálam 4-es tab van, C-nél 8-as.
Stroustrup és ha jól emléxem Kerninghenék is csak 1 esetben javasolják a goto-t: többszörösen egymásbaágyazott ciklusból való kilépésre. Erre valóban nincs jobb megoldás, amíg nincs "break cimke" utasítás C(++) -ban (mint a Java-ban).
Ja még 1 eset: ha nagyon fontos a sebesség. Gondolom ezért van tele a Linux kernel is goto-kkal :).
