Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > .NET Frameworks (точка нет фреймворки) > C# (си шарп)
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 30.03.2017, 18:12   #1
WonderDoggy
Пользователь
 
Регистрация: 12.01.2017
Сообщений: 18
По умолчанию Найти сумму максимальных значений

Доброго времени суток. Вот условие задачи: Выставка проходит в зале, разделенном на MxN павильонов. Каждая из 4 стен имеет дверь в соседний павильон (кроме граничных). Каждый павильон раздает посетителям предмет одного вида, выдают только один раз в одни руки. Однако посещать данный павильон можно сколь угодно раз. Путь начинается с (1,1) и состоит и последовательности координат. Необходимо выяснить, на какую максимальную сумму можно набрать предметов в течение К минут, если на посещение одного павильона дается 1 минута.
В общем проблема в поиске ближайшего максимального значения, я вроде бы написал проверку, но что-то все равно не так, я уже не знаю как там поменять. Помогите пожалуйста.
Вот мои наработки
Код:
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int n, m, i, j, k, max = 0;
            Console.WriteLine("Введите n: ");
            n = Int32.Parse(Console.ReadLine());
            Console.WriteLine("Введите m: ");
            m = Int32.Parse(Console.ReadLine());
            if ((m == 0 || n == 0) || (m < 0 || n < 0) || (m == 0 && n == 0) || (m < 0 && n < 0))
            {
                Console.WriteLine("Ошибка, не корректно введено значение!");
            }
            int[,] mas = new int[n, m];
            Console.WriteLine("Вот он, выставочный зал: ");
            Random r = new Random();
            for (i = 0; i < n; i++)
            {
                for (j = 0; j < m; j++)
                {
                    mas[i, j] = r.Next(9);
                    Console.Write(mas[i, j] + "\t");
                }
                Console.WriteLine();
            }

            Console.WriteLine();
            //for (i = 0; i < n; i++)
            //{
            //    for (j = 0; j < m; j++)
            //    {
            //        dubl[i, j] = 0;
            //        Console.Write(dubl[i, j] + "\t");
            //    }
            //    Console.WriteLine();
            //}
            Console.WriteLine("------------------------------------------------");
            Console.WriteLine("Введите количество минут на посещение выставки: ");
            k = Int32.Parse(Console.ReadLine());
            int p;
            int e = 0;
            int g = 0;
            int h = 0;
            int s = 0;
            p = mas[0, 0];

            for (i = 0; i < 1; i++)
            {
                for (j = 0; j < k; j++)
                {
                    if (mas[i, j + 1] > mas[i + 1, j])
                    {
                        //mas[i, j] = mas[i, j] + mas[i, j + 1];
                        p += mas[i, j + 1];
                    }
                    if (mas[i + 1, j] > mas[i, j + 1])
                    {
                        // mas[i, j] = mas[i + 1, j] + mas[i, j];
                        e += mas[i + 1, j];
                    }
                    if ((i >= 1 && j >= 1) || (i >= 1 || j >= 1))
                    {
                        if (mas[i - 1, j] > mas[i, j + 1] && mas[i - 1, j] > mas[i + 1, j] && mas[i - 1, j] > mas[i, j - 1])
                        {
                            g += mas[i - 1, j];
                        }
                        if (mas[i, j - 1] > mas[i, j + 1] && mas[i, j - 1] > mas[i + 1, j] && mas[i, j - 1] > mas[i - 1, j])
                        {
                            h += mas[i, j - 1];
                        }
                    }
                    int[] dubl = new int[] { p, e, g, h };
                    Console.WriteLine();

                    for (i = 0; i < 3; i++)
                        Console.Write(dubl[i] + " ");

                    for (i = 0; i < 3; i++)
                    {
                        if (max < dubl[i])
                            dubl[i] = max;
                    }
                    s = max + s;
                    Console.Write(p + "\t");
                }
            }

            //for (i = 0; i < 1; i++)
            //{
            //    for (j = 0; j < k; j++)
            //    {
                    
            //        if (mas[i, j + 1] > mas[i + 1, j])
            //        { 
            //            //mas[i, j] = mas[i, j] + mas[i, j + 1];
            //            p+= mas[i, j+1];
            //        } 
            //        if (mas[i + 1, j] > mas[i, j + 1])
            //        {
            //           // mas[i, j] = mas[i + 1, j] + mas[i, j];
            //            p+= mas[i+1, j];
            //        }
                    
            //       if (i>=1 && mas[i - 1, j] > mas[i, j + 1] && mas[i - 1, j] > mas[i + 1, j] && mas[i - 1, j] > mas[i, j - 1])
            //            {
            //                p+= mas[i - 1, j];
            //            }
            //       if (j >= 1 && mas[i, j-1] > mas[i, j + 1] && mas[i, j-1] > mas[i + 1, j] && mas[i, j-1] > mas[i-1, j])
            //       {
            //           p += mas[i, j-1];
            //       }
            //        Console.Write(p+ "\t");
            //        //cur = Max(mas[i + 1, j], mas[i - 1, j], mas[i, j + 1], mas[i, j - 1]) + mas[i, j];
            //    }
            //}
            
            Console.WriteLine("Максимальная сумма составляет: " + s);
            //for (i = 0; i < n; i++)
            //{
            //    for (j = 0; j < m; j++)
            //    {
            //        Console.Write(mas[i, j] + "\t");
            //    }
            //    Console.WriteLine();
            //}
            Console.ReadKey();
        }

        //public static int Max(int v1, int v2, int v3, int v4)
        //{
        //    return Math.Max(Math.Max(v1, v2), Math.Max(v3, v4));
        //}
    }
}
Все, что закомментировано тоже можно использовать, может там что правильное и было.
WonderDoggy вне форума Ответить с цитированием
Старый 31.03.2017, 10:41   #2
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,229
По умолчанию

а зачем новая тема, чем Вас предыдущая ваш тема не устроила?

Посчитать сумму ближайших максимальных элементов матрицы
Serge_Bliznykov вне форума Ответить с цитированием
Старый 31.03.2017, 10:47   #3
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 18,922
По умолчанию

полагаю min(k,m*n)
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 31.03.2017, 11:02   #4
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,229
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
полагаю min(k,m*n)
Т.е. Вы думаете, что стоимость каждого предмета (одного) в каждом павильоне одинакова?!!

Но ведь об этом в условии задачи не сказано однозначно!
И задача вырождается в какую-то банальщину!


p.s. хотя, конечно, в условии и не сказано, что каждый предмет имеет свою стоимость!

p.p.s. поиском нашёл НОРМАЛЬНЫЕ условия этой задачи:
607. E - Малый бизнес
или тут - http://www.snarknews.info/files/snws/probs/snws3.pdf

Цитата:
Выставка компьютерных фирм проходит в зале, разделенном на N ´ N павильонов. Каждая из четырех стен любого павильона, кроме граничных стен, имеет дверь в соседний павильон. Каждый павильон занят какой-либо фирмой, которая раздает посетителям предметы какого-либо одного вида (ручки, пакеты, проспекты и т.д.). Начинающий компьютерный бизнесмен Вася желает набрать бесплатных предметов на возможно большую сумму. К сожалению, в одни руки выдают только по одному предмету за одно посещение, поэтому Вася вынужден постоянно переходить из павильона в павильон. Посещать один и тот же павильон можно сколько угодно раз. На получение одного предмета Васе требуется одна минута. Требуется определить максимальную сумму, на которую Вася может набрать предметов в течение K минут. Зал определяется квадратной матрицей, содержащей стоимость предметов, выдаваемых в каждом павильоне. , 2 £ N £ 100, 0 < aij <10 000,
aij ÎZ
Путь Васи всегда начинается с павильона (1,1) и состоит из последовательности пар координат (i1, j1), (i2, j2),… ,(iK, jK), 1 £ K £ 10 000, в которой для любого t 1 £ t < K 1 £ it, jt £ N и . По данным N, K и матрице A найти (it, jt), t=1..K такие, что i1 = j1 = 1 и сумма максимальна.
Входные и выходные данные
Первая строка входного файла содержит числа N и K. Следующие N строк представляют 1,2,…,N-ю строки матрицы, по N чисел в строке.
Выходной файл должен содержать единственное число — максимальную сумму.

Последний раз редактировалось Serge_Bliznykov; 31.03.2017 в 11:08.
Serge_Bliznykov вне форума Ответить с цитированием
Старый 31.03.2017, 11:05   #5
Аватар
Старожил
 
Аватар для Аватар
 
Регистрация: 17.11.2010
Сообщений: 18,922
По умолчанию

Там о стоимости предметов в павильонах вообще ни слова не сказано. Значит равна )) Иначе задача лишена смысла до тех пор, пока не будет задаваться стоимость в каждом павильоне. Тогда все гораздо интересней ))
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
Аватар вне форума Ответить с цитированием
Старый 31.03.2017, 11:23   #6
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,229
По умолчанию

Цитата:
Сообщение от Аватар Посмотреть сообщение
Там о стоимости предметов в павильонах вообще ни слова не сказано. Значит равна )) Иначе задача лишена смысла до тех пор, пока не будет задаваться стоимость в каждом павильоне. Тогда все гораздо интересней ))
то, что автору темы дали кривое описание задачи (или он сам её так криво скопировал), совсем не означает, что задача такая уж банально-простая
Конечно, в каждой клетке своя стоимость предмета. и сколько раз посетил клетку - столько раз получил эту стоимость.
Иначе, разумеется, тут и решать нечего.

вот описание входных данных и пример ввода/вывода:
Цитата:
Формат входного файла:
В первой строке записаны числа N и K, 2 <= N <= 100, 1 <= K <= 10000.
В следующих N строках записаны целые значения элементов 1, 2, …, N-ой строки матрицы Ai1, Ai2, …, AiN, по N чисел в строке, 0 < Aij < 10000.

Формат выходного файла:
В первой строке вывести полученный результат – максимальную сумму.

Пример ввода:
Код:
5 7 
1 1 1 1 1 
1 1 3 1 9 
1 1 6 1 1 
1 1 3 1 1 
1 1 1 1 1
Пример вывода:
21


вот, нашёл решение через динамику. На Pascal.
взято тут - http://forum.ru-board.com/topic.cgi?...&limit=1&m=1#1

(с) creer
Код:

var 
  n, k: integer; 
  a, c, p: array [0..101, 0..101] of integer; 
  i, j, kk: integer; 
 
function max(v1, v2, v3, v4: integer):integer; 
begin 
  if (v1>=v2) and (v1>=v3) and (v1>=v4) then 
    max:=v1; 
  if (v2>=v1) and (v2>=v3) and (v2>=v4) then 
    max:=v2; 
  if (v3>=v1) and (v3>=v2) and (v3>=v4) then 
    max:=v3; 
  if (v4>=v1) and (v4>=v2) and (v4>=v3) then 
    max:=v4; 
end; 
 
begin 
  readln(n, k); 
  for i:=1 to n do 
  begin 
    for j:=1 to n do 
      read(a[i,j]); 
    readln; 
  end; 
 
  for kk:=1 to k do 
  begin 
  p:=c; 
    for i:=1 to n do 
      for j:=1 to n do 
        c[i,j]:=max(p[i-1][j], p[i+1][j], p[i][j-1], p[i][j+1])+a[i][j]; 
  end; 
  writeln(c[1,1]); 
end.
разумеется, чтобы выдать не только максимальное значение, а и путь,
решение надо чуток допилить!
Serge_Bliznykov вне форума Ответить с цитированием
Старый 31.03.2017, 16:55   #7
WonderDoggy
Пользователь
 
Регистрация: 12.01.2017
Сообщений: 18
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
что автору темы дали кривое описание задачи
К сожалению, мне именно таким условие и выдали. Нам специально поменяли немного условия в задачах чтобы не было легкой возможности найти в инете решение. А по поводу стоимости: каждая клетка (или же элемент массива) и является стоимостью предмета, и при возвращении в ту или иную клетку сумма повторно не должна считаться.
WonderDoggy вне форума Ответить с цитированием
Старый 31.03.2017, 17:24   #8
Serge_Bliznykov
Старожил
 
Регистрация: 09.01.2008
Сообщений: 26,229
По умолчанию

Цитата:
Сообщение от WonderDoggy Посмотреть сообщение
К сожалению, мне именно таким условие и выдали.Нам специально поменяли немного условия в задачах
вот, я так и понял, что специально не очень умные люди испортили нормальную задачу своими кривыми формулировками.



Цитата:
Сообщение от WonderDoggy Посмотреть сообщение
А по поводу стоимости: каждая клетка (или же элемент массива) и является стоимостью предмета
ткните пальцев, где об этом сказано в условиях задачи!
Если об этом не сказано в условиях задачи, откуда Вы это взяли?
Интуиция? Голос свыше? Тайное послание от Юстаса?
Или просто придумали?


Цитата:
Сообщение от WonderDoggy Посмотреть сообщение
и при возвращении в ту или иную клетку сумма повторно не должна считаться
а это откуда взялось?!
раз посещать можно многократно? да ещё и про одни руки зачем-то сказано!
Цитата:
Сообщение от WonderDoggy Посмотреть сообщение
Каждый павильон раздает посетителям предмет одного вида, выдают только один раз в одни руки. Однако посещать данный павильон можно сколь угодно раз.
подразумевается один раз в одни руки при каждом посещении этого павильона? Если это не так, почему в условии об этом не сказано?

А где ограничения на входные данные?
Размеры N и M чем-то ограничены? Матрицу 1000000 на 4000000000 решите?
А стоимость каждого предмета? Если стоимость предмета от 1 до 4000000000 есть решение задачи?

вот поэтому я и говорю, не очень квалифицированные у Вас учителя, которые Вас криво учат.
Разумеется, всё сказанное - это исключительно моё личное мнение, IMHO.
Это Вам учиться, Вам решать эту не очень прямую задачу и Вам её сдавать.



p.s. чувствую, что в задаче про расставленных мышах тот же изобретатель классическую задачу испоганил так, чтобы решение в интернете нельзя было найти. Ну а то, что задача при этом стала бессмысленное, это уже не так важно, это, так сказать, побочный эффект!
Serge_Bliznykov вне форума Ответить с цитированием
Старый 31.03.2017, 18:26   #9
WonderDoggy
Пользователь
 
Регистрация: 12.01.2017
Сообщений: 18
По умолчанию

Цитата:
Сообщение от Serge_Bliznykov Посмотреть сообщение
ткните пальцев, где об этом сказано в условиях задачи!
Это мой фейл, прошу прощения. Это я выяснил после уточнения условия у преподавателя. Я говорю и про стоимости, и про то, что сумма с павильоном не считается по возвращении в предыдущий. Собственно поэтому я ее и скинул сюда в надежде на какое-нибудь объяснение или помощь
WonderDoggy вне форума Ответить с цитированием
Старый 01.04.2017, 16:34   #10
WonderDoggy
Пользователь
 
Регистрация: 12.01.2017
Сообщений: 18
По умолчанию

В общем решил я задачу, не совсем сам конечно, мне помогли, однако все же она решена. Вот скидываю сюда, вдруг кому пригодится:
Код:
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;
using System.Diagnostics;
using System.Threading;
using System.Data;

namespace ConsoleApplication1
{
    class Program
    {
        static Random rnd = new Random();
        static void Main(string[] args)
        {
            Console.Write("Введите n=");
            int n = int.Parse(Console.ReadLine());
            Console.Write("Введите m=");
            int m = int.Parse(Console.ReadLine());
            int[,] labirinth = new int[n, m];
            for (int i = 0; i < labirinth.GetLength(0); i++)
            {
                for (int j = 0; j < labirinth.GetLength(1); j++)
                {
                    labirinth[i, j] = rnd.Next(1, 10);
                    Console.Write(labirinth[i, j] + "  ");
                }
                Console.WriteLine();
            }
            Console.Write("Количество минут на посещение выставки=");
            int k = int.Parse(Console.ReadLine());
            k = k + 1;
            Console.WriteLine("Максимальная сумма предметов составляет:");
            Console.WriteLine(MaxSum(labirinth, k));
            Console.ReadKey(true);
        }
        static int MaxSum(int[,] array, int t, int x = 0, int y = 0, int sum = 0)
        {
            array = (int[,])array.Clone();
            sum += array[x, y];
            array[x, y] = 0;
            if (--t == 0) return sum;
            if (x == 0)
            {
                if (y == 0) return Math.Max(MaxSum(array, t, x + 1, y, sum), MaxSum(array, t, x, y + 1, sum));
                if (y == array.GetLength(1) - 1) return Math.Max(MaxSum(array, t, x + 1, y, sum), MaxSum(array, t, x, y - 1, sum));
                return Math.Max(Math.Max(MaxSum(array, t, x + 1, y, sum), MaxSum(array, t, x, y + 1, sum)), MaxSum(array, t, x, y - 1, sum));
            }
            if (x == array.GetLength(0) - 1)
            {
                if (y == 0) return Math.Max(MaxSum(array, t, x - 1, y, sum), MaxSum(array, t, x, y + 1, sum));
                if (y == array.GetLength(1) - 1) return Math.Max(MaxSum(array, t, x - 1, y, sum), MaxSum(array, t, x, y - 1, sum));
                return Math.Max(Math.Max(MaxSum(array, t, x - 1, y, sum), MaxSum(array, t, x, y + 1, sum)), MaxSum(array, t, x, y - 1, sum));
            }
            if (y == 0)
            {
                return Math.Max(Math.Max(MaxSum(array, t, x + 1, y, sum), MaxSum(array, t, x, y + 1, sum)), MaxSum(array, t, x - 1, y, sum));
            }
            if (y == array.GetLength(1) - 1)
            {
                return Math.Max(Math.Max(MaxSum(array, t, x - 1, y, sum), MaxSum(array, t, x + 1, y, sum)), MaxSum(array, t, x, y - 1, sum));
            }
            return Math.Max(Math.Max(MaxSum(array, t, x + 1, y, sum), MaxSum(array, t, x, y + 1, sum)), Math.Max(MaxSum(array, t, x - 1, y, sum), MaxSum(array, t, x, y - 1, sum)));
        }
    }
}
Задача решалась методом рекурсивного обхода.
WonderDoggy вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Pascal abc: Дан двумерный массив размерностью 10 на 10 . Найти сумму элементов максимальных в каждом столбце. Artemikkk Помощь студентам 2 06.11.2016 12:49
найти сумму максимальных значений из 2-х масивов. bratello41 C++ Builder 1 17.12.2010 14:25
Pascal/ Найти сумму максимальных элементов 3ех массивов. lMasterl Помощь студентам 8 26.09.2010 17:30
Паскаль-Найти сумму максимальных элементов строк матрицы tanyhaftv Помощь студентам 9 24.03.2010 16:03
Найти сумму вычисленных значений функции Meet163 Фриланс 12 17.02.2010 05:22