Знакомство с Erlang. Часть 3.

Решение problem2 на projecteuler

Вариант 1

-module(problem002).
-export([solve/1, fib_ex/4]).

fib_ex(Max, Sum, P, PP) ->
    Next = P + PP,
    if
        Next < Max, Next rem 2 == 0 -> fib_ex(Max, Next + Sum, Next, P);
        Next < Max, Next rem 2 == 1 -> fib_ex(Max, Sum, Next, P);
        Next >= Max -> Sum
    end.

solve(Max) ->
    fib_ex(Max, 0, 1, 1).

Вариант 2

-module(problem002).
-export([solve/1, fib_ex/4]).

fib_ex(Max, Sum, P, PP) when P + PP >= Max ->
    Sum;
fib_ex(Max, Sum, P, PP) ->
    Next = P + PP,
    case Next rem 2 of
        0 -> fib_ex(Max, Next + Sum, Next, P);
        1 -> fib_ex(Max, Sum, Next, P)
    end.

solve(Max) ->
    fib_ex(Max, 0, 1, 1).

Знакомство с Erlang. Часть 2.

Вычисление факториала

Книжный пример. Тут все просто и понятно:

factorial(0) -> 1;
factorial(N) ->
    N * factorial(N-1).

Вычисление чисел Фибоначчи

Пишу реализацию в лоб в надежде, что интерпретатор Erlang внутри реализует DP.

fib(0) -> 0;
fib(1) -> 1;
fib(N) ->
    fib(N-1) + fib(N-2).

Но уже при N=50 не могу дождаться результата. Выходит, никакого DP внутри нет, интерпретатор тупо уходит в рекурсию. Экспоненциальная сложность. Конечно, можно исправить на хвостовую рекурсию, но это уже не так красиво:

fib_ex(1) -> {1, 0};
fib_ex(2) -> {1, 1};
fib_ex(Num) ->
    {P, PP} = fib_ex(Num-1),
    {P + PP, P}.

fib(N) ->
    {P, _PP} = fib_ex(N),
    P.

Знакомство с Erlang. Часть 1.

Уже 5 лет разрабатываю на С++. И до сих пор не хочу ни на что его менять. Но вдруг появилось желание познакомиться с функциональными языками, в частности Erlang. На Yac2011 один умный дядечка призывал изучать другие языки программирования, т.к. это помогает взглянуть на вещи под другим углом. Ведь простые в одних языках конструкции, могут быть сложно выразимы в других. На эту тему есть отличное видео на TED (правда, про natural languages, но один в один):

Вдохновленный этими идеями и, несмотря на покручивания у виска коллег, начал читать Программирование в Erlang. Ф. Чезарини, С. Томпсон. После первых 2-3 глав выбрал в качестве helloworld решить problem1 на projecteuler на Erlang. Минут через 30 насилия над моим императивным мозгом выдавил:

-module(problem001).
-export([solve/1]).

% solve routine calculates sum of all natural numbers <= N which are multiples of 3 or 5

solve(N) when N == 0 ->
    0;
solve(N) when N rem 3 == 0 ->
    N + solve(N-1);
solve(N) when N rem 5 == 0 ->
    N + solve(N-1);
solve(N) ->
    solve(N-1).

highlight.js

Давно хотел научиться по-человечески подсвечивать код на своих страничках. Взял первое попавшееся - highlight.js

Как пользоваться:

1. Добавляем перед </head> строчки:

   <link rel="stylesheet" href="http://yandex.st/highlightjs/7.3/styles/default.min.css">
   <script src="http://yandex.st/highlightjs/7.3/highlight.min.js"></script>
   <script type="text/javascript">
       hljs.initHighlightingOnLoad();
   </script>

2. Вместо default.min.css можно указать какой-нибудь другой стиль. Например, solarized_dark.min.css. Список стилей можно посмотреть здесь
3. Оборачиваем блоки с кодом в пару тегов <pre><code> ... </code></pre>. Язык определяется автоматически.

Примеры:

Python

#!/usr/bin/env python
import sys, os

def foo():
    pass

C++

#include <iostream>
using namespace std;

int main() {
    cout << "Hello, World!" << endl;
    return 0;
}