Black Friday Black Friday
Black Friday výprodej! Až 80 % extra bodů zdarma! Více informací zde
Avatar
Ferko
Člen
Avatar
Ferko:5. září 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. září 19:14
Avatar
Andy Scheuchzer:6. září 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. září 6:38
Za správnost neručím.
Avatar
Odpovídá na Ferko
Matúš Olejník:6. září 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 :D ale keď budem pri PC to skúsim aj nakódiť.

Nahoru Odpovědět 6. září 8:17
/* I am not sure why this works but it fixes the problem */
Avatar
David Hynek
Redaktor
Avatar
Odpovídá na Ferko
David Hynek:6. září 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. září 9:58
Čím víc vím, tím víc věcí nevím.
Avatar
Ferko
Člen
Avatar
Odpovídá na David Hynek
Ferko:6. září 10:33

22 a 4, takže 2

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

 
Nahoru Odpovědět  +1 6. září 10:33
Avatar
Lubor Pešek
Člen
Avatar
Lubor Pešek:6. září 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. září 11:17
Nahoru Odpovědět 6. září 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.
Avatar
Lubor Pešek
Člen
Avatar
Lubor Pešek:6. září 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:

  1. metoda - validace na prvočíslo
  2. 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
  3. 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  +2 6. září 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.
Avatar
Ferko
Člen
Avatar
Odpovídá na Lubor Pešek
Ferko:7. září 9:00

Ďakujem, skúsim to urobiť.

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

 
Nahoru Odpovědět 7. září 9:00
Avatar
Lubor Pešek
Člen
Avatar
Lubor Pešek:7. září 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. září 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.
Avatar
Odpovídá na Lubor Pešek
Matyáš Procházka:7. září 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. září 22:42
Avatar
Matyáš Procházka:7. září 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. září 22:47
 
Nahoru Odpovědět  +1 7. září 22:45
Avatar
Odpovídá na Matyáš Procházka
Andy Scheuchzer:8. září 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  +1 8. září 11:15
Za správnost neručím.
Avatar
Odpovídá na Andy Scheuchzer
Matyáš Procházka:8. září 23:23

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

 
Nahoru Odpovědět  +1 8. září 23:23
Avatar
Peter Mlich
Člen
Avatar
Peter Mlich:12. září 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. září 13:02
Avatar
Petr
Člen
Avatar
Petr:21. září 2:40

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

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

  1. pro kazdou kombinaci z faze 1 proved ciferny soucet
  2. pokud je ciferny soucet > x tak vyhod danou kombinaci ze seznamu
  3. pokud je ciferny soucet = x tak nic nedelej
  4. 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. září 2:42
 
Nahoru Odpovědět 21. září 2:40
Avatar
Petr
Člen
Avatar
Petr:21. září 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. září 2:46
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 16 zpráv z 16.