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

Написание алгоритма - C++

Восстановить пароль Регистрация
 
Mindz
 Аватар для Mindz
7 / 7 / 1
Регистрация: 31.01.2010
Сообщений: 51
25.08.2012, 21:20     Написание алгоритма #1
Приветствую.
Имеется некоторая задача которую не удается решить.
Суть такова.Явно определен целочисленный массив из n элементов, требуется найти медиану,которая будет равна максимально ближнему элементу к среднеарифметическому данного массива.
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
void setMedian( int Array[], int Size )
{
    int lh[LeftSize], rh[RightSize], Max, Min;
    
    for( int index = 0; index < Size; index++ ) {
         if( Array[index] == Average ) {
             Median = Array[index];
             break;
         } else {    
                if( Array[index] < Average ) lh[index] = Array[index];
                   else if( Array[index] > Average ) rh[index] = Array[index];//Это не верно ибо можем обратится к несуществующему индексу,вот именно в этой части и надо что то придумать.               
                if( index > 0 ) {
                    Max = lh[index] > lh[index - 1] ? lh[index] : lh[index - 1];
                    Min = lh[index] < lh[index - 1] ? rh[index] : rh[index - 1];
                }
           }
           Median = ( Average - Max ) < ( Min - Average ) ? Max : Min;
    }        
}
 
void setSize( int A[], int size )
{
     for( int index = 0; index < size; index++ ) {
          if( A[index] > Average ) RightSize++;
              else LeftSize++;
     }            
}
Если у кого есть какие идеи по этому поводу был весьма благодарен,сразу скажу варианты STL не проканают.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.08.2012, 21:20     Написание алгоритма
Посмотрите здесь:

C++ написание функций
Написание функции C++
C++ написание выражения
написание контрольных C++
написание функций C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.08.2012, 21:27     Написание алгоритма #2
Цитата Сообщение от Mindz Посмотреть сообщение
Явно определен целочисленный массив из n элементов, требуется найти медиану,которая будет равна максимально ближнему элементу к среднеарифметическому данного массива.
Если следовать тому что Вы написали, тогда нужно 2 прохода по массиву:
- в 1-ом проходе высчитываем среднеарифметическое массива
- во 2-ом проходе вычисляем медиану.
У Вас даже 1-го пункта в коде нет.

Цитата Сообщение от Mindz Посмотреть сообщение
Имеется некоторая задача которую не удается решить.
ссылку на задачу можете дать?
Mindz
 Аватар для Mindz
7 / 7 / 1
Регистрация: 31.01.2010
Сообщений: 51
25.08.2012, 21:34  [ТС]     Написание алгоритма #3
Вычисление среднего
C++
1
2
3
4
5
6
7
8
9
10
11
12
srand( unsigned ( time(0) ) );
 
for( int index = 0; index < SIZE ; index++ ) {
         A[index] = rand() % 100;
         Summ += A[index];
}
 
Average = Summ/SIZE;
 
setSize( A, SIZE );
 
setMedian( A, SIZE );
Добавлено через 37 секунд
Ссылку к сожалению дать не могу.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.08.2012, 21:38     Написание алгоритма #4
Mindz, Вы весь код показать можете? Давая небольшие кусочки Вы только порождаете множество вопросов:
- Каким типом является Average? Если типом int , то точность вычисления может быть потеряна именно из-за этого.
И желательно полное условие задачи напишите (или ссылку на саму задачу).
Mindz
 Аватар для Mindz
7 / 7 / 1
Регистрация: 31.01.2010
Сообщений: 51
25.08.2012, 21:46  [ТС]     Написание алгоритма #5
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
#include <iostream>
#include <time.h>
 
#define SIZE 10
 
 
using namespace std;
 
void setMedian( int[], int );
void setSize( int[], int );
 
int Median, Average, LeftSize, RightSize;                    
 
 
int main()
{
    system( "TITLE CodeNurf :D" );
    system( "COLOR A" );
    
    int A[SIZE] = { 0 }, Summ = 0;
    
    srand( unsigned ( time(0) ) );
    
    cout << "Massive: ";
    
    for( int index = 0; index < SIZE ; index++ ) {
         A[index] = rand() % 100;
         Summ += A[index];
         cout << "  " << A[index];
    }
    
    Average = Summ/SIZE;
    
    setSize( A, SIZE );
    
    cout << "\nSize of left half: " << LeftSize << endl
         << "Size of right half: " << RightSize << endl;
    
    setMedian( A, SIZE );
    
    cout << "\n=======================" << endl
         << "\nAverage of massive: " << Average << endl
         << "\nMedian of massive: " << Median << endl;
         
    system( "pause" );
    
    return 0;        
}
 
void setMedian( int Array[], int Size )
{
    int lh[LeftSize], rh[RightSize], Max, Min;
    
    for( int index = 0; index < Size; index++ ) {
         if( Array[index] == Average ) {
             Median = Array[index];
             break;
         } else {    
                if( Array[index] < Average ) lh[index] = Array[index];
                   else if( Array[index] > Average ) rh[index] = Array[index];               
                if( index > 0 ) {
                    Max = lh[index] > lh[index - 1] ? lh[index] : lh[index - 1];
                    Min = lh[index] < lh[index - 1] ? rh[index] : rh[index - 1];
                }
           }
           Median = ( Average - Max ) < ( Min - Average ) ? Max : Min;
    }        
}
 
void setSize( int A[], int size )
{
     for( int index = 0; index < size; index++ ) {
          if( A[index] > Average ) RightSize++;
              else LeftSize++;
     }            
}
На счет точности вы абсолютно правы,оно отбросит всю дробную составляющую.Но для меня на данном этапе важно понять как сделать дальше.

Добавлено через 5 минут
Вот собственно задание:
Сортировка разделением с использованием в качестве медианы среднего арифметического на текущем интервале и подсветкой разделяемой части.
Способ разделения: движение двух индексов от краев к середине и обменом (по необходимости) находящихся под ними элементов.

Я реализовал почти все,то есть я графически обазначил середину массива и отсортировал элементы.Но теперь хочу внести коррективы в эту задачу и сделать медиану элементом,и относительно этого элемента вывести сортировку.
Тот код который я привел,это тестовый вариант то есть проверка на работу алгоритма.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.08.2012, 21:50     Написание алгоритма #6
Я что-нибудь такое тогда сделал бы:
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
#include <iostream>
#include <time.h>
#include <math.h>
#define SIZE 10
 
 
using namespace std;
 
void setMedian( int[], int );
void setSize( int[], int );
 
int Median, Average, LeftSize, RightSize;                    
 
 
int main()
{
    system( "TITLE CodeNurf :D" );
    system( "COLOR A" );
    
    int A[SIZE] = { 0 }, Summ = 0;
    
    srand( unsigned ( time(0) ) );
    
    cout << "Massive: ";
    
    for( int index = 0; index < SIZE ; index++ ) {
         A[index] = rand() % 100;
         Average += A[index];
         cout << "  " << A[index];
    }        
   
 
    
    setMedian( A, SIZE );
    Average/=SIZE;
    cout << "\n=======================" << endl
         << "\nAverage of massive: " << Average << endl
         << "\nMedian of massive: " << Median << endl;
         
    system( "pause" );
    
    return 0;        
}
 
void setMedian( int Array[], int Size )
{
    Median=0;
    for(int i=1; i<Size; i++)
        if(abs(Array[i]*Size-Average)<abs(Array[Median]*Size-Average))
            Median=i;
    Median=Array[Median];
}
Mindz
 Аватар для Mindz
7 / 7 / 1
Регистрация: 31.01.2010
Сообщений: 51
25.08.2012, 22:06  [ТС]     Написание алгоритма #7
Не понятны следующие строки:

Цитата Сообщение от valeriikozlov Посмотреть сообщение
setMedian( A, SIZE );
Average/=SIZE;
Почему вы устанавливаете значение среднего после того как функция отрабатывает и устанавливает значение медианы?

Добавлено через 8 минут
А все понял

Добавлено через 20 секунд
Классное решение.Спасибо за ваш совет.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.08.2012, 22:07     Написание алгоритма #8
Цитата Сообщение от Mindz Посмотреть сообщение
Почему вы устанавливаете значение среднего после того как функция отрабатывает и устанавливает значение медианы?
Что-бы не терять точность, используя тип int, можно сравнивать так:
(значение элемента массива)*(количество элементов массива) сравниваете с (сумма всех элементов массива)
В данном случае точность не теряется.
Mindz
 Аватар для Mindz
7 / 7 / 1
Регистрация: 31.01.2010
Сообщений: 51
25.08.2012, 22:08  [ТС]     Написание алгоритма #9
Я проверил ваш код но пока не могу полностью осознать всю простоту и гениальность вот этого
C++
1
 if( abs( Array[i] * Size - Average ) < abs( Array[Median] * Size - Average ) )
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.08.2012, 22:18     Написание алгоритма #10
Цитата Сообщение от Mindz Посмотреть сообщение
Я проверил ваш код но пока не могу полностью осознать всю простоту и гениальность вот этого
- Average - в данном случае сумма всех элементов массива
- Median - индекс элемента массива, самого близкого к среднеарифметическому.

Цитата Сообщение от Mindz Посмотреть сообщение
C++
1
if( abs( Array[i] * Size - Average ) < abs( Array[Median] * Size - Average ) )
получается так:
if(абсолютное значение ((значение очередного элемента массива)*(размер массива) - сумма всех элементов массива) < абсолютное значение ((значение элемента массива с индексом Median)*(размер массива) - сумма всех элементов массива) )
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
25.08.2012, 22:20     Написание алгоритма
Еще ссылки по теме:

Написание Makefile C++
Написание кода C++
Написание компилятора на C++ C++

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

Или воспользуйтесь поиском по форуму:
Mindz
 Аватар для Mindz
7 / 7 / 1
Регистрация: 31.01.2010
Сообщений: 51
25.08.2012, 22:20  [ТС]     Написание алгоритма #11
Да это то понятно ).Просто реализовано все в 3 строки.
Yandex
Объявления
25.08.2012, 22:20     Написание алгоритма
Ответ Создать тему
Опции темы

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