Most asszem találtam egy ilyet. Adott egy n számból álló bemenet. Erre számolunk valami ellenőrzőkódot ( mert az fontos dolog :) ). A polinomiális interpoláció nevű módszerrel találunk egy olyan f(x) polinomfüggvényt, ahol f(1) az első szám értékét adja, f(2) a másodikét és így tovább, viszont f(n+1)-re az ellenőrzőkódot. Ebben a polinomban n+1 darab együttható van, amiknek a birtokában tökéletesen visszaállítható az eredeti adat. Ezek közül a kimenetre kiírjuk az elsőt ( tehát x^n együtthatóját ). Maradt n számunk. Számoljunk erre is ellenőrzőkódot, és illesszünk ezekre is egy polinomfüggvényt, ahogy az eredeti adattal tettük! A keletkező n+1 együttható közül írjuk le az elsőt, és a maradék n számot és az ellenőrzőkódjukat megint írjuk le interpolációval, így egy végtelen rekurziót hozva létre, ahol minden lépésben kiírunk egy számot, azaz sosem lesz vége a kimenetnek ( se az algoritmusnak ).
Egy hasonló végtelen rekurziós algoritmus pedig vissza tudja állítani az eredeti adatot, ha ismert a végtelen hosszú kimenő sorozat összes eleme.
Lehet, hogy ez a gondolatmenet hibás, bizonyítani kéne még pár apróságot, de így összességében jónak tűnik. Valami vélemény? Esetleg egy egyszerűbb megoldás?
- Tibixe blogja
- A hozzászóláshoz be kell jelentkezni
- 1015 megtekintés
Hozzászólások
És hogy határozod meg az utolsó elemet, ha nincs utolsó elem? :)
Egyébként sokkal egyszerűbb, ha a bemenet 1. karakterét kiírod, majd cat /dev/zero. Majd a 2. karakter, majd újra /dev/zero. Persze értelme kevesebb van, de mennyivel egyszerűbb lekódolni. :)
- A hozzászóláshoz be kell jelentkezni
Nem kell utolsó elem, csak n-edik. Ahhoz meg elég, ha minden egészhez hozzárendelek valamit.
Azzal az a baj, hogy ( jórészt az érdekesség kedvéért ) a feltételekhez azt írtam, hogy nem az első n elem alapján nem szabad számolhatónak lennie az eredeti adatnak, hanem bármilyen véges részhalmaz alapján sem. Amit te írtál, abban van egy részhalmaz, ami PONT azokat az elemeket tartalmazza. Az más kérdés, hogy ezt a gyakorlatban nem lehet megtalálni, de mindig, törvényszerűen létezik.
- A hozzászóláshoz be kell jelentkezni
Aha, már értem. Csak ennyire elvontan kicsit nehezebb gondolkozi, de hát ez a matematika. :)
- A hozzászóláshoz be kell jelentkezni
Mondjuk így még egyszer végiggondolva nem biztos, hogy teljesen korrekt ez a feltétel, amit írtam.
Viszont ha jól értem, akkor amit írtál, az nem is szokásos sorozat, mert nem tudod az elemeket az egész számokkal indexelni.
Aztán ezt is még egyszer végiggondolva, a feltételem korrekt "szokásos" sorozatokra, csak az ilyen szörnyszülöttekre nem, mint amikor végtelenszer elszámolsz végtelenig.
( Tudnám szépen definiálni, hogy mit értek "szokásos" alatt, de most nem akarom azt a förtelmet a világra szabadítani )
- A hozzászóláshoz be kell jelentkezni
Ha nem feltétel, hogy a végtelen hosszú adat minden részét felhasználjuk a visszaállítás során, bármit hozzácsaphatsz.
Ha feltétel, hogy a végtelen hosszú adat minden része fel legyen használva, akkor újra kell gondolni, az ellenőrzőösszeg nem képezi részét az eredeti adatnak.
Hogyha félreértettem valamit, szólj...
addig megkeresem Sövény kollégát, majd ő megírja az algoritmust :)
upd: egy bármilyen algoritmus megfelel, amivel a tömörítvény csak egy kicsit is hosszabb, majd többször megnöveled, csak egy kicsikét, és így végtelen hosszú lesz...
- A hozzászóláshoz be kell jelentkezni
Az óra 51-kor írt hozzászólásom második felét hagyd figyelmen kívül, az nagyrészt hülyeség :) Az a lényeg, hogy véges sok (n, n-edik elem) pár ismeretében ne lehessen megcsinálni, végtelen sok ismeretében meg igen.
Természetesen nem kell mindent felhasználni ( pontosabban: az is felhasználás, ha nem csinálsz vele semmit )
Az, hogy valamit hozzácsapsz, azért nem jó, mert
a) Ha a végére raksz valamit, akkor veszed az elejét és megvan
b) Ha elé raksz valamit, akkor azt figyelmen kívül hagyod, ha meg végtelen, akkor nem lesz rendes sorozat
c) Ha közé raksz valamit, akkor az egyrészt az elé rakás, másrészt a mögé rakás, tehát az se nagyon zavar be
Amit én írtam, ott az ellenőrző kódot pedig itt olyan reménytelenül belekeveri a többi közé, hogy csak akkor lehet szétválasztani, ha már visszafejtetted.
- A hozzászóláshoz be kell jelentkezni
> Esetleg egy egyszerűbb megoldás?
Én az 1 = 0.9999... azonosságból indulnék ki. A tömörítendő adatsort egy 1-nél kisebb számértékként értelmezve, át lehetne alakítani olyanná, hogy végtelen sok jegyűvé váljon.
- A hozzászóláshoz be kell jelentkezni
Ilyesmire én is gondoltam, de ha mindig racionális szám a kimenet, akkor mindig ismétlődnek a jegyei. Ezért hiába lesz végtelen sok jegye, az első valahányból meghatározható az összes.
- A hozzászóláshoz be kell jelentkezni
> Ezért hiába lesz végtelen sok jegye, az első valahányból meghatározható az összes.
Nézzünk egy példát: '0.99999'. Ez egy végtelen sok jegyből álló szám "első valahány" jegye. Határozd meg az összest. :-)
- A hozzászóláshoz be kell jelentkezni
Röviden, tömören: igazad van.
- A hozzászóláshoz be kell jelentkezni
Tenyleg nem akarok moderatorkent viselkedni, de annyira szurja a szememet a cim. Tudod, a blogok cimei a fooldalon is megjelennek. Biztos, hogy premier planba kell mindenkinek elvezni a "sz*r" szot az oldalon, foleg a keresoknek?
--
Ki oda vagyik, hol szall a galamb, elszalasztja a kincset itt alant.
- A hozzászóláshoz be kell jelentkezni
Igaz, ez elkerülte a figyelmemet. Csak valaki így írta le, aztán őt szó szerint idéztem.
- A hozzászóláshoz be kell jelentkezni
koszonom.
--
()=() Ki oda vagyik,
('Y') hol szall a galamb
C . C elszalasztja a
()_() kincset itt alant.
- A hozzászóláshoz be kell jelentkezni
Csak epp az allitasrol nem esett szo: barmely veges reszsorozatabol nem allithato elo az eredeti adat. Nem azt kell latni hogy a modszerbol nem latszik semmilyen visszaallitas, hanem hogy nem allithato elo. En ugy erzem talatal egy modszert ami ugyan nem hibas, de nincs koze ahhoz amit bizonygatni szeretnel.
==
`Have some wine,' the March Hare said in an encouraging tone.
Alice looked all round the table, but there was nothing on it but tea.
- A hozzászóláshoz be kell jelentkezni
Ööö... jogos, erre nem tértem ki.
A polinomiális interpoláció tulajdonságaiból következik pár dolog, köztük:
1. Ha ismered a függvényt ( tehát az együtthatókat ), és azt, hogy milyen pontokon kell alkalmazni, akkor ebből megvannak az adatok. Ha akár egy ismeretlen együttható is van, akkor nem tudod az adatokat.
2. Egy adatsorozatra csak egy polinomfüggvény illeszthető ( megadott pontokon ) Ha hiányzik egy adat a sorozatból, akkor semmit sem tudsz a polinomfüggvényről.
3. Mivel semmi más adatot nem szolgáltatunk, mint a polinomfüggvények együtthatói, nem számolhatók ki máshonnan a keresett adatok.
Tehát, ha a kiértékelések helyeit előre eldöntöttük ( most az egészek 1-től n-ig ), akkor a kettő ismerete ekvivalens.
Így valami olyanunk van, hogy
bemenet ismerete == első polinomfüggvény ismerete == leírt szám és második polinomfüggvény ismerete == második leírt szám és harmadik polinomfüggvény ismerete == ...
Mivel ez a végtelenségig megy, végtelen sok együtthatót kell ismerned. Véges sok együtthatóból így tényleg nem tudod kiszámolni.
Egyébként megkérdeztem valakit, kb. elsőre adott egy SOKKAL szebb és egyszerűbb megoldást: alakítsuk az adatokat polinommá, ahogy fent, és adjuk meg az értékét a -1, -2, -3 ... helyeken. Ha végtelen sok helyen ismerjük egy polinom értékét, akkor ismerjük a polinomot ( ha létezik, de most létezik, mert az volt a kiindulás ), de ha csak véges sok helyen, akkor még nem egyértelmű. Ennek mondjuk az a hátránya, hogy ha már a tízmilliomodik számot vizsgálod meg, és az összes illeszkedik egy 4200 fokú polinomra, akkor erősen gyanakszol arra, hogy az alapján generálták, még ha matematikailag nem is biztos.
- A hozzászóláshoz be kell jelentkezni
azert durva, hogy a semmit mennyire korbe tudod jarni (gyk: nulla informaciot tartalmaznak a bejegyzeseit, inkabb ~trivialitasokat)
nem gondolkoztal meg a konyvirason? ;P
- A hozzászóláshoz be kell jelentkezni
Matematika. Ha nem járod körbe a triviálisnak látszó dolgokat háromszor, akkor nagyon el lehet csúszni, lásd a fenti tévedéseimet :)
- A hozzászóláshoz be kell jelentkezni
az egyik oldalam matematikusnak probaljak kepezni, tobb kevesebb sikerrel, szoval tudom mirol karattyolsz :)
- A hozzászóláshoz be kell jelentkezni
while (1){} egyenerteku.
Ha nincs tisztesegesen definialt vegallapot, akkor ez nem egy tisztesseges algoritmus.
- A hozzászóláshoz be kell jelentkezni