Fórum: Algoritmusok

Igazad van Alma, úgy gondolom a kései időpontban én néztem el.

Az ötletem csak akkor lenne életképes a gyakorlatban, ha létezne egy olyan algoritmus, ami nagy számokról képes lenne gyorsan megállapítani, hogy egy tetszőleges (prím)szám alapú számrendszerbe átírva 0-ra végződne-e, vagy sem.

100 000 nem osztható 4951-gyel, mint ahogy 100 sem osztható 3-mal. Szerintem gondold végig még egyszer, bár lehet, hogy eme kései órában én nézek el valamit csúnyán.

Pl: 2003 osztható 3mal?

Úgy gondolom, sikerült egy lépést tennem abban az irányban, hogyan lehetne nagy számokat gyorsan, hatékonyan faktorizálni, viszonylag olcsó számítógépeken.

(Tudom, lehet hogy sikamlós terep ez, de a bankok és a titkosszolgálatok majd-csak találnak más módszereket, ha netalán annyira nagy törzsszám-szorzatokra is hatékony lenne az ötlet, amilyeneket ők használnak.)

1. Abból indulok ki, hogy a törzstényezős fölbontás egy olyan oszthatósági probléma, ahol a prímszámokkal való oszthatóságot vizsgáljuk.

2. De hogyan lehet rájönni gyorsan, hogy egy nagy szám osztható-e maradék nélkül például: 4951-el?

Például úgy, hogy a tízes számrendszerben fölírt szám utolsó 5 számjegyét átírjuk 4951-es számrendszerbe, és ha így 0-ra végződik akkor nyilván oszható 4951-el, ha nem, akkor nem osztható, és akkor nem is kell a nagy számot elosztani 4951-el, és ezzel rengeteg időt lehet megtakarítani.

3. Algoritmus terv-vázlat, és a számítógép fölépítésének vázlata: Ha a faktorizálandó szám páros, akkor a gép elkezdi osztani 2-vel, és ezt addig folytatja, amíg páratlan számot nem kap eredményül (ha a faktorizálandó szám páratlan ez a lépés értelemszerűen kimarad).

A(z egyik) processzor elkezdi kiszámítani a páratlan szám négyzetgyökét.

A gépben van egy gyors ROM szilárdttest memória, rajta szép sorban a prímszámok, 3-tól amennyi csak ráfér.

A (másik) processzor átszámítja a szám utolsó két számjegyét 3-as számrendszerbe, és ha 0-ra végződő számot kap akkor el is végzi az osztást 3-mal.

Ha nem 0-ra végződő számot kap, akkor meghívja a ROM-ból a következő törzsszámot az 5-öt és azzal osztja el a faktorizálandó szám 5-ös számrendszerbe átszámolt utolsó két 10-es számrendszerbeli számjegyét. (Ez egyébként az a kivétel, ahol lehetne azt is vizsgálni, hogy 10-es számrendszerben írva 0-ra, vagy 5-re végződik-e, de valószínűleg összességében nem lenne gyorsabb a program ha beleírnánk ezt a kivételt, sőt..)

Azt hiszem, a folytatást mindenki könnyen el tudja képzelni, aki ért a számítástechnikához, az ötlet lényege egyébként sem a számítástechnikai megoldásban van, ezt a leírást csak gondolat-ébresztőnek szántam, gyakorlott programírók valószínűleg csak mosolyognak rajta.

Talán még csak annyit, hogy ha a ROM kifogyna a prímszámokból akkor kicsit lassulunk, néhány processzort be kell fogni, hogy szépen sorban szoftveresen szolgáltassák a továbi prímszámokat.

Köszönöm a választ Róbert Gida.

85 jegyű számokat lehet 1 óra alatt faktorizálni egy mai átlagos 2 GHz-es gépen, 1 magon.

Elnézést kérek ha nem a megfelelő fórumhba írok, sajnos tapasztalatlan vagyok számítástechnikában.

A kérdésem:

Tételezzük föl, hogy bemegyek egy átlagos magyar számítástechnikai üzletbe, és veszek egy átlagos képességű PC-t.

Installálok rá egy olyan programot ami (nagy) számok törzstényezős fölbontását végzi el.

Maximium hány jegyű számok törzstényezős fölbontására számíthatok üzembiztosan, ha egy számra kb 1-2 óra üzemidőt szánhatok?

Nem az Eternity II.-re gondoltál? Az 16x16-os és 2 millió dollárt ér egy helyes kirakása, szerintem reménytelen. Hasonló, mint a gubanc, itt is parkettázni kell.

Üdv!

Egy fórumon olvastam, hogy egy algoritmus, ami a 15*15-ös Rubik gubanc-ot belátható időn belül kirakja, 1 millió dollárt ér. Ez igaz?

Olvasd el ezt. Nem hiszem, hogy beférne a tartalma egy hozzászólásba. :)

hellosztok sajnos az a helyzet van, hogy mindenhez értek egy kicsit a matekon belül (naggyából) de az algoritmusokhoz kuka vagyok. ha lenne valaki olyan kedves, hogy egy kicsit részletesen elmagyarázná örök hálám adnám neki. előre is nagyon-nagyon-nagyon köszönöm.

nem, hanem már elkészítettem. Csak akkor vmi kezdőötlet kellett, de már megvan.

Hopp, ez a prog.hu-ról van. 2000x2000-es a maximális mátrix mérete, k2*n. Nem jutottál be a második fordulóba? Vagy mi történt?

A feladat már tárgytalan...

Sziasztok! Lenne egy elég nehéz feladatom,amit nem tudok jelenleg elkezdeni sem:( Megköszönném ha segítenétek. Csak annyit szeretnék kérni hogy segítsetek az elindulásban. Íme a feladat:

Adott egy N×N-es négyzet (mátrix). A kis négyzetek egy számot tartalmaznak, az értéküket. Lépni a szomszédos négyzetekre léphetünk (jobbra,balra,fel,le). A feladat a következő: Keressünk maximális értékű k hosszúságú körutat, mégpedig úgy hogy minden tag (kis négyzet) csak egyszer szerepel (kivéve persze a kezdőpontot, ami egyben a végpont is)! A feladat nehézsége nem N és k értékétől nehéz. (A négyzetünk kb 100*100-as, az út pedig mondjuk 30 hosszú.)

Köszönök előre is minden segítséget, ha nem értetek valamit írjatok. köszi.

Sajnos jelenleg nem tudok neked [feltételt]-t konstruálni. Amit leírtam az a leghosszabb vektorösszegre vonatkozik, de nem tudom garantálni, nem látom, hogy bármely részvektortól kezdve ezzel a módszerrel el lehet-e jutni a leghosszabbhoz. Gyanítom, hogy ha az eredő nem nullvektor és nagysága egy nagyságrendel marad csak el a leghosszabbétól, akkor szerkeszthető jó induló feltétel.

Csakhogy a jó eljárásnak le kell tudni kezelnie a nullvektoros eredőjű kiosztást is.

Igazad van, megint rossz irányban implementáltam! :)

A [79]-ben vázolt kilépési feltétel formális kontextusa a következő:

ha [feltétel], akkor keresés vége, egyébként A legyen A+K

ahol A az aktuális összeg, K a következő "tagjelölt". [79] esetében pedig [feltétel]: E*(A+K)<0, ahol E az összeg első tagja (tehát az a vektor, amelyikhez a "jelöltet" keressük). Kérlek, írd le, hogy [80] alapján mi a konstruálható [feltétel]! Újra átgondolva szerintem [feltétel]: E^2>(A+K)^2 vagy (E-(A+K))^2>(A+K)^2, de ezzel meg az 1:(1,0), 2:(2,0), 3:(0,1), 4:(-1,-3) bemenet tol ki. :)

Az 5. pont nincs benne és M(1,9) a jó megoldás, szerintem.

Ez sajnos a [79]-es kontextusaban nem alkalmazhato, neha tul hamar kilepne.

(Peldaul ha a vektorok irany szerint rendezve 1:(3,1), 2:(4,4), 3:(-3,2), 4:(-3,2), 5:(-1,0), akkor a legtavolabbi pont (1,9), az elso vektor jeloltjei kozott lenne, de a targyalt kilepesi feltetel miatt nem talalnank meg.)

Néhány (további) megállapítás:

Az nyilvánvaló, hogy a vektorokat bármilyen sorrendben is illesztem egymás után, az eredőt adja ki, azaz az eredő a végpont. Két csoportba osztom a vektorok összeadását. Először keresem és feltételesen ismerem a leghosszabb összegvektort, így az első csoportba ezeket adom hozzá, majd a maradékot. Így a vektorsornak elvileg át kell haladnia a feltételezett legmesszebbi ponton. E három pontot (Kezdő, legMesszebb, Vég) nevezzük sarokpontoknak.

Mindhárom szakaszra (K-M, M-V, --> K-M-V) igaz, hogy a szakasz vektorait bármilyen sorrendbe is adom össze, a lencsén belül kell maradnia. Ha kilép, hibás volt az M pont, ha a vonalat nem csak az M pontban érint, több megoldás létezik, ha létezhet.

Eddig még nem írtam le, de az ábrából nyilvánvalóan leolvasható, ha kilép, akkor ez a kinti pont vagy K-tól vagy M-től messzebb van, mint a feltételezett legmesszebbi távolság.

Sőt. Az eredő vektornak is a rajz szerinti 'lencsébe' kell mutatnia!

Nemcsak derékszögnél jobban nem térhet ki, hanem szigorúbb feltétel is szükséges. A leghosszabb összegvektor két végpontjára ráhúzott köríven sem mehetnek ki a részvektorok.

Habár nem tudom, hogy ennek kihasználása növeli-e a leghosszabb összegvektor megtalálásának sebességét.

A [70]-ben leírtakon annyit "csiszol" a [66]-os ötlete, hogy nem akkor hagyjuk abba egy vektorhoz a "jelölt" keresését, amikor a következő tag az elsőtől 180 foknál jobban kitérne, hanem amikor a következő taggal bővített összeg az első tagtól 90 foknál jobban kitérne.

Megnéztem újra, és mégis jó a [66]-ban felvetett kilépési feltétel, csak rosszul implementáltam. Az "OP_maxsq" nevű függvény "if(ns*varr[k]<0) break;" sorában a "k"-t "i"-re kell javítani, hogy működjön. :)

Hali szerintem a [70] es jó megoldás és is egy hasonlót gondoltam ki, és egyenlőre nem találtam még rá ellenpéldát.

Forráskód