- 🔴 21:26 Повітряна тривога в Харків.обл.
- #21
Ну все таки оформите хотя бы на псевдокоде полный, логически-завершенный алгоритм.
🔴 21:26 Повітряна тривога в Харків.обл.
Разминка для моска.
🔴 21:26 Повітряна тривога в Харків.обл.
- Автор теми ASokol
- Дата створення
Ну все таки оформите хотя бы на псевдокоде полный, логически-завершенный алгоритм.
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #22
Хоть это уже совсем не серьезно, но ладно, приведу готовый псевдокод:
Код:
Для i = 1..n-1 // В предыдущий раз ошибся с конечными индексами
Для j = 0..m-1
indFrom = j;
indTo = j;
Если indFrom > 0
indFrom--;
Если indTo < m - 1
indTo++;
indMin = indFrom;
Для k = indFrom + 1 .. indTo
Если Fee[i - 1, k] < Fee[i - 1, indMin]
indMin = k;
Ind[i, j] = indMin;
Fee[i, j] = A[i, j] + Fee[i - 1, indMin]- 🔴 21:26 Повітряна тривога в Харків.обл.
- #23
Код:
const int n = 4;
const int m = 4;
int Fee[n][m] = {{1,1,1,1},{1,1,1,1},{1,2,2,2},{1,1,1,1}};
int A[n][m] = {{1,1,1,1},{1,1,1,1},{1,2,2,2},{1,1,1,1}};
int Ind[n][m];
for(int i = 1; i<n; i++)
{
for(int j = 0; j<m; j++)
{
int indFrom = j;
int indTo = j;
if(indFrom > 0)
indFrom--;
if(indTo < (m-1))
indTo++;
int indMin = indFrom;
for(int k = indFrom+1; k<indTo+1; k++)
{
if(Fee[i-1][k] < Fee[i-1][indMin])
indMin = k;
Ind[i][j] = indMin;
Fee[i][j] = A[i][j] + Fee[i-1][indMin];
}
}
}Все верно?
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #25
Ну собственно, что и требовалось доказать.
Код:
const int n = 4;
const int m = 4;
int Fee[n][m] = {{1,1,1,1},{1,1,1,1},{1,2,2,2},{1,1,1,1}};
int A[n][m] = {{1,1,1,1},{1,1,1,1},{1,2,2,2},{1,1,1,1}};
int Ind[n][m];
for(int i = 1; i<n; i++)
{
for(int j = 0; j<m; j++)
{
int indFrom = j;
int indTo = j;
if(indFrom > 0)
indFrom--;
if(indTo < (m-1))
indTo++;
int indMin = indFrom;
for(int k = indFrom+1; k<indTo+1; k++)
{
if(Fee[i-1][k] < Fee[i-1][indMin])
indMin = k;
}
Ind[i][j] = indMin;
Fee[i][j] = A[i][j] + Fee[i-1][indMin];
}
}Вот матрица Ind. Как по ней определить оптимальный маршрут?
-858993460 -858993460 -858993460 -858993460
0 0 1 2
0 0 1 2
0 0 1 2
Последняя строка Fee
4 4 5 5
Статус:
Offline
Реєстрація: 16.12.2008
Повідом.: 2067
Реєстрація: 16.12.2008
Повідом.: 2067
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #26
Достопримечательный АСокол,зачем вы так себя ославили в генерациях милипидрического текста.Мы же все таки находимся там,где серьезные люди бывают.Подобные задачи вызовут интерес,если вместо циферок будут сложные обьекты.
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #27
Нет, я не понимаю алгоритмов на словах. Формализуйте в виде псевдокода, как именно из этих матриц восстановить оптимальный маршрут.
А если в последней строке матрицы Fee вы получите 500, 1000, 10000... одинаковых значений?
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #28
Если вы самостоятельно не умеете это делать, обратитесь к более опытным товарищам.
Я сначала подумал это исходная матрица.
Первая строчка страшна, так как там мусор (ох уж этот C), но на нее можно не смотреть - она не используется
Одинаковые числа в последней строчке Fee говорят о том, что штраф (суммарный) для каждой из этих клеток будет одинаков. Поэтому выбирайте из них любую, хоть первую, хоть последнюю, хоть рандомную.
В даном случае выбираем, например, первую четверку. Дальше смотрим на Ind[3,0] (ведь 4 стоит в этой позиции), видим там 0, что означает что нам надо перейти вверх на нулевую колонку. Дальше повторяем то же самое для второй и первой строки. В итоге получаем: 1 1 1 1
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #29
Ну так вперед, формализуйте способ получения оптимального маршрута. А то вы доказываете, что понимаете, а формализовать не в состоянии.
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #30
Послушайте, я достаточно написал для решения задачи. Разжевывать задачу уровня школьной олимпиады я больше не буду. Предлагаю все-таки, как написано в теме, размять свой моск.
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #31
Да не надо разжевывать, ваш код занимает меньше, чем ваш флуд на форуме. Мне проще объяснять алгоритм на псевдокоде, это занимает меньше времени! чем бесполезные умозрительные заключения.
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #32
+1 к Оршанскому. Шварцу незачет - дешевый слив "я типа написал достаточно". Достаточно - это когда копипастишь в Студию, нажимаешь Ф5 - и оно работает. Именно так делают и ТС и Оршанский.
А вообще тут уже справедливо упоминали коммивояжера. ИМХО если надо идеальное решение (а не статистически хорошее) - то кроме полного перебора тут ничего не придумаешь. И собсно задача тогда сводится к тому, кто лучше придумает алгоритм отсечения заведомо невыгодных ветвей. Но опять же на любой самый хитро закрученный алгоритм можно придумать матрицу, которая заставит этот алгоритм сделать ПОЛНЫЙ перебор.
ИМХО смысл этой задачи на конкурсе: отсечь дятлов, которые слышали слово рекурсия, но не знают сколько будет 3 в 1000-й степени
А вообще тут уже справедливо упоминали коммивояжера. ИМХО если надо идеальное решение (а не статистически хорошее) - то кроме полного перебора тут ничего не придумаешь. И собсно задача тогда сводится к тому, кто лучше придумает алгоритм отсечения заведомо невыгодных ветвей. Но опять же на любой самый хитро закрученный алгоритм можно придумать матрицу, которая заставит этот алгоритм сделать ПОЛНЫЙ перебор.
ИМХО смысл этой задачи на конкурсе: отсечь дятлов, которые слышали слово рекурсия, но не знают сколько будет 3 в 1000-й степени
Останнє редагування:
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #33
Это необходимая достаточность разве что для людей едва знакомых с программированием. Ну раз настолько все туго, то придется мне отказаться от своих слов и не только разжевать, но и в рот положить.
Вот заветные три строчки кода:
Код:
// indMin - индекс клетки с минимальным значением в нижней строке
// Res(n) - результирующий вектор
Для i = n-1..0 // двигаемся в обратную сторону
Res[i] = A[i, indMin];
indMin = Ind[i, indMin];Насчет производительности алгоритма, то можно её улучшить, применяя одно сравнение на клетку вместо двух. Кто захочет, тот подумает как.
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #34
Странно читать такое от весьма мною уважаемого (это не шутка) BFG-9000. Я в этой дискуссии поддержу Shwartz'а. Его подход к решению, по-моему, является правильным, а сама задача является типичной задачей на динамическое программирование и, конечно, не требует полного перебора (в смысле NP-полного, как для задачи коммивояжёра). Странно, что другие участники дискуссии не видят из описания алгоритма Shwartz'а, что это и есть классическое решение задач такого рода, которое, опять таки по-моему, действительно не требует дальнейшего разжёвывания для понимания человеком с каким-никаким опытом.
И всё же специально для тех, кому нужно F5, вот Вам мой код на языке моего выбора C#, который вполне поддерживается современной студией:
Код:
using System;
using System.IO;
namespace ShortestPath
{
class Program
{
static int[,] ReadFromFile(string fileName)
{
using (Stream inp = new FileStream(fileName, FileMode.Open, FileAccess.Read))
using (TextReader reader = new StreamReader(inp))
{
string tmpString;
string[] tmpTokens;
tmpString = reader.ReadLine();
tmpTokens = tmpString.Split(' ');
int colCount = int.Parse(tmpTokens[0]);
int rowSize = int.Parse(tmpTokens[1]);
int[,] res = new int[colCount, rowSize];
for (int y = 0; y < colCount; y++)
{
tmpString = reader.ReadLine();
tmpTokens = tmpString.Split(' ');
for (int x = 0; x < rowSize; x++)
{
res[y, x] = int.Parse(tmpTokens[x]);
}
}
return res;
}
}
static void Main(string[] args)
{
int[,] penalty = ReadFromFile("input.txt");
//int[,] penalty = new int[,]
// {
// {3, 2, 8, 6, 4,},
// {4, 7, 12, 9, 1},
// {55, 8, 3, 2, 8},
// {20, 7, 4, 9, 1},
// };
//int[,] penalty = new int[,] {{1, 1, 1, 1}, {1, 1, 1, 1}, {1, 2, 2, 2}, {1, 1, 1, 1}};
int rowSize = penalty.GetLength(1);
int colCount = penalty.GetLength(0);
int[,] indFrom = new int[colCount, rowSize];
int[,] sum = new int[colCount, rowSize];
for (int x = 0; x < rowSize; x++)
{
indFrom[0, x] = -1;
sum[0, x] = penalty[0, x];
//Console.Write(sum[0, x] + "\t");
}
//Console.WriteLine();
for (int y = 1; y < colCount; y++)
{
for (int x = 0; x < rowSize; x++)
{
int[] p = new int[]{
(x == 0) ? int.MaxValue : sum[y - 1, x - 1],
sum[y - 1, x],
(x == rowSize - 1) ? int.MaxValue : sum[y - 1, x+1],
};
int minInd = 0;
for (int i = 1; i < p.Length; i++)
{
if (p[i] < p[minInd]) minInd = i;
}
indFrom[y, x] = minInd + (x - 1);
sum[y, x] = p[minInd] + penalty[y, x];
//Console.Write(sum[y, x] + "\t");
}
//Console.WriteLine();
}
{
int minInd = 0;
for (int i = 1; i < rowSize; i++)
{
if (sum[colCount - 1, i] < sum[colCount - 1, minInd]) minInd = i;
}
Console.WriteLine(sum[colCount - 1, minInd]);
int[] optPen = new int[colCount];
for (int y = colCount - 1; y >= 0; y--)
{
optPen[y] = penalty[y, minInd];
minInd = indFrom[y, minInd];
}
for (int y = 0; y < colCount; y++)
{
Console.Write(optPen[y] + " ");
}
Console.WriteLine();
}
}
}
}- 🔴 21:26 Повітряна тривога в Харків.обл.
- #35
Ну что ж, давайте поиграем в destructive engineering
Код:
using System;
using System.IO;
namespace ShortestPath
{
class Program
{
static int[,] ReadFromFile(string fileName)
{
using (Stream inp = new FileStream(fileName, FileMode.Open, FileAccess.Read))
using (TextReader reader = new StreamReader(inp))
{
string tmpString;
string[] tmpTokens;
tmpString = reader.ReadLine();
tmpTokens = tmpString.Split(' ');
int colCount = int.Parse(tmpTokens[0]);
int rowSize = int.Parse(tmpTokens[1]);
int[,] res = new int[colCount, rowSize];
for (int y = 0; y < colCount; y++)
{
tmpString = reader.ReadLine();
tmpTokens = tmpString.Split(' ');
for (int x = 0; x < rowSize; x++)
{
res[y, x] = int.Parse(tmpTokens[x]);
}
}
return res;
}
}
static void Main(string[] args)
{
//int[,] penalty = ReadFromFile("input.txt");
//int[,] penalty = new int[,]
// {
// {3, 2, 8, 6, 4,},
// {4, 7, 12, 9, 1},
// {55, 8, 3, 2, 8},
// {20, 7, 4, 9, 1},
// };
int[,] penalty = new int[,] {{1, 1, 1, 0}, {1, 1, 1, 0}, {1, 2, 2, 0}, {1, 1, 1, 0}};
int rowSize = penalty.GetLength(1);
int colCount = penalty.GetLength(0);
int[,] indFrom = new int[colCount, rowSize];
int[,] sum = new int[colCount, rowSize];
for (int x = 0; x < rowSize; x++)
{
indFrom[0, x] = -1;
sum[0, x] = penalty[0, x];
//Console.Write(sum[0, x] + "\t");
}
//Console.WriteLine();
for (int y = 1; y < colCount; y++)
{
for (int x = 0; x < rowSize; x++)
{
int[] p = new int[]{
(x == 0) ? int.MaxValue : sum[y - 1, x - 1],
sum[y - 1, x],
(x == rowSize - 1) ? int.MaxValue : sum[y - 1, x+1],
};
int minInd = 0;
for (int i = 1; i < p.Length; i++)
{
if (p[i] < p[minInd]) minInd = i;
}
indFrom[y, x] = minInd + (x - 1);
sum[y, x] = p[minInd] + penalty[y, x];
//Console.Write(sum[y, x] + "\t");
}
//Console.WriteLine();
}
{
int minInd = 0;
for (int i = 1; i < rowSize; i++)
{
if (sum[colCount - 1, i] < sum[colCount - 1, minInd]) minInd = i;
}
Console.WriteLine(sum[colCount - 1, minInd]);
int[] optPen = new int[colCount];
for (int y = colCount - 1; y >= 0; y--)
{
optPen[y] = penalty[y, minInd];
minInd = indFrom[y, minInd];
}
for (int y = 0; y < colCount; y++)
{
Console.Write(optPen[y] + " ");
}
Console.WriteLine();
}
}
}
}Рузультат работы программы:
0
0 0 0 0
Хочу заметить, что в теоретико-множественной модели натурального ряда ноль - является натуральным числом.
Код:
using System;
using System.IO;
namespace ShortestPath
{
class Program
{
static int[,] ReadFromFile(string fileName)
{
using (Stream inp = new FileStream(fileName, FileMode.Open, FileAccess.Read))
using (TextReader reader = new StreamReader(inp))
{
string tmpString;
string[] tmpTokens;
tmpString = reader.ReadLine();
tmpTokens = tmpString.Split(' ');
int colCount = int.Parse(tmpTokens[0]);
int rowSize = int.Parse(tmpTokens[1]);
int[,] res = new int[colCount, rowSize];
for (int y = 0; y < colCount; y++)
{
tmpString = reader.ReadLine();
tmpTokens = tmpString.Split(' ');
for (int x = 0; x < rowSize; x++)
{
res[y, x] = int.Parse(tmpTokens[x]);
}
}
return res;
}
}
static void Main(string[] args)
{
//int[,] penalty = ReadFromFile("input.txt");
//int[,] penalty = new int[,]
// {
// {3, 2, 8, 6, 4,},
// {4, 7, 12, 9, 1},
// {55, 8, 3, 2, 8},
// {20, 7, 4, 9, 1},
// };
int[,] penalty = new int[,] {{1, 1, 1, 1}, {1, 1, 1, 1}, {2, 1, 1, 1}, {1, 1, 1, 1}};
int rowSize = penalty.GetLength(1);
int colCount = penalty.GetLength(0);
int[,] indFrom = new int[colCount, rowSize];
int[,] sum = new int[colCount, rowSize];
for (int x = 0; x < rowSize; x++)
{
indFrom[0, x] = -1;
sum[0, x] = penalty[0, x];
//Console.Write(sum[0, x] + "\t");
}
//Console.WriteLine();
for (int y = 1; y < colCount; y++)
{
for (int x = 0; x < rowSize; x++)
{
int[] p = new int[]{
(x == 0) ? int.MaxValue : sum[y - 1, x - 1],
sum[y - 1, x],
(x == rowSize - 1) ? int.MaxValue : sum[y - 1, x+1],
};
int minInd = 0;
for (int i = 1; i < p.Length; i++)
{
if (p[i] < p[minInd]) minInd = i;
}
indFrom[y, x] = minInd + (x - 1);
sum[y, x] = p[minInd] + penalty[y, x];
//Console.Write(sum[y, x] + "\t");
}
//Console.WriteLine();
}
{
int minInd = 0;
for (int i = 1; i < rowSize; i++)
{
if (sum[colCount - 1, i] < sum[colCount - 1, minInd]) minInd = i;
}
Console.WriteLine(sum[colCount - 1, minInd]);
int[] optPen = new int[colCount];
for (int y = colCount - 1; y >= 0; y--)
{
optPen[y] = penalty[y, minInd];
minInd = indFrom[y, minInd];
}
for (int y = 0; y < colCount; y++)
{
Console.Write(optPen[y] + " ");
}
Console.WriteLine();
}
}
}
}Ну тут вообще нет слов.
Рузультат работ программы:
4
1 1 1 1
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #36
Ну что ж, давайте попробуем! Никто не идеален и я не исключение.
По поводу того, является ли 0 натуральным или нет я спор предлагаю отложить, хотя, по-моему, более общепринятым ответом является отрицательный. Хотелось бы уточнить, чем не устраивает ответ программы?
Как я вижу, оптимальный путь выглядит так
1 1 1 0
1 1 1 0
1 2 2 0
1 1 1 0
Или я что-то недопонял в условии?
Аналогично второй пример
Вариантов на выбор - море, например так
1 1 1 1
1 1 1 1
2 1 1 1
1 1 1 1
Итак, вопрос к господам деструкторам: Можно конкретизировать претензию и предоставить "правильный авторский ответ" для приведенных примеров?
Кроме того, хотелось бы увидеть комментарий к ответам, приведенным в самом первом посте как пояснение к задаче. Для сравнения вот моё понимание первого примера:
3 2 8 6 4
4 7 12 9 1
55 8 3 2 8
20 7 4 9 1
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #37
Да, похоже что все верно, честно говоря подумал что необходимо выводить номер оптимальной ячейки в каждой строке матрицы.
- 🔴 21:26 Повітряна тривога в Харків.обл.
- #38
Краткая история вопроса:
Ну и так, в качестве резюме:
P.S. Адекватность нарезки цитат на совести автора (т.е. моей). Каждый может посмотрерть историю и увидеть полный контекст.
К сожалению, всё оказалось ещё туже:
Однако не всё потеряно! Всё таки, если не только разжевать, а ещё и предварительно пропустить через блендер и превратить совсем уж в пюре, то условие, а следом за ним и решение становятся доступными для понимания даже самыми упорными участниками дискуссии.
Ну и так, в качестве резюме:
ИМХО смысл этой задачи на конкурсе: отсечь дятлов, которые слышали слово рекурсия, но не знают сколько будет 3 в 1000-й степени
P.S. Адекватность нарезки цитат на совести автора (т.е. моей). Каждый может посмотрерть историю и увидеть полный контекст.
Останнє редагування: