Názory k článku
Studentská soutěž v programování PilsProg

Když jsem se podíval na úlohy z minulého ročníku, tak mi přišlo, že použít na ně Javu, C, nebo Pascal je pěkná bejkárna. Mimo to zadání http://pilsprog.fav.zcu.cz/ulohy/0820.pdf obsahuje už v zadání chybu. Mám dvě baktérie, po půl hodině mám 4 a po další půlhodině (celkově po hodině) mám 4 baktérie jelikož původní bakterie "umírá současně se vznikem druhé bakterie". Mimoto zadání přímo říká, že má být vrácen počet žijících potomků. Původní bakterie nejsou potomci. Teda, úroveň soutěže dosti mizerná.

Hmm tak včera cestou domů mě došlo, že je to správně, zapomněl jsem na potomky, kteří vzniknou z první generace potomků. Nicméně to ilustrační řešení má exponenciální složitost. Navíc to učí řešitele řešit nevhodným způsobem. Najdi něco čemu se to podobá - fibonačiho posloupnost, tu vyřeš (ještě ke všemu špatně) a s výsledkem udělej nějakou operaci aby to odpovídalo zadání. Přitom ta úloha jde tak krásně řešit i bez znalosti fibonačiho posloupnosti a pěkně přímočaře. Přímočaré řešení v erlangu:

% bakterie(N, T) -> R
% kde N je počet bakterií na začátku,
%     T je počet hodin experimentu
%     R výsledek - počet bakterií na konci experimentu
bakterie(N, T) ->
  % Budeme simulovat po půlhodinách
  % bakterie mohou být na konci každé půlhodiny jen dvou druhů
  % A - bakterie staré půl hodiny
  % B - čerstvě narozené bakterie
  % počet kroků simulace bude T*2
  % výsledek dostaneme zavoláním funkce
  % bakterie(A, B, K)
  bakterie(0, N, 2*T).

% bakterie(A, B, K) -> R
% kde A je počet půl hodiny starých bakterií
%     B je počet nových bakterií
%     K je počet půlhodin do konce experimentu
%     R je počet bakterií na konci experimentu
bakterie(A, B, 0) ->
  % počet kroků simulace je nula
  % tedy vrátíme počet žijících bakterií
  A+B;
bakterie(A, B, K) when K>0 ->
  % na konci půlhodiny bude
  % B půlhodiny starých bakterií
  % a A+B nově narozených bakterií
  % (půlhodiny staré bakterie budou staré hodinu
  % rozdělí se na A bakterií a zemřou -> A,
  % nové bakterie se poprvé rozdělí a vznikne B)
  bakterie(B, A+B, K-1).

S vynecháním komentářů celý program:

-module(bakterie).

-export([bakterie/0, start/0]).

start() -> bakterie(), init:stop().

bakterie() ->
    {ok, [N, T]} = io:fread([], "~d ~d"),
    R = bakterie(N, T),
    ok = io:format("~b~n", [R]).

bakterie(N, T) -> bakterie(0, N, T * 2).

bakterie(A, B, 0) -> A + B;
bakterie(A, B, K) when K > 0 ->
    bakterie(B, A + B, K - 1).

Dtto v C:

#include <stdio.h>
int Bakterie(int stare, int nove, int pulh){
	return pulh > 0
		? Bakterie(nove, nove+stare, pulh - 1)
		: nove+stare;
}
int main(void){
	int cas, pocet;
	scanf("%d %d", &pocet, &cas);
	printf("%d\n", Bakterie(0, pocet, cas * 2));
	return 0;
}

Stačí srovnat se vzorovou implementací a rozdíl je vidět na první pohled. "Ukázkové" řešení je O(N^2) time a O(N) space, používá jakéhosi vedlejší znalosti - komplikované, hnusné a nečitelné. Uvedené řešení je proti tomu KISS, tedy naprosto přímočaré bez nutnosti vědět o existenci nějaké fibonačiho řady. Prostě řeší přímo zadání. Je navíc O(N) time a O(1) space. Existuje ještě O(logN) řešení, ale to bych sem netahal (viz SICP tuším druhá kapitola). V praxi se setkávám právě s tím, že lidi ze škol nedokáží řešit problém přímočaře a nekomplikovaně. Prostě KISS! Přílišná akademičnost škodí. Kdyby raději na školách učili třeba podle SICP, sice je to akademické, ale KISS. Tisíckrát radši, než tyhle překomplikované a nesmyslné sajrajty, které neučí hlavně programátorsky myslet.

Vsetci zaujemcovia o sutazenie v exotickych jazykoch, kuknite sem: http://www.spoj.pl/
Ide o velmi kvalitnu stranku obsahujucu hromadu dobrych zadani a zacitujem: "support for more than 30 programming languages and compilers, including C, C++, Pascal, JAVA, C#, Perl, Python, Ruby, Haskell, Ocaml, and esoteric languages."

Tak jsem tam kuknul a nemůžu najít kompletní seznam těch více než jazyků abych si ověřil, že je tam ten můj oblíbený (dc ;-)).

A proč dc, protože třeba pro VFMUL těžko někdo překoná tohle řešení:

?[?*pr1-d0<a]dsax

Ked si das submit, tak tam mas pulldown menu so zoznamom.

Akorát, že ten seznam je pro každou úlohu jiný.

A kdo má rád spíš příklady na zamyšlení než tupé bastlení kódu, může zkusit KSP - Korespondenční Seminář z Programování (http://ksp.mff.cuni.cz/). Vedle všech rozumných programovacích jazyků (včetně Brainfucku :D) je možné řešení popsat i česky nebo anglicky a možná se najde někdo, kdo by dokázal opravit řešení i v jiném přirozeném jazyce.

Je aj slovenska verzia KSP (http://www.ksp.sk/). Odporucam taktiez sutaz IPSC (tamtez), kde sa skutocne ukaze schopnost riesit problemy.

A este by som si prihrial vlastnu polievocku: http://palma.strom.sk/ Urcene pre stredoskolakov, ale casto tie priklady potrapia aj vysokoskolakov a o takzvanych "profesionaloch" ani nehovorim :) A mozno niekoho zaujme aj uz momentalne mrtvy projekt http://www.itliga.sk/