Uždavinys: pupos ir beždžionės

Šita užduotis buvo naudojama Oxford'o universiteto interviu metu, stojant į Computer Science kursą.

 

Urnoje yra 23 baltos pupelės ir 34 juodos pupelės. Beždžionė traukia dvi pupeles iš urnos. Jeigu jos vienodos spalvos, beždžionė įdeda juodą pupelę į urną, o jeigu nevienodos spalvos - tada į urną idedama balta pupelė iš didelės krūvos šalia beždžionės. Beždžionė kartoja šį veiksmą, kol urnoje lieka tik viena pupelė. Kokia jos spalva?

 

Atsakymas, mano manymu, yra balta. Kaip mąsčiau - nesakysiu, kol nepamatysiu kažką panašaus mąstant. Taigi bandykit:)

 

EDIT: my bad -.-

Redagavo Rugsėjo 22, 2012 ValentasD

Šita užduotis buvo naudojama Oxford'o universiteto interviu metu, stojant į Computer Science kursą.

 

Urnoje yra 23 baltos pupelės ir 34 juodos pupelės. Beždžionė traukia dvi pupeles iš urnos. Jeigu jos vienodos spalvos, beždžionė įdeda juodą pupelę į urną, o jeigu vienodos spalvos - tada į urną idedama balta pupelė iš didelės krūvos šalia beždžionės. Beždžionė kartoja šį veiksmą, kol urnoje lieka tik viena pupelė. Kokia jos spalva?

 

Atsakymas, mano manymu, yra balta. Kaip mąsčiau - nesakysiu, kol nepamatysiu kažką panašaus mąstant. Taigi bandykit:)

 

neturėtų kažkuris būti nevienodos?

 

Edit: Pasitaisei, bet vistiek nėra logikos "Jeigu jos vienodos spalvos, beždžionė įdeda juodą pupelę į urną", o jeigu abi baltos tai iš kur tą juodą gaus? ne ten gal "nevienodos" žodį panaudojai? :D

 

P.S. ar čia abiem galioja "iš didelės krūvos šalia beždžionės" ?

Redagavo Rugsėjo 22, 2012 korner

 

Urnoje yra 23 baltos pupelės ir 34 juodos pupelės. Beždžionė traukia dvi pupeles iš urnos. Jeigu jos vienodos spalvos, beždžionė įdeda juodą pupelę į urną, o jeigu nevienodos spalvos - tada į urną idedama balta pupelė iš didelės krūvos šalia beždžionės. Beždžionė kartoja šį veiksmą, kol urnoje lieka tik viena pupelė. Kokia jos spalva?

 

 

Truputi nesuvokiu pačios užduoties...

1. Urnoje yra pupelės dviejų rūšių pupelės

2. Beždžionė traukia iš jos pupeles.

3.1. Jei vienodos, tuomet įdedą į urną juodą pupelę. O kur kita pupelę padeda?

3.2. Jei nevienodos, tuomet iš kažkokios krūvos įdeda baltą pupelę. Ir vėl, kur padėjo nevienodas tuomet?

4. Tai kartojasi kol urnoje lieka tik viena pupelė.

 

Nesuvokiu kaip jai tas pupelių skaičius mažėja išviso, jei iš kažkokios papildomos krūvos į ją kraunama...

neturėtų kažkuris būti nevienodos?

 

Edit: Pasitaisei, bet vistiek nėra logikos "Jeigu jos vienodos spalvos, beždžionė įdeda juodą pupelę į urną", o jeigu abi baltos tai iš kur tą juodą gaus? ne ten gal "nevienodos" žodį panaudojai? :D

 

P.S. ar čia abiem galioja "iš didelės krūvos šalia beždžionės" ?

 

man atrodo blogai pataisė, nes kiek bandžiau mastyt kitu atveju gaunasi tikimybių teorija ir neaišku kuri liks :)

 

Truputi nesuvokiu pačios užduoties...

1. Urnoje yra pupelės dviejų rūšių pupelės

2. Beždžionė traukia iš jos pupeles.

3.1. Jei vienodos, tuomet įdedą į urną juodą pupelę. O kur kita pupelę padeda?

3.2. Jei nevienodos, tuomet iš kažkokios krūvos įdeda baltą pupelę. Ir vėl, kur padėjo nevienodas tuomet?

4. Tai kartojasi kol urnoje lieka tik viena pupelė.

 

Nesuvokiu kaip jai tas pupelių skaičius mažėja išviso, jei iš kažkokios papildomos krūvos į ją kraunama...

 

koks skirtumas iš kur įkrauna, vistiek visada išima dvi o įdeda tik vieną :)

Sąlyga gera, o sprendimas reikalauja laiko...aš irgi ilgai galvojau. Bandžiau ir su pavyzdžiais daryti, tai gaunu, kad lieka balta. Mąstykit.

Radau šitą uždavinį:

Monkey beans. An urn contains 23 white beans and 34 black beans. A monkey takes out two beans; if they are the same, he puts a black bean into the urn, and if they are different, he puts in a white bean from a large heap he has next to him. The monkey repeats this procedure until there is only one bean left. What colour is it?

 

Ar nebūtų galima tiesiog paskaičiuoti visų įmanomų variantų? Gautųsi didžiulis medis, kurio šakos visada šakosis į tai ar vienodos ar ne. Nors galbūt reiktų dar atskirti vienodos baltos ar juodos. Ir taip suki ciklą kol lieka tik viena, ir žiūri kokia. Jei visų šakų skirtingos, tuomet kažkur susimovė :)

Redagavo Rugsėjo 22, 2012 Plutonium

Tikiuos klaidos neįvėliau..? Jo. Radai. Bandyk spręsti. Čia nesunku, bet biški smegenis pakrutina..

Mano manymu irgi jog balta, nes tiesiog didesnė tikimybė jog ištrauks nevienodas, kai juodų pupelių beveik perpus daugiau

Baltų pupelių nelyginis skaičius. Taigi pagal pateiktus reikalavimus neišeis suporuot baltu , o kadangi skirtingu pupelių atveju įdedama balta, tai vienu žodžiu ji ir liks :D Taip ?

 

Tarkim lieka 3 juodos ir 2 baltos.

 

Ištrauki 2 juodas įdedi 1.

 

Lieka 2 juodos 2 baltos.

 

Tarkim ištrauki 2 baltas ir įdedi viena atgal.

 

lieka 2 juodos 1 balta.

 

ir taip toliau, bet kokiu atveju viskas baigsis tuo kad liks balta.

 

Tai priklauso nuo jų nelyginio skaičiaus ir antros sąlygos dalies, kad nevienodu pupelių atveju įdedama balta.

Redagavo Rugsėjo 22, 2012 fluxas

Ė, bet čia gerą mintį iškėlė :) Jei paima dvi baltas, tai iš kur ji juodą įdeda.. :D Nu matyt, susimauta, turi galvoj, kad ir juodų turi kažkur su savim. Aš laikiau, kad juodos mėtos dar kažkur. Nes kitaip nelogiška. Juodos pupos iš niekur atsirastų.

White. Mėginau visada sakyti kad ww ištraukia, ir daėjau iki tol kol liko 1w ir 45b. Ir pasirinkimai arba bb arba wb, ir toliau wb eini ir gaunasi kad mažės tik b. Ir lieka w. Ir jei ties tuo kai lieka 1w ir 45b sukčiau bb keliu, tai vistiek lieka w

Sveikinu, Plutonium. Aš taip pat padariau. +1 :D

 

Taip, kad nenuvertinkit savęs ir stokite į Oxford :)

Nors jei stoji į tokį dalyką tikrai galėtum pasidaryti programėlę kokią :D

 

Mazgas (baltos, juodos, rodykle i ww, rodykle i bb, rodykle i wb). Ir gausis gan gražus medelis, kurio galutiniai mazgai turės baltos+juodos=1 :D

Oxfordas mano, kad tu neturi jokios programavimo patirties, prieš stodamas. Aišku dauguma turi, bet.. :D

 

Kadangi jau pradėjom, tai http://www.cs.ox.ac.uk/admissions/ugrad/Sample_interview_problems

 

Ir pasižiūrim į šeštą nr. Tas yra gan įdomus irgi.

Redagavo Rugsėjo 22, 2012 ValentasD

Na čia su matematika ir geru loginiu mąstymu pralysti ir galima :D

 

Užkabliavai mane, o aš miegot norėjau jau... :D

http://www.skelbkite.lt/pupos/ išsprendžiau, bandžiau juodų skaičių padaryti nelyginį, o baltų lyginį ir gavos, kad lieka juoda, o kai baltų 23, o juodų 34, tai visada lieka balta :) Visa esmė pradinis pupelių skaičius, nelyginis prieš lyginį laimi :)

Neskaiciau sprendimo variantu, tik uzduoti, tai pamastymas toks, kad visada prieisim tokia situacija, kai liks 1 balta ir n juodu pupeliu, o nuo to momento galimi veiksmai arba dvi juodos arba skirtingos, betkokiu atveju baltu pupeliu skaicius nepasikeicia, o juodu sumazeja 1 arba 2, atsakymas balta, right?

Tas šeštas uždavinys, jeigu trūksta tik vieno skaičiaus, manau būtų daromas taip:

 

Susumuoji visą skaičių eilę, aritmetine progresija.

Tada Susumuoji visą eilę, kuri tau duota kompu...sukišti viskas į vieną array...

 

Akivaizdžiai suma duotos tau eilės bus mažesnė. Tada pilna eilė - duota eilė = skaičius, kurio ir trūktų... Ne?

1.variantas.

Truputi nesuprantu šeštos :/

1. Man duoda listą su skaičiais: visi skirtingi, visi teigiami ir max yra mažesnis už 1kk.

2. Man reikia surasti skaičių, kuris nėra mano duodate liste, tik atitinka rėžius.

 

Tai koks tikslas iš listo kurį man davė? Ar čia reikia galvoti iš kažkokio algoritmo pusės?

Jei norėčiau rasti pozicija, tuomet išrikiuoju savo listą didėjimo tvarka. Emu pirmą ir tikrinu ar duotas skaičius didesnis už jį didesnis. Jei ne, emu antrą, jei taip, tuomet turiu sumažintą intervalą tarp pirmo ir antro. Ir tuomet jau paieška truks daug trumpiau

 

Čia jei supratau gerai uždavinį

 

2. variantas

Reikia rasti nežinomą skaičių, kuris nėra tavo duotame saraše? Ar bus tik vienas skaičius ar gali būti ir keli?

Redagavo Rugsėjo 22, 2012 Plutonium

Uždavinys sako missing numbers, tai turiu suprasti, kad trūksta daugiau nei vieno. Bet pabaigoje sako, kad surasti vieną skaičių...Tai skaitau, kad apie vieną kalba. Ždž sąlygos tikrai neaiškios.

 

Tam, kad prisikasti ligi interviu, turėtumėte išlaikyti ir šitą testą : http://www.maths.ox.ac.uk/prospective-students/undergraduate/specimen-tests

 

Yra pavyzdžių klausimų. Kai kurie lengvi, kai kurie labai sunkūs, bent man. Vakar ligi 2-os nakties sprendžiau.. :D

1.variantas.

Truputi nesuprantu šeštos :/

1. Man duoda listą su skaičiais: visi skirtingi, visi teigiami ir max yra mažesnis už 1kk.

2. Man reikia surasti skaičių, kuris nėra mano duodate liste, tik atitinka rėžius.

 

Tai koks tikslas iš listo kurį man davė? Ar čia reikia galvoti iš kažkokio algoritmo pusės?

Jei norėčiau rasti pozicija, tuomet išrikiuoju savo listą didėjimo tvarka. Emu pirmą ir tikrinu ar duotas skaičius didesnis už jį didesnis. Jei ne, emu antrą, jei taip, tuomet turiu sumažintą intervalą tarp pirmo ir antro. Ir tuomet jau paieška truks daug trumpiau

 

Čia jei supratau gerai uždavinį

 

2. variantas

Reikia rasti nežinomą skaičių, kuris nėra tavo duotame saraše? Ar bus tik vienas skaičius ar gali būti ir keli?

As panasiai galvoju kaip ir tu, tik esme, kad sis variantas nevisada atitiks salyga "in a reasonable time", nes jeigu skaicius bus intervalo galas, tai turesi alikti tiek palyginimu, right?

Man gerai ir KTU :D Nežadu belstis iki Oxfordo :D Bet kai turėsiu laiko tai turbūt paklibinsiu. Visai smagūs galvosūkiai :)

 

As panasiai galvoju kaip ir tu, tik esme, kad sis variantas nevisada atitiks salyga "in a reasonable time", nes jeigu skaicius bus intervalo galas, tai turesi alikti tiek palyginimu, right?

Man atrodo yra kažkokia vidurio pjūvio taisyklė ar kažkas tokio. Paemi vidurinį narį ir tikrini ar didesnis ar mažesnis. Tuomet naujasis intervalas bus jau nukirstas per puse tik priklausomai į dešinę ar į kairę. Ir vėl kertam per puse. Ir taip reikės mažiau veiksmų kol rasi :)

Be to, jeigu darant viską kompu, atminties gali neužtekt ir kompas pastringt :D Skaičių belekiek.

 

Kas matėte Harvard CS50 pirmą paskaitą udemy.com, tai instruktorius kažką panašaus kaip jūs siūlote ir darė. Ieškojo telefonų knygoje žmogaus "Mike Smith", tai kadangi žinai, kad "S" yra toliau nei pusė abecėlės, perplėšė telefonų knygą per pusę. Tai čia jaučiu ir su šita užduotim kažkas tokio. Tik skirtumas tas, kad mes nežinom to skaičiaus...

Redagavo Rugsėjo 22, 2012 ValentasD

Gera mintis su tuo per puse, reiketu apie 20 spejimu (2^20 > 9999999), aisku jeigu galimas toks klausimas, ar skaicius didesnis/mazesnis

Be to, jeigu darant viską kompu, atminties gali neužtekt ir kompas pastringt :D Skaičių belekiek.

 

Kas matėte Harvard CS50 pirmą paskaitą udemy.com, tai instruktorius kažką panašaus kaip jūs siūlote ir darė. Ieškojo telefonų knygoje žmogaus "Mike Smith", tai kadangi žinai, kad "S" yra toliau nei pusė abecėlės, perplėšė telefonų knygą per pusę. Tai čia jaučiu ir su šita užduotim kažkas tokio. Tik skirtumas tas, kad mes nežinom to skaičiaus...

Taip, mano sprendimas tiktų jei žinotume koks skaičius yra. Bet čia kaip ir nėra pasakyta mes žinome jį ar ne. Tad gaunasi du sprendimo variantai :) Kai žinom tai karpom pusiau, o kai nežinome gali vėl būti du variantai: vienas nežinomas ar daug nežinomų. Jei vienas, tai tuomet sudedam visus skaiičuos nuo 0 iki 999 999 ir listo. Tuomet iš didesnio atemam mažesnį ir gauname. Jei daugiau, tai tuomet gausime kažkokį skaičių, kurį reikės gvildenti. Pvz gauname 4. Tai jis bus 13 ir 4. Ir tuomet iš gautų skaičiukų dar patikriname ar jie jau yra mūsų liste ar nėra. Jei yra, tai atmetam, jei nėra, tai mes randam skaičius :)

 

Gera mintis su tuo per puse, reiketu apie 20 spejimu (2^20 > 9999999), aisku jeigu galimas toks klausimas, ar skaicius didesnis/mazesnis

20tas spėjimas jau sumautų visą reikalą. Tad reiktų likti ties 19tu :)

O dėl klausimo ar gali, tai manau čia palikta pačiam nuspręsti. Jei įžvelgi daugiau nei vieną variantą ir gali juos išspręsti, tai dar geriau :) O jei konkrečiai viskas būtų, tai jokio mąstymo neliktų ;)

Redagavo Rugsėjo 22, 2012 Plutonium