Форум программистов, компьютерный форум, киберфорум
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Bloodykeeper
This party getting crazy!
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
#1

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

15.02.2010, 18:12. Просмотров 1006. Ответов 14
Метки нет (Все метки)

Имеется k селений. Если в селении i расположена больница, то поездка в селение j займёт время a[i][j]. Найти номер селения i, в котором выгоднее всего разместить больницу (поездка из i в самое удалённое по времени селение должна занять минимальное время).

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

дана квадратичная матрица z[n][n]. составить программу, которая если матрица симметричная(транспонированная матрица равна исходной), сделает ее не сим - C++
помогите пожалуйста. условие: дана квадратичная матрица z. составить программу, которая если матрица симметричная(транспонированная...

Дана матрица целых чисел, из n строк и n столбцов (n < = 100).Определить является ли матрица нулевой (состоит из одних нулей) - C++
#include &lt;iostream.h&gt; #include &lt;iomanip.h&gt; #include&lt;conio.h&gt; void main() { int mas; int N; int max_element; int...

Дана матрица целых чисел, из n строк и n столбцов (n < = 100).Определить является ли матрица нулевой (состоит из одних нулей) - C++
#include &lt;iostream.h&gt; #include &lt;iomanip.h&gt; #include &lt;stdlib.h&gt; int main(int argc, char* argv) { srand(time(NULL)); int mas; ...

Даны квадратная матрица A порядка n и вектор с n элементами. Получить вектор: (A=E)b, где E единичная матрица порядка n - C++
Даны квадратная матрица A порядка n и вектор с n элементами. Получить вектор: (A=E)b, где E-единичная матрица порядка n. Помогите...

Определить базовый класс "Матрица" и класс-потомок "Треугольная матрица" - C++
Нужно определить класс &quot;матрица&quot; с возможностью динамического выделения и освобождения памяти, наполнения матрицы, сохранения и чтения из...

скажите выгодная ли покупка? - Выбор компьютера
Процессор - Intel Core i7 960, 3.2 GHz Мат. плата - Gigabyte GA-X58A-UD5 Память - DDR3 6 Gb Kit of 3 2gb*3 видео - Radeon HD6870 / 1...

14
Day
1159 / 964 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
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;
1
Bloodykeeper
This party getting crazy!
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
15.02.2010, 19:03  [ТС] #3
ещё идеи??
0
valeriikozlov
Эксперт С++
4676 / 2502 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
15.02.2010, 19:10 #4
Нужно искать во всех строках максимальные элементы. А потом выбрать строку с самым минимальным из них. Номер строки и будет ответом.
1
Bloodykeeper
This party getting crazy!
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
16.02.2010, 16:25  [ТС] #5
Может быть глупый вопрос, но никогда не искал максимальные элементы в столбах и строках. Можно мне хотя бы черновой вариант для моих "шаблонов"? А я подправлю. Заранее спасибо.
0
valeriikozlov
Эксперт С++
4676 / 2502 / 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 находится нужное нам значение (номер нужной строки - соответственно номер селения)
1
Bloodykeeper
This party getting crazy!
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 минут
Какие-то элементы менять прийдёться??
0
valeriikozlov
Эксперт С++
4676 / 2502 / 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).
2
Day
1159 / 964 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
17.02.2010, 19:25 #9
Во вторых матрица должна быть симметричной относительно главной диагонали (расстояние от i до j должно быть таким же как и от j до i). И элементы главной диагонали должны быть равны 0 (ведь расстояние от населенного пункта до него же самого равно 0).
И вовсе это не обязательно! Дорога из А в Б может быть под горку, а обратно, естесственно,
в горку!
А в деревне Х такие колдобины, что легче до райценра доехать, чем до хаты дяди Васи.
А главное - на решении задачи эти допущения никак не отражаются!
0
valeriikozlov
Эксперт С++
4676 / 2502 / 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).
Тоже утверждение остается в силе, т.к. в задании рассматривается только время поездки между селениями.
На всякий случай (предчувствую следующую выдумку), объясняю, что формы и размеры населенных пунктов тоже не учитывались, т.к. по заданию (по умолчанию), они все в виде точки.
0
Bloodykeeper
This party getting crazy!
78 / 74 / 1
Регистрация: 22.09.2009
Сообщений: 427
17.02.2010, 22:14  [ТС] #11
Day, зачёт, поржал обалденно))) мы ж в общем случае смотрим, как Валерий сказал=))
0
Day
1159 / 964 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
18.02.2010, 11:42 #12
Подписку снимаю.
Пока!

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

Дана квадратная матрица А порядка n. Проверьте, является ли матрица единичной - Delphi
Дана квадратная матрица А порядка n. Проверьте, является ли матрица единичной. Описать с помощью функций и процедур. Ввод-вывод в текстовый...

Дана квадратная матрица А порядка n. Проверить, является ли матрица единичной. - Turbo Pascal
Ребят,помогите решить задачу &quot;Дана квадратная матрица А порядка n. Проверить, является ли матрица единичной&quot;

Как доказать то, что матрица и транспонированная ей матрица имеют одинаковые собственные числа? - Алгебра
Как доказать то, что матрица и транспонированная ей матрица имеют одинаковые собственные числа с одинаковой кратностью? Добавлено...

Матрица:Даны натуральное число n, действительная матрица размера n х 9. Найти среднее арифметическое: каждого - QBasic
Даны натуральное число n, действительная матрица размера n х 9. Найти среднее арифметическое: каждого из столбцов.


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

Или воспользуйтесь поиском по форуму:
15
Ответ Создать тему
Опции темы

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