Олимпиадная задача

Вопросы программирования на Free Pascal, использования компилятора и утилит.

Модератор: Модераторы

Re: Олимпиадная задача

Сообщение kim » 10.04.2019 14:40:19

Это оно?

Спасибо. Вообщем все что вы сделали работает. Но наверное мне ещё нужно самому много чего выучить, потому что много в части кода просто не понимаю. Графы и всё что выше мы не изучали. Прошли лишь курс до матриц. Как бы мне нужен код как для школьного курса (типа циклы, матрицы), а вы пишите уже код на ПРОФИ. Для меня это слишком сложно. Но наверное школьными методами это не решается.
В любом случае я вам очень всем благодарен.
kim
незнакомец
 
Сообщения: 3
Зарегистрирован: 04.04.2019 13:10:14

Re: Олимпиадная задача

Сообщение Vadim » 10.04.2019 15:32:12

kim писал(а):... а вы пишите уже код на ПРОФИ.

Вряд ли это так уж однозначно можно назвать "ПРОФИ", т.к. работа с графами это один из стандартных методов решения тех или иных задач. Профи обычно решают либо нестандартную задачу, либо стандартную, но нестандартными методами. А стандартные задачи, в силу накопленного опыта, решаются на раз, без долгих раздумий. Другое дело, что может быть по вашей учебной программе Вы до этого ещё не добрались, но Вам, как минимум, когда доберётесь будет легче изучать. ;-)
kim писал(а):Как бы мне нужен код как для школьного курса (типа циклы, матрицы)...

Есть там и циклы и матрицы, не волнуйтесь. Так что давайте признаем код вполне себе узнаваемым, пусть и не с первого раза... ;-)
Vadim
долгожитель
 
Сообщения: 4112
Зарегистрирован: 05.10.2006 08:52:59
Откуда: Красноярск

Re: Олимпиадная задача

Сообщение iskander » 10.04.2019 16:25:13

kim писал(а):Как бы мне нужен код как для школьного курса (типа циклы, матрицы)

Так у меня во втором варианте кроме циклов и матриц больше ничего и нет.
iskander
энтузиаст
 
Сообщения: 590
Зарегистрирован: 08.01.2012 18:43:34

Re: Олимпиадная задача

Сообщение serbod » 10.04.2019 17:18:03

У меня есть готовый код на Си с комментариями.
Код: Выделить всё
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// Размеры карты
#define MAX_X  24
#define MAX_Y  24
// Скорость поиска пути, чем выше скорость, тем ниже точность (0..4)
#define SPEED 0.5
// Номер лабиринта. Если лабиринт непроходим, ставьте другой номер
#define MAZE 1

// Точка на карте
struct mapPoint {
       int x;  // положение по оси x
       int y;  // положение по оси y
       int z;  // проходимость точки (0-непроходима, 99-путь)
       int px; // x предыдущей точки
       int py; // y предыдущей точки
       int rating; // рейтинг точки
       int trip; // время прохождения к этой точке (с учетом проходимости)
       };

// Для оптимизации лучше использовать список точек в виде int list[MAX_X*MAX_Y]
// точки представлять в виде числа (x+(y*MAX_X))
// активнее использовать ссылки
// это сэкономит кучу машинного времени и памяти..
// Но вариант со списком точек (как структур) и координатами X,Y
// выглядит более наглядным

// Список точек
struct pointList {
       int count;
       struct mapPoint list[MAX_X*MAX_Y];
       };

struct mapPoint map[MAX_X][MAX_Y];  // карта
struct pointList aOpen;  // список точек-кандидатов
struct mapPoint startPoint;  // начальная точка
struct mapPoint finalPoint;  // конечная точка

//=============================================
// Задержка в миллисекундах
void wait(int mseconds){
   clock_t endwait;
   endwait=clock()+mseconds*(CLOCKS_PER_SEC/1000);
   while (clock()<endwait);
}

//--------------------------------------------
// Проверка на одинаковость точек
int same_point(struct mapPoint point_a, struct mapPoint point_b) {
  return ((point_a.x == point_b.x) && (point_a.y == point_b.y));
}

//--------------------------------------------
// Добавление точки в список
int add_point(struct pointList *list, struct mapPoint point) {
  list->list[list->count]=point;
  return list->count++;
}

//--------------------------------------------
// Удаление точки из списка
int del_point(struct pointList *list, struct mapPoint point) {
  int i, n;
  for (i=0; i < list->count; i++) {
    if (same_point(list->list[i], point)) {
      // slide list
      list->count--;
      for (n=i; n < list->count; n++) {
        list->list[n] = list->list[n+1];
      }
      return i;
    }
  }
  return 0;
}

//=============================================
// Начальное заполнение карты случайными значениями проходимости
// и установка начальных значений свойств точек
void fill_map() {
  int x, y, z;
  for (y=0; y<MAX_Y; y++) {
    for (x=0; x<MAX_X; x++) {
      z=rand() % 4;
      map[x][y].x=x;
      map[x][y].y=y;
      map[x][y].z=z;
      map[x][y].rating=0;
    }
  }
}

//--------------------------------------------
// Чтение карты из файла
void read_map() {
  FILE *fp;
  int x, y;
  char s[128];

  fp=fopen("map.dat", "rt");
  if (fp) {
    for (y=0; y<MAX_Y; y++) {
      fgets(s, 80, fp);
      for (x=0; x<MAX_Y; x++) map[x][y].z = s[x]-'0';
    }
    fclose(fp);
  }
}

//--------------------------------------------
// Отображение карты
void show_map(int showOpen) {
  int x, y;  // variables for iteration
  char c;
  printf("\n");
  for (y=0; y<MAX_Y; y++) {
    for (x=0; x<MAX_X; x++) {
      // Установка символа точки на карте (для наглядности)
      switch (map[x][y].z) {
        case 0: c='#'; break;
        case 1: c=' '; break;
        case 2: c='.'; break;
        case 3: c='*'; break;
        case 99: c='0'; break;
        default: c='?';
      }
      // Если на этой точке кандидат, то покажем его
      if (showOpen && (map[x][y].rating>0)) c='$';
      // show character
      printf("%c", c);
    }
    // line feed, caret return
    printf("\n");
  }
  // Задержка для анимации
  wait(100);
}

//--------------------------------------------
// Проверка точки
int point_check(struct mapPoint point, int x, int y) {
  int d;
  // Проверка на проходимость
  if (map[x][y].z == 0) return 0;
  // Проверка на принадлежность точки к кандидатам
  if (map[x][y].rating > 0) return 0;
  // d обратно пропорционален расстоянию до финиша
  d=(MAX_X-(finalPoint.x-x))+(MAX_Y-(finalPoint.y-y));
  // Установка рейтинга точки. Чем больше рейтинг точки, тем она дальше
  // от старта и ближе к цели.
  // От этой строки зависит качество работы всего алгоритма в целом
  map[x][y].rating = 10000 + d*SPEED - point.trip - map[x][y].z;
  // Установка времени прохождения в точку, нужно для расчета рейтинга
  map[x][y].trip = point.trip + map[x][y].z;
  // Установка координат предыдущей точки
  map[x][y].px = point.x;
  map[x][y].py = point.y;
  // Добавляем точку в список
  add_point(&aOpen, map[x][y]);
  return 1;
}

//--------------------------------------------
// Построение пути из финиша к старту по цепочке предыдущих точек
// Сделано рекурсией (так проще), но можно переделать на цикл
void build_path(struct mapPoint point) {
  map[point.x][point.y].z=99;
  if (same_point(point, startPoint)) return;
  build_path(map[point.px][point.py]);
}

//--------------------------------------------
// Поиск пути
void find_path() {
  struct mapPoint point; // текущая точка
  int i;  // Итератор
  int mr, mri; // Максимальный рейтинг и его индекс
 
  aOpen.count=0;

  // помещаем в список кандидатов начальную точку
  point = startPoint;
  add_point(&aOpen, point);
  // Пока есть кандидаты, делаем цикл
  while (aOpen.count > 0) {
    // удаляем текущего кандидата из списка кандидатов
    del_point(&aOpen, point);
    // Если текущий кандидат - это финиш, то строим путь и выходим
    if (same_point(point, finalPoint)) {
      build_path(point);
      return;
    }
    // обрабатываем соседние точки
    if (point.y > 0)       point_check(point, point.x, point.y-1); // top
    if (point.y+1 < MAX_Y) point_check(point, point.x, point.y+1); // bottom
    if (point.x+1 < MAX_X) point_check(point, point.x+1, point.y); // right
    if (point.x > 0)       point_check(point, point.x-1, point.y); // left
   
    // Выбираем из списка кандидатов точку с наибольшим рейтингом
    // и делаем ее текущей
    mr=0;
    for (i=0; i<aOpen.count; i++) {
      if (aOpen.list[i].rating > mr) {
        mr = aOpen.list[i].rating;
        mri = i;
      }
    }
    point=aOpen.list[mri];
       
    // покажем карту с кандидатами
    show_map(1);
  }
  // если до финиша не дошли, построим путь в тупик..
  build_path(point);
}

//=============================================
// основной цикл
int main(int argc, char *argv[])
{
  int i, n;
  // Создаем и показываем карту
  srand(MAZE);
  fill_map();
  read_map();
  show_map(0);
  printf("Press Enter");
  getchar();
 
  // Устанавливаем начальную и конечную точки в разные углы карты
  startPoint.x = 0;
  startPoint.y = 0;
  finalPoint.x = MAX_X-1;
  finalPoint.y = MAX_Y-1;

  // Находим путь и показываем карту
  find_path();
  show_map(0);
  printf("Press Enter");
  getchar();
  return 0;
}
Аватара пользователя
serbod
постоялец
 
Сообщения: 449
Зарегистрирован: 16.09.2016 11:03:02
Откуда: Минск

Re: Олимпиадная задача

Сообщение Лекс Айрин » 10.04.2019 17:31:44

serbod, это ты типа так тонко издеваешься?
Аватара пользователя
Лекс Айрин
долгожитель
 
Сообщения: 5723
Зарегистрирован: 19.02.2013 16:54:51
Откуда: Волгоград

Re: Олимпиадная задача

Сообщение serbod » 10.04.2019 20:32:55

Лекс Айрин писал(а):serbod, это ты типа так тонко издеваешься?

Нет, это я пытаюсь помочь чем могу.

А издеваюсь я так: https://www.youtube.com/watch?v=cdX8r3ZSzN4
Аватара пользователя
serbod
постоялец
 
Сообщения: 449
Зарегистрирован: 16.09.2016 11:03:02
Откуда: Минск

Re: Олимпиадная задача

Сообщение Лекс Айрин » 10.04.2019 21:21:47

serbod, это не тонко... Да и мало кто любит русский рэп.
Аватара пользователя
Лекс Айрин
долгожитель
 
Сообщения: 5723
Зарегистрирован: 19.02.2013 16:54:51
Откуда: Волгоград

Пред.

Вернуться в Free Pascal Compiler

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 17

Рейтинг@Mail.ru