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

Метод Шелла - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
osen'
 Аватар для osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
24.10.2010, 01:02     Метод Шелла #1
попробовала написать это в С++, но что-то не так. можете подсказать
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
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
int main(int argc, char* argv[])
{
        int i,n,j,inc,x;
        cin>>n;
        int *A= new int [n];
        randomize();
        for (i=0;i<n;i++)
        {
        A[i]=rand()%20;
        cout<<A[i]<<" ";
        }
        for (inc=n/2;inc>=1;inc=inc/2)
        {
                while (inc>0)
                {
                        for (i=inc+1;i<=n;i++)
                        {
                                j=i-inc;
                                while (j>0)
                                {
                                        if (A[j]>A[j+inc])
                                        {
                                                x=A[j];
                                                A[j]=A[j+inc];
                                                A[j+inc]=x;
                                        }
                                }
                                
                        }
                }
        }
        for (i=0;i<n;i++)
        {
        cout<<A[i];
        }
        getch();
        return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.10.2010, 01:02     Метод Шелла
Посмотрите здесь:

Метод Шелла C++
C++ Метод Шелла
C++ Не получается обнаружить ошибку(метод Шелла)
Метод Шелла, алгоритм обмена C++
C++ Метод Шелла
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
24.10.2010, 08:17     Метод Шелла #2
Отладчиком не пробовала пройтись?
osen'
 Аватар для osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
24.10.2010, 10:47  [ТС]     Метод Шелла #3
к сожалению, я не знаю, как это делается
papochka
 Аватар для papochka
32 / 32 / 2
Регистрация: 14.11.2009
Сообщений: 137
24.10.2010, 10:58     Метод Шелла #4
Что именно что-то не так? Конкретно вопрос?
Не компилируется? Не тот результат? Что?

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
#include <iostream>
#include <ctime>
#include <math.h>
using namespace std;
int main(int argc, char* argv[])
{
        int i,n,j,inc,x;
        cin>>n;
        int *A= new int [n];
        for (i=0;i<n;i++)
        {
        A[i]=rand()%20;
        cout<<A[i]<<" ";
        }
        for (inc=n/2;inc>=1;inc=inc/2)
        {
                while (inc>0)
                {
                        for (i=inc+1;i<=n;i++)
                        {
                                j=i-inc;
                                while (j>0)
                                {
                                        if (A[j]>A[j+inc])
                                        {
                                                x=A[j];
                                                A[j]=A[j+inc];
                                                A[j+inc]=x;
                                        }
                                }
                                
                        }
                }
        }
        for (i=0;i<n;i++)
        {
        cout<<A[i];
        }
        cin.get();
        return 0;
}
Но что-то у вас в этом участке кода:
C++
1
2
3
4
5
6
7
8
9
                                while (j>0)
                                {
                                        if (A[j]>A[j+inc])
                                        {
                                                x=A[j];
                                                A[j]=A[j+inc];
                                                A[j+inc]=x;
                                        }
                                }
В отладке он получается всегда больше нуля, и бесконечно работает, значение не меняется....
osen'
 Аватар для osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
24.10.2010, 11:11  [ТС]     Метод Шелла #5
он просто выводит массив, никакой сортировки не происходит

Добавлено через 2 минуты
"for (inc=n/2;inc>=1;inc=inc/2)"
правильно ли я разместила этот цикл?

Добавлено через 9 минут
попробую разобраться, что не так. спасибо=)
papochka
 Аватар для papochka
32 / 32 / 2
Регистрация: 14.11.2009
Сообщений: 137
24.10.2010, 11:12     Метод Шелла #6

Не по теме:

Администрация, 10 минут малова-то, я провозился, хотел поменять код - но нет...



Запомните: выделили память - освободите её.
щас дальше разбирать пойду.
osen'
 Аватар для osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
24.10.2010, 11:14  [ТС]     Метод Шелла #7
cin.get(); - для чего используется это функция?
papochka
 Аватар для papochka
32 / 32 / 2
Регистрация: 14.11.2009
Сообщений: 137
24.10.2010, 11:17     Метод Шелла #8
Цитата Сообщение от osen' Посмотреть сообщение
cin.get(); - для чего используется это функция?
аналогично getch(); в данном случае. и впишите перед cin.get();
C++
1
delete [] A;
osen'
 Аватар для osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
24.10.2010, 17:04  [ТС]     Метод Шелла #9
теперь выходит ошибка "Project1.exe raised exception…», что это значит, скажите пожалуйста.
osen'
 Аватар для osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
26.10.2010, 22:22  [ТС]     Метод Шелла #10
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
#include <iostream.h>
#include <conio.h>
#include <stdio.h>
#include <math.h>
int main(int argc, char* argv[])
{
        int i,n,j,inc,x;
        cin>>n;
        int *A= new int [n];
        randomize();
        for (i=0;i<n;i++)
        {
                A[i]=rand()%20;
                cout<<A[i]<<" ";
                for (inc=n/2;inc>=1;inc=inc/2)
                {       cout<<inc;
                        for (i=inc+1;i<=n;i++)
                        {
                              j=i-inГ±;
                              if (A[j]>A[i])
                              {
                                        x=A[j];
                                        A[j]=A[i];
                                        A[i]=x;
                              }
 
 
 
                        }
                }
        cout<<A[i];
        }
 
delete [] A;
cin.get();
return 0;
}
попробовала так, но все равно что-то не то...

Добавлено через 20 часов 31 минуту
неужели совсем безвыходная задача... подтолкните в нужном направлении, пожалуйста.
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
27.10.2010, 04:19     Метод Шелла #11
Цитата Сообщение от osen' Посмотреть сообщение
попробовала так, но все равно что-то не то...
Для начала сделай так, чтобы все элементы массива генерировались до запуска сортировки. Где у тебя в программе цикл, который этим занимается?
osen'
 Аватар для osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
27.10.2010, 12:07  [ТС]     Метод Шелла #12
C++
1
2
3
4
5
for (i=0;i<n;i++)
        {
                A[i]=rand()%20;
                cout<<A[i]<<" ";
         }
вот он
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
27.10.2010, 16:35     Метод Шелла #13
Теперь напиши отдельно цикл который выполняет сортировку.
osen'
 Аватар для osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
27.10.2010, 16:51  [ТС]     Метод Шелла #14
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (inc=n/2;inc>=1;inc=inc/2)
        {
                while (inc>0)
                {
                        for (i=inc+1;i<=n;i++)
                        {
                                j=i-inc;
                                if (A[j]>A[j+inc])
                                        {
                                                x=A[j];
                                                A[j]=A[j+inc];
                                                A[j+inc]=x;
                                        }
                                                              
                        }
                }
        }
Добавлено через 1 минуту
я не уверена, что это правильно
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
27.10.2010, 22:24     Метод Шелла #15
Это цикл из самого первого варианта. Давай лучше из последнего. А когда ты получишь тело цикла, попытайся в комментариях обьяснить, что делает каждая строчка.
osen'
 Аватар для osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
27.10.2010, 23:25  [ТС]     Метод Шелла #16
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for (inc=n/2;inc>=1;inc=inc/2)              //для приращения inc,начиная от inc=n/2, с шагом inc/2 пока inc>=1 выполнять цикл
        {
                 for (i=inc+1;i<=n;i++)         //для элемента i, начиная от i=inc+1, с шагом 1 пока i<=n выполнять цикл
 
                        {
                                j=i-inc;              //находим j - номер элемента массива, с к-м будет сравниваться i-й элемент
                                    if (A[j]>A[j+inc])  //сравниваем i-й и j-й элементы
                                        {
                                                x=A[j];      //меняем местами i-й и j-й элементы, если j-й элемент больше i-го  
 
                                                A[j]=A[j+inc];
                                                A[j+inc]=x;
                                        }
                                                              
                        
                }
        }
я его немного изменила, удалила цикл while(inc>0),по-моему, он не нужен
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
27.10.2010, 23:43     Метод Шелла #17
Такое описание никуда не годится. Как ты можешь понять смысл этих циклов, когда ты их описываешь дословно? В чем смысл первого цикла, в чем смысл второго?

Заодно посмотри описание сортировки шелла:

http://ru.wikipedia.org/wiki/%D0%A1%...BB%D0%BB%D0%B0
osen'
 Аватар для osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
28.10.2010, 00:58  [ТС]     Метод Шелла #18
Я просто хотела более подробно описать, эта первая моя "серьезная" работа, до этого я писала только самые элементарные программки. Я читала о сортировке (не просто же так я писала, когда переводила этот код из паскаля, я старалась разобраться).В чем состоит суть сортировки я понимаю, вроде бы, а может и не правильно понимаю.
Если мой массив состоит из n элементов, то значение приращения inc для первого прохода равно половине элементов массива в случае если n-четное, в случае нечетного n берется целое от деления n на 2. Далее для элементов от i=inc+1 до n (для каждого элемента отдельно) я нахожу j элемент (он находится на расстоянии inc от i-го элемента), с которым и сравниваю значение i-го элемента и в случае если j больше, меняю их местами. Потом беру следующее значение приращения inc,равное половине или целому от деления от предыдущего приращения, и так до тех пор, пока приращениие не станет равно 1. В конце концов массив должен отсортироваться.
Просто ни в одном из примеров, которые я рассматривала, я не поняла, чему равно приращение, поэтому решила использовать деление на 2. В идеале это должно быть 1,3,5,9, если я не ошибаюсь или приращение рассчитывается по спец.формулам, к-е оказались для меня тяжелыми в реализации.
Может и правда, я не правильно поняла смысл сортировки, объсните, пожалуйста.
alexzak
84 / 57 / 1
Регистрация: 07.08.2010
Сообщений: 185
28.10.2010, 08:50     Метод Шелла #19
Ты в принципе понимаешь правильно. Одна неточность только в том, что по j должен быть цикл, где j пробегает от i до числа меньшего чем inc, и в нём нужно обменивать элементы больший с меньшим. Так как у тебя этого цикла не было, то алгоритм работал неправильно. И inc можно уменьшать не в два раза а в 2.2 для большей эффективности алгоритма. В общем будет где-то так:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
    for (int inc = n / 2; inc > 0; inc = inc * 5 / 11)
    {
        for (int i = inc; i < n; ++i)  // идём вверх от inc до n
        {
            int temp = a[i];
 
            int j = i;
            for (; j >= inc && a[j - inc] > temp; j -= inc)
                            // идём в обратном направлении,
                            // сдвигая temp вниз, пока возможно,
                            // а остальные элементы, которые больше temp, вверх
            {
                a[j] = a[j - inc];
            }
 
            // в этом месте выполяется условие a[j - inc] > temp,
            // или j - самый нижний элемент для шага inc.
            // заканчиваем перемещение (сдвиг) temp
            a[j] = temp;
        }
    }
Вместо обмена можно ещё двигать меньший элемент вниз по массиву, пока он не встретит более меньший (т.е. элементы будут в отсортированном порядке). Это и делается в коде выше.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.10.2010, 20:21     Метод Шелла
Еще ссылки по теме:

C++ Сортировка, метод шелла
C++ метод сортировки Шелла
C++ СЛАУ. Метод обратной матрицы, метод Гаусса, метод Крамера, метод Зейделя

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

Или воспользуйтесь поиском по форуму:
osen'
 Аватар для osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
28.10.2010, 20:21  [ТС]     Метод Шелла #20
спасибо большое, вот только при нахождении inc=inc*5/11 у меня массив не полностью сортируется, а при inc=inc/2 все нормально. Поэтому решила для нахождения приращения оставить деление на 2.
Yandex
Объявления
28.10.2010, 20:21     Метод Шелла
Ответ Создать тему
Опции темы

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