Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/9: Рейтинг темы: голосов - 9, средняя оценка - 4.89
MILAN
888 / 782 / 186
Регистрация: 21.02.2009
Сообщений: 1,722
1

Определить, в каком доме необходимо установить АТС, чтобы суммарное расстояние от АТС к телефонным аппаратам было минимальное

27.10.2010, 11:51. Просмотров 1618. Ответов 15
Метки нет (Все метки)

Здравствуйте!!! Есть вопрос по составлению алгоритма. Вот собственно задача:

В деревне N домов, расположенных вдоль дороги с одной стороны на равных расстояниях. В деревне проводят телефонную связь. В таблице Т, которую нужно придумать указывается сколько телефонных аппаратов нужно нужно установить в каждом доме. Каждый аппарат должен быть связан з АТС отдельным проводом. Определить, в каком доме необходимо установить АТС, чтобы суммарное расстояние от АТС к телефонным аппаратам было минимальное!!!

Может кто натолкнет не мысль. Заранее благодарен!!!
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
27.10.2010, 11:51
Ответы с готовыми решениями:

Определить, в каком доме необходимо установить АТС, чтобы расстояние до всех телефонов было минимальным
В поселке N домов, расположенных вдоль дороги с одной стороны на равных...

Требуется определить: какое изделие и на каком оборудовании необходимо изготавливать, чтобы суммарное время изготовления всех изделий было минимально
Пусть на предприятии имеется n типов универсальных станков и требуется...

Определить, в каком из домов надо установить АТС
Городок состоит из N многоквартирных коттеджей, расположенных вдоль прямой...

Определить номер точки, для которой суммарное расстояние до всех остальных точек минимальное
На прямой задано n точек с равными расстояниями между ними. Определить номер...

Облачная АТС и виртуальная АТС
Доброго времени суток!!! Это синонимы. Либо разные вещи?

15
Dzhej-Dzhej
Заблокирован
27.10.2010, 12:09 2
Z(i) - длинна кабелей для i-того дома
двойной цикл по i и j:
Z(i) = Z(i) + (T(j) * a * abs(i-j))

T(j) - количество телефонов j-того дома
а - расстояение между соседними домами
abs(i-j) - расстояение между домами i и j(в домах)
находим минимальное из Z(i), i - номер дома с АТС



примерно так
1
Mr.X
Эксперт С++
3184 / 1711 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
28.10.2010, 03:37 3
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
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
////////////////////////////////////////////////////////////////////////////////////
//В деревне N домов, расположенных вдоль дороги с одной стороны на равных расстояниях. 
//В деревне проводят телефонную связь. В таблице Т, которую нужно придумать 
//указывается сколько телефонных аппаратов нужно нужно установить в каждом доме. 
//Каждый аппарат должен быть связан з АТС отдельным проводом. 
//Определить, в каком доме необходимо установить АТС, чтобы суммарное расстояние 
//от АТС к телефонным аппаратам было минимальное
////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<int>  T_quantity;
////////////////////////////////////////////////////////////////////////////////////
int  get_telephone_exchange_house_number(T_quantity  phones_quantity)
{
    T_quantity  cables_len_total(phones_quantity.size());
    //Если станция будет расположена в доме с индексом 0, то, длина кабелей до него
    //очевидно равна сумме произведений вектора на их индексы.
    
    for(size_t  house_ind = 0; house_ind < phones_quantity.size(); ++house_ind)
    {
        cables_len_total[0] += phones_quantity[house_ind] * house_ind;
    }
 
    //При перемещении станции из дома с индексом i в дом с индексом i + 1 длина кабеля
    //увеличивается для каждого индекса ind_prev = 0..i на phones_quantity[ind_prev],
    //и, соответственно, уменьшается для остальных индексов ind_post = (i + 1)..(n - 1)
    //на phones_quantity[ind_post].
    for(size_t  phone_exchange_ind = 1; phone_exchange_ind < cables_len_total.size(); 
        ++phone_exchange_ind)
    {        
        for(size_t  house_ind = 0; house_ind < phones_quantity.size(); ++house_ind)
        {
            cables_len_total[phone_exchange_ind] += house_ind < phone_exchange_ind 
                                                        ?  phones_quantity[house_ind]
                                                        : -phones_quantity[house_ind];
        }
    }
 
    //Итак, в первом элементе вектора имеем значение, а в остальных разности соседних
    //элементов. Вычисляем значения:
    std::partial_sum(cables_len_total.begin(), cables_len_total.end(), 
                     cables_len_total.begin());
 
    return std::distance
        (
            cables_len_total.begin(),
            std::min_element(cables_len_total.begin(), cables_len_total.end())
        );
}
////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int n = 0;
    do
    {
        std::cout << "Введите количество домов: ";
        std::cin >> n;
    }while(n < 2);
 
    std::cout << "Введите количество телефонов в домах:"
              << std::endl;
 
    T_quantity  phones_quantity(n);
    for(int i = 0; i < n; ++i)
    {
        std::cout << "телефонов в доме № "
                  << i + 1
                  << ": ";
 
        std::cin >> phones_quantity[i];
    }
 
    std::cout << "АТС нужно установить в доме № "
              << get_telephone_exchange_house_number(phones_quantity) + 1
              << std::endl;   
}
1
MILAN
888 / 782 / 186
Регистрация: 21.02.2009
Сообщений: 1,722
02.11.2010, 18:39  [ТС] 4
Mr.X, а можно как то без векторов сделать?
0
Dexter
286 / 146 / 34
Регистрация: 13.10.2009
Сообщений: 164
02.11.2010, 19:03 5
Если по-простому, то так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<iostream>
 using namespace std;
void main()
{
  int kol=11;//количество домов
  int length=5;//растояние между домами
  int full=0,pos_min,full_min;
  int kolphone=2;//количество телефонов в доме
  for(int i=1;i<=kol;i++)
  {
      full=0;
      for(int j=1;j<=kol;j++)
          full+=2*abs(i-j)*length;
      if(full<full_min||i==1)
      {
          full_min=full;
          pos_min=i;
      }
  }
  cout<<"In "<<pos_min<<" house, length cable - "<<full_min<<endl;
  system("pause");
}
Данные просто забил.

А если нужно просто номер дома, то при данном условии будет так:
C++
1
2
3
4
5
6
7
8
#include<iostream>
 using namespace std;
void main()
{
  int kol=11;//количество домов
  cout<<"In "<<kol/2+1<<" house"<<endl;
  system("pause");
}
так как для нечетного количества домов он будет строго по середине, а для четного один из двух - kol/2 или kol/2+1
0
Mr.X
Эксперт С++
3184 / 1711 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
02.11.2010, 19:05 6
Цитата Сообщение от MILAN Посмотреть сообщение
Mr.X, а можно как то без векторов сделать?
А чем они вам не нравятся?
0
MILAN
888 / 782 / 186
Регистрация: 21.02.2009
Сообщений: 1,722
02.11.2010, 19:56  [ТС] 7
не изучал еще!!!!!
0
Mr.X
Эксперт С++
3184 / 1711 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
02.11.2010, 22:24 8
Цитата Сообщение от MILAN Посмотреть сообщение
не изучал еще!!!!!
Ну тогда можно на массивы заменить.
0
Dzhej-Dzhej
Заблокирован
03.11.2010, 09:18 9
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
#include<iostream>
#include <math.h>
 using namespace std;
void main()
{
  const int kol=10;//количество домов
  int length=5;//растояние между домами
  int min,num;
  int kolphone[kol];//количество телефонов в доме
  int len[kol];//количество проводов для атс
  for(int i=0;i<kol;i++)
  {
      kolphone[i]=i+1;
      len[i]=0;
  }
  for(int i=0;i<kol;i++)
      for(int j=0;j<kol;j++)
          len[i]=len[i]+kolphone[j]*length*abs(i-j);
  min=len[0];
  num=0;
  for(int i=0;i<kol;i++)
      if(min>len[i])
      {
          min=len[i];
          num=i;
      }
  for(int i=0;i<kol;i++)
      cout<<"In "<<i+1<<" house, length cable - "<<len[i]<<endl;
  cout<<endl<<"In "<<num+1<<" house, length cable - "<<len[num]<<endl;
  system("pause");
}
может так
0
MILAN
888 / 782 / 186
Регистрация: 21.02.2009
Сообщений: 1,722
05.11.2010, 15:32  [ТС] 10
Mr.X, еще пару вопросов.

Можна лы обойтись без
C++
1
2
std::partial_sum(cables_len_total.begin(), cables_len_total.end(), 
                     cables_len_total.begin());
И заменить size_t на int?
0
Mr.X
Эксперт С++
3184 / 1711 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
05.11.2010, 16:58 11
Цитата Сообщение от MILAN Посмотреть сообщение
Mr.X, еще пару вопросов.

Можна лы обойтись без
C++
1
2
std::partial_sum(cables_len_total.begin(), cables_len_total.end(), 
                     cables_len_total.begin());
И заменить size_t на int?
Разумеется алгоритм можно заменить самодельной функцией.
А тип size_t введен для переменных, которые сравниваются со значением, возвращаемым методом size() контейнера. Поскольку вы не будете использовать контейнеры, то и этот тип вам не нужен.
1
MILAN
888 / 782 / 186
Регистрация: 21.02.2009
Сообщений: 1,722
05.11.2010, 20:55  [ТС] 12
Mr.X, если вам не трудно, обясните для для чего надо алгоритм partial_sum?
0
Mr.X
Эксперт С++
3184 / 1711 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
06.11.2010, 01:15 13
Цитата Сообщение от MILAN Посмотреть сообщение
Mr.X, если вам не трудно, обясните для для чего надо алгоритм partial_sum?
http://www.cplusplus.com/reference/std/numeric/partial_sum/
1
MILAN
888 / 782 / 186
Регистрация: 21.02.2009
Сообщений: 1,722
06.11.2010, 11:35  [ТС] 14
Вот, пробовал переписать вашу програму на массивы, только у меня чето неправильно считает, может подскажыте где ошыбка?

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
int ats_house(int *number_tel)
{
for(int house=0; house < number_house; ++house)
    {
        cab_len_total[0] += number_tel[house]*house;
    }
 for(int phone_exchange_ind = 1; phone_exchange_ind <number_house;
        ++phone_exchange_ind)
    {
        for(int house=0; house < number_house; ++house)
        {
            cab_len_total[phone_exchange_ind] += house<phone_exchange_ind ? number_tel[house] : -number_tel[house];
        }
    }
  for(int i=0; i<number_house; i++)
    {
       sum+=cab_len_total[i];
       cab_len_total[i]=sum;
    }
  min=cab_len_total[0];
  for(int i=0; i<number_house; i++)
    {
      if(cab_len_total[i]<min)
        {
          min=cab_len_total[i];
          count3=i;
        }
    }
   return count3;
}
0
Mr.X
Эксперт С++
3184 / 1711 / 435
Регистрация: 03.05.2010
Сообщений: 3,867
06.11.2010, 13:14 15
Цитата Сообщение от MILAN Посмотреть сообщение
Вот, пробовал переписать вашу програму на массивы, только у меня чето неправильно считает, может подскажыте где ошыбка?
Непонятно, почему переменные sum и min сделаны глобальными.
А переменная sum каким значением инициализируется?
1
MILAN
888 / 782 / 186
Регистрация: 21.02.2009
Сообщений: 1,722
06.11.2010, 19:09  [ТС] 16
Mr.X, очень вам благодарен!!! Вот, розобрался

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
int ats_house(int *number_tel, int number_house)
{
  int *mini;
  mini = new int[number_house];
  int min,sum_after=0,sum_to=0,num;
   for(int i=0; i<number_house; i++)
    {
      for(int j=0; j<i; j++)
       {
         sum_to+=number_tel[j];
       }
      for(int j1=number_house-1; j1>i; j1--)
       {
         sum_after+=number_tel[j1];
       }
      mini[i]=abs(sum_to-sum_after);
      sum_to=0;
      sum_after=0;
    }
   min=mini[0];
   for(int i=0; i<number_house; i++)
   {
     if(mini[i]<min)
     {
         min=mini[i];
         num=i;
     }
   }
  return num;
}
0
06.11.2010, 19:09
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
06.11.2010, 19:09

Установить мини IP-АТС
Доброе время суток! Есть такая задача, установить мини IP-АТС на обычной...

Найти наименьшую сумму цен карточек чтобы суммарное время было не меньше за N
Есть карточки ценой 1, 2, 4, 8, 16 ... {2}^{30} на a, a, a ... a секунд...

Определить минимальное количество операций необходимо для того, чтобы сделать число a равным числу b
Помогите пож-ста срочно


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

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

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