Avatar
coells
Redaktor
Avatar
coells:

Zdravím pání programátoři! Protože okolo vidím spoustu nadšení, rád bych vyhlásil malou soutěž, abyste mohli ukázat,co doopravdy umíte.

Co bude odměnou? Dobrý pocit, že jste se něco naučili... tentokrát. Pokud se mi totiž sejde alespoň 10 správných řešení, vyhlásím před vánoci soutěž o ceny! To už za trochu námahy stojí, ne?

A co je soutěžní úloha?

Vaším úkolem je napsat program, který spočítá součet všech faktoriálů od 1 do 10.000. Musíte tedy spočítat X = 10.000! + 9.999! + ... 3! + 2! + 1!
Ale pozor, výsledné číslo bude mít přes 35.000 číslic. Na konci vypište počet číslic v X a prvních několik číslic zepředu a zezadu.

Poznámka:
Matematická funkce faktoriál se zapisuje jako n!, kde n je přirozené číslo. Například 5! = 5 * 4 * 3 * 2 * 1 = 120

Pokud by program počítal hodnoty pro X = 10! + 9! + ... + 2! + 1!, pak by výsledkem bylo X = 4037913.

Podmínky:

  1. jsou povolené jazyky Ansi C, C++, Java a C#
  2. nesmíte použít knihovny na práci s velkými čísly (žádný BigInteger)
  3. program by měl běžet několik sekund, určitě ne minuty nebo hodiny

A nápověda na závěr: 99% programování je matematika a přemýšlení, zkuste si nejdřív na papír ručně spočítat X pro hodnotu 10.

Editováno 14.11.2013 17:52
 
Odpovědět  +1 14.11.2013 17:50
Avatar
Neaktivní uživatel:

je nejaky casovy limit?

Nahoru Odpovědět 14.11.2013 19:11
Neaktivní uživatelský účet
Avatar
coells
Redaktor
Avatar
coells:

Pokud myslíš časový limit běhu programu, tak ... 10 sekund :-)

Pokud myslíš časové omezení soutěže, nestojím si za žádným termínem. Uvidíme podle odezvy.

A pokud nějaký termín potřebuješ, tak tady je termín speciálně pro tebe: 16.11.2013 17:45:36

 
Nahoru Odpovědět 14.11.2013 19:17
Avatar
Neaktivní uživatel:

myslel jsem omezeni souteze :D

samozrejme lepsi bude bez limitu :D

jinak ma to fungovat tedy tak ze program bude scitat

10000 + 9999 ... 2 + 1 = vysledek?

Nahoru Odpovědět  -1 14.11.2013 19:22
Neaktivní uživatelský účet
Avatar
coells
Redaktor
Avatar
coells:

10000! + 9999! + ... 3! + 2! + 1! = výsledek

 
Nahoru Odpovědět 14.11.2013 19:32
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na coells
Silvinios:

Posílám řešení v JavaScriptu. V Chrome se do 10 sekund vejdu.

<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8" />
<title>Ukaž, co umíš? Faktoriál!</title>
</head>
<script type="text/javascript">
function run(){for(var d=[0],c=[1],e=1;1E4>=e;e++){for(var a=0,b=c.length-1;0<=b;b--)a+=e*c[b],c[b]=a%10,a=Math.floor(a/10);for(;0<a;)c.unshift(a%10),a=Math.floor(a/10);for(var a=0,f=c.length-1,b=d.length-1;0<=b;b--)a+=d[b]+c[f--],d[b]=a%10,a=Math.floor(a/10);for(;0<=f;)a+=c[f--],d.unshift(a%10),a=Math.floor(a/10);for(;0<a;)c.unshift(a%10),a=Math.floor(a/10)}c=d.length+";";for(b=0;10>b;b++)c+=d[b];c+="...";for(b=d.length-10;b<d.length;b++)c+=d[b];document.body.innerHTML=c};</script>
<body onload="run()">
</body>
</html>
Editováno 14.11.2013 19:55
 
Nahoru Odpovědět 14.11.2013 19:55
Avatar
Kit
Redaktor
Avatar
Odpovídá na Silvinios
Kit:

Mně to ve FF a Chromiu vypíše jen

35661;4579776707...0420940313
Nahoru Odpovědět 14.11.2013 20:08
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Odpovídá na Kit
Ondřej Štorc:
Ale pozor, výsledné číslo bude mít přes 35.000 číslic. Na konci vypište počet číslic v X a prvních několik číslic zepředu a zezadu.
Nahoru Odpovědět 14.11.2013 20:10
Život je příliš krátký na to, abychom bezpečně odebírali USB z počítače..
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na Kit
Silvinios:

35661 je počet číslic a zbytek je prvních několik číslic zepředu a zezadu.

 
Nahoru Odpovědět 14.11.2013 20:11
Avatar
coells
Redaktor
Avatar
Odpovídá na Silvinios
coells:
:-)))

Moc hezký pokus, pobavil jsi mě. Mám rád podobné funkce.

Bohužel, jsou zde dva malé problémy:

  1. JavaScript není mezi povolenými jazyky z toho důvodu, že jsem nechtěl skriptovací jazyky kvůli mnohým zjednodušením
  2. výsledek není správný

Držím palce.

 
Nahoru Odpovědět 14.11.2013 20:13
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na coells
Silvinios:
  1. Vím a chápu. Toto bylo mimo soutěž. Chtěl jsem jen vyzkoušet, jak výpočetně náročná je moje řešení.
  2. Díky za upozornění, měl jsem tam chybu :-)
<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8" />
<title>Ukaž, co umíš? Faktoriál!</title>
</head>
<script type="text/javascript">function run(){for(var d=[0],c=[1],f=1;1E4>=f;f++){for(var a=0,b=c.length-1;0<=b;b--)a+=f*c[b],c[b]=a%10,a=Math.floor(a/10);for(;0<a;)c.unshift(a%10),a=Math.floor(a/10);for(var a=0,e=c.length-1,b=d.length-1;0<=b&&0<=e;)a+=d[b]+c[e],d[b]=a%10,a=Math.floor(a/10),b--,e--;for(;0<=e;)a+=c[e--],d.unshift(a%10),a=Math.floor(a/10);for(;0<a;)d.unshift(a%10),a=Math.floor(a/10)}c=d.length+" ";for(b=0;10>b;b++)c+=d[b];c+="...";for(b=d.length-10;b<d.length;b++)c+=d[b];document.body.innerHTML=c};</script>
<body onload="run()">
</body>
</html>
Editováno 14.11.2013 21:29
 
Nahoru Odpovědět 14.11.2013 21:28
Avatar
coells
Redaktor
Avatar
Odpovídá na Silvinios
coells:

Teď už je výsledek správný, gratuluji!

Ale algoritmus lze napsat ještě jednodušším způsobem, dokážeš na to příjít? :-)

 
Nahoru Odpovědět 14.11.2013 21:51
Avatar
Silvinios
Redaktor
Avatar
Odpovídá na coells
Silvinios:

To je pravda, nicméně asymptotická složitost je stejná jako v případě mého prvního naivního řešení :-)
Nejraději mám úlohy, kdy první "blbé" řešení nefunguje vůbec a je potřeba vymyslet něco lepšího.

<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8" />
<title>Ukaž, co umíš? Faktoriál!</title>
</head>
<script type="text/javascript">function run(){for(var c=[1],b=1E4;1<b;b--){for(var a=1,d=0;d<c.length;d++)a+=b*c[d],c[d]=a%10,a=Math.floor(a/10);for(;0<a;)c.push(a%10),a=Math.floor(a/10)}a=c.length+" ";for(b=c.length-1;b>c.length-11;b--)a+=c[b];a+="...";for(b=9;0<=b;b--)a+=c[b];document.body.innerHTML=a};</script>
<body onload="run()">
</body>
</html>
 
Nahoru Odpovědět 15.11.2013 7:12
Avatar
Panda38
Redaktor
Avatar
Panda38:

To je tak pitomé zadání že jsem si to musel také zkusit. :D V C trvá výpočet 2 sekundy (pole int po 5 číslicích). ... tedy snad jsem se nesekl v algoritmu :-)

Editováno 15.11.2013 11:07
 
Nahoru Odpovědět  +1 15.11.2013 11:05
Avatar
coells
Redaktor
Avatar
Odpovídá na Silvinios
coells:

Pro takhle malá čísla není důležitá asymptota, ale velikost konstanty. Ale řešení už je správné.

 
Nahoru Odpovědět 15.11.2013 13:28
Avatar
coells
Redaktor
Avatar
Odpovídá na Panda38
coells:

V C# trvá výpočet cca 0.5 sekundy (Core i5 2.8GHz) ;-)

Čistě pro zajímavost... Nedávno jsem pomáhal kamarádovi se zápočtovou úlohou a kód v C# byl asi o 10% rychlejší, než C-čkový kód pod GCC. Stejně tak Apple uvádí, že CLang compiler je o 20-50% rychlejší než GCC.

 
Nahoru Odpovědět  +1 15.11.2013 13:32
Avatar
Kit
Redaktor
Avatar
Odpovídá na coells
Kit:

Zkusím to napsat ve Fortranu, mělo by to být ještě o něco rychlejší.

Nahoru Odpovědět  ±0 15.11.2013 14:50
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
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 17 zpráv z 17.