Intelektuāls jautājums LVIII jeb veram krelles
Iepriekšējās nedēļas uzdevums parādīja, ka tomēr ir problēmas ar rēķināšanu, ja uzdevumā tiek iekļauti lodveidīgi ķermeņi. Tādēļ šoreiz nolēmu, ka ir pats laiks savērt krelles.
Iedomāsimies, ka mums ir divu krāsu bumbiņas – baltas un melnas. Mums ir arī diegs. Par krelli mēs uzskatām sekojošu veidojumu – viens diegs, kas veido noslēgtu apli un uz kura savērts noteikts skaits ar bumbiņām. Nu tā kā augšā uz bildītes (ģenerēts ar MS Paint).
Un tagad pats jautājums. Cik dažādas krelles var izgatavot, izmantojot 5, 7 un 11 bumbiņas? Mans piemērs augšā ilustrē gadījumu, ja krelles ver izmantojot 3 bumbiņas, man sanāca 4 dažādas krelles.
Comments
++x
8, 18 un 126
http://paste.php.lv/7dae535711bdbb00f9c959328ce9a6e4?lang=python
nu ja es pareizi sapratu, ka ir tikai 2 krāsas, tad atbildes gadījumā nav pēc paskāla trijstūra? tb vienu bumbu var ievērt 2 dažādos veidos, divas bumbas 3 dažādos veidos, trīs bumbas 3 dažādos veidos utt? respektīvi 5 bumbas būs 20 veidos, 7 bumbas būs 70 un 11 bumbas 924 veidos?
hah, uzzīmējot uz papīra ar 0 un 1 varēja pavisam vienkārši saprast, ka tā ir elementāra lieta. pieņemot ka balts ir 0 un melns ir 1, tad var skatīties cik dažādas summas sanāk un vienmēr būs tā, ka ja bumbiņu skaits ir n, tad sanāks (n+1) dažādas krelles. piemēram no 5 bumbiņām var savākt 6 dažādas summas: 0,1,2,3,4,5, repektīvi tas ir melno bumbiņu skaits virknē. es ceru, ka runa ir tikai par skaitu nevis arī izkārtojumu. tb ka bbbmm=bmbbm 🙂
Imho svarīgs arī izkārtojums. Jo bbbmm krelle jau atšķiras, tb izskatās savādāk, nekā bmbbm krelles.
Reku darba kolēģis atrada teorētisko formulu, ar kuru to kreļļu skaitu var aprēķināt bez pilnās pārlases:
http://www-mechmath.univer.kharkov.ua/funcan/staff/novikov/pdf/33.pdf
41.lpp – 10.3 formula. Polya teorēma.
Reku kods, kas 5,7,11 (tikai pirmskaitļiem, man slinkums pilnu eilera fju rakstīt 🙂 to izrēķina:
http://paste.php.lv/5a9d4676b7d02e6b5fdd1b93bf36373d?lang=python
Atbildes sakrīt – 8, 18 un 126.
Bubu atbilde ir pareiza. Patiesībā šai problēmai nepastāv universāla funkcija f(n), kur n bumbiņu skaits.
Vieglākiem gadījumiem var uzzīmēt uz papīra, smagākiem jāraksta kods,vai jāizmanto rekursija. Šajī uzdevuma jautājumos, es apzināti iekļāvu vienkāršākos gadījumus, kad bumbiņu skaits ir pirmskaitlis, kas lielāks par 2.
Funkcija tad ir ((2^(n-1))-1)/n+2^((n-1)/2)+1. Tad 19 lodītēm sanāk 14,310 kreļļu veidi. bubu var iedarbināt savu programmu, domāju, ka sanāks tas pats.
Kā nepastāv? Es parādīju, ka pastāv gan 😀
Nu tas jau ir algoritms 🙂
Nesapratu. Kāds algoritms?
Tu tam pdf’am apskatīji 41.lpp 10.3 formulu? Imo ļoti f(n) veida formula. Pat īstenībā f(n,m), kur m ir iespējamo krāsu skaits, šajā gadījumā 2 – melna un balta.
Kādam pdf’am?
Nu 6. komentārā, kurš “Komentārs gaida apstiprināšanu.”
Tagad man jāmet kažoks uz otru pusi un jāsaka funkcija ir. Es kaut kā biju ieciklējies uz polinomu izteiksmēm. Cepuri nost tava kolēģa priekšā.
vot, sākam jau kombinatoriku implementēt 😀
visu cieņu, bet tik sarežģītas f-jas tomēr ir jāmeklē, ar loģisko domāšanu vien nepietiek 😀
Nu var jau, kā parādīju, neko nemeklēt, bet tikai programmēt 😉
nu pilnā atlase tak ir sex, iedomājies ja tev vajadzētu ar 100 bumbiņām atlasīt..