Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
#1

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

24.10.2010, 01:02. Просмотров 1369. Ответов 19
Метки нет (Все метки)

попробовала написать это в С++, но что-то не так. можете подсказать
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;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.10.2010, 01:02
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Метод Шелла (C++):

Не сходится теория и практика метод Шелла и метод простого выбора
Здравствуйте! Помогите пожулуйста найти ошибке в коде, Я уже не знаю где ее...

Метод Шелла
Помогите найти ошибку. Задание - Провести сортировку последовательности а1, …...

Метод Шелла
Помогите пожалуста решить задачу. Провести сортировку последовательности а1, …...

Метод Шелла
Ошибка после сортировки методом Шелла. По примеру сайта...

Метод Шелла
Проверить упорядочены ли элементы строк матрицы. Если нет, то упорядочить их в...

Метод сортировки Шелла
помогите дописать программу в case 6 СТРОИТЕЛЬНАЯ КОМПАНИЯ (поля: заказчик,...

19
alexzak
84 / 57 / 8
Регистрация: 07.08.2010
Сообщений: 185
24.10.2010, 08:17 #2
Отладчиком не пробовала пройтись?
0
osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
24.10.2010, 10:47  [ТС] #3
к сожалению, я не знаю, как это делается
0
papochka
33 / 33 / 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;
                                        }
                                }
В отладке он получается всегда больше нуля, и бесконечно работает, значение не меняется....
0
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 минут
попробую разобраться, что не так. спасибо=)
0
papochka
33 / 33 / 2
Регистрация: 14.11.2009
Сообщений: 137
24.10.2010, 11:12 #6

Не по теме:

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



Запомните: выделили память - освободите её.
щас дальше разбирать пойду.
0
osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
24.10.2010, 11:14  [ТС] #7
cin.get(); - для чего используется это функция?
0
papochka
33 / 33 / 2
Регистрация: 14.11.2009
Сообщений: 137
24.10.2010, 11:17 #8
Цитата Сообщение от osen' Посмотреть сообщение
cin.get(); - для чего используется это функция?
аналогично getch(); в данном случае. и впишите перед cin.get();
C++
1
delete [] A;
1
osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
24.10.2010, 17:04  [ТС] #9
теперь выходит ошибка "Project1.exe raised exception…», что это значит, скажите пожалуйста.
0
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 минуту
неужели совсем безвыходная задача... подтолкните в нужном направлении, пожалуйста.
0
alexzak
84 / 57 / 8
Регистрация: 07.08.2010
Сообщений: 185
27.10.2010, 04:19 #11
Цитата Сообщение от osen' Посмотреть сообщение
попробовала так, но все равно что-то не то...
Для начала сделай так, чтобы все элементы массива генерировались до запуска сортировки. Где у тебя в программе цикл, который этим занимается?
0
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]<<" ";
         }
вот он
0
alexzak
84 / 57 / 8
Регистрация: 07.08.2010
Сообщений: 185
27.10.2010, 16:35 #13
Теперь напиши отдельно цикл который выполняет сортировку.
0
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 минуту
я не уверена, что это правильно
0
alexzak
84 / 57 / 8
Регистрация: 07.08.2010
Сообщений: 185
27.10.2010, 22:24 #15
Это цикл из самого первого варианта. Давай лучше из последнего. А когда ты получишь тело цикла, попытайся в комментариях обьяснить, что делает каждая строчка.
0
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),по-моему, он не нужен
0
alexzak
84 / 57 / 8
Регистрация: 07.08.2010
Сообщений: 185
27.10.2010, 23:43 #17
Такое описание никуда не годится. Как ты можешь понять смысл этих циклов, когда ты их описываешь дословно? В чем смысл первого цикла, в чем смысл второго?

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

http://ru.wikipedia.org/wiki/%D0%A1%...BB%D0%BB%D0%B0
0
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, если я не ошибаюсь или приращение рассчитывается по спец.формулам, к-е оказались для меня тяжелыми в реализации.
Может и правда, я не правильно поняла смысл сортировки, объсните, пожалуйста.
0
alexzak
84 / 57 / 8
Регистрация: 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;
        }
    }
Вместо обмена можно ещё двигать меньший элемент вниз по массиву, пока он не встретит более меньший (т.е. элементы будут в отсортированном порядке). Это и делается в коде выше.
1
osen'
5 / 5 / 1
Регистрация: 09.10.2010
Сообщений: 49
28.10.2010, 20:21  [ТС] #20
спасибо большое, вот только при нахождении inc=inc*5/11 у меня массив не полностью сортируется, а при inc=inc/2 все нормально. Поэтому решила для нахождения приращения оставить деление на 2.
0
28.10.2010, 20:21
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.10.2010, 20:21
Привет! Вот еще темы с решениями:

Сортировка, метод шелла
Всем доброй ночи, задача, дан список студентов и у каждого 5 оценок,...

Метод сортировки Шелла
Написать программу которая реализует метод сортировки Шелла. Сгенерировать...

Метод Шелла, алгоритм обмена
Помогите написать программы. 1. Упорядочить заданный список целых значений...

Не получается обнаружить ошибку(метод Шелла)
Проблема в том что я написала программу на паскале,а преподаватель попросил...


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

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

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