taapati ([info]taapati) rakstīja [info]koderi kopienā,
@ 2006-02-19 23:16:00
Previous Entry  Add to memories!  Tell a Friend!  Next Entry
"Reizinājuma ciparu atminēšana. Dotas 3 simbolu virknes A, B, C, kas apzīmē veselus skaitļus, kuru cipari tiek pierakstīti ar burtiem a,b,c,d,e,f,g,h,i,j un simbolu *, ar nosacījumu, ka dažādiem burtiem atbilst dažādi cipari, un * var nozīmēt jebkādu ciparu. Atgriezt kādu iespējamo A, B un C skaitļu vērtības, lai izpildītos A=B*C. Ja risinājums neeksistē, tad paziņot par to."

varbūt Jums ir kādas gudras idejas, kas būtu labākas par pilno pārlasi? ;) būšu bezgala pateicīga par jebkuru ierosinājumu :)))

(Ierakstīt jaunu komentāru)


[info]barvins
2006-02-19 23:58 (saite)
Ja ir izmantoti visi 10 burti, tad sanāk pārlasīt 10*9*8*..*2*1 = 3628800 kombinācijas. Par katru zvaigznīti kombināciju skaits pieaug 10 reizes.
Droši vien jāpārlasa tikai tie burti, kas ir sastopami B un C virknēs, A virknes burti ir nozīmīgi tikai tad, kad B ar C jau ir sareizināts un ir dabūts rezultāts, ko salīdzināt ar A virkni.

(Atbildēt uz šo) (Diskusija)


[info]taapati
2006-02-20 00:03 (saite)
nu, jā - pilnā pārlase :) jautājums - vai tiešām tas ir labākais/vienīgais veids? ;) (*man kkā ir aizdomas, ka tas var sanākt diezgan ilgi neveiksmīgiem ievaddatiem*)

(Atbildēt uz šo) (Iepriekšējais) (Diskusija)


[info]barvins
2006-02-20 00:17 (saite)
Nu, var arī mēģināt no otra gala. Ņemam virkni A, izvēlamies, kāds būs tās pēdējais cipars, un tad, pārlūkojam kādi drīkst būt pēdējie cipari virknēs B un C - tur ir ļoti maz iespējamo kombināciju. Piemēram, ja A beidzas ar 6, tad B un C var beigties ar (1,6), (2,3), (3,2), (6,1). Un visu laiku sekojam līdzi, kādiem burtiem kādi cipari ir piešķirti, un vai nerodas kādas pretrunas, ka vienam un tam pašam burtam piešķir dažādus ciparus, vai dažādiem burtiem vienādus ciparus.
Pēc tam bīdāmies uz otro ciparu no beigām, un darbojamies līdzīgi. Taču šeit jau kļūst sarežģīti - jādarbojas pēc tā veida, kā ciparus skolā mācījāmies reizināt - jāpatur prātā atlikums un tamlīdzīgi.

Šādi ir daudz sarežģītāk, taču vajadzētu būt krietni ātrāk, nekā pilnajai pārlasei. Neņemos gan aprēķināt, cik tieši ātrāk.

(Atbildēt uz šo) (Iepriekšējais) (Diskusija)


[info]taapati
2006-02-20 00:26 (saite)
tikai - nav vis ļoti maz iespējamo kombināciju tam pašam piemēram - var būt arī (6,6) (4,9) (9,4) (4,4) (2,8) (8,2) (7,8) (8,7). tātad kopā 12 iespējas. un vēl - kas notiek ar zvaigznīti? šis variants man bija padomā, tikai sāka likties pārāk nereāls un, iespējams, vēl lēnāks nekā pilnā pārlase :) es gan neņemos to apgalvot - nav tik liela pieredze :)

(Atbildēt uz šo) (Iepriekšējais) (Diskusija)


[info]barvins
2006-02-20 01:09 (saite)
Jā, taisnība.
Hmm.
Bet padomāsim, kā ir ātrāk.
Katram ciparam ir, teiksim, kādas padsmit (pieņemsim, 15) iespējas, kā to iegūt sareizinot divus citus ciparus. Tādā gadījumā, pie pašiem sliktākajiem apstākļiem, kad A ir visas zvaigznītes un vispār nekādi nesokas uzminēt pareizo kombeni...

Sanāk (10*15) salīdzināšanas katram ciparam, bet kopā 150^a, kur a ir A virknes garums. jau 150^3 pārsniedz 3 miljonus, kas ir aptuveni tikpat, cik pie pilnās pārlases, ja ir izmantoti visi 10 burti, bet nav zvaigznīšu. Pie pilnās pārlases, ja būtu visur tikai zvaigznītes, sanāktu 10^b * 10^c, kas būtu tikai viens miljons, ja B un C katrs sastāv no 3 zvaigznītēm.

Viennozīmīgi, ja ir galīgi draņķīga situācija, tad pilnā pārlase rullē. Bet man ir čujs, ka pie standartīgākām situācijām, kur atrisinājums ir iespējams, un nav arī daudz zvaigznīšu, labāk strādātu tas algoritms, kas no otra gala ņemās, jo tur jau pašā sākumā tiktu izslēgtas daudzas nederīgas situācijas. Un galu galā, ja ir daudz zvaigznīšu, tad, visticamāk, ir arī daudz iespējamo atrisinājumu, tā kā maz ticams, ka nāksies izskatīt cauri nezin-cik tur variantu, lai nonāktu pie atbildes.
Tobiš, gribēju teikt, ka otrs variants, tas, kas nav pilnās pārlases variants, tiecas uz atbildi mērķtiecīgāk, pa ceļam atmetot veselus zarus ar nepareizajām atbildēm.

(Atbildēt uz šo) (Iepriekšējais) (Diskusija)


[info]taapati
2006-02-20 10:33 (saite)
njā. izklausās prātīgi :) tikai vismaz pagaidām mani biedē tā otrā varianta kodēšana - nav ne jausmas, kā lai to smuki uzraksta :) būs vairāk jāpadomā laikam :)

Paldies ;)

(Atbildēt uz šo) (Iepriekšējais)


[info]bubu
2006-02-22 10:19 (saite)
Tieši šo mājasdarbu LU pirms pāris gadiem risināju ar pilno pārlasi. Nebija ne vainas.

(Atbildēt uz šo) (Diskusija)


[info]taapati
2006-02-22 16:22 (saite)
nja. laikam tieši tā arī nāksies darīt :)))

(Atbildēt uz šo) (Iepriekšējais)

Neesi iežurnalējies. Iežurnalēties?