Diskuze: Ciferný súčet = súčin = x. Ako najlepšie na to?
V předchozím kvízu, Online test znalostí Java, jsme si ověřili nabyté zkušenosti z kurzu.

Člen

Zobrazeno 16 zpráv z 16.
//= Settings::TRACKING_CODE_B ?> //= Settings::TRACKING_CODE ?>
V předchozím kvízu, Online test znalostí Java, jsme si ověřili nabyté zkušenosti z kurzu.
Já bych si asi zjistil jednociferné dělitele a zkoušel z nich skládat čísla (postupně, takže kdybys měl šestku, tak 1, 11, 12, 13, 111, 112, 113…), z nichž každé otestuješ, až po délku daného čísla. Číslům <1 rovnou vyhoď je samotné, nebo pokud <-9 tak nic. No ještě jsem to nezkoušel a asi by to šlo omezit i víc nebo vymyslet ještě jinak, ale podle mě by tohle mohlo fungovat.
PS: ještě si to můžeš zkusit rozložit i odčítáním a nějak experimentovat porovnáváním těch a těch rozkladů, ale nad tímto jsem se moc nezamýšlel.
Úplne prvé by mi napadlo rekurziou si zistiť kombinácie čísel ktorých
súčet je N (hádam že to nájdeš aj na nete), tie potom prejsť a zistiť
či aj ich súčin je N a ak hej tak z tých cifier vytvoriť unique kombinácie
a nakoniec vypísať ich počet. Viem že sa to píše ľahko ale keď budem pri PC to skúsim
aj nakódiť.
obávám se, že takové číslo je jen jedno:
4 pro (2*2 = 4 a 2 + 2 = 4)
22 a 4, takže 2
Pre 8 je to až 23 čísel napr. 8,1142,...
Takže se ti jedná o čísla, která nejsou prvočíslem a pak to budeš
dolaďovat jedničkami jo?
(příklad 10 uděláš jako 2+5+1+1+1 a 25111)?
Jaký význam to má, to nechápu....
Postup je potom jednoduchý - v projektu si udělej nejdřív metodu pro
validaci prvočísla.Do této metody předáš jako parametr zadané číslo.
Metoda ti vrátí třeba true, když nebude prvočíslo, false, když bude.
Když bude, tak máš hned ukončení vlákna, protože s tím nic
nenaděláš.
Pokud není prvočíslo, tak si nejdřív zjistíš jeho možný součin
(osobně bych navrhoval součin s druhým největším číslem. S prvním
největším číslem bude vždy x = x * 1, takže když dáš 1000 * 1, tak
sice tento součin dostaneš, ale ten nechceš, protože potom nemůžeš
dorazit jedničky pro součet. Takže si najdeš potom 500 * 2 a potom tam
dorazíš 498 jedniček. Kdybys měl jiné číslo, tak tam dáš těch
jedniček logicky víc (třeba 250 * 4 bude mít 746 jedniček atd.)
Takže asi tak:
případně by to šlo kombinovat (3 x 2 x 2 x (14 jedniček) ), ale to by fungovalo, kdybys usnadnil druhou metodu, která by ti vracela jakékoliv čitatele, kromě 1 * x)
Toto ale nechápu, jaké by mohlo mít někdy nějaké uplatnění - i něco podobného. Vcelku blbý příklad.....
Ďakujem, skúsim to urobiť.
Len si nie som istý, čo myslíš druhým najväčším číslom.
tak součin se skládá z několika činitelů. A každý součin můžeš
vypočítat tak, že dáš čitatel (který má stejnou hodnotu jako výsledný
součin) krát jedna.
příklad: 5 x 1 = 5 (čitatel je 5, součin taky). To samé 55555 x 1 =
55555.
No a to je největší číslo, které můžeš použít jako čitatel pro tento
výsledek. Vyšší číslo by mohlo být, kdybys násobil v oboru desetinných
míst (třeba 10 x 0.5 = 5, takže čitatel 10 je skutečně vyšší, než
čitatel 5). Ale tak předpokládám, že se bavíme v oboru N, čili
přirozených čísel.
No a v tomto případě bude vždy nejvyšší čitatel ten, který vynásobíš
jedničkou. Jenže ten nechceš, protože to bys nemohl potom přidávat další
jedničky. Kupříkladu teď, kdybys ve svém úkolu měl číslo 5, tak to
nemůžeš použít (protože je to dokonce prvočíslo:D), ale třeba číslo
12 dostaneš těmito čitateli: 12x1, 6x2, 4x3. No a druhé nejvyšší číslo
z těchto všech čitatelů je číslo 6 a to bys právě mohl použít (to je
nejvhodnější, protože potom k tomu přičteš míň jedniček)
Abys splnil svůj úkol, tak máš v tomto případě dvě možné
řešení:
4x3x1x1x1x1x1
a nebo
6x2x1x1x1x1
Takže máš díky tomu o jednu jedničku míň.
No ale nemůžeš použít součin s nejvyšším čitatelem ze všech možných
řešení - což je 12x1, protože součin ti sice vyjde 12, ale součet máš
už teď 13. Proto to nemůžeš použít.
A zase abys použil co nejmenší počet jedniček, tak musíš použít co
největší číslo, aby ten součet byl co největší a přidávals k tomu už
jen málo jedniček.
Snad to dává trošku smysl a už to chápeš:)
PS: v podstatě takhle jsi i ty dal příklad toho čísla 8. Taky jsou tady
možnosti 8x1 4x2 2x2x2. Ty jsi vybral tu druhou možnost, protože potom k tomu
dodáš už jen 2 jedničky (u toho třetího by to bylo taky, ale tam máš
rozklad čísla 4, takže máš o jednu cifru navíc).
Taky jsi vybral druhý nejvyšší možný čitatel, ze kterého jde tento
součin provést.
Ale mate mě co, jsi napsal - Pre 8 je to až 23 čísel. Jak jsi to myslel? 23
čísel?
Nemáš pravdu. Použít to jde pouze s čísly, která lze rozložit na součin jednociferných čísel.
Příklad těch tvých 1000, pokud bys použil 500*2 doplněný o 498 jedniček - vznikne 50021111... - ciferný součin je 0. A ciferný součet je navíc 505 (vůbec ne 1000).
Stejně tak, pokud jeden z násobků bude více než jednociferný, součin nebude sedět. Opět třeba ten příklad s 12. Píšeš že 12 s jednou jedničkou má součet 13, ale to číslo 121 má ciferný součet 4 a ciferný součin 2 - ani jedno není správně.
Řešení: najdi všechna řešení součinů jednociferných čísel, která dají x. Zjisti si jejich součet, pokud je menší než x, doplň jedničkami. Je-li roven, doplňovat nemusíš. Je-li větší, řešení pro tuhle kombinaci neexistuje:
Pokud chceš najít všechny čísla, která splňují ten ciferný součin a ciferný součet, projdu všechna řešení z první věty, pokud pouze jedno, stačí najít první validní.
Jenom malá poznámka: jestli chceš všechna čísla, musíš ty jedničky
házet na všechny možné pozice. Pokud si najdeš řešení, jak získat
čísla pouze v jednom pořadí, musíš přehaozvat i je. Ale to je ti asi
jasné…
Máš pravdu a mě to ani vlastně nenapadlo . A dost razantně to změní
počet řešení, takže thumb up i tobě
.
K puvodnimu dotazu.
To je otazkou, zda nebude rychlejsi projit jednoduchym algoritmem kazdou moznost
(hrubou silu) nebo vytvorit jiny, slozitejsi. Scitani cisel je pomerne rychla
operace na bazi procesoru. Nasobeni take, ale je trochu komplikovanejsi.
a = a ... 'a' muze byt 0
a + b = a * b ... 'a' nebo 'b' > 0
a + b + c = a * b * c
a + b + c + d = a * b * c * d
Urychlit by se to dalo mozna jen googlovanim a najit si neco k teorii k takovemu pocetnimu vzorci.
a + b + c + d = a * b * c * d
Sude cislo se da zjistit tim, ze ma posledni bit 0, (cislo & 0x01)==0.
Otazkou je, zda by tahle samotna podminka nebyla slozitejsi nez provest cely
soucet a nasobeni. Nebo jen soucet a pak zjistovat sudost.
Ano, eliminujes nekolik vypoctu. Ale ostatni vypocty zatizis podminkou
navic.
Ale dalo by se prochazet a skladat cisla od zacatku. S tim, ze nasledujici
musi byt <= predchozimu a pak je promichat, provest vsechny kombinace
11
12
13
14 ...
Pokud nektere z nich vyhovuje, tak vsechny kombinace jsou
ab nebo ba
Podobne pro 3 cifry (abc)
aaa (aaX)
aab (aaX)
aac (aaX)
abb (abX)
abc (abX)
acc (acX)
bbb (bbX)
bbc (bbX) - pokud sedi, promichas, bbc, bcb, cbb
bcc (bcX)
ccc (cXY) ... cca uz resi acc, ccb resi bcc, ... takze zbyva uz jen kombinace ccc
Za abc postupne dozazujes cisla 1 az 9. Tohle by melo snizit pocet testovani.
Sice asi pozde ale obecny algoritmus by mohl vypadat takto:
Faze 1:
3. ke kazdemu poli ktere vratilo rekurzivni volani funkce pripoj hodnotu delitele, ktery byl pouzit pro vypocet podilu, ktery byl pouzit pro rekurzivni volani funkce, nasledne posbirej vsechna nova pole od vsech delitelu (cisel 2 .. 9) a vrat je jako vysledek funkce
Timto bychom meli ziskat vsechny mozne kombinace cinitelu ktere mohou tvorit
dany ciferny soucin.
Faze 2:
Faze 3:
pro kazdou kombinaci cinitelu z faze 2 vygeneruj vsechny mozne permutace
Zobrazeno 16 zpráv z 16.