Методы решения задач типа: ход конем

[Levsha100]

Да, реализация- это самое ужасное(и затягивающие!)

[jojahti]

Попробовал решить. ) Метод тупого перебора, развосьмеряющимся конём в рекурсии. Считает до 5го перемещения. Если больше, то получается аналог шахматной доски и маковых зёрнышек из притчи. ))

#include <iostream>
#include <iomanip>
#include <vector>
using namespace std;
            //[y][x]
struct Userdat
{ int startY;
  int startX;
  int endY;
  int endX;
void getdat()
  { cout<<"write you start position:"<<endl;
    cout<<"y: ";  cin>>startY; 
    cout<<" x: "; cin>>startX; 
                   cout<<endl;
    cout <<"write final coordinate"<<endl;
    cout<<"y: "; cin>>endY; cout<<endl;
    cout<<"x: "; cin>>endX; cout<<endl;   }       
};

Userdat udat; //user coordinate
            
struct cordXY
{ int key;
  int y;
  int x;
  int cx; // absolute coordinate
  int cy; };

struct INdat
  { int ny;     //number chain
    int nx; }; //max x

INdat ndat; //matrix chain
//==============================           
int xy[2][8] ={ {-2,-1,1,2, 2, 1,-1,-2},
                { 1, 2,2,1,-1,-2,-2,-1}};
//======================================//
void writechain(vector<vector<cordXY> > &matrix, int y)
{
  for(int x=/*0*/1;x<matrix[y].size();++x)
          cout<<setiosflags(ios::showpos)
          <<"matrix["<<y<<"]"<<" key|"<<matrix[y][x].key<<"| --- "<<"y: "<<matrix[y][x].y<<"; x: "<<matrix[y][x].x<<
                                                                " || y: "<<matrix[y][x].cy<<" x:"<<matrix[y][x].cx<<endl;
           cout<< "============="<< endl;                
}
//======================================//
void stable(int dir, int n, vector<vector<cordXY> > &matrix,   //-=|| STABLE ||
                            vector<cordXY> path      )
{ 
  ++n; // jump
  cordXY cord;
  cord.key = dir;
  cord.y = xy[0][dir];
  cord.x = xy[1][dir];
  path.push_back(cord); // remember jump
  matrix.push_back(path);
  if(n<5)
     { for(int i=0;i<8;++i)
       stable(i, n, matrix, path);  }
}
//================================================|| INIT ABSOLUTE XY ||=
void initabsYX(vector<vector<cordXY> > &matrix, Userdat udat)
{
  for(int y=0;y<matrix.size();++y)
  {  
  for(int x=0;x<matrix[y].size();++x)
     { 
       matrix[y][x].cy=udat.startY;   
       matrix[y][x].cx=udat.startX;
       if(x>0)
           {matrix[y][x].cy = matrix[y][x-1].cy + matrix[y][x].y;
            matrix[y][x].cx = matrix[y][x-1].cx + matrix[y][x].x;}
     }
  }
}
//================================================|| INIT DAT ||=
bool initdat(vector< vector<cordXY> >  &matrix, vector<INdat> &dat, Userdat udat) {     
bool detect=false;
  for(int y=0;y<matrix.size();++y)
  {  
        for(int x=0;x<matrix[y].size();++x)
        {
         if( (matrix[y][x].cy==udat.endY) && (matrix[y][x].cx==udat.endX) )
                                                 { detect=1;
                                                   writechain(matrix, y);
                                                   ndat.ny = y;
                                                   ndat.nx = x;
                                                   dat.push_back(ndat);
                                                   break;                 }                                                                        
        }
  }          
 return detect;    
}
//================================================|| FINALSTR
int finalstr(vector<INdat> &dat) {
  int first=0;
  int temp;
  temp=dat[0].nx;
  for(int i=1;i<dat.size();++i)
  {  if(dat[i].nx < temp)
             { temp=dat[i].nx;  
               first = i;     }
  }
 // cout<< "first: "<<first<<endl;
 return dat[first].ny;
}
//=====================================//
//===========|| MAIN()   ||============//
int main() {
  vector< vector<cordXY> >  matrix;  // matrix  2d
  vector<cordXY>              path;  //  path
  char ch;
  udat.getdat(); // GET USER DAT

 stable(0, 0, matrix, path); //  init matrix relative coordinate
 initabsYX(matrix, udat);  //    init matrix absolute coordinate

for(int y=0;y<matrix.size();++y)  // write matrix
      { writechain(matrix, y); } //  write matrix

vector<INdat> dat; //=========================|| field ghost dat
if(initdat(matrix, dat, udat) == false) 
                   {cout<<"no true chain"<<endl; cin>>ch; }

  int y = finalstr(dat); // search first true string
cout << "You shortest chain:"<<endl; 
  writechain(matrix, y);
  cin >>ch;
 return 0;
}

[Levsha100]

Подскажите, плиз, как решать задачи типа этой.

Есть комната размером n*m (n, m – целые числа). На складе есть квадратные коврики, размеры которых задаются целыми числами а1, а2, а3 … аn. Сколько и каких необходимо ковриков, чтобы ими полностью покрыть пол(накладывать коврики один на один нельзя), при этом количество ковриков должно быть минимальным.

[ds.Dante]

Однозначно, начинать надо с самых больших. :) Я даже не знаю, как подступиться к задаче. Некоторе коврики может быть лучше положить под углом. У Мартина Гарднера описывались подобные задачи с картонками.

[L_M]

Мне кажется, можно воспользоваться жадным алгоритмом: сначала отсортировать по убыванию размера, потом цикл перебора всех ковриков, каждый коврик поверяем, подходит или нет, если подходит, то положить, если нет - пропускать. Так получиться оптимальное решение, но оно вполне может и не получиться))