Форум программистов, компьютерный форум CyberForum.ru

Выгодная матрица - C++

Восстановить пароль Регистрация
 
Bloodykeeper
This party getting crazy!
 Аватар для Bloodykeeper
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
15.02.2010, 18:12     Выгодная матрица #1
Имеется k селений. Если в селении i расположена больница, то поездка в селение j займёт время a[i][j]. Найти номер селения i, в котором выгоднее всего разместить больницу (поездка из i в самое удалённое по времени селение должна занять минимальное время).

Подкиьте пару троек идей, не могу додуматься что надо сделать...(
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
15.02.2010, 18:12     Выгодная матрица
Посмотрите здесь:

матрица C++
матрица C++
C++ Матрица
C++ Матрица
МАТРИЦА C++
C++ матрица
матрица C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
15.02.2010, 19:01     Выгодная матрица #2
Примерно так
C
1
2
3
4
5
6
7
8
9
10
11
 for(i=0; i<k; i++) {
   for(j=0; j<k; j++) 
      if (j==0 || a[i][j] > t) t = a[i][j];
   }
      // t - max время, если больньничка в i
    if (i==0 || t < tm) {
         tm = t;
         im = i;
     }
}
cout<< "Selo "<<i << "Time="<< tm;
Bloodykeeper
This party getting crazy!
 Аватар для Bloodykeeper
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
15.02.2010, 19:03  [ТС]     Выгодная матрица #3
ещё идеи??
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.02.2010, 19:10     Выгодная матрица #4
Нужно искать во всех строках максимальные элементы. А потом выбрать строку с самым минимальным из них. Номер строки и будет ответом.
Bloodykeeper
This party getting crazy!
 Аватар для Bloodykeeper
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
16.02.2010, 16:25  [ТС]     Выгодная матрица #5
Может быть глупый вопрос, но никогда не искал максимальные элементы в столбах и строках. Можно мне хотя бы черновой вариант для моих "шаблонов"? А я подправлю. Заранее спасибо.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.02.2010, 16:51     Выгодная матрица #6
Допустим есть матрица a[n][n] (для данного задания она будет квадратной), тогда так:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    int i, j, max, temp, max_min_i=0;
    max=a[0][0];
    for(j=1; j<n; j++)
        if(a[0][j]>max)
            max=a[0][j];
    for(i=1; i<n; i++)
    {
        temp=a[i][0];
        for(j=1; j<n; j++)
            if(temp<a[i][j])
                temp=a[i][j];
        if(temp<max)
        {
            max=temp;
            max_min_i=i;
        }
    }
// вот здесь в переменной max_min_i находится нужное нам значение (номер нужной строки - соответственно номер селения)
Bloodykeeper
This party getting crazy!
 Аватар для Bloodykeeper
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
16.02.2010, 20:04  [ТС]     Выгодная матрица #7
А как это можно соединить с шапочкой? К примеру динамического массива? естесственно, мы предусматриваем, что матрица должна быть квадратной.
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
 
int main ()
{
    int **mas, n, m, k, i,j;
    printf("Enter numbers rows of array: \n");
    scanf("%d", &n);
    printf("Enter numbers columns of array: \n");
    scanf("%d", &m);
 
    mas=(int **)   calloc(n,sizeof(int));
    for(i=0; i<n; i++)
        mas[i]=(int *) calloc(m, sizeof(int));
    printf("Enter elements of array: \n");
    for(i=0; i<n; i++)
       for(j=0; j<m; j++)
       {
          printf("[%d][%d]= ", i, j);
          scanf("%d", &mas[i][j]);
       }
Элемент K объявил на всякий случай.

Добавлено через 2 часа 55 минут
Какие-то элементы менять прийдёться??
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.02.2010, 20:21     Выгодная матрица #8
Вот код:
C
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
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
 
int main()
{
  int i,j,**mas, n, max, temp, max_min_i=0;
        printf("Kol-vo naselennih punctov n= ");
        scanf("%d", &n);
  mas = (int **)malloc (n * sizeof (int *));
  for (i = 0; i < n; i++)
  mas [i] = (int *)malloc (n * sizeof (int));
  for(i=1;i<n;i++)  
     for(j=0;j<i;j++)
     {
        printf("Vvod rastoyniy ot %d do %d =",i+1,j+1);
        scanf("%d",&mas[i][j]);
     }
    for(i=0;i<n;i++)  
        mas[i][i]=0;
    for(i=0;i<n-1;i++)  
         for(j=i+1;j<n;j++)
             mas[i][j]=mas[j][i];
  printf("Ishodnie rasstoyniy\n");
  for(i=0;i<n;i++)  
  {
          for(j=0;j<n;j++)
         printf("%d\t",mas[i][j]);  
      printf("\n\n");
  }
   max=mas[0][0];
        for(j=1; j<n; j++)
                if(mas[0][j]>max)
                        max=mas[0][j];
        for(i=1; i<n; i++)
        {
                temp=mas[i][0];
                for(j=1; j<n; j++)
                        if(temp<mas[i][j])
                                temp=mas[i][j];
                if(temp<max)
                {
                        max=temp;
                        max_min_i=i;
                }
        }
        printf(" Vibiraem %d naselenni punkt", max_min_i+1);
 
 
  return 0;
}
Но еще раз повторю: для этой задачи матрица должна быть квадратной (кол-во строк и столбцов должно быть одинаковым). Во вторых матрица должна быть симметричной относительно главной диагонали (расстояние от i до j должно быть таким же как и от j до i). И элементы главной диагонали должны быть равны 0 (ведь расстояние от населенного пункта до него же самого равно 0).
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
17.02.2010, 19:25     Выгодная матрица #9
Во вторых матрица должна быть симметричной относительно главной диагонали (расстояние от i до j должно быть таким же как и от j до i). И элементы главной диагонали должны быть равны 0 (ведь расстояние от населенного пункта до него же самого равно 0).
И вовсе это не обязательно! Дорога из А в Б может быть под горку, а обратно, естесственно,
в горку!
А в деревне Х такие колдобины, что легче до райценра доехать, чем до хаты дяди Васи.
А главное - на решении задачи эти допущения никак не отражаются!
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
17.02.2010, 20:00     Выгодная матрица #10
Цитата Сообщение от Day Посмотреть сообщение
И вовсе это не обязательно! Дорога из А в Б может быть под горку, а обратно, естесственно,
в горку!
А в деревне Х такие колдобины, что легче до райценра доехать, чем до хаты дяди Васи.
А главное - на решении задачи эти допущения никак не отражаются!
То что в деревне X колдобины, на результат не отражается вообще (по заданию, рассматривается только время между населеных пунктов). Если колдобины между двух населенных пунктов, то они будут влиять и на время пути как туда, так и обратно. А если рассматривать:
Цитата Сообщение от Day Посмотреть сообщение
Дорога из А в Б может быть под горку, а обратно, естесственно,
в горку!
то опять же, просто так данные вбивать нельзя. Окажется, объезжая три пункта по кругу (возращаясь в исходный пункт), мы все время будем ехать под горку. Получится как на гравюре К.Эсхера.
Подводим итог:
Цитата Сообщение от Day Посмотреть сообщение
матрица должна быть симметричной относительно главной диагонали (расстояние от i до j должно быть таким же как и от j до i)
Утверждение остается в силе. (про разность во времени от i до j и от j до i должен решать автор темы).
Цитата Сообщение от Day Посмотреть сообщение
И элементы главной диагонали должны быть равны 0 (ведь расстояние от населенного пункта до него же самого равно 0).
Тоже утверждение остается в силе, т.к. в задании рассматривается только время поездки между селениями.
На всякий случай (предчувствую следующую выдумку), объясняю, что формы и размеры населенных пунктов тоже не учитывались, т.к. по заданию (по умолчанию), они все в виде точки.
Bloodykeeper
This party getting crazy!
 Аватар для Bloodykeeper
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
17.02.2010, 22:14  [ТС]     Выгодная матрица #11
Day, зачёт, поржал обалденно))) мы ж в общем случае смотрим, как Валерий сказал=))
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
18.02.2010, 11:42     Выгодная матрица #12
Подписку снимаю.
Пока!

Добавлено через 8 часов 34 минуты
valeriikozlov, не понял ты моих метафор! Я даже приобиделся слегка, но по утру решил свою точку зрения попытаться отстоять. Дело в том, что мы ненароком затронули методологический вопрос, и его обсуждение может быть полезно не только нам с тобой.
Есть задача. Ее условие задается матрицей (или еще чем - неважно). Найдено решение (алгоритм). И это решение никаким образом не нуждается в наложении ограничений на исходные данные. Оно проходит даже если допустить отрицательные числа! Вообще, говоря по умному,
оно работает на "любой аббелевой группе с полной упорядоченностью". И математик радостно применяет его на любой матрице, а уж какая бытовая задача туда вложена - на это плевать!
Это может построение космической базы в условиях нелинейной гравитации, статистика футбольных или карточных игр, матрица военных противостояний - была бы матрица и был бы нужен минимакс!
А ты, имея уже общий алгоритм, зачем-то накладываешь НЕСУЩЕСТВЕННЫЕ с точки зрения АЛГОРИТМА условия. Математики так не поступают, они, напротив, пытаются обобщить задачу до предела, а потом и за ним.
Другое дело, если б ты предложил алгоритм, использующий эти ограничения. Это не исключено.
Так, для симметричной матрицы с нулями на диагонали можно расположить данные так, что
потребуется не N*N, а только N*(N-1) памяти. Тогда и алгоритм слегка изменится.
Еще можно потребовать, чтоб значения расстояний принимали только 2 значения, тогда
для хранения элемента матрицы потребуется всего 1 бит. И, скорее всего, найдутся здесь более эффективные алгоритмы, отличные от полного перебора.
Что же касается ограничений для реальной задачи - ты забыл о неравенстве треугольника
(АБ + БВ <= АВ). Хотя тут я не помню, верно ли оно для других поверхностей, отличных от плоскости. Для Тора это точно не так.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.02.2010, 12:01     Выгодная матрица #13
Не нужно искать сложностей там где их нет. Конкретно для этой задачи:
Цитата Сообщение от Day Посмотреть сообщение
Что же касается ограничений для реальной задачи - ты забыл о неравенстве треугольника
(АБ + БВ <= АВ). Хотя тут я не помню, верно ли оно для других поверхностей, отличных от плоскости. Для Тора это точно не так.
не нужно здесь рассматривать Тор. Так же не нужно здесь рассматривать двумерную поверхность в пространстве. Здесь все намного проще - ровная плоскость. Так же не нужно рассматривать есть ли на поверхности моря, болота, пустыни. И еще много чего не нужно рассматривать для этой задачи.
Цитата Сообщение от Day Посмотреть сообщение
Так, для симметричной матрицы с нулями на диагонали пожно расположить данные так, что
потребуется не N*N, а только N*(N-1) памяти.
Можно. Только код будет немного посложнее.
Цитата Сообщение от Day Посмотреть сообщение
Еще можно потребовать, чтоб значения расстояний принимали только 2 значения, тогда
для хранения элемента матрицы потребуется всего 1 бит.
Вот здесь пожалуйста поподробнее. Интересен будет пример для этой задачи.
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
18.02.2010, 12:30     Выгодная матрица #14
Вот здесь пожалуйста поподробнее. Интересен будет пример для этой задачи.
Пожалуйста!
1 - недостижимо, 0 - достижимо (или наоборот)
не нужно здесь рассматривать Тор. Так же не нужно здесь рассматривать двумерную поверхность в пространстве. Здесь все намного проще - ровная плоскость. Так же не нужно рассматривать есть ли на поверхности моря, болота, пустыни. И еще много чего не нужно рассматривать для этой задачи.
Опять не понят я народом!
Ну да ладно!
Пора работать. Это я таким образом от серьезной работы отлыниваю.
Разминаюся типа.
Последнее слово оставляю тебе
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.02.2010, 12:51     Выгодная матрица
Еще ссылки по теме:

C++ Матрица
Матрица C++ C++
C++ Матрица
C++ матрица
Матрица C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
18.02.2010, 12:51     Выгодная матрица #15
Цитата Сообщение от Day Посмотреть сообщение
Пожалуйста!
1 - недостижимо, 0 - достижимо (или наоборот)
Круто конечно, но есть предположение, что значения расстояний примут только одно значение - достижимо. А вот найти решение - в каком населенном пункте построить больницу выгоднее всего с такими данными будет нереально.
Yandex
Объявления
18.02.2010, 12:51     Выгодная матрица
Ответ Создать тему
Опции темы

Текущее время: 01:43. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru