Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
23. 10. 2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

#1 29. 07. 2017 10:20

sio
Příspěvky: 37
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

Súčet čísel

Dobrý deň,

potrebujem vyriešiť takúto situáciu: mám postupnosť 36 kladných celých čísel z intervalu od 0 po $10^{10}$ a vstup je nejaké kladné číslo N. Ako zistím, či N môžem napísať ako súčet 2 alebo viacerých čísel postupnosti?   

Ďakujem.

Offline

 

#2 30. 07. 2017 12:57

ViliX
Místo: Praha
Příspěvky: 195
Škola: MFF
Pozice: student
Reputace:   11 
Web
 

Re: Súčet čísel

↑ sio:

Zdravím,

věděl bys jak na to jít, kdyby to bylo pouze jen součet dvou čísel z posloupnosti? Jak by jsi takovou úlohu řešil ručně?

Offline

 

#3 30. 07. 2017 14:22

sio
Příspěvky: 37
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

Re: Súčet čísel

↑ ViliX:
Dobrý deň,

to by som skúsil od čísla N odrátať postupne každé číslo z intervalu a kontroloval či výsledok nie je nejaké iné číslo z intervalu.

Offline

 

#4 30. 07. 2017 14:25

ViliX
Místo: Praha
Příspěvky: 195
Škola: MFF
Pozice: student
Reputace:   11 
Web
 

Re: Súčet čísel

↑ sio:

Ano. Pro n=3 by to šlo udělat třeba tak, že bys od N odečetl vždy jedno číslo a pak jen udělal to co jsi už popsal, tj. algoritmus pro n=2.

Offline

 

#5 30. 07. 2017 14:37

sio
Příspěvky: 37
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

Re: Súčet čísel

↑ ViliX:

Bol by to funkčný postup ale mám pocit, že je tam veľmi vysoká časová zložitosť. V podstate musím vyskúšať všetky dvojice, trojice, štvorice, pätice,... až po súčet všetkých 36 prvkov. Ale to je veľmi veľa možností.

Offline

 

#6 30. 07. 2017 14:43

ViliX
Místo: Praha
Příspěvky: 195
Škola: MFF
Pozice: student
Reputace:   11 
Web
 

Re: Súčet čísel

↑ sio:

Nejsem si zcela jistý, zdali existuje pěknější způsob než $36^n$. Je to z části rozebrané zde. Dochází tam ale k závěru, že kromě drobné optimalizaci se tomu vyhnout nedá.

Offline

 

#7 30. 07. 2017 15:04

sio
Příspěvky: 37
Škola: Gymnazium Leonarda Stockela
Pozice: Študent
Reputace:   
 

Re: Súčet čísel

↑ ViliX:

Skúsim si prejsť tú optimalizáciu, ďakujem.

Offline

 

#8 31. 07. 2017 15:51

mracek
Zablokovaný
Příspěvky: 164
Reputace:   
 

Re: Súčet čísel

↑ sio:
Je to problem obchodniho cestujiciho. Vis vzdalenosti mezi mesty a mas navrhnout nejkratsi trasu.

Ja bych ty cisla seradil podle velikosti a zkousel odcitat od nejvetsiho.
X - nej - nej... dokud to jde a pak dalsi cisla
Vysledek si nejspis zapisujes, takze v dalsim kroku bych nej cislo odcital je n-1 a pak zkusil ostatni cisla. Atd.

Pak je tu moznost, jit na to opacne. Pouzit v podstate algoritmus hledani nejkratsi cesty, pricitat k cislu ostatni, vsechny moznosti. Coz je silenost, trochu. Neco, jako sachy :)

Mno, a jeste by slo udelat z tech cisel jednice, dvojice, trojice a pricitat to jako celky. Kde uz mas soucet te trojice, takze to nemusis pokazde scitat.

A jeste by to udelat skupinky vetsich a mensich cisel. Pokud je zbytek po odcitani >0 a <x, pouzijes cisla ze skupiny 1, <y, skupina2, ... Ale, kdyz to mas serazene, tak skoncis algoritmem stejne v okamziku, kdy cislo bude <0.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson