Diskuze: Ciferný súčet = súčin = x. Ako najlepšie na to?

Ferko

Člen

Ferko:5.9.2018 19:14

Ahoj,
riešim matematický problém, kde je úlohou zistiť počet čísel, kde: platí ciferný súčet = ciferný súčin = zadané x.

Neviem si s tým poradiť, nenapadne ma žiadne rozumné riešenie.

Zkusil jsem: Napadá ma jedine skúsiť všetky čísla od 1 po 10^x a spočítať to pre každé. To je ale neefektívne, keďže x očakávame rôzne veľké. Čísla obsahujúce nulu sú zbytočné, lebo súčin bude 0. To ale nejako extra nepomôže.

Chci docílit: Pre x = 4 sú to čísla 4 a 22, čiže výsledok je 2.

Ide mi o to robiť to čo najefektívnejšie, ale neviem ako.

Napadne niekoho niečo lepšie?

Ďakujem

Odpovědět

5.9.2018 19:14

Neaktivní uživatel

Člen

Neaktivní uživatel:6.9.2018 6:38

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.

Nahoru Odpovědět

6.9.2018 6:38

Neaktivní uživatelský účet

Matúš Olejník

Člen

Matúš Olejník:6.9.2018 8:17

Ú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ť.

Nahoru Odpovědět

6.9.2018 8:17

/* I am not sure why this works but it fixes the problem */

David Hynek

Tvůrce

David Hynek:6.9.2018 9:58

obávám se, že takové číslo je jen jedno:

4 pro (2*2 = 4 a 2 + 2 = 4)

Nahoru Odpovědět

6.9.2018 9:58

Čím víc vím, tím víc věcí nevím.

Ferko

Člen

Ferko:6.9.2018 10:33

22 a 4, takže 2

Pre 8 je to až 23 čísel napr. 8,1142,...

Nahoru Odpovědět

6.9.2018 10:33

Lubor Pešek

Člen

Lubor Pešek:6.9.2018 11:15

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

Editováno 6.9.2018 11:17

Nahoru Odpovědět

6.9.2018 11:15

Existují dva způsoby, jak vyřešit problém. Za prvé vyhoďte počítač z okna. Za druhé vyhoďte okna z počítače.

Lubor Pešek

Člen

Lubor Pešek:6.9.2018 11:42

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:

metoda - validace na prvočíslo
metoda pro možný součin s druhým největším číslem (pozor, nebude to vždy 2 x něco, třeba číslo 9 má 3 x 3 a 3 jedničky
nejrychlejší metoda, která ti sečte oba činitele, odečte toto číslo od zadaného čísla a to je tvůj limit v cyklu, který přidá tolik jedniček (číslo 24. (první metoda zjistí, že to není prvočíslo a může se pokračovat, druhá metoda zjistí čitatele 12 * 2, třetí metoda ti vypočítá 24 - (12 + 2) = 10 a tak v cyklu přidá 10 jedniček)

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

Nahoru Odpovědět

6.9.2018 11:42

Existují dva způsoby, jak vyřešit problém. Za prvé vyhoďte počítač z okna. Za druhé vyhoďte okna z počítače.

Ferko

Člen

Ferko:7.9.2018 9:00

Ďakujem, skúsim to urobiť.

Len si nie som istý, čo myslíš druhým najväčším číslom.

Nahoru Odpovědět

7.9.2018 9:00

Lubor Pešek

Člen

Lubor Pešek:7.9.2018 14:51

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?

Nahoru Odpovědět

7.9.2018 14:51

Existují dva způsoby, jak vyřešit problém. Za prvé vyhoďte počítač z okna. Za druhé vyhoďte okna z počítače.

Matyáš Procházka

Člen

Matyáš Procházka:7.9.2018 22:42

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ě.

Nahoru Odpovědět

7.9.2018 22:42

Matyáš Procházka

Člen

Matyáš Procházka:7.9.2018 22:45

Ř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í.

Editováno 7.9.2018 22:47

Nahoru Odpovědět

7.9.2018 22:45

Neaktivní uživatel

Člen

Neaktivní uživatel:8.9.2018 11:15

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é… ;-)

Nahoru Odpovědět

8.9.2018 11:15

Neaktivní uživatelský účet

Matyáš Procházka

Člen

Matyáš Procházka:8.9.2018 23:23

Máš pravdu a mě to ani vlastně nenapadlo . A dost razantně to změní počet řešení, takže thumb up i tobě .

Nahoru Odpovědět

8.9.2018 23:23

Peter Mlich

Člen

Peter Mlich:12.9.2018 13:02

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

soucet 4 lichych cisel je sude cislo
nasobenim 4 lichych cisel sude cislo nedostanes (1 * 3 * 5 * 7 * 9)
vyradit lze ty nuly

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.

Nahoru Odpovědět

12.9.2018 13:02

Petr

Člen

Petr:21.9.2018 2:40

Sice asi pozde ale obecny algoritmus by mohl vypadat takto:
Faze 1:

pokud je x > 9 podel x cisly od 2 do 9, pokud je x delitelne danym cislem beze zbytku, zavolej rekurzivne to same na vysledek deleni (pokud neni x delitelne ani jednim cislem od 2 do 9 tak konecna, protoze reseni neexistuje - vyhod vyjimku)
pokud je x <= 9 tak pro:

9 vrat [9], [3,3]
8 vrat [8], [2, 4], [2,2,2]
7 vrat [7]
6 vrat [6], [2,3]
5 vrat [5]
4 vrat [4], [2,2]
3 vrat [3]
2 vrat [2]

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:

pro kazdou kombinaci z faze 1 proved ciferny soucet
pokud je ciferny soucet > x tak vyhod danou kombinaci ze seznamu
pokud je ciferny soucet = x tak nic nedelej
pokud je ciferny soucet < x tak dopln do kombinace (x - ciferny soucet) jednicek

Faze 3:
pro kazdou kombinaci cinitelu z faze 2 vygeneruj vsechny mozne permutace

Editováno 21.9.2018 2:42

Nahoru Odpovědět

21.9.2018 2:40

Petr

Člen

Petr:21.9.2018 2:46

jeste me napada ze po fazi 1 tam muzou byt stejne kombinace, takze by bylo vhodne seradit ta pole a vyhazet duplikaty

Nahoru Odpovědět

21.9.2018 2:46