Aki profi kombinatorikából, segítene?

1.) jelölje A0 azoknak a 10 jegyû számoknak a halmazát, amiben NEM szerepel a 0 számjegy. Az A1 meg A2 hasonlóan jelölje az 1et ill. 2t NEM tartalmazó 10jegyû számok halmazát.

Téged ennek a háromnak uniójának a mérete érdekel, hiszen ha az tartalmazza a rossz esteteket, és ha azt levonnod az összes esetbôl (tehát hogy hány 10jegyû szám van), akkor megkapod a jó esetek számát.

Az A0, A1, A2 uniójának méretét meg könnyen ki lehet fejezni az A0, A1, A2 és ezek metszeteinek méretével. Mivel ezeket mind elég könnyen ki lehet számolni, így ezzel kész is vagy.

A #2 válasz a jó, de nem mondanám, hogy "ezeket mind elég könnyen ki lehet számolni"... jó munkás dolog lenne.

A második rész pedig még bonyolultabb.

Mondj már többet a feladatról. Nem programozáshoz adták fel? Program gyorsan és viszonylag egyszerűen ki tudja számolni mindkettőt.

"A #2 válasz a jó, de nem mondanám, hogy "ezeket mind elég könnyen ki lehet számolni"... jó munkás dolog lenne"

Azért azt nem olyan nehéz kiszámolni azt, hogy pl. vajon hány olyan 10jegyû szám van, amiben nem szerepel az 1 és 0 (ami az A0 és A1 metszete)...

Összesen 7 ilyet kell kiszámolni (A0, A1, A2, bármely kettô metszete, mindhárom metszete), és ezek közül is csomó ugyanúgy számolódik => ha az ember lassabban pötyögi a számológépet, akkor eltarthat talán 3 percig is ezek kiszámolása.

Ezeknek a megfelelô összekombinálása, hogy megkapjuk az (A0 unió A1 unió A2) méretét, az 6 darab összeadás / kivonás => közepesen súlyos köszvénnyel akár újabb 3 percig is eltart ennek a 7 számnak és 6 mûveleti jelnek a bepötyögése.

Ezután kiérdemeltünk egy 1perces pihenôt, ami alatt kifújhatjuk magunkat, majd még 3 perc alatt kiszámoljuk, hogy vajon hány 10 jegyû szám van, és az utolsó másodpercekben egy erôs hajrával még ebbôl kivonjuk a korábban kiszámolt rossz esetek számát.

Ez összesen 10 perc így, kávészünet és köszvény nélkül 5 alatt is simán megvan.

Rendben, igazad van, könnyű kiszámolni... de azért munkás.

[link]

A program kiszámolta ezt is, meg a második részt is; ezt írta ki a végén:

Összesen 9000000000 tízjegyű szám van.

Ebből 2119020270 számban van 0, 1 és 2 is,

és 299475 számban 3 egymást követő számjegy összege max 9.

Csak ellenőrzésképpen írtam, ha valaki rájönne, hogy kombinatorikával hogyan kell a második részt kiszámolni.

Igazad van... szégyellem, hogy nem csináltam egy ilyesmi nagyságrendi ellenőrzést.

Volt egy elírás a programban, 9 helyett 0 került bele sajnos az egyik feltételbe...

A javított program ezt írja:

Összesen 9000000000 tízjegyű szám van.

Ebből 2119020270 számban van 0, 1 és 2 is,

és 21838806 számban 3 egymást követő számjegy összege max 9.

> A másodikra is kellene valamilyen képlet, vagy algoritmus, ami esetleg 15, 20 számjegy esetén is működik

Oszd meg és uralkodj algoritmussal kijön több is.

Alap:

Mondjuk 10 jegyűig egész gyorsan ki lehet számolni a jók számát. Kis módosítás kell: nem csak egy eredményt kell számolni, hanem azt is, hogy a,b kezdettel és c,d végződéssel hány 10-jegyű jó szám van; a,b,c,d = {0-9}. Ez összesen 10000 adat, nem túl sok.

Ezekkel aztán hosszabb számokat is fel lehet dolgozni: egymás mellé rakjuk a 10 jegyűeket és az illesztéseket az a,b,c,d alapján kezeljük. Viszonylag egyszerű backtrack-es algoritmus lesz. 40 jegyű számot még belátható időn belül lehet vele kezelni.

(Persze kell hozzá nagyjából 140 bites aritmetika is az összegzéshez...)

Igazi oszd meg és uralkodj:

Ha megvan n jegyű számmal a 10000 adat, összeillesztünk két ilyet a lehetséges módokon, és lesz 2n jegyű számhoz 10000 adatunk. Aztán ugyanígy 4n, 8n, stb. hosszak is kijönnek. 80 jegyű számot még belátható időn belül lehet így kezelni szerintem.