Názor ke zprávičce Studentská soutěž v programování PilsProg od Pichi - Hmm tak včera cestou domů mě došlo, že...

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.