| ← Июль 2012 → | ||||||
|
1
|
||||||
|---|---|---|---|---|---|---|
|
2
|
3
|
4
|
5
|
6
|
7
|
8
|
|
10
|
11
|
12
|
13
|
14
|
15
|
|
|
16
|
17
|
18
|
19
|
20
|
21
|
22
|
|
23
|
24
|
25
|
26
|
27
|
28
|
29
|
|
30
|
31
|
|||||
За последние 60 дней ни разу не выходила
Сайт рассылки:
http://rfpro.ru/
Открыта:
11-11-2009
Статистика
0 за неделю
RFpro.ru: Алгоритмы и теория программирования
Хостинг портала RFpro.ru: РАССЫЛКИ ПОРТАЛА RFPRO.RU
Лучшие эксперты по данной тематике
/ КОМПЬЮТЕРЫ И СОФТ / Программирование / Алгоритмы и теория программирования
Консультация # 181931: Добрый день, уважаемые эксперты! Представим, что есть поле размером 5 на 5 клеток. На этом поле нужно разместить три фигурки - две двухклеточных и одну одноклеточную, размещать фигурки нужно так, чтобы они друг друга не касались (ни сторонами, ни уголками), четко по клеткам. Задача такая: нужно перебрать все возможные варианты размеще... Консультация # 109319: Помогите написать программу для решения задачи на языке Pascal (если можно с описанием): Дано натуральное число n меньше-ровно 9999 а) Является ли это число палиндромом (перевёртышем) с учетом четырех цифр, как, например, числа 2222, 6116, 0440 и т. д.? б) Верно ли, что это число содержит ровно три одинаковые цифры, как, например, чис... Консультация # 177612: Доброго времени суток!Друзья,подскажите ответ на вопрос - "Значение машины Тьюринга. И что общего у неё с реальными вычислителями?" там врдоде несколько видов есть...... Добрый день, уважаемые эксперты!
Дата отправки: 18.01.2011, 18:10 Консультирует coremaster1 (Профессор): Здравствуйте, lupus campestris! Код : Таблица попаданий двухклеточных фигур: 608 718 622 718 608 718 608 508 608 718 622 508 424 508 622 718 608 508 608 718 608 718 622 718 608 Таблица попаданий одноклеточных фигур: 242 179 151 179 242 179 111 89 111 179 151 89 84 89 151 179 111 89 111 179 242 179 151 179 242 Суммарная таблица попаданий: 850 897 773 897 850 897 719 597 719 897 773 597 508 597 773 897 719 597 719 897 850 897 773 897 850 Остальные вопросы: а) 3888 б) Задача решена методом машинного перебора. В программе реализован алгоритм поиска с возвратом (backtrace) с элементами динамического программирования. в) На кодирование алгоритма затратил примерно 1 час, программа исполняется менее секунды. Приложение:
Консультирует Лысков Игорь Витальевич (Старший модератор): Здравствуйте, lupus campestris! Код : #include <stdio.h>
#include <conio.h>
#include <time.h>
typedef struct _field
{
int row;
int col;
}FIELD;
typedef struct _sosed
{
int count;
FIELD *pField;
}SOSED;
#define n 5
#define n00 3
#define n01 5
#define n02 5
#define n03 5
#define n04 3
#define n10 5
#define n11 8
#define n12 8
#define n13 8
#define n14 5
#define n20 5
#define n21 8
#define n22 8
#define n23 8
#define n24 5
#define n30 5
#define n31 8
#define n32 8
#define n33 8
#define n34 5
#define n40 3
#define n41 5
#define n42 5
#define n43 5
#define n44 3
FIELD s00[n00] = {{0,1},{1,0},{1,1}};
FIELD s01[n01] = {{0,0},{0,2},{1,0},{1,1},{1,2}};
FIELD s02[n02] = {{0,1},{0,3},{1,1},{1,2},{1,3}};
FIELD s03[n03] = {{0,2},{0,4},{1,2},{1,3},{1,4}};
FIELD s04[n04] = {{0,3},{1,3},{1,4}};
FIELD s10[n10] = {{0,0},{0,1},{1,1},{2,0},{2,1}};
FIELD s11[n11] = {{0,0},{0,1},{0,2},{1,0},{1,2},{2,0},{2,1},{2,2}};
FIELD s12[n12] = {{0,1},{0,2},{0,3},{1,1},{1,3},{2,1},{2,2},{2,3}};
FIELD s13[n13] = {{0,2},{0,3},{0,4},{1,2},{1,4},{2,2},{2,3},{2,4}};
FIELD s14[n14] = {{0,3},{0,4},{1,3},{2,3},{2,4}};
FIELD s20[n20] = {{1,0},{1,1},{2,1},{3,0},{3,1}};
FIELD s21[n21] = {{1,0},{1,1},{1,2},{2,0},{2,2},{3,0},{3,1},{3,2}};
FIELD s22[n22] = {{1,1},{1,2},{1,3},{2,1},{2,3},{3,1},{3,2},{3,3}};
FIELD s23[n23] = {{1,2},{1,3},{1,4},{2,2},{2,4},{3,2},{3,3},{3,4}};
FIELD s24[n24] = {{1,3},{1,4},{2,3},{3,3},{3,4}};
FIELD s30[n30] = {{2,0},{2,1},{3,1},{4,0},{4,1}};
FIELD s31[n31] = {{2,0},{2,1},{2,2},{3,0},{3,2},{4,0},{4,1},{4,2}};
FIELD s32[n32] = {{2,1},{2,2},{2,3},{3,1},{3,3},{4,1},{4,2},{4,3}};
FIELD s33[n33] = {{2,2},{2,3},{2,4},{3,2},{3,4},{4,2},{4,3},{4,4}};
FIELD s34[n34] = {{2,3},{2,4},{3,3},{4,3},{4,4}};
FIELD s40[n40] = {{3,0},{3,1},{4,1}};
FIELD s41[n41] = {{3,0},{3,1},{3,2},{4,0},{4,2}};
FIELD s42[n42] = {{3,1},{3,2},{3,3},{4,1},{4,3}};
FIELD s43[n43] = {{3,2},{3,3},{3,4},{4,2},{4,4}};
FIELD s44[n44] = {{3,3},{3,4},{4,3}};
SOSED sosedi[n][n] =
{
{{n00, s00}, {n01, s01}, {n02, s02}, {n03, s03}, {n04, s04}},
{{n10, s10}, {n11, s11}, {n12, s12}, {n13, s13}, {n14, s14}},
{{n20, s20}, {n21, s21}, {n22, s22}, {n23, s23}, {n24, s24}},
{{n30, s30}, {n31, s31}, {n32, s32}, {n33, s33}, {n34, s34}},
{{n40, s40}, {n41, s41}, {n42, s42}, {n43, s43}, {n04, s44}}
};
int sum2[n][n];
int sum1[n][n];
int sum3[n][n];
int CmpSosed(int ii1, int jj1, int ii2, int jj2)
{
int i;
int iRet = 1;
FIELD *pField = sosedi[ii1][jj1].pField;
for (i=0; i<sosedi[ii1][jj1].count; i++)
{
if ((pField[i].row == ii2) && (pField[i].col == jj2))
{
iRet = 0;
break;
}
}
return iRet;
}
int main()
{
int i, j, row1, col1, row2, col2, i1, j1, i2, j2, i3, j3, count, c;
time_t t0 = time(0);
for (count=i1=0; i1<n; i1++)
{
for (j1=0; j1<n; j1++)
{
for (i=0; i<sosedi[i1][j1].count; i++)
{
row1 = sosedi[i1][j1].pField[i].row;
col1 = sosedi[i1][j1].pField[i].col;
if (((i1 == row1) || (j1 == col1)) && (row1 >=i1) && (col1>=j1))
{
for (i2=i1; i2<n; i2++)
{
for (j2=0; j2<n; j2++)
{
if (((i2==i1)&&(j2>=col1))||(i2>i1))
{
if (CmpSosed(i1, j1, i2, j2) && CmpSosed(row1, col1, i2, j2))
{
for (j=0; j<sosedi[i2][j2].count; j++)
{
row2 = sosedi[i2][j2].pField[j].row;
col2 = sosedi[i2][j2].pField[j].col;
if (((i2 == row2) || (j2 == col2)) && (row2>=i2) && (col2>=j2))
{
if (CmpSosed(i1, j1, row2, col2) && CmpSosed(row1, col1, row2, col2))
{
for (c=i3=0; i3<n; i3++)
{
for (j3=0; j3<n; j3++)
{
if (CmpSosed(i1, j1, i3, j3) &&
CmpSosed(row1, col1, i3, j3) &&
CmpSosed(i2, j2, i3, j3) &&
CmpSosed(row2, col2, i3, j3))
{
count ++;
c++;
sum1[i3][j3]++;
sum2[i1][j1]++;
sum2[row1][col1]++;
sum2[i2][j2]++;
sum2[row2][col2]++;
sum3[i3][j3]++;
sum3[i1][j1]++;
sum3[row1][col1]++;
sum3[i2][j2]++;
sum3[row2][col2]++;
}
}
}
}
}
}
}
}
}
}
}
}
}
}
time_t t1 = time(0);
printf("Total: %d\nTime: %d s\n\nLenght 1 table:\n",count,t1-t0);
for (i1=0; i1<n; i1++)
{
for (j1=0; j1<n; j1++)
printf("%d\t",sum1[i1][j1]);
printf ("\n");
}
printf ("\nLenght 2 table:\n");
for (i1=0; i1<n; i1++)
{
for (j1=0; j1<n; j1++)
printf("%d\t",sum2[i1][j1]);
printf ("\n");
}
printf ("\nSum table:\n");
for (i1=0; i1<n; i1++)
{
for (j1=0; j1<n; j1++)
printf("%d\t",sum3[i1][j1]);
printf ("\n");
}
printf ("\nPress any key");
getch();
return 0;
}
Вывод программы: Код : Total: 3888 Time: 0 s Lenght 1 table: 242 179 151 179 242 179 111 89 111 179 151 89 84 89 151 179 111 89 111 179 242 179 151 179 242 Lenght 2 table: 608 718 622 718 608 718 608 508 608 718 622 508 424 508 622 718 608 508 608 718 608 718 622 718 608 Sum table: 850 897 773 897 850 897 719 597 719 897 773 597 508 597 773 897 719 597 719 897 850 897 773 897 850 Метод решения: строятся для каждого поля таблица смежности, т.е. какие клетки являются соседними. Затем, перебирая варианты размещения, сначала первого двупалубного, затем второго двупалубного (учитываем таблицы смежности, чтобы не было касания), считаем варианты размещения однопалубного (опять же учитываем таблицы смежности) Времени ушло часа три (с перерывами)
Консультирует Зенченко Константин Николаевич (Модератор): Здравствуйте, lupus campestris!
Одиночные:
Суммарные:
Total: 3888 Time: 0 б) Метод - полный перебор начального положения первых двух клеток. Положение второй пары находится ниже-правее первой. Вычеркиваются соседние клетки, оставшиеся - являются позициями одиночных клеток, их количество определяет количество вариантов. в) Время написания- 2-а часа с перерывами, время работы - 0(Как не старался получить время, результат - ноль.возможно на старых машинах его можно будет определить). Удач и! Приложение:
Консультирует Micren (Профессор): Здравствуйте, lupus campestris! Код : .../GNU-Linux-x86> time ./181931 Одноклеточные: 242 179 151 179 242 179 111 89 111 179 151 89 84 89 151 179 111 89 111 179 242 179 151 179 242 Двухклеточные: 608 718 622 718 608 718 608 508 608 718 622 508 424 508 622 718 608 508 608 718 608 718 622 718 608 Общая таблица: 850 897 773 897 850 897 719 597 719 897 773 597 508 597 773 897 719 597 719 897 850 897 773 897 850 Всего вариантов: 3888 real 0m0.070s user 0m0.064s sys 0m0.000s Код :
#include <locale>
#include <limits>
#include <iostream>
#include <iomanip>
#include <valarray>
#include <stdexcept>
#include <string>
#include <map>
using namespace std;
const bool FIGURE1[1][1] = {1};
const bool FIGURE2[1][2] = {1, 1};
const size_t BOARD_SIZE = 5;
class figure_base
{
public:
figure_base(size_t rows, size_t cols);
char& operator()(size_t row, size_t col);
char operator()(size_t row, size_t col) const;
size_t rows() const;
size_t cols() const;
template<class char_type, class traits_type> void out(basic_ostream<char_type, traits_type>& stream);
protected:
typedef valarray< valarray<char> > _fields_t;
_fields_t _fields;
size_t _rows, _cols;
};
class figure : public figure_base
{
public:
enum direction_t
{
LEFT, RIGHT
};
template<size_t DIM1, size_t DIM2> figure(size_t rotations, const bool (&fields)[DIM1][DIM2], char id);
size_t rotations() const;
char id() const;
void rotate(direction_t direction = LEFT);
protected:
size_t _rotations;
char _id;
};
class board : public figure_base
{
public:
board(size_t size);
void place(size_t row, size_t col, const figure& fig);
void remove(size_t row, size_t col, const figure& fig);
protected:
bool test(size_t row, size_t col, const figure& fig) const;
};
class solver
{
public:
typedef valarray< valarray< map<char, size_t> > > _counters_t;
struct counters_t
{
_counters_t counters;
size_t variants;
};
template<size_t DIM> solver(const figure(&figures)[DIM], size_t board_size);
counters_t run();
private:
valarray<figure> _figures;
board _board;
counters_t _counters;
void place(size_t fig_no);
};
void visualisation(const char* const msg, solver::counters_t &counters, const char* const fig_ids, unsigned int divisor);
unsigned fact(unsigned val);
/*
*
*/
int main()
{
locale::global(locale(""));
figure figures[3] = {figure(1, FIGURE1, '1'), figure(2, FIGURE2, '2'), figure(2, FIGURE2, '3')};
solver::counters_t counters = solver(figures, BOARD_SIZE).run();
unsigned div = fact(2) * fact(1);
visualisation("Одноклеточные:", counters, "1", div);
visualisation("Двухклеточные:", counters, "23", div);
visualisation("Общая таблица:", counters, "123", div);
cout << "Всего вариантов: " << counters.variants / div << endl;
return 0;
}
void visualisation(const char* const msg, solver::counters_t &counters, const char* const fig_ids, unsigned int divisor)
{
valarray< valarray<size_t> > result(counters.counters.size());
for (size_t i = 0; i < result.size(); ++i)
{
result[i] = valarray<size_t > (static_cast<size_t> (0), counters.counters[i].size());
for (size_t j = 0; j < result[i].size(); ++j)
{
const char* ids = fig_ids;
while (*ids)
{
result[i][j] += counters.counters[i][j][*ids++];
}
}
}
cout << msg << endl;
for (size_t i = 0; i < result.size(); ++i)
{
for (size_t j = 0; j < result[i].size(); ++j)
{
size_t tmp = result[i][j] / divisor;
cout << setw(5) << tmp << ' ';
}
cout << endl;
}
}
unsigned fact(unsigned val)
{
unsigned result = 1;
while (val)
{
result *= val--;
}
return result;
}
figure_base::figure_base(size_t DIM1, size_t DIM2)
: _fields(valarray<char>(static_cast<char> (0), DIM2), DIM1)
, _rows(DIM1)
, _cols(DIM2)
{
}
char& figure_base::operator ()(size_t row, size_t col)
{
return _fields[row][col];
}
char figure_base::operator ()(size_t row, size_t col) const
{
return _fields[row][col];
}
size_t figure_base::rows() const
{
return _rows;
}
size_t figure_base::cols() const
{
return _cols;
}
template<class char_type, class traits_type>
void figure_base::out(basic_ostream<char_type, traits_type>& stream)
{
const ctype<char_type>& facet = use_facet< ctype<char_type> >(stream.getloc());
static basic_string<char_type> hline(1 + 2 * _rows, facet.widen('-'));
stream << hline << endl;
for (size_t i = 0; i < _rows; ++i)
{
for (size_t j = 0; j < _cols; ++j)
{
stream << facet.widen('|') << (_fields[i][j] ? facet.widen(_fields[i][j]) : facet.widen(' '));
}
stream << facet.widen('|') << endl << hline << endl;
}
}
template<size_t DIM1, size_t DIM2 >
figure::figure(size_t rotations, const bool (&fields)[DIM1][DIM2], char id)
: figure_base(DIM1, DIM2)
, _rotations(rotations)
, _id(id)
{
if (_rotations > 4)
{
throw invalid_argument("К-во поворотов фигуры не может быть более 4х");
}
for (size_t i = 0; i < DIM1; ++i)
{
for (size_t j = 0; j < DIM2; ++j)
{
_fields[i][j] = fields[i][j] ? id : 0;
}
}
}
size_t figure::rotations() const
{
return _rotations;
}
char figure::id() const
{
return _id;
}
void figure::rotate(direction_t direction)
{
figure_base newFigure(_cols, _rows);
for (size_t i = 0; i < _cols; ++i)
{
for (size_t j = 0; j < _rows; ++j)
{
switch (direction)
{
case LEFT:
newFigure(i, j) = _fields[j][ _cols - 1 - i];
break;
case RIGHT:
newFigure(i, j) = _fields[_rows - 1 - j][i];
break;
default:
throw invalid_argument("Неверное направление");
}
}
}
*reinterpret_cast<figure_base*> (this) = newFigure;
}
board::board(size_t size)
: figure_base(size, size)
{
}
void board::place(size_t row, size_t col, const figure& fig)
{
if (!(row < _rows && col < _cols))
{
throw invalid_argument("Неверно заданы координаты");
}
if (!(fig.rows() <= _rows - row && fig.cols() <= _cols - col))
{
throw invalid_argument("Фигура слишком велика");
}
if (!test(row, col, fig))
{
throw invalid_argument("Невозможно установить");
}
for (size_t i = 0; i < fig.rows(); ++i)
{
for (size_t j = 0; j < fig.cols(); ++j)
{
if (!_fields[i + row][j + col] && fig(i, j))
{
_fields[i + row][j + col] = fig.id();
}
}
}
}
void board::remove(size_t row, size_t col, const figure& fig)
{
if (!(row < _rows && col < _cols))
{
throw invalid_argument("Неверно заданы координаты");
}
if (!(fig.rows() <= _rows - row && fig.cols() <= _cols - col))
{
throw invalid_argument("Фигура слишком велика");
}
for (size_t i = 0; i < fig.rows(); ++i)
{
for (size_t j = 0; j < fig.cols(); ++j)
{
if (fig(i, j))
{
_fields[i + row][j + col] = 0;
}
}
}
}
bool board::test(size_t row, size_t col, const figure& fig) const
{
for (size_t i = 0; i < fig.rows(); ++i)
{
for (size_t j = 0; j < fig.cols(); ++j)
{
if (fig(i, j))
{
for (size_t r = i + row - 1, er = r + 3; r != er; ++r)
{
for (size_t c = j + col - 1, ec = c + 3; c != ec; ++c)
{
if (r < _rows && c < _cols && _fields[r][c])
{
return false;
}
}
}
}
}
}
return true;
}
template<size_t DIM >
solver::solver(const figure(&figures)[DIM], size_t board_size)
: _figures(figures, DIM)
, _board(board_size)
{
}
solver::counters_t solver::run()
{
_counters.counters = valarray< valarray< map<char, size_t> > >(valarray< map<char, size_t > >(_board.cols()), _board.rows());
_counters.variants = 0;
place(_figures.size());
return _counters;
}
void solver::place(size_t fig_no)
{
if (!fig_no)
{
for (size_t i = 0; i < _board.rows(); ++i)
{
for (size_t j = 0; j < _board.cols(); ++j)
{
++_counters.counters[i][j][_board(i, j)];
}
}
++_counters.variants;
}
else
{
figure fig(_figures[--fig_no]);
for (size_t pos = 0; pos < fig.rotations(); ++pos)
{
for (size_t row = 0; row < _board.rows(); ++row)
{
for (size_t col = 0; col < _board.cols(); ++col)
{
try
{
_board.place(row, col, fig);
this->place(fig_no);
_board.remove(row, col, fig);
}
catch (...)
{
}
}
}
fig.rotate();
}
}
}
Метод решения - полный перебор. Времени ушло ~6ч. Вообще то, изначально была мысль написать программу для решения задач типа полиомино, где фигуры могут быть заметно сложнее чем 2х клеточные. Так же была цель обеспечить относительно легкую модификацию и сопровождение кода. Напр. легкое изменение размера доски, добавление различных фигур и т.п. Отсюда заметная избыточность кода. Часть той программы была использована здесь.
Помогите написать программу для решения задачи на языке Pascal (если можно с описанием):
Дата отправки: 14.11.2007, 03:27 Консультирует Лысков Игорь Витальевич (Старший модератор): Здравствуйте, Мироненко Николай Николаевич!
Консультирует Зиновьев Дмитрий Владимирович: Здравствуйте, Мироненко Николай Николаевич!
Доброго времени суток!Друзья,подскажите ответ на вопрос - "Значение машины Тьюринга. И что общего у неё с реальными вычислителями?"
Дата отправки: 02.04.2010, 23:16 Консультирует coremaster1 (Профессор): Здравствуйте, Poult.
Консультирует Сергей Мороз / F®ost (Шеф-редактор журнала): Здравствуйте, Poult.
Оценить выпуск | Задать вопрос экспертам
главная страница
|
стать участником
|
получить консультацию
© 2001-2012, Портал RFPRO.RU, Россия
Авторское право: ООО "Мастер-Эксперт Про" Калашников О.А. | Гладенюк А.Г. Хостинг: Версия системы: 2011.6.36 от 26.01.2012 |
| В избранное | ||
