Algoritmusok

Gyors logaritmus fixpontos aritmetikával

Fórumok

Sziasztok!

Egész számoknak keresem a logaritmusát és mivel kernelben működne a program ezért nem használhatok lebegőpontos számokat. Van pl. egy 1 és 100e9 közötti tartomány, ezt szeretném logaritmussal leképezni egy kettő hatvány méretű területre. Teszem azt 10 bitem van, legnagyobb értékem az 1024, ez lenne a 100e9 és a hozzá közel eső számok. Az ehhez tartozó logaritmus a 1.025 alapú, mert ha x^1024 = 100e9 akkor x ~ 1.025. Mivel x bármilyen értéket felvehet 1 és 100e9 között én az ehhez legközelebbi logaritmus értéket keresem.

A jelenlegi megoldásom úgy néz ki, hogy előre kigenerálom az értékeket egy táblázatba, az első ezer számra ez így néz ki:
x : log_1.025(x)
1   : 0
2   : 28
3   : 44
4   : 56
....
912-934: 276
935-957: 277
958-981: 278
982-1000: 279

És ebben a táblázatban max 10 lépésben csinálok bináris keresést x-re és a kapott index lesz a logaritmus.

A kérdésem: lehetne-e ezt elegánsabban? Tudnátok-e mondani valami olyan módszert, amivel esetleg megspórolom a táblázatot meg a bináris keresést és képes lennék "egy lépésben" mondani x-hez egy log_1.025(x)-et? Szerencsére minden ismert fordítási időben x-et leszámítva, tehát megvan mi a legkisebb és legnagyobb x, megvan hogy hány bitre kell leképezni és milyen alapú logaritmussal.

Előre is köszönöm az ötleteket.

EOV to WGS84

Fórumok

Sziasztok,

 

Azzal a kihívással találkoztam, hogy EOVX és EOVY koordinátákat kellene átszámolnom GPS lon és lat formátumokra.

Találtam online átszámítókat, de maga a képlet nincs meg. Szeretnék írni egy kis programot, ami egy csv fájlt alakít át lokálisan.

Nézegettem pár szakdolgozatban, ami elérhető online, de sajnos nem találtam meg a képletet.

Köszi a segítséget előre is.

 

Itt tartok:

 

using System;


namespace GPS_transformer
{
    class Position
    {
        public DateTime timeStamp { get; private set; }
        public string address { get; private set; }
        public int eovx { get; private set; }
        public int eovy { get; private set; }

        public double longitude { get; private set; }

        public double latitude { get; private set; }

        public Position(DateTime timeStamp, string address, int eovx, int eovy)
        {
            this.timeStamp = timeStamp;
            this.address = address;
            this.eovx = eovx;
            this.eovy = eovy;
            this.EOV_to_GPS84();
        }

        private void EOV_to_GPS84()
        {
            //longitude = 47;
            //latitude = 19;
        }
    }
}

Üdv,

 

Zoli

algoritmust keresek - létezik-e - átlag számítás csak utolsó érték megtartásával

Fórumok

(Valószínűleg borzalmasan fogalmazok, terminológia szempontjából kövezzetek meg :) . )

Adott x db szám, és szeretnék egy átlagot (számtani közepet), anélkül, hogy tárolnom kellene az adatgyűjtés végéig az összes számot. Kevés matematikai tudásom alapján megoldhatónak tűnt, rosszul megfogalmazva: csak az átlagot tárolom, és az új adattal annak számolom ki az átlagát, és azt tárolom tovább. Így mindig csak egy számot kell tárolnom.

Próbáltam gyorsan egy egyszerű tesztet csinálni, lehet az jobban érthető egyeseknek, összehasonlítottam a két algoritmust, nem ugyan az az eredmény jön ki, de egymáshoz "nagyjából" közeli.

Kérdések: van-e ilyen algoritmus, és jó irányba próbálkoztam?

- - - - -

$nums = array();

for ($i = 0; $i < 100; $i++){
    $nums[] = rand(0,1000);
}

$sum = 0;
foreach ($nums as $num){
    $sum += $num;
}
$avg = $sum / count($nums);
unset($sum);
var_dump($avg);
unset($avg);

$first = 1;
foreach ($nums as $num){
    if ($first){
        $avg = $num;
        $first = 0;
    } else {
        $avg = ( $avg + $num ) / 2 ;
    }
}
var_dump($avg);

Raktér feltöltés optimalizációja

Fórumok

Van egy probléma, amit régóta próbálok megoldani. Nem létkérdés, a régi ELITE számítógépes játékból ered, abból "absztraháltam".

Szóval: adott egy áru lista kellően sok elemmel. Minden áruról tudjuk a térfogatát és az értékét. Szeretnénk egy rakteret úgy feltölteni, hogy a lehető legnagyobb értékű áru kerüljön a raktérbe.

Kicsit konkretizálva: Adott egy 100 egység méretű raktér. Adott egy 100 elemű áru lista, kb ilyesmi:

Áru Térfogat Érték
Áru 1 15 1414.3851
Áru 2 80 7613.9906
Áru 3 70 6981.7767
Áru 4 65 6772.0219
Áru 5 100 10339.2598
Áru 6 65 6498.7702

Tehát vannak áru típusok, amik egyedül is kitöltik az egész rakteret (pl Áru 5), de ha kisebb árut pakolok be, akkor több dolgot is be tudok rakni (pl Áru 1 + Áru 3).

Olvasgattam a témában, és találtam egy csomó cikket konténer feltöltés optimalizációra, de nekem azok túl bonyolultak, pl én nem szeretnék az egyes áruk alakjával foglalkozni, meg hogy miket lehet egymásra rakni, stb.

Két úttal próbálkoztam: Először arra gondoltam, hogy meghatározom, maximum hány áru fér be a listáról a raktérbe. Erre találtam egy gyors és egyszerű algoritmust. Az volt a tervem, hogy legenerálom ezzel a maximális mérettel az összes lehetséges al-listát, és kiválasztom a legnagyobb értékűt, de rájöttem, hogy 100 elemű kiindulási listával és pl 10-13 maximális áruszámmal a lehetséges listák száma túl nagy, nem végeznék valós időben.

Ezután nagyfiam javaslatára megpróbáltam egy rekurziós megoldást: legeneráltam az áruk fajlagos értékét (érték/térfogat), ez alapján sorba rendeztem az árukat. Vettem az első elemet (a legnagyobb fajlagos értékű árut), ami még befér a raktérbe, és beraktam a listába. Megnéztem, mennyi szabad raktér maradt, és ha az több, mint a legkisebb térfogatú áru, akkor a maradék raktér mérettel loopoltam a rekurziós függvényt. Szemléltetve: Lett egy új oszlop a táblázatomban fajlagos érték néven: érték/térfogat. TFH a legnagyobb fajlagos értékű áru térfogata 70, ezt berakom a listámba. Maradt 30 méretű raktér, az eredeti árulistámon 5 a legkisebb méretű áru, tehát loop. Kidobok mindent , ami nagyobb mint 30 (hiszen úgyse férnének már be), és megint veszem a legnagyobb fajlagos méretű árut, és hozzáadom a listához. Mondjuk a térfogata 25, tehát maradt még ö méretű rakterem, tehát loop.

Ezzel a megoldással az a bajom, hogy nem látom be, hogy valóban a legjobb értékű árulistát generálja nekem. Cserébe elég gyorsan végez, és legalább valamilyen listát generál.

Tudnátok adni fogozókat, hogy jó irányban indultam e el, esetleg hogyan lehetne ellenőrizni, hogy a rekurziós megoldás mennyire jó, vagy van e értelmes alternatíva? Érdekelne heurisztikus megoldás is, de ott megint elakadtam olyanokon, hogy generáljak pl max 3 elemű allistákat, aminek az össztérfogata 100. (Ha tudnék ilyet, akkor esetleg meg tudnám saccolni az értékösszeg eloszlását, hogy lássam, mennyire jó a rekurziós megoldásból kapott lista.)

Bármi kommentet megköszönök.

Hányszor szerepel(nek) a listában

Fórumok

Nem vágom az értelmes elnevezését a problémának, de:

- van 1 csomó szatyrom, amiben amúgy egyforma színes golyók vannak, változó számban, de 1 zacskóban bármely színből max. 1,

- Legyen mondjuk a 3,

- Melyik az a 3 (vagy valamennyi) szín, ami legtöbbször szerepel együtt a szatyrokban?

Olyasmi, mintha azt kérdezném, melyik az a 2-3-4 lottószám, melyeket legtöbbször sorsoltak ki együtt.

 

Illetve valami graphDB-vel lehet-e ilyesmi feladatot egyszerűen megoldani

Regex pattern kitalálóka

Fórumok

Párszor már beleakadtam ebbe a problémába, de most nagyon jó lenne 1 ilyen tool: Van 1 csomó string-em, amire meg kéne találni azt a regex pattern-t ami a lehető legszigorúbb és minden megadott stringre illeszkedik. Van erre kész megoldás, illetve hogy kéne nekiállni?

Igazából az a feladat, hogy:

  • a lista 1 része meccsel regex1-re,
  • a lista másik része meccsel regex2-re,
  • Kéne egy 3-ik regex, amire a maradék meccsel,
  • illetve a maradékból menyi az, amire regex3 mégsem meccsel.

Mondjuk úgy, hogy a nem well-formed stringeket kéne megtalálni és ez tényleg az a 2 legyen a nagyonsokból, amit biztosan javítani kell kézzel.

Ötlet, tipp, bármi?

Apropó LenstraLenstraLovász aka LLL: Abel díj Lovász Lászlónak

Fórumok

A Norvég Tudományos Akadémia 2021-ben az Abel-díjat Lovász Lászlónak, a budapesti Eötvös Loránd Tudományegyetem professor emeritusának, a Rényi Alfréd Matematikai Kutatóintézet (ELKH, MTA Kiváló Kutatóhely) kutatóprofesszorának és Avi Wigdersonnak, a princetoni Fejlett Tanulmányok Intézete (USA) munkatársának ítéli oda „meghatározó jelentőségű munkásságukért az elméleti számítógép-tudomány és a diszkrét matematika terén és szerepükért abban, hogy ezek a modern matematika központi területeivé válhattak”.

A számítógép-tudományt megalapozó munkája mellett Lovász László széles körben alkalmazható, hatékony algoritmusokat is kidolgozott. Ezek egyike a róla, valamint az Arjen Lenstra és Hendrik Lenstra testvérpárról elnevezett LLL-algoritmus, mely fogalmi áttörést jelentett a rácsok megértésében, amelyek figyelemre méltóan jól alkalmazhatók többek között a számelmélet, a kriptográfia és a mobil számítástechnika területén. A jelenleg ismert titkosítási rendszerek, amelyek képesek ellenállni egy kvantumszámítógép támadásának, az LLL-algoritmuson alapulnak.

Részletek

Generációs probléma

Fórumok

Sziasztok, egy kicsit programozós kérdés is (inkább algoritmus).

Van 1000 férfi és 1000 nő. Ezek összeházasodnak, minden családban lesz 2 gyermek, 1 fiú és 1 lány. Ezek utána tovább házasodnak. Feltesszük, hogy nem a családon belül veszik el a másikat.

Szerk: Minden párnak mindenkoron 1 fiú és 1 lány utóda van aki egészséges, a másik nemhez vonzódik.

Kérdés: hanyadik generáció múlva lesz mindenképpen az, hogy a "tágabb" családon belül fognak házasodni?

Építsünk virtuális gépet?

Fórumok

Észrevettem, hogy jobbára amatőr fejlesztői körökben a compilereket, fordító-programokat kisebb fajta misztikum övezi. Feltételezem a beléjük képzelt bonyolultságuk, "áttekinthetetlenségük" okán. A nyelvek közül az assembly is hasonlóképpen túl van misztifikálva.

Arra gondoltam, hogy ezt a helyzetet oldhatnám, ha lépésről-lépésre bemutatnám egy szimpla, végletesen redukált utasításkészletű virtuális processzor [VCPU] felépítését. Még hozzá, a tervezés lépéseitől a megvalósításig, valamint egy, a VCPU-hoz tartozó nagyon egyszerű assemblert, szintén annak tervezésétől a megvalósításáig, néhány lépésben.

Maga a VCPU roppant egyszerű (kb. 300 sor kód), mindössze tíz utasítást lenne képes végrehajtani. Ezek elsajátítása gondolom nem okoz különösebb nehézséget azok számára, akik érdeklődnek efféle dolgok iránt. Az egész "virtualizáció" tulajdonképpen alig lenne több egy CASE utasításnál. Az assembler is a végletekig egyszerűsített, bár valamivel összetettebb lenne mint a VCPU, de ez is alig 3-400 sornyi kód, 10-12 függvény, ami bemutatná azokat a fázisokat, amelyen keresztülmegy a bemenet, a forrás, amíg végül futtatható binárissá nem lényegül.

Ha van a dologra érdeklődő, akkor szívesen megírom a körítést, a magyarázó szöveget és publikálom is a forrással együtt, mert maga a VCPU és annak assemblere már évek óta készen van.

Értőbbek számára:
A VCPU egy munkaregiszteres /ez az ACCU, és mindössze 8 bit széles/.
A VCPU-hoz kapcsolódó memória maximum 256 byte. Címzésmódja lineáris.
Aritmetikai utasítások operandusai: az ACCU és egy memóriacím tartalma. Az eredmény mindig az ACCU-ban tárolódik.
A VCPU (a maga korlátain belül (memória mérete)) turing teljes. 
Használata: A VCPU az assemblált "binárist" beolvassa a memóriába, majd rákerül adott címre [org] a vezérlés. A program lefut, minden CPU állapot és memóriatartalom formázottan, szekvenciálisan egy kimeneti file-ba (.html) íródik. Ezt a file-t lehet analizálni.

[Igaz, van egy interaktív megvalósítás is, lépésenkénti programvégrehajtással, backstep lehetőséggel, stb. de oktatási célokra a .html-es verzió szvsz alkalmasabb]  

Szóval?
Vélemények, hozzáfűzni valók, javaslatok, ellenvélemények, kérdések?
Minden kommentet szivesen fogadok, ha  tartalmilag érdemes, akkor hasznosítom. 
Köszönöm előre is. 

Programozható robot gyerekeknek

Fórumok

Sziasztok!

Van tapasztalatotok a jelenleg kapható, gyerekeknek szánt programozható robotokkal?

8 éves gyerek számára gondolkozom programozható roboton. Az alábbi lego például nekem tetszik:
https://www.lego.com/hu-hu/product/boost-creative-toolbox-17101

Ugyanakkor azt gondolom, hogy egy egyszerű tabletes vagy pc-s programozós játék több lehetőséget rejt.

Ti mit gondoltok?
A kézzel megfogható robot jobb kapudrog lehet a programozás felé, mint egy alkalmazás?
Esetleg van konkrét robototok, ami beváltotta a hozzá fűzött reményeket?