学食のラーメンは

不味い。

なんで、あんなに、不味いのか。。。

それはそうと、昨日のソース

見苦しいところもありますが、ご勘弁を

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

class Symbol {
public:
    double p;
    int len;
    int idx;
    vector<int> f;
    Symbol() { p=0.0; len=0; idx = -1; }
    bool operator<(const Symbol& obj) const { return p > obj.p; }
};

double p[] = {0.8, 0.2};
const int NUM = 20;
vector<Symbol> t;

void init()
{
    Symbol tmp;
    for (int i=0;i < sizeof(p)/sizeof(double);i++) {
        tmp.p = p[i];
        tmp.idx = i;
        t.push_back(tmp);
    }
}

void calc_p()
{
    vector<Symbol> tmp;
    Symbol s;
    int n = sizeof(p)/sizeof(double);

    for (int i=0;i < t.size();i++) {
        for (int j=0;j < n;j++) {
            s.p = t[i].p * p[j];
            s.idx = i * n + j;
            tmp.push_back(s);
        }
    }
    t = tmp;
}

void add_len(Symbol& s)
{
    for (int i=0;i < s.f.size();i++)
        t[s.f[i]].len++;
}

double calc_l()
{
    priority_queue<Symbol> pq;
    Symbol tmp, sum;
    double length = 0.0;

    for (int i=0;i < t.size();i++)
        pq.push(t[i]);

    while (pq.size() != 1) {
        sum.f.clear();
        sum.p = 0.0;
        for (int i=0;i < 2;i++) {
            tmp = pq.top();
            pq.pop();
            sum.p += tmp.p;
            if (tmp.idx == -1)
                for (int j=0;j < tmp.f.size();j++)
                    sum.f.push_back(tmp.f[j]);
            else
                sum.f.push_back(tmp.idx);
        }
        add_len(sum);
        pq.push(sum);
    }

    for (int i=0;i < t.size();i++)
        length += t[i].p * t[i].len;
    return length;
}

int main()
{
    init();

    cout << "平均符号長(1次) : " << calc_l() << endl;
    for (int i=2;i <= NUM;i++) {
        calc_p();
        cout << "平均符号長("<<i<<"次) : " << calc_l()/i << endl;
    }

    return 0;
}