Vicces bug túlcsordulással int c
Jó napot, kedves olvasók. Ma elmondom neked, hogy milyen mankóval jöttem létre, egy kis programot fejlesztettem ki a C ++-ban.
Az összeolvasztás előadásáról szóló előadás után. Érdekes feladatot vártam. Hadd idézzem a probléma szövegét, remélem senki nem tiltakozik.
Az első beviteli vonal tartalmazza az n számot (1 ≤ n ≤ 100000), a második pedig az A000000000000 számú természetes számot tartalmazó A [1 ... n] tömböt. Meg kell számolni az 1 ≤ i A [j] indexpárok számát.
Nagyjából elmondható, hogy meg kell találnunk az inversions számát a tömbben. A naiv végrehajtás nagyon egyszerű. Hasonlítsa össze a tömb összes számpárt, számolja be az inversions számát. A-la, így:
Ez a kód talán jó. Érthető bárki számára. Még a junior is. De van egy probléma. Az algoritmus ilyen megvalósításában az idő-aszimptotikus O (n * n).
Természetesen az algoritmusokra és az adatstruktúrákra szánt kurzus természetesen nem járt el (a teszt időben meghibásodott). Olyan algoritmusra van szükségünk, amely legalább O (n * log (n)) -ot működtet.
Mióta átfutottam az összeolvasztásról szóló előadást, azt gondoltam, hogy valamilyen módon részt vesz ebben. És az igazság az, hogy van egy standard algoritmus az O (n * log (n)) tömbben lévő inversions számának megtalálásához.
Tétovázás nélkül megtaláltam az algoritmus leírását és megvalósítottam C ++-ban. A kódot az automatikus ellenőrzésre dobom a webhelyen - a kód elesik. Érvénytelen megoldás a 6. adatkészlethez.
Önmagában nincs kétségem, ezért azonnal gondoltam, hogy a hiba valahol a kódomban. Azonban ez nem feltétlenül szörnyű: végül is a zsebemben már naiv módon végrehajtottam a problémát, így gyorsan megtalálhatom a problémát.
Egyszerű generátort írok, amely véletlen sorozatokat generál. Mindegyiküknél kétszer fordított számot fordítok: egy naiv algoritmust és egy algoritmust használok a merge sorting használatával.
Én 1000 iterációt kezdek, én iszom teát. Jöttem - látom, hogy minden teszt sikeresen megtörtént. Itt már én is zavartan voltam: nehezen hibázik a naiv megvalósításban, de kiderül, hogy még mindig hibáztam a normális végrehajtásban.
Elmentem a Google-ba, keressem az algoritmus meglévő implementációit. Úgy tűnik, ez a feladat nagyon gyakori az algoritmusok során. Megtaláltam legalább öt különböző megvalósítást, hogy megkeressem az inversions számát a tömbben. Érdemes megjegyezni, hogy mindegyikük a 6. adatkészletre esett.
Már gondoltam, hogy hiba történt a tesztben. Megírtam a tanfolyam alkotóit, megtanultam, hogy a hiba az oldalamon áll: vannak emberek, akik megoldották ezt a problémát.
Ekkor voltam zavarban, hogy mit tegyek. A naiv megvalósítás rendkívül egyszerű, hiba elkövetése érdekében. Nincs a teszt bemenete: nem is tudom kiderülni, hogy megtalálja a hibát.
És akkor felkeltette rám: talán az oroszok írnak valamit erről (régen csak angolul kerestem információt). Kiderül, hogy van néhány információ a VT-ben.
Kétszer gondolkoztam kétszer, teszteld ezt a tesztet. És mit látok? Negatív válasz (ez nyilvánvalóan abszurd). És akkor megértem az összes ostobaságomat. Számoltam az inversions számát, és hozzáadtam az eredményt int-hoz.
Miért ez a ostobaság? Az inversziók maximális száma eléri, amikor a bemeneti tömb sorrendben sorrendben van rendezve. Ebben az esetben az inversions száma 100,000 * 99999/2 = 4,999,950,000 - közel 5 milliárd. És az int 2,147,483,647-nek van. Itt van itt a baj.
Saját hibám volt, hogy nem gondoltam azonnal az eredményre. Nem is gondoltam a túlcsordulás lehetőségére. Végtére is, az adatokat, amelyekre teszteltem, az ilyen problémák még nem voltak közeliek. Mint mondják, minden lehetséges bemeneti adaton meg kell vizsgálnia a programot.
Az oszlop további bejegyzései: