Страниц: 1 [2]
  Печать  
Автор Тема: Треугольное дерево 2  (Прочитано 14244 раз)
0 Пользователей и 1 Гость смотрят эту тему.
Michael
Гость
Ответ #15 : Январь 16, 2013, 15:32:31 �

 
а чего это все дружно прекратили вычисления?
Ждём когда посчитаются нечётные цифры для 18 Smiley
Записан
iPhonograph
Гений-Говорун
*
Offline Offline

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #16 : Январь 17, 2013, 07:58:45 �

ну а чо 19 не выкладываете?
или вы все жертвы моды и вместо нормальных компьютеров у вас имеются только карманные пародии на эвм?
Записан

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
iPhonograph
Гений-Говорун
*
Offline Offline

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #17 : Январь 19, 2013, 16:00:56 �

чота всё затихло...
Показать скрытый текст
Записан

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
Michael
Гость
Ответ #18 : Январь 20, 2013, 05:20:11 �

moonlight, iPhonograph, здорово!  ПивоУ меня пока только 16, но хочу попробовать получить 23. Если получится, скажу. Если не получится, тоже скажу.  iPhonograph, у вас скорость какая-то запредельная.
Записан
iPhonograph
Гений-Говорун
*
Offline Offline

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #19 : Январь 20, 2013, 08:44:50 �

ок, ждём)))
кто вычислит 23 раньше всех - получит спасибку )))
для проверки правильности результата - вот чётные цифры
Показать скрытый текст
Записан

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
iPhonograph
Гений-Говорун
*
Offline Offline

Сообщений: 2100

СПАСИБО
-вы поблагодарили: 561
-вас поблагодарили: 1315

Дискоед


Просмотр профиля
Ответ #20 : Январь 20, 2013, 08:47:58 �

iPhonograph, у вас скорость какая-то запредельная.
да я понимаю, на что вы намекаете
типа, кто будет писать случайные цифры и выдавать их за результат, получит по наглой рыжей морде )))
могу дать исходник программы, чтобы вы запустили её на своём компе
Записан

"Было бы величайшей ошибкой думать" (с) В.И.Ленин, Полн. cобр. cоч., т.34, стр.375
Michael
Гость
Ответ #21 : Январь 20, 2013, 11:58:56 �

Да ну, iPhonograph, о чём вы говорите?   Плохо
У нас джентльменам верят на слово!  Пиво тут то мне карта и поперла(шутка)  Laugh
Тем более, что проверить отдельные цифры можно и без памяти. Чтение
Но у меня и в мыслях этого не было. Нет 
Я не про скорость написания, а про ваш секундомер. Я намекал на то что у вас должен быть классный алгоритм.  Браво
Когда всё кончится, конечно, интересно будет посмотреть.  Сдаюсь
А пока не надо.  Lips Sealed
Последнее редактирование: Январь 20, 2013, 12:44:11 от Michael Записан
or0ez
Новенький
*
Offline Offline

Сообщений: 5

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0


Просмотр профиля
Ответ #22 : Январь 08, 2020, 12:58:13 �

программа на С
Код:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 16
#define u16 unsigned short
#define u32 unsigned
#define max 20

typedef struct{u16 q[N];short nz;}u16N;
typedef struct{u16N u0,u1;}u16N2;
typedef struct{int n,g;}int2;
typedef struct{int len;int2* p;}int2arr;

u16N new16N(){u16N a;for(int i=0;i<N;i++)a.q[i]=0;a.nz=0;return a;}

int nZ(u16 q[N]){int cnt=N;for(int i=N-1;i>=0;i--)if(q[i])break;else cnt--;return cnt;}

u16N toU16N(u32 n){u16N a=new16N();a.q[0]=n;a.q[1]=(n>>16);a.nz=a.q[1]?2:(a.q[0]?1:0);return a;}

u16N sum(u16N a,u16N b){
    int m=a.nz>=b.nz?a.nz:b.nz;
    u16N s=new16N();
    u32 c=0;
    for(int i=0;i<m;i++){u32 t=c+a.q[i]+b.q[i];s.q[i]=t;c=t>>16;}
    if(c&&m<N)s.q[m]=1;
    s.nz=nZ(s.q);
    return s;
}

int cmp(u16N a, u16N b){
    int s=a.nz-b.nz;
    if(s)return s;
    for(int i=a.nz-1;i>=0;i--)if(s=a.q[i]-b.q[i])return s;
    return 0;
}

u16N inv(u16N a){
    u16N b;
    for(int i=0;i<N;i++)
    b.q[i]=~a.q[i];
    b.nz=nZ(b.q);
    return b;
}

u16N subt(u16N a, u16N b){return sum(a,sum(inv(b),toU16N(1)));}

u16N shL0(u16N a,int n){
    u16N b=new16N();
    u16 c=0;
    for(int i=0;i<a.nz;i++){u32 r=c|((u32)a.q[i]<<n);b.q[i]=r;c=r>>16;}
    if(a.nz<N)b.q[a.nz]=c;
    b.nz=nZ(b.q);
    return b;
}

u16N shL(u16N a,int n){
    u16N b=shL0(a,n&0xf);
    int n1=n>>4;
    if(n1)for(int i=a.nz;i>=0;i--){int j=i+n1;if(j<N)b.q[j]=b.q[i];if(i<N)b.q[i]=0;}
    b.nz=nZ(b.q);
    return b;
}

u16N shR(u16N a){
    u16N b=new16N();
    for(int i=a.nz-1;i>=0;i--){u32 u=(i==a.nz-1?0:a.q[i+1]);u32 w=(u<<16)|a.q[i];b.q[i]=(w>>1);}
    b.nz=nZ(b.q);
    return b;
}

int max1(u16N a){
    int k=-1;
    if(a.nz){for(int i=15;i>=0;i--)if((a.q[a.nz-1]>>i)&1){k=i;break;}k+=(a.nz-1)<<4;}
    return k;
}

u16N2 div2(u16N a,u16N b){
    u16N2 res;
    res.u0=new16N();
    int d=max1(a)-max1(b);
    if(d<0){res.u1=a;return res;}
    u16N bb=shL(b,d);
    if(cmp(a,bb)>=0){res.u0=toU16N(1);a=subt(a,bb);}
    while(cmp(bb,b)){
        bb=shR(bb);
        res.u0=shL(res.u0,1);
        int k=cmp(a,bb);
        if(k>=0){if(!res.u0.nz)res.u0.nz=1;res.u0.q[0]|=1;a=subt(a,bb);}
    }
    res.u1=a;
    return res;
}

void show(u16N a){
    if(!a.nz){printf("0\n");return;}
    int d[(int)(N*1.25)+1];
    int cnt=0;
    u16N b=toU16N(1000000);
    while(a.nz){u16N2 c=div2(a,b);d[++cnt-1]=c.u1.q[0]+((u32)c.u1.q[1]<<16);a=c.u0;}
    printf("%d",d[cnt-1]);
    for(int i=cnt-2;i>=0;i--)printf(" %06d",d[i]);
}

int2arr f(int n,int l){
    int q[max-1];
    int cnt=0;
    for(int i=0;i<l;i++)
        if((n>>i)&1)q[++cnt-1]=i;
    int q1[max],s[max];
    int cnt1=0;
    for(int i=0;i<cnt;i++)
        if(i==0){q1[0]=q[0];q1[1]=q[0]+1;s[0]=s[1]=1;cnt1=2;}
        else{
            if(q[i]==q1[cnt1-1])s[cnt1-1]++;
            else{q1[++cnt1-1]=q[i];s[cnt1-1]=1;}
            q1[++cnt1-1]=q[i]+1;s[cnt1-1]=1;
        }
    int2arr a;
    a.len=1<<cnt1;a.p=(int2*)malloc(a.len*sizeof(int2));
    for(int i=0;i<a.len;i++){
        int g=0;int n=0;
        for(int j=0;j<cnt1;j++){int k=(i>>j)&1;n|=k<<q1[j];if(k&&s[j]>1)g++;}
        a.p[i].n=n;a.p[i].g=g;
    }
    return a;
}

char* hms(char* time){
    char* hms=(char*)malloc(9*sizeof(char));
    for(int i=0;i<8;i++)hms[i]=time[i+11];
    hms[8]='\0';
    return hms;
}

int main(){
    printf("max=%d\n\n",max);
    int l=1;
    u16N* m=(u16N*)malloc(2*sizeof(u16N));
    m[0]=toU16N(0);m[1]=toU16N(1);
    while(l<max){
        int size=1<<l;
        int size1=1<<(l+1);
        u16N* m1=(u16N*)malloc(size1*sizeof(u16N));
        for(int i=0;i<size1;i++)m1[i]=new16N();
        for(int i=0;i<size;i++){
            int2arr a=f(i,l);
            for(int j=0;j<a.len;j++)m1[a.p[j].n]=sum(m1[a.p[j].n],shL0(m[i],a.p[j].g));
            free(a.p);
        }
        free(m);m=m1;l++;
        u16N s=new16N();
        for(int i=0;i<size1;i++)s=sum(s,m1[i]);
        int tm=time(0);
        printf("%s",hms(ctime(&tm)));
        printf("%4d = ",l);
        show(s);printf("\n\n");
    }
    free(m);
    return 0;
}
Записан
or0ez
Новенький
*
Offline Offline

Сообщений: 5

СПАСИБО
-вы поблагодарили: 0
-вас поблагодарили: 0


Просмотр профиля
Ответ #23 : Январь 12, 2020, 14:15:46 �

Извиняюсь, в функции main() должно быть не shL0, а shL. Ошибка проявляется на 19, 20.
Записан
Страниц: 1 [2]
  Печать  
 
Перейти в: