FANDOM


http://www.progz.ru/forum/index.php?s=&showtopic=189&view=findpost&p=138559

Числа Хэмминга (gromozeka 11.4.2007, 22:17) - числа, которые можно представить в виде 2^i*3^j*5^k, где i,j и k >=0.
Начало последовательности - "1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36, 40, 45, 48, 50, 54, 60, 64, 72, 75, 80, 81, 90, 96, 100".

Хаскелль(пример, приведенный Эхудом Ламмом на лекции), из четырех строк кода, три - слияние отсортированных списков:

hamming = 1 : map (*2) hamming # map (*3) hamming # map (*5) hamming
    where xxs@(x:xs) # yys@(y:ys)
              | x==y = x : xs#ys
              | x<y  = x : xs#yys
              | x>y  = y : xxs#ys

Python(gromozeka), генератор:

import psyco
psyco.full()

def my_min(arr):
    j,m=0,arr[0]
    for i in xrange(len(arr)):
        if arr[i]<m: j,m=i,arr[i]
    return m,j

def ham():
    lst,ixs=[1],[0,0,0]
    yield 1
    while True:
        m,i=my_min([lst[ixs[0]]*2,lst[ixs[1]]*3,lst[ixs[2]]*5])
        if m!=lst[-1]:
            lst.append(m)
            yield m
        ixs[i]+=1

C++(pEtr0):

static const double a = log(3.0)/log(2.0);
static const double b = log(5.0)/log(2.0);

struct point {
    int x, y, z;
    point():x(0),y(0),z(0){};
    point(int _x, int _y, int _z):x(_x),y(_y),z(_z) {};
};

typedef std::map<double, point> point_map;
typedef std::pair<double, point> point_pair;

inline double f(point p) { return p.x + a * p.y + b * p.z; }

point hem(long n) {    
    long k = 0;
    point cp0, cp;    
    point_map border;
    border.insert(point_pair(f(cp0), cp0));
    
    while (k++ < n)    {
        cp0 = border.begin()->second;
        border.erase(border.begin());
        
        cp = point(cp0.x + 1, cp0.y, cp0.z);
        border.insert(point_pair(f(cp), cp));

        cp = point(cp0.x, cp0.y + 1, cp0.z);        
        border.insert(point_pair(f(cp), cp));

        cp = point(cp0.x, cp0.y, cp0.z + 1);        
        border.insert(point_pair(f(cp), cp));
    }
    return cp0;
}

Python(pEtr0):

import psyco
psyco.full()

import time
from bisect import *

def my_insert(arr, val, lo):
    k = bisect(arr, val, lo)
    if arr[k-1] <> val:
        arr.insert(k, val)
    return k 

def hem(n):    
    k, lst = 0, [1]        
    while k < n:      
        cp = lst[k]                                    
        my_insert(lst, cp*2, k)
        my_insert(lst, cp*3, k)
        my_insert(lst, cp*5, k)                        
        k+=1                            
    return cp

tbefore = time.time()
hp = hem(1000000)
tspan = time.time() - tbefore
print hp
print "In " + `tspan` + " seconds"

C++(D_K):

const double k32 = log(3.0)/log(2.0);
const double k52 = log(5.0)/log(2.0);

struct hem_num//число хемминга
{
    int i, j, k;//степени
    hem_num():i(0),j(0),k(0){};
    hem_num(int i_, int j_, int k_):i(i_),j(j_),k(k_){};
    double get_num()const{return i+k32*j+k52*k;}
    bool operator<(const hem_num&c)const{return get_num()<c.get_num();}//оператор < для set
};//hem_num

hem_num get_hem(long n)
{
    std::set<hem_num> gen;
    gen.insert(hem_num());    
    while(n---1)
    {
        hem_num num=*gen.begin();
        gen.erase(gen.begin());
        gen.insert(hem_num(num.i+1,num.j,num.k));
        gen.insert(hem_num(num.i,num.j+1,num.k));
        gen.insert(hem_num(num.i,num.j,num.k+1));
    }
    return *gen.begin();
}

C(D_K):

double k32;/* = log(3.0)/log(2.0);*/
double k52;/* = log(5.0)/log(2.0);*/
struct hem_num{int i, j, k;double n;};
struct hem_el{struct hem_num num;struct hem_el *parent,*less,*more;};
double get_num(struct hem_num*n){if(!n->n>0)n->n=n->i+k32*n->j+k52*n->k;return n->n;}
int less(struct hem_num*n1,struct hem_num*n2){return get_num(n1)<get_num(n2);}

struct hem_el *insert(struct hem_el**begin,struct hem_el**root,int i,int j,int k);
struct hem_num erase(struct hem_el**begin,struct hem_el**root,struct hem_el *el);
void clear(struct hem_el**root);

struct hem_num get_hem(long n)
{
    struct hem_el *begin=NULL,*root=NULL;    
    struct hem_num num;
    insert(&begin,&root,0,0,0);    
    while(n---1)
    {
        num=erase(&begin,&root,begin);
        insert(&begin,&root,num.i+1,num.j,num.k);
        insert(&begin,&root,num.i,num.j+1,num.k);
        insert(&begin,&root,num.i,num.j,num.k+1);
    }
    num=erase(&begin,&root,begin);
    clear(&root);
    return num;
}

K(Trurl):

ham:{[n]
  a: ,1.0
  x2:2.0; x3:3.0; x5:5.0 / float, чтобы не парицца с длинными целыми
  i2:0; i3:0; i5:0
  do[n
    t:&/(x2;x3;x5)  
    a,:t
    while[~x2>t; i2+:1; x2:2*a[i2]] 
    while[~x3>t; i3+:1; x3:3*a[i3]]
    while[~x5>t; i5+:1; x5:5*a[i5]]]
  t}

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.