Re: 22: 345532572678 43191857688
От: Pushkin Россия www.linkbit.com
Дата: 14.03.03 09:26
Оценка: 53 (3)
Вот до такой строчки мой комп додумался сегодня ночью Не сам, конечно, а после сильной переработки кода. По сравнению с ранее опубликованным всё бегает раз в 15 быстрее. Прога по-прежнему нагружает только проц. Можно перевести её в низкий приоритет и комфортно работать на компе. И лет через 8 я достигну инетовского рекорда 28

Замечательно, что ускорение совпало с сильным упрощением текста. Пропало сложное и немного искусственное понятие "кодирующей последовательности". Две функции слились в одну весьма прозрачную, рекурсивную, как и просилось сразу. Она ровно по разу обходит все полимино порядка n и считает их, а заодно (почти без потерь времени) и все меньшие порядки.

После ускорения перебора в полный рост встал вопрос об ускорении отсеивания отражений (который раньше был не критичен). Здесь крайне своевременной оказалась идея МихаилаП о "центре тяжести". (В моём воспалённом мозгу она тоже бродила, но давно и не столь ясно.) Забавно, что при внешней простоте, идея потребовала очень аккуратной реализации — я долго не мог добиться одновременно верного ответа и ясного понимания, что делаю. (Хотя порознь было много раз )

Ниже приведён код, который можно откомпилировать и поиграться (даже порисовать). Я нахожу его совершенным и потому больше не буду терроризировать ни себя ни вас. Если кому-то удастся серьёзно ускорить, оценку обещаю Пояснять код нет большого смысла, тем более, что там половина строк комментарии.

// Polymino.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <stdio.h>
#include <memory.h>
#include <string.h>
#include <stdlib.h>

//максимальный порядок полимино 
#define N 33 //странная цифра, но почему нет :-)

//если не жалко времени, можно рисовать полимино
//либо для всех порядков либо только для старшего 
//причём выводим не в банальный столбик, а в строчку ;-)
//#define NEED_DRAW_ALL 
//#define NEED_DRAW_HIGH
#if defined NEED_DRAW_ALL || defined NEED_DRAW_HIGH
char out[N+1][80]={0};
#endif

//4 возможных направления движения
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

char board[N+1][2*N-2];
// полимино в раскодированном виде, удобном для отражений
//поле битвы и результат работы основной функции Enum()
//матрица [y][x], в ячейках одно из 3-х значений:
//-1 - запрет - точно нет заполненной клетки
// 1 - стоит - точно есть заполненная клетки
// 0 - туман - пока неизвестно, есть ли клетка
int x1,x2,y1,y2;//границы полимино, лежащего в board[][]
int x0,y0;      //а здесь лежать суммы всех x и y для вычисления среднего

//довесок к board - перспективы заполнения
int fifo_x[N-1]; 
int fifo_y[N-1];
int fifo_tail=0;
int fifo_head=0;

int n; //порядок полимино (цель)
int k; //сколько клеток уже поставлено
__int64 countTotal[N], countMain[N];//здесь будем считать, 
//причём сразу оба (всего и без отражений) и для всех порядков

//вспомогательная функция для отсеивания отражений
bool IsMainBoard();

//основная рекурсивная функция
//в результате её работы вглубь от k=0 до k=n
//в board последовательно перебывают ровно по одному разу (!)
//все полимино порядка не больше n (вообще все, с отражениями)
//стартуя с того, что сейчас лежит в board+fifo+k
//подсчитывет число продолжений до порядка n
//в результате board+fifo+k остаётся без изменений (!)
void Enum()
{
    if(k==0) //первый вход
    {
        memset(countTotal,0,sizeof(countTotal));
        memset(countMain ,0,sizeof(countMain ));
        
        memset(board, 0,sizeof(board));               //заполняем всё туманом
        memset(board,-1,sizeof(board[0][0])*(3*N-4)); //заполняем начало запретами

        //поставим первую клетку
        fifo_x[0]=N-2;
        fifo_y[0]=1;
        fifo_tail=1;
        fifo_head=0;
        board[fifo_y[0]][fifo_x[0]]=1; 
        x0=x1=x2=fifo_x[0];
        y0=y1=y2=fifo_y[0];
        
        k=1;
        Enum();
        k=0;                  //board+fifo можно не восстанавливать - 
        return;               //при следующем входе всё равно обнулим
    }
        
    int save_fifo_head=fifo_head; //сохраним чтобы потом вернуть

    while(fifo_tail>fifo_head)    //перебор возможностей поставить 
    {
        for(int d=0;d<4;d++)  //ищем самую первую возможность 
        {
            int y=fifo_y[fifo_head]+dy[d];
            int x=fifo_x[fifo_head]+dx[d];
                
            if(board[y][x]==0)     //точка в тумане - нашли !
            {                
                board[y][x]=1; //сначала попробуем сюда поставить
                k++;
            
                int save_y2=y2;//поправим границы
                int save_x1=x1;
                int save_x2=x2;
                if(y>y2) y2=y;
                if(x<x1) x1=x;
                if(x>x2) x2=x;
                x0+=x;
                y0+=y;
                
                //помещаем поставленную клетку в очередь 
                fifo_y[fifo_tail]=y;
                fifo_x[fifo_tail]=x;
                fifo_tail++;
            
                countTotal[k]++;
                if(IsMainBoard())
                {
                    countMain[k]++;

#ifdef NEED_DRAW_HIGH
                    if(k==n)
#endif
#if defined NEED_DRAW_ALL || defined NEED_DRAW_HIGH
                    {
                        if(strlen(out[0])+n+1>75)
                        for(int y=0;y<n+1;y++)
                            printf("%s\n",out[y]),out[y][0]=0;
                        for(int y=1;y<n+1;y++)
                        for(int x=0;x<n+1;x++)
                            strcat(out[y-1],board[y][x1+x]==1? "\1":" ");
                    }
#endif
                }
                                
                if(k<n)         //продолжение банкета
                    Enum(); //сколько развитий при поставленной

                //теперь попробуем наоборот запретить
                board[y][x]=-1;    
                k--;
                
                //вернём границы
                y2=save_y2;
                x1=save_x1;
                x2=save_x2;
                x0-=x;
                y0-=y;
                
                //убираем из очереди 
                fifo_tail--;
                
                Enum(); //сколько развитий при запрещённой

                //наконец, не забудем отыграть всё обратно
                board[y][x]=0;    
                fifo_head=save_fifo_head;

                return; //никакого цикла реально нет - 
                //нашли первую возможность и либо ставим либо нет 
            }
        }
        
        //из этой фишки идти уже некуда - идём к следующей
        fifo_head++; 
    }

    //не нашли ни одной возможности, куда бы поставить 
    //возвращаем всё как было и уходим 
    fifo_head=save_fifo_head;

#if defined NEED_DRAW_ALL || defined NEED_DRAW_HIGH
    if(k==1)//конец игре - распечатаем остаток
        for(int y=0;y<n+1;y++)
            printf("%s\n",out[y]),out[y][0]=0;
#endif
}


//возвращает true если в board находится "правильно" повёрнутая конфигурация 
//"правильность" можно задавать довольно произвольно, важно чтобы однозначно - 
//среди всех 8 отражений должно быть ровно 1 правильное
//эта реализация обычно проверяет попадание центра тяжести в нужную восьмушку
//и только в пограничных случаях врубает полную мощь вычислений
//можно попробовать поулучшать, но ускорить вдвое - это вряд ли 
bool IsMainBoard()
{
    int bx=x0*2-(x1+x2)*k;
    int by=y0*2-(y1+y2)*k;

    if(bx==0 && by<0)
    {
        //проверка, а не симметричная ли фигура относительно вертикали
        int ny=y2-y1, nx=x2-x1;
        for(int y=0;y<=ny;y++)
        for(int x=0;x<(nx+1)/2;x++)
        {
            if(board[y1+y][x1+x]==1 && board[y1+y][x1+nx-x]!=1)
                return true;
            if(board[y1+y][x1+x]!=1 && board[y1+y][x1+nx-x]==1)
                return false;
        }
        return true;
    }

    else if(bx<0 && by==bx)
    {
        //проверка, а не симметричная ли фигура относительно диагонали
        int ny=y2-y1, nx=x2-x1;
        if(nx<ny)
            return false;
        if(nx>ny)
            return true;

        for(int y=0;y<=ny;y++)
        for(int x=0;x<y;x++)
        {
            if(board[y1+y][x1+x]==1 && board[y1+x][x1+y]!=1)
                return true;
            if(board[y1+y][x1+x]!=1 && board[y1+x][x1+y]==1)
                return false;
        }
        return true;
    }

    else if(bx==0 && by==0)
    {
        int ny=y2-y1, nx=x2-x1;
        if(nx<ny)
            return false;

        int reflect_impossible[2][2][2]={0};//[x<->y][y<->ny-y][x<->nx-x]
        
        for(int y=0;y<=ny;y++)
        for(int x=0;x<=nx;x++)
        {
            if(1==board[y1+y][x1+x])
            {
                 if(1!=board[y1+y   ][x1+nx-x])   reflect_impossible[0][0][1] =1;
                 if(1!=board[y1+ny-y][x1+x   ])   reflect_impossible[0][1][0] =1;
                 if(1!=board[y1+ny-y][x1+nx-x])   reflect_impossible[0][1][1] =1; if(nx==ny)  {
                 if(1!=board[y1+x   ][x1+y   ])   reflect_impossible[1][0][0] =1;
                 if(1!=board[y1+x   ][x1+nx-y])   reflect_impossible[1][0][1] =1;
                 if(1!=board[y1+nx-x][x1+y   ])   reflect_impossible[1][1][0] =1;
                 if(1!=board[y1+nx-x][x1+nx-y])   reflect_impossible[1][1][1] =1;             }
            }
            else if(1==board[y1+y   ][x1+nx-x] && reflect_impossible[0][0][1]==0 ||
                    1==board[y1+ny-y][x1+x   ] && reflect_impossible[0][1][0]==0 ||
                    1==board[y1+ny-y][x1+nx-x] && reflect_impossible[0][1][1]==0 || nx==ny && (
                    1==board[y1+x   ][x1+y   ] && reflect_impossible[1][0][0]==0 ||
                    1==board[y1+x   ][x1+nx-y] && reflect_impossible[1][0][1]==0 ||
                    1==board[y1+nx-x][x1+y   ] && reflect_impossible[1][1][0]==0 ||
                    1==board[y1+nx-x][x1+nx-y] && reflect_impossible[1][1][1]==0 )            )
            {
                return false;
            }
        }
        return true;
    }

    //почти всегда доходим до этого места, особенно для больших порядков

    if(bx<0 && by<bx)
        return true; //здесь выходим примерно 1/8 случаев

    return false; //здесь выходим примерно в 7/8 случаев
}


int main(int argc, char* argv[])
{
    while(1)
    {
        char s[80];
        gets(s);
        n=atoi(s);
        if(n<1 || n>31)
        {
            printf("Enter a polyominoe size 0<N<32\n\n");
            continue;
        }
        printf("--\n");

        k=0;Enum();
        
        printf("\n");
        for(k=2;k<=n;k++)
        {
            char s1[80],s2[80];
            _i64toa(countTotal[k],s1,10);
            _i64toa(countMain [k],s2,10);
            printf("%2d: %16s %16s\n",k,s1,s2);
        }
        printf("\n\n");
    }

    while(getchar());
    return 0;
}
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.