Алгоритм - Общие вопросы C/C++

JoSkream · 04.06.2009, 23:19

Здравствуйте
прошу помоч написать алгоритм к ниже приведенному коду
так же дам условие задачи
=============Текст задачи==============
Из какого наименьшего числа коней можно создать активный эскадрон?
решить задачу численным методом.
Пояснения:
Эскадрон -- Группа коней , размещенный на бесконечной шахметной доске
Активный Эскадрон -- это эскадрон, который может сделать любое число ходов на шахматной доске и занять одним из своих коней любое поле доски, не оставляя ни на один ход ни одного коня без защиты.

JoSkream · 04.06.2009, 23:20

Код:

#define STARTX 1000
#define STARTY 1000
#define MAXHORSE 100
#define MINHORSE 3
#define HISTORY 100
#define DEPTH 100
#include <stdio.h>
#include <conio.h>

struct horse
    {
    int x;
    int y;
    int history[2][HISTORY];
    int sizeHistory;
    };

bool checkStep(horse * masHorse, int amountHorse, int step_x, int step_y)
    {
    int i;
    for(i=0; i<amountHorse; i++)
        {
        if( (masHorse[i].x == step_x) && (masHorse[i].y == step_y) )
            {
            
            return false;
            }
        }
    return true;
    }
    
bool checkHistory(horse * oneHorse, int step_x, int step_y)
    {
    int i;
    for(i=0; i<oneHorse->sizeHistory; i++)
        {
        if( (step_x == oneHorse->history[0][i]) && (step_y == oneHorse->history[1][i]) )
            {
            return false;
            }
        }
    return true;
    }
    

bool checkMtrix(horse * masHorse, int amountHorse, bool * mtrix, int mtrix_x, int mtrix_y)
    {
    int min_x, max_x, min_y, max_y, i;
    min_x = max_x = masHorse[0].x;
    min_y = max_y = masHorse[0].y;
    for(i=1; i<amountHorse; i++)
        {
        if(masHorse[i].

 *Nix (00:59:25 5/06/2009)
x<min_x) min_x = masHorse[i].x;
        if(masHorse[i].x>max_x) max_x = masHorse[i].x;
        if(masHorse[i].y<min_y) min_y = masHorse[i].y;
        if(masHorse[i].y>max_y) max_y = masHorse[i].y;
        }
    max_x -= min_x;
    max_y -= min_y;
    if( (max_x == mtrix_x) && (max_y == mtrix_y) )
        {
        bool * mtrixNow = new bool[max_x*max_y];
        for(i=0; i<max_x*max_y; i++)
            {
            mtrixNow[i] = false;
            }
        for(i=0; i<amountHorse; i++)
            {
            mtrix[(masHorse[i].x-min_x)*(masHorse[i].y-min_y)] = true;
            }
        for(i=0; i<max_x*max_y; i++)
            {
            if( mtrix[i] != mtrixNow[i] )
                {
                delete [] mtrixNow;
                return false;
                }
            }
        delete [] mtrixNow;
        return true;
        }
    }
    
bool checkProtect(horse * masHorse, int amountHorse)
    {
    int i,j;
    bool stat;
    for(i=0; i<amountHorse; i++)
        {
        stat = false;
        for(j=0; j<amountHorse; j++)
            {
            if( ( masHorse[j].x-2 == masHorse[i].x) && (masHorse[j].y-1 == masHorse[i].


y) )
                {
                stat = true;
                break;
                }
            if( ( masHorse[j].x-1 == masHorse[i].x) && (masHorse[j].y+3 == masHorse[i].y) )
                {
                stat = true;
                break;
                }
            if( ( masHorse[j].x+3 == masHorse[i].x) && (masHorse[j].y-1 == masHorse[i].y) )
                {
                stat = true;
                break;
                }
            if( ( masHorse[j].x-1 == masHorse[i].x) && (masHorse[j].y-2 == masHorse[i].y) )
                {
                stat = true;
                break;
                }
            if( ( masHorse[j].x-2 == masHorse[i].x) && (masHorse[j].y+1 == masHorse[i].y) )
                {
                stat = true;
                break;
                }
            if( ( masHorse[j].x+1 == masHorse[i].x) && (masHorse[j].y+3 == masHorse[i].y) )
                {
                stat = true;
                break;
                }
            if( ( masHorse[j].x+3 == masHorse[i].x) && (masHorse[j].y+1 == masHorse[i].y) )
                {
                stat = true;
                break;
           


  }
            if( ( masHorse[j].x+1 == masHorse[i].x) && (masHorse[j].y-2 == masHorse[i].y) )
                {
                stat = true;
                break;
                }
            }
        if(!stat) return false; 
        }
    }
    
int step(horse * masHorse, int amountHorse, bool * mtrix, int mtrix_x, int mtrix_y, int depth)
    {
    int i,j, newX, newY, oldX, oldY, result;
    for(i=0; i<amountHorse; i++)
        {
        for(j=0; j<amountHorse; j++)
            {
            oldX = masHorse[j].x;
            oldY = masHorse[j].y;
            newX = masHorse[j].x-2;
            newY = masHorse[j].y-1;
            masHorse[j].x = newX;
            masHorse[j].y = newY;
            if( checkProtect(masHorse, amountHorse) )
                {
                masHorse[i].x = oldX;
                masHorse[i].y = oldY;
                if( checkStep(masHorse, amountHorse, newX, newY) && checkHistory(&masHorse[i], newX, newY) )
                    {
                    masHorse[j].x = newX;
                    masHorse[j].y = newY;
                    if( checkMtrix(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y) )

JoSkream · 04.06.2009, 23:20

Код:

    {
                        return amountHorse;
                        }
                    
                    if(depth)
                        {
                        masHorse[j].history[0][masHorse[j].sizeHistory] = newX;
                        masHorse[j].history[1][masHorse[j].sizeHistory] = newY;
                        masHorse[j].sizeHistory++;
                        if(result = step(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y, (depth-1) ) )
                            {
                            return result;
                            }
                        }
                    }
                }
            masHorse[i].x = oldX;
            masHorse[i].y = oldY;
            
            newX = masHorse[j].x-1;
            newY = masHorse[j].y+3;
            masHorse[j].x = newX;
            masHorse[j].y = newY;
            if( checkProtect(masHorse, amountHorse) )
                {
                masHorse[i].x = oldX;
                masHorse[i].y = oldY;
                if( checkStep(masHorse, amountHorse, newX, newY) && checkHistory(&masHorse[i], newX, newY) )
                    {
                    masHorse[j]

.x = newX;
                    masHorse[j].y = newY;
                    if( checkMtrix(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y) )
                        {
                        return amountHorse;
                        }
                    
                    if(depth)
                        {
                        masHorse[j].history[0][masHorse[j].sizeHistory] = newX;
                        masHorse[j].history[1][masHorse[j].sizeHistory] = newY;
                        masHorse[j].sizeHistory++;
                        if(result = step(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y, (depth-1) ) )
                            {
                            return result;
                            }
                        }
                    }
                }
            masHorse[i].x = oldX;
            masHorse[i].y = oldY;
            
            newX = masHorse[j].x+3;
            newY = masHorse[j].y-1;
            masHorse[j].x = newX;
            masHorse[j].y = newY;
            if( checkProtect(masHorse, amountHorse) )
                {
                masHorse[i].x = oldX;
                masHorse[i].y = oldY;
       


      if( checkStep(masHorse, amountHorse, newX, newY) && checkHistory(&masHorse[i], newX, newY) )
                    {
                    masHorse[j].x = newX;
                    masHorse[j].y = newY;
                    if( checkMtrix(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y) )
                        {
                        return amountHorse;
                        }
                    
                    if(depth)
                        {
                        masHorse[j].history[0][masHorse[j].sizeHistory] = newX;
                        masHorse[j].history[1][masHorse[j].sizeHistory] = newY;
                        masHorse[j].sizeHistory++;
                        if(result = step(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y, (depth-1) ) )
                            {
                            return result;
                            }
                        }
                    }
                }
            masHorse[i].x = oldX;
            masHorse[i].y = oldY;
            
            newX = masHorse[j].x-1;
            newY = masHorse[j].y-2;
            masHorse[j].x = newX;
            masHorse[j].y = newY;
  


       if( checkProtect(masHorse, amountHorse) )
                {
                masHorse[i].x = oldX;
                masHorse[i].y = oldY;
                if( checkStep(masHorse, amountHorse, newX, newY) && checkHistory(&masHorse[i], newX, newY) )
                    {
                    masHorse[j].x = newX;
                    masHorse[j].y = newY;
                    if( checkMtrix(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y) )
                        {
                        return amountHorse;
                        }
                    
                    if(depth)
                        {
                        masHorse[j].history[0][masHorse[j].sizeHistory] = newX;
                        masHorse[j].history[1][masHorse[j].sizeHistory] = newY;
                        masHorse[j].sizeHistory++;
                        if(result = step(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y, (depth-1) ) )
                            {
                            return result;
                            }
                        }
                    }
                }
            masHorse[i].x = oldX;
            masHorse[i].y = oldY;

JoSkream · 04.06.2009, 23:21

Код:

          newX = masHorse[j].x-2;
            newY = masHorse[j].y+1;
            masHorse[j].x = newX;
            masHorse[j].y = newY;
            if( checkProtect(masHorse, amountHorse) )
                {
                masHorse[i].x = oldX;
                masHorse[i].y = oldY;
                if( checkStep(masHorse, amountHorse, newX, newY) && checkHistory(&masHorse[i], newX, newY) )
                    {
                    masHorse[j].x = newX;
                    masHorse[j].y = newY;
                    if( checkMtrix(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y) )
                        {
                        return amountHorse;
                        }
                    
                    if(depth)
                        {
                        masHorse[j].history[0][masHorse[j].sizeHistory] = newX;
                        masHorse[j].history[1][masHorse[j].sizeHistory] = newY;
                        masHorse[j].sizeHistory++;
                        if(result = step(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y, (depth-1) ) )
                            {
                            return result;
                


         }
                        }
                    }
                }
            masHorse[i].x = oldX;
            masHorse[i].y = oldY;
            
            newX = masHorse[j].x+1;
            newY = masHorse[j].y+3;
            masHorse[j].x = newX;
            masHorse[j].y = newY;
            if( checkProtect(masHorse, amountHorse) )
                {
                masHorse[i].x = oldX;
                masHorse[i].y = oldY;
                if( checkStep(masHorse, amountHorse, newX, newY) && checkHistory(&masHorse[i], newX, newY) )
                    {
                    masHorse[j].x = newX;
                    masHorse[j].y = newY;
                    if( checkMtrix(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y) )
                        {
                        return amountHorse;
                        }
                    
                    if(depth)
                        {
                        masHorse[j].history[0][masHorse[j].sizeHistory] = newX;
                        masHorse[j].history[1][masHorse[j].sizeHistory] = newY;
                        masHorse[j].sizeHistory++;
                        if(result = st

ep(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y, (depth-1) ) )
                            {
                            return result;
                            }
                        }
                    }
                }
            masHorse[i].x = oldX;
            masHorse[i].y = oldY;
            
            newX = masHorse[j].x+3;
            newY = masHorse[j].y+1;
            masHorse[j].x = newX;
            masHorse[j].y = newY;
            if( checkProtect(masHorse, amountHorse) )
                {
                masHorse[i].x = oldX;
                masHorse[i].y = oldY;
                if( checkStep(masHorse, amountHorse, newX, newY) && checkHistory(&masHorse[i], newX, newY) )
                    {
                    masHorse[j].x = newX;
                    masHorse[j].y = newY;
                    if( checkMtrix(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y) )
                        {
                        return amountHorse;
                        }
                    
                    if(depth)
                        {
                        masHorse[j].history[0][masHorse[j].sizeHistory] = newX;
              


       masHorse[j].history[1][masHorse[j].sizeHistory] = newY;
                        masHorse[j].sizeHistory++;
                        if(result = step(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y, (depth-1) ) )
                            {
                            return result;
                            }
                        }
                    }
                }
            masHorse[i].x = oldX;
            masHorse[i].y = oldY;
            
            newX = masHorse[j].x+1;
            newY = masHorse[j].y-2;
            masHorse[j].x = newX;
            masHorse[j].y = newY;
            if( checkProtect(masHorse, amountHorse) )
                {
                masHorse[i].x = oldX;
                masHorse[i].y = oldY;
                if( checkStep(masHorse, amountHorse, newX, newY) && checkHistory(&masHorse[i], newX, newY) )
                    {
                    masHorse[j].x = newX;
                    masHorse[j].y = newY;
                    if( checkMtrix(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y) )
                        {
                        return amountHorse;
                        }

JoSkream · 04.06.2009, 23:22

Код:

if(depth)
                        {
                        masHorse[j].history[0][masHorse[j].sizeHistory] = newX;
                        masHorse[j].history[1][masHorse[j].sizeHistory] = newY;
                        masHorse[j].sizeHistory++;
                        if(result = step(masHorse, amountHorse, mtrix, mtrix_x, mtrix_y, (depth-1) ) )
                            {
                            return result;
                            }
                        }
                    }
                }
            masHorse[i].x = oldX;
            masHorse[i].y = oldY;
            }
        };
    return 0;
    }
            //----------------------------------------------------------------------------------------------
                        
    int placement(horse * masHorse, int amountHorse, int leftHorse)
        {
        int i,n=amountHorse-leftHorse, stepX, stepY, min_x, max_x, min_y, max_y, z, result;
        masHorse[n].sizeHistory = 0;
        for(i=0, n; i<n; i++)
            {
            printf("step 1\n");
            stepX = masHorse[i].x-2;
            stepY = masHorse[i].y-1;
            if( checkSte


p(masHorse, amountHorse, stepX, stepY) )
                {
                masHorse[n].x = stepX;
                masHorse[n].y = stepY;
                if(leftHorse)
                    {
                    if( result = placement(masHorse, amountHorse, (leftHorse-1) ) )
                        {
                        return result;
                        }
                    }
                else
                    {
                    min_x = max_x = masHorse[0].x;
                    min_y = max_y = masHorse[0].y;
                    for(z=1; z<amountHorse; z++)
                    {
                    if(masHorse[z].x<min_x) min_x = masHorse[z].x;
                    if(masHorse[z].x>max_x) max_x = masHorse[z].x;
                    if(masHorse[z].y<min_y) min_y = masHorse[z].y;
                    if(masHorse[z].y>max_y) max_y = masHorse[z].y;
                    }
                    max_x -= min_x;
                    max_y -= min_y;
                    bool * mtrix = new bool[max_x*max_y];
                    for(z=0; z<max_x*max_y; z++)
                    {
                    mtrix[z] = false;
                    }
                  

for(z=0; z<amountHorse; z++)
                    {
                    mtrix[(masHorse[z].x-min_x)*(masHorse[z].y-min_y)] = true;
                    }
                    if( result = step(masHorse, amountHorse, mtrix, max_x, max_y, DEPTH) )
                        {
                        delete [] mtrix;
                        return result;
                        }
                    }
                }                        
        
        
        //-------------------------------------------------------------------------------------------------------
        printf("Step 2\n");
                stepX = masHorse[i].x-1;
            stepY = masHorse[i].y+3;
            if( checkStep(masHorse, amountHorse, stepX, stepY) )
                {
                masHorse[n].x = stepX;
                masHorse[n].y = stepY;
                if(leftHorse)
                    {
                    if( result = placement(masHorse, amountHorse, (leftHorse-1) ) )
                        {
                        return result;
                        }
                    }
                else
                    {
                    min_x = max_x = ma


sHorse[0].x;
                    min_y = max_y = masHorse[0].y;
                    for(z=1; z<amountHorse; z++)
                    {
                    if(masHorse[z].x<min_x) min_x = masHorse[z].x;
                    if(masHorse[z].x>max_x) max_x = masHorse[z].x;
                    if(masHorse[z].y<min_y) min_y = masHorse[z].y;
                    if(masHorse[z].y>max_y) max_y = masHorse[z].y;
                    }
                    max_x -= min_x;
                    max_y -= min_y;
                    bool * mtrix = new bool[max_x*max_y];
                    for(z=0; z<max_x*max_y; z++)
                    {
                    mtrix[z] = false;
                    }
                    for(z=0; z<amountHorse; z++)
                    {
                    mtrix[(masHorse[z].x-min_x)*(masHorse[z].y-min_y)] = true;
                    }
                    if( result = step(masHorse, amountHorse, mtrix, max_x, max_y, DEPTH) )
                        {
                        delete [] mtrix;
                        return result;
                        }
                    }
                }

JoSkream · 04.06.2009, 23:22

Код:

       
        
//-------------------------------------------------------------------------------------------------------
        printf("step3\n");
                    stepX = masHorse[i].x+3;
            stepY = masHorse[i].y-1;
            if( checkStep(masHorse, amountHorse, stepX, stepY) )
                {
                masHorse[n].x = stepX;
                masHorse[n].y = stepY;
                if(leftHorse)
                    {
                    printf("Recursia!");
                    if( result = placement(masHorse, amountHorse, (leftHorse-1) ) )
                        {
                        return result;
                        }
                    }
                else
                    {
                    printf("Start else3!\n");
                    min_x = max_x = masHorse[0].x;
                    min_y = max_y = masHorse[0].y;
                    for(z=0; z<amountHorse; z++)
                    {
                    printf("masHorse[%d] x: %d\ty:%d\n", z, masHorse[z].x, masHorse[z].y);
                    getch();
                    if(masHorse[z].x<min_x) min_x = masHorse[z].x;
                    if(masHorse[z].x>max_x) max_x = masHors

04.06.2009, 23:19	#1
JoSkream Пользователь Регистрация: 26.04.2009 Сообщений: 12	Алгоритм Здравствуйте прошу помоч написать алгоритм к ниже приведенному коду так же дам условие задачи =============Текст задачи============== Из какого наименьшего числа коней можно создать активный эскадрон? решить задачу численным методом. Пояснения: Эскадрон -- Группа коней , размещенный на бесконечной шахметной доске Активный Эскадрон -- это эскадрон, который может сделать любое число ходов на шахматной доске и занять одним из своих коней любое поле доски, не оставляя ни на один ход ни одного коня без защиты.

Похожие темы
Тема	Автор	Раздел	Ответов	Последнее сообщение
Алгоритм	G@sh!sh	Общие вопросы по Java, Java SE, Kotlin	4	21.06.2009 16:17
Алгоритм?!	Spartaner	Фриланс	2	28.05.2009 03:22
Алгоритм	SunKnight	Работа с сетью в Delphi	5	29.04.2008 15:24
Алгоритм	Rifler	Паскаль, Turbo Pascal, PascalABC.NET	3	30.03.2008 01:33