Navigate / search

Intelektuāls jautājums LVIII jeb veram krelles

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

Zandis
Reply

++x

sn
Reply

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?

sn
Reply

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 :)

bubu
Reply

Imho svarīgs arī izkārtojums. Jo bbbmm krelle jau atšķiras, tb izskatās savādāk, nekā bmbbm krelles.

asmo
Reply

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.

bubu
Reply

Kā nepastāv? Es parādīju, ka pastāv gan :D

asmo
Reply

Nu tas jau ir algoritms :)

bubu
Reply

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.

asmo
Reply

Kādam pdf’am?

bubu
Reply

Nu 6. komentārā, kurš “Komentārs gaida apstiprināšanu.”

asmo
Reply

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šā.

desperado
Reply

vot, sākam jau kombinatoriku implementēt :D

sn
Reply

visu cieņu, bet tik sarežģītas f-jas tomēr ir jāmeklē, ar loģisko domāšanu vien nepietiek :D

bubu
Reply

Nu var jau, kā parādīju, neko nemeklēt, bet tikai programmēt ;)

sn
Reply

nu pilnā atlase tak ir sex, iedomājies ja tev vajadzētu ar 100 bumbiņām atlasīt..

Leave a comment

name*

email* (not published)

website