Форум программистов, компьютерный форум, киберфорум
Pascal ABC
Войти
Регистрация
Восстановить пароль
Другие темы раздела
Pascal ABC Введите с клавиатуры номер месяца и выведите его название, используя разные цвета для каждого сезона составить алгоритм и программу, введите с клавиатуры номер месяца и выведите его название, используя разные цвета для каждого сезона. не могу никак правильно сделать. помогите пожалуйста) https://www.cyberforum.ru/ pascalabc/ thread1389058.html Введите 3 числа с клавиатуры и выведите в левом верхнем углу экрана четные из них Pascal ABC
составить программу, введите 3 числа с клавиатуры и выведите в левом верхнем углу экрана четные из них, а в правом нижнем углу - нечетные, используя синий цвет для четных и красный для нечетных....
Pascal ABC Разроботать список процедур, для работы с динамической структурой данных Разработать список процедур, для работы с динамической структурой данных (Дек) https://www.cyberforum.ru/ pascalabc/ thread1388942.html Pascal ABC Написать программу для работы с файлом В файле содержатся записи из выбранной вами предметной области. Запись должна содержать 10 полей различных типов данных. Написать программу для работы с файлом. Программа должна содержать следу-... https://www.cyberforum.ru/ pascalabc/ thread1388940.html
Написать программу подсчета в тексте количества циклов while . . . do; Pascal ABC
В файле хранится работающая программа на ЯП Pascal. Написать программу подсчета в тексте количества циклов while . . . do;
Pascal ABC Написать программу перевода целого числа a из цифрового формата в прописной Написать программу перевода целого числа a из цифрового фор- мата в прописной. a < 1012 Пример: a = 123 ⇒ cто двадцать три. https://www.cyberforum.ru/ pascalabc/ thread1388938.html
Pascal ABC Заполнить двумерный массив числами от 1 до N*N по правилу https://www.cyberforum.ru/ pascalabc/ thread1388935.html
Надо заполнить двумерный массив NxN числами от 1 до N*N следующим образом (N вводится с клавиатуры): а вот и сама змейка. Спасибо
Pascal ABC Вычисление значение функции в точке х, используя разложение в ряд Маклорена
надо написать программу для вычисление значение функции в точке х, с помощью разложения в ряд Маклорена. x, ε вводятся с клавиатуры. \sqrt {1+x} = 1+\frac{x}{2} -\frac{x^2}{8} +\frac{x^3}{16}+...=...
Pascal ABC Сформировать массив из произведений положительных элементов каждой строки Дан двумерный массив C из M строк и N столбцов. 1) Сформировать массив из: а) произведений положительных элементов каждой строки; если их нет, результат должен быть равен 0; б) количества таких... https://www.cyberforum.ru/ pascalabc/ thread1388888.html Pascal ABC Изменить программу интегрирования методом второго порядка https://www.cyberforum.ru/ pascalabc/ thread1388875.html
Здравствуйте. Возникла проблема с задачей. Вот ее решение: Const Dt=0.1; V=-0.5; Q=0.0; Var f:Text; V_old,V_new,Q_old,Q_new,t:Real; i:integer;
Удалить подсписок студентов с фамилии F1 до фамилиии F2 включительно Pascal ABC
Пусть задан список студентов . Элемент списка содержит : фамилию , имя , № курса , № группы , оценки по пяти экзаменах последней сессии . пусть , фамилии студентов в списке упорядочены по алфавиту...
Pascal ABC Ввести с клавиатуры или сгенерировать 20 элементов массива https://www.cyberforum.ru/ pascalabc/ thread1388761.html
Помогите с программой: 1. Ввести с клав. или с генерировать 20 элементов массива так чтобы среди них были положительные отрицательные и равные нулю. каких элементов массива больше, вывести...
Модератор
Эксперт по электронике
7689 / 3846 / 1490
Регистрация: 01.02.2015
Сообщений: 11,887
Записей в блоге: 2
07.03.2015, 14:48 0

Найти маршрут, двигаясь по которому мышка соберет наибольшее количество зернышек - Pascal ABC - Ответ 7309458

07.03.2015, 14:48. Показов 1026. Ответов 2
Метки (Все метки)

Ответ

А можно ещё одним способом - смесью bfs и алгоритма Дейкстры. Должно быть быстрее за счёт сохранения оптимальной предистории и сокращения вариантов перебора. Правда исходник разрастётся.

Добавлено через 16 часов 11 минут
Например так
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
program Mouse;
 
const
  Mmax = 100;
  Nmax = 100;
  Kmax = 30000;
var
  m, n: integer;
  floor: array of array of DWord; //"пол" в храме
  grain: array of array of DWord; //максимальное количество зёрен при прохождении к ячейке
  prev: array of array of char;   //в символьном виде указывает предыдущую плитку в маршруте
  WaveI, WaveJ: array of array of integer; //список ячеек для текущего и следующего прохода
  WaveL: array [0..1] of integer; //длины списков текущего и следующего проходов
  WaveN, WaveNnext: integer;      //индексы списков текущего и следующего проходов
  i, j: integer;
  ii, jj: integer;
  s: string;
begin
  Assign(input, 'mouse.in');
  reset(input);
  readln(m, n);
  SetLength(floor, m, n);
  SetLength(grain, m, n);
  SetLength(prev, m, n);
  SetLength(WaveI, 2, m + n);
  SetLength(WaveJ, 2, m + n);
  for i := 1 to m do
  begin
    for j := 1 to n do
    begin
      Read(floor[i - 1, j - 1]);
      grain[i - 1, j - 1] := 0;
    end;
    readln;
  end;
  
  WaveN := 0;
  WaveL[WaveN] := 0;
  WaveI[WaveN][WaveL[WaveN]] := n - 1;
  WaveJ[WaveN][WaveL[WaveN]] := 0;
  Inc(WaveL[WaveN]);
  grain[n - 1, 0] := floor[n - 1, 0];
  prev[n - 1, 0]  := 'S';
  while WaveL[WaveN] > 0 do
  begin
    WaveNnext := (WaveN + 1) mod 2;
    WaveL[WaveNnext] := 0;
    for i := 0 to WaveL[WaveN] - 1 do
    begin
      ii := WaveI[WaveN][i];
      jj := WaveJ[WaveN][i];
      if ii < n - 1 then
      begin
        if grain[ii, jj] < grain[ii + 1, jj] + floor[ii, jj] then
        begin
          prev[ii, jj]  := 'F';
          grain[ii, jj] := grain[ii + 1, jj] + floor[ii, jj];
        end;
      end;
      if jj > 0 then
      begin
        if grain[ii, jj] < grain[ii, jj - 1] + floor[ii, jj] then
        begin
          prev[ii, jj]  := 'R';
          grain[ii, jj] := grain[ii, jj - 1] + floor[ii, jj];
        end;
      end;
      if ii > 0 then
      begin
        WaveI[WaveNnext][WaveL[WaveNnext]] := ii - 1;
        WaveJ[WaveNnext][WaveL[WaveNnext]] := jj;
        Inc(WaveL[WaveNnext]);
      end;
      if (jj < n - 1) and (ii = n - 1) then
      begin
        WaveI[WaveNnext][WaveL[WaveNnext]] := ii;
        WaveJ[WaveNnext][WaveL[WaveNnext]] := jj + 1;
        Inc(WaveL[WaveNnext]);
        grain[ii, jj + 1] := grain[ii, jj] + floor[ii, jj + 1];
        prev[ii, jj + 1]  := 'R';
      end;
    end;
    WaveN := WaveNnext;
  end;
  {восстановление пути}
  SetLength(s, n + m - 2);
  ii := 0;
  jj := n - 1;
  for i := n + m - 2 downto 1 do
  begin
    s[i] := prev[ii, jj];
    if s[i] = 'F' then
      ii := ii + 1
    else
      jj := jj - 1;
  end;
  writeln(s);
  Close(input);
end.
Здесь реализовано подобие волнового алгоритма (разновидность bfs). Переключение между текущей и предыдущей волнами по переменной WaveN - чтобы избежать длительного копирования массивов. Это подобие "очереди", сейчас мне кажется, что можно было обойтись одной общей очередью.
В grain хранится максимально возможное количество зерен, при перемещении из начальной клетки в grain[i,j].

Вернуться к обсуждению:
Найти маршрут, двигаясь по которому мышка соберет наибольшее количество зернышек Pascal ABC
1
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
07.03.2015, 14:48
Готовые ответы и решения:

Напишите программу, которая находит наибольшее количество монет, которое может собрать пират, и выводит его маршрут
Прямоугольный остров разделён на квадраты, так что его размеры – N на M квадратов. В каждом...

Найти наибольшее возможное значение суммы и маршрут, на котором достигается эта сумма
В левом верхнем углу прямоугольной таблицы размером N×M находится черепашка. В каждой клетке...

Найти наибольшее возможное значение суммы и маршрут, на котором достигается эта сумма
Добрый вечер. Не понимаю вообще как решить. Прошу помочь. В левом верхнем углу прямоугольной...

Массив: Последнее дело Оушена. Составьте маршрут, следуя которому, Оушен успеет ограбить все банки.
Оушен отправляется на пенсию! Но для обеспечения безбедной старости он решил напоследок ограбить n...

2
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
07.03.2015, 14:48

Найти маршрут, включающий максимальное количество городов и удовлетворяющий вышеназванными условиям
Вы победили в соревновании, организованном Канадскими авиалиния-ми. Приз – бесплатное путешествие...

Найти маршрут, включающий максимальное количество городов и удовлетворяющий вышеназванными условиям
Вы победили в соревновании, организованном Канадскими авиалиния-ми. Приз – бесплатное путешествие...

0
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.