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

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

Войти
Регистрация
Восстановить пароль
 
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 43
#1

Поиск наименьшего расстояния от одного элемента массиа до остальных - C++

05.09.2013, 14:00. Просмотров 617. Ответов 11
Метки нет (Все метки)

Дан неотсортированный массив чисел (но это не беда, отсортируем...) тогда получится отсортированный по возрастанию массив чисел))
В нём могут быть поворяющиеся элементы...

Нужно найти такое значение элемента массива, из которого все расстояния до остальных элементов будет минимальным (вот это уже проблема(( ). Расстояние от одного элемента массива A до другого будет находиться по формуле:
D(ij) = |A(i)-A(j)|
(расстояние считается от каждого элемента массива до каждого (включая повторяющиеся элементы и исключая самого себя)

Пример:
В таком массиве:
1 2 3 4
это будет число 2 или 3 (без разницы) суммарная разность (например для 2 будет: 1+1+2 = 4)

а в таком массиве:
1 1 1 2 3 4
это будет 1 или 2 суммарная разность (например для 2 будет: 1+1+1 +1+2 = 6)
(а для 1 будет: 0+0+1+2+3 = 6)

Нужно даже найти не элемент массива, а эту МИНИМАЛЬНУЮ РАЗНОСТЬ...

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

Поиск k-ого наименьшего элемента - C++
Друзья есть код на паскале, нужно переписать на с++. Это алгоритм поиска к-го наименьшего элемента. У меня получается криво, с ошибками. ...

Поиск наименьшего элемента массива - C++
#include<iostream.h> #include<conio.h> const n=5; char StrBuf; int i; int poshyk(int a, int NextIndex); void vved(int a); ...

Поиск по вектору наименьшего отсутствующего элемента - C++
В общем, есть вектор, в нем хранятся значения типа <unsigned int>. Как за наименьшее количество проходов по вектору найти наименьший...

Поиск индекса самого наименьшего элемента в массиве - C++
Нужно написать шаблонную функцию, которая будет возвращать индекс самого наименьшего элемента в массиве.

Функция: поиск экстремального (наибольшего или наименьшего) элемента массива - C++
Написать программу с функцией для поиска экстремального числа(наибольшего или наименьшего) элемента массива. Массив заполнить случайными...

Получить новую матрицу путем вычитания из каждого элемента данной матрицы ее наименьшего элемента - C++
Доброго времени суток!) я был бы благодарен получить небольшую консультацию и правку в моем коде по этой задачке: Дана действительная...

11
Nikitko_Cent
144 / 114 / 12
Регистрация: 27.10.2011
Сообщений: 686
Завершенные тесты: 3
05.09.2013, 14:13 #2
Если нужно просто чтоб работало (без ограничений по времени) - сделай полный перебор. Пишешь функцию, которая для очередного элемента в массиве вычисляет "расстояние" до всех остальных элементов и затем запускаешь эту функцию для всех элементов массива. Ответом будет минимальное значение, возвращенное функцией

P.S. при таком методе сортировка массива не потребуется
1
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
05.09.2013, 14:34 #3
Цитата Сообщение от mano Посмотреть сообщение
D(ij) = |A(i)-A(j)|
(расстояние считается от каждого элемента массива до каждого (включая повторяющиеся элементы и исключая самого себя)
Какая разница, исключать или нет? Результат одинаковый будет (0). В лоб можно сделать просто перебором двойным циклом без никакой сортировки. O(N^2). Если надо оптимизация какая-то, то надо подумать.

Добавлено через 2 минуты
Не будет ли это ближайшим числом к среднему арифметическому? Если да, то первым проходом находишь среднее арифметическое, а вторым находишь ближайшее к нему число. O(N)
1
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 43
05.09.2013, 15:32  [ТС] #4
М... к сожалению, близким к среднему арифметическому не будет((
Пример:
1 1 1 3 4 5 5
Среднее арифметическое:
2,85

Распределение разностей:
1 - 13
3 - 11
4 - 12
5 - 15
((

В задаче написано, что вход может быть до 500 элементов включительно...
Можно смотреть в думающий экран... около часа, может((
500*500*500*500... так 500 раз((

Тут наверняка как всегда где-то таится математический ключ))
0
Raali
623 / 327 / 34
Регистрация: 06.07.2013
Сообщений: 1,070
Завершенные тесты: 1
05.09.2013, 15:42 #5
дак почему бы все таки не сделать как сказал Nikitko_Cent, будет всего 500*500 операций(500 вычитаний для каждого из элементов)
1
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 43
05.09.2013, 15:45  [ТС] #6
может, можно и так)) попробую...
0
Raali
623 / 327 / 34
Регистрация: 06.07.2013
Сообщений: 1,070
Завершенные тесты: 1
05.09.2013, 15:47 #7
Цитата Сообщение от mano Посмотреть сообщение
D(ij) = |A(i)-A(j)|
операции такого вида из серии мат.статистики, там без перебора нельзя никак
1
lesha1980
3 / 3 / 0
Регистрация: 06.01.2012
Сообщений: 48
05.09.2013, 16:12 #8
Если правильно понял задание, то можно в принципе алгоритмом А* воспользоваться... Когда делал программку, использовавшую поиск кратчайшего расстояния в массиве к определенной позиции, то этот алгоритм весьма хорошо помог справиться с решением... Попробовать его адаптировать к данной задаче...
1
mano
0 / 0 / 0
Регистрация: 11.04.2013
Сообщений: 43
05.09.2013, 16:41  [ТС] #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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
#include <fstream>
#include <conio.h>
#include <vector>
 
using namespace std;
ifstream in ("input.txt");
ofstream out ("output.txt");
 
int main(){
    int n_blocks;
    in>>n_blocks;
 
    for (int  k = 0; k<n_blocks; k++){
        int size;//размер блока
        in>>size;
        
        vector<int> block(size);
        for (int  i = 0; i<size; i++){
            in>>block[i];
        }
 
        for (int  i = 0; i<block.size()-1; i++){//сортировка блока для нахождения разностей
            for (int  j = i; j<block.size(); j++){
                if (block[j]<block[i]){
                    int k = block[i];
                    block[i] = block[j];
                    block[j] = k;
                }
            }
        }
 
        vector<int> diff(size);//разности для каждого из чисел
        for (int  i = 0; i<diff.size(); i++) diff[i] = 0;
 
        for (int  i = 0; i<block.size(); i++){
            for (int j = 0; j<block.size(); j++){
                if (i!=j){
                    diff[i] += abs(block[j]-block[i]);
                    //cout<<i<<j;
                }
            }
        }
 
        int min_diff = diff[0];//поиск минимальной разности
        for (int  i = 1; i<diff.size(); i++){
            if (diff[i]<min_diff) min_diff = diff[i];
        }
 
        out<<min_diff<<endl;
        
    }
    
    //getch();
}
0
salam
171 / 152 / 16
Регистрация: 10.07.2012
Сообщений: 751
05.09.2013, 18:08 #10
Цитата Сообщение от mano Посмотреть сообщение
М... к сожалению, близким к среднему арифметическому не будет((
Пример:
1 1 1 3 4 5 5
Среднее арифметическое:
2,85
Распределение разностей:
1 - 13
3 - 11
4 - 12
5 - 15
не понял шутку...
0
Nekto
342 / 287 / 10
Регистрация: 23.03.2012
Сообщений: 838
05.09.2013, 22:20 #11
Цитата Сообщение от mano Посмотреть сообщение
М... к сожалению, близким к среднему арифметическому не будет((
Пример:
1 1 1 3 4 5 5
Среднее арифметическое:
2,85

Распределение разностей:
1 - 13
3 - 11
4 - 12
5 - 15
((

В задаче написано, что вход может быть до 500 элементов включительно...
Можно смотреть в думающий экран... около часа, может((
500*500*500*500... так 500 раз((

Тут наверняка как всегда где-то таится математический ключ))
3 - 11, самое близкое к 2.85. Я не понимаю, в чем проблема возникла.

Добавлено через 24 минуты
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>
#include <iomanip>
#include <numeric>
#include <algorithm>
 
int main()
  {
  double a [] = { 1, 5, 3, 4, 5, 1, 1 };
  double arithmetic_mean = std::accumulate(std::begin(a), std::end(a), 0.)/std::distance(std::begin(a), std::end(a));
  auto CloserByAbsoluteValue = [&arithmetic_mean] (double i_1, double i_2) -> bool
    {
    return fabs(i_1-arithmetic_mean)<fabs(i_2-arithmetic_mean);
    };
  auto element = std::min_element(std::begin(a), std::end(a), CloserByAbsoluteValue);
  auto Distance = [&element] (double sum, double i_1) -> double
    {
    return sum+fabs(i_1-*element);
    };
  double distance = std::accumulate(std::begin(a), std::end(a), 0., Distance);
  std::cout<<std::setprecision(DBL_DIG)<<distance<<std::endl;
  return 0;
  }
1
Nikitko_Cent
144 / 114 / 12
Регистрация: 27.10.2011
Сообщений: 686
Завершенные тесты: 3
07.09.2013, 20:14 #12
Цитата Сообщение от mano Посмотреть сообщение
Всем огромное спасибо за ответы))
Решил))

просто иногда хочется поискать более сложное решение, когда этого не надо))...

//Задача оказалась довольно простой, работает перебор в отсортированном массиве
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
#include <iostream>
#include <fstream>
#include <conio.h>
#include <vector>
 
using namespace std;
ifstream in ("input.txt");
ofstream out ("output.txt");
 
int main(){
    int n_blocks;
    in>>n_blocks;
 
    for (int  k = 0; k<n_blocks; k++){
        int size;//размер блока
        in>>size;
        
        vector<int> block(size);
        for (int  i = 0; i<size; i++){
            in>>block[i];
        }
 
        for (int  i = 0; i<block.size()-1; i++){//сортировка блока для нахождения разностей
            for (int  j = i; j<block.size(); j++){
                if (block[j]<block[i]){
                    int k = block[i];
                    block[i] = block[j];
                    block[j] = k;
                }
            }
        }
 
        vector<int> diff(size);//разности для каждого из чисел
        for (int  i = 0; i<diff.size(); i++) diff[i] = 0;
 
        for (int  i = 0; i<block.size(); i++){
            for (int j = 0; j<block.size(); j++){
                if (i!=j){
                    diff[i] += abs(block[j]-block[i]);
                    //cout<<i<<j;
                }
            }
        }
 
        int min_diff = diff[0];//поиск минимальной разности
        for (int  i = 1; i<diff.size(); i++){
            if (diff[i]<min_diff) min_diff = diff[i];
        }
 
        out<<min_diff<<endl;
        
    }
    
    //getch();
}
В код особо не вникал, но если там простой перебор "в лоб" сортировка вообще не нужна - даже лучше её убрать, ибо она только ухудшает производительность
0
07.09.2013, 20:14
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.09.2013, 20:14
Привет! Вот еще темы с ответами:

Поиск минимального значения элемента и определение порядкового номера наименьшего элемента - Delphi
Дана непустая последовательность различных натуральных чисел. Определить порядковый номер наименьшего из них. помогите! очень нужен код...

Поиск наименьшего элемента оформить в виде процедуры - Turbo Pascal
Нужно поиск наименьшего элемента оформить в виде процедуры вот программу написал,вроде, а как теперь переделать в процедуру?( ...

Поиск индекса наименьшего элемента одномерного массива - MathCAD
Найти и напечатать индекс наименьшего элемента одномерного массива Р размерности М. Из разных наименьших элементов выбрать элемент с...

Создать функцию.(Поиск наименьшего элемента строк матрицы А). - Pascal
Найти наибольший из минимальных элементов строк матрицы А.(через функцию определить минимальный элемент каждой строки матрицы А,а в...


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

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

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