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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 37, средняя оценка - 4.70
ForEveR
В астрале
Эксперт С++
7971 / 4733 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
#1

Сортировка выбором. Рекурсия - C++

08.08.2010, 02:47. Просмотров 5099. Ответов 26
Метки нет (Все метки)

Дичайше туплю... Нужна сортировка выборкой одномерного массива. Рекурсией. Итерацией могу сделать. Рекурсией - никак... Застопорило что-то. Буду благодарен за подсказку и помощь.

Добавлено через 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
#include <iostream>
#include <ctime>
 
void selectionSort(int Arr[], int size); 
 
int main()
{
    srand(time(NULL));
    const int Size=10;
    int Arr[Size];
    for(int i=0;i<Size;++i)
        Arr[i]=1+rand()%100-1+1;
    std::cout<<"Arr is:\n";
    for(int i=0;i<Size;++i)
    {
        std::cout<<Arr[i]<<' ';
    }
    std::cout<<std::endl;
    selectionSort(Arr, Size);
    return 0;
}
 
void selectionSort(int Arr[], int size)
{
    int k=0, x=0;
    for(int i=0; i < size; i++) 
    { 
        k=i; x=Arr[i];
        for(int j=i+1; j < size; j++) 
        if (Arr[j] < x) 
        {
            k=j; x=Arr[j]; 
        }
        Arr[k] = Arr[i]; 
        Arr[i] = x;
    }
    std::cout<<"Sorted array:\n";
    for(int i=0;i<size;++i)
        std::cout<< Arr[i] <<' ';
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.08.2010, 02:47
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сортировка выбором. Рекурсия (C++):

сортировка выбором - C++
помогите пожалуйста, алгоритм не работает то есть не сортирует #ifndef FUNC #define FUNC #include &quot;vibor.h&quot; #include &lt;vector&gt; ...

Сортировка выбором - C++
Сортировка выбором. Дана последовательность чисел а1, а2,..., аn. Требуется переставить элементы так, чтобы они были расположены по...

Сортировка выбором - C++
Добрый день, я заметил, что при сортировке массива из N элементов по алгоритму сортировки &quot;Выбором&quot;, количество смены местами элементов...

Сортировка выбором - C++
Разбираю сортировку выбором. Как реализовать сортировку по возрастанию понял, а как реализовать сортировку по возрастанию до первого...

Сортировка выбором - C++
#include &lt;iostream&gt; #include &lt;math.h&gt; #include &lt;conio.h&gt; #include &lt;cstdlib&gt; using namespace std; void SetRussianLocale() {...

сортировка выбором - C++
не могу разобраться с задачей, не разбираюсь в указателях(((: сортировка выбором символов в строке. Использовать указатели на текущий и...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
ForEveR
08.08.2010, 05:52  [ТС]     Сортировка выбором. Рекурсия
  #16

Не по теме:

fasked, Про определитель. Это уже завтра... Если вообще смогу. Вспомнилась алгебра и моя не слишком большая любовь к определителям.

nikkka
Мат в 32 хода
235 / 170 / 8
Регистрация: 10.09.2009
Сообщений: 1,096
08.08.2010, 09:35 #17
Не короче, не красивше, но зато моё!!!!
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int sum(int arr[], int size)
{
    if(size==0) return arr[0];
    else {return (arr[size]+sum(arr, size-1)); size--;};
}
int main()
{
    int a[10];
    for(int i=0;i<10;i++)
        cin>>a[i];
    cout<<sum(a,9)<<"\n";
    system("pause");
}
Добавлено через 6 минут
Вот, "подкрасил".
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
#include <iostream>
int sum(int arr[], int size)
{
    if(size==0)  return arr[0];
    else return arr[size]+sum(arr, --size);
}
int main()
{
    int a[10]={1,2,3,4,5,6,7,8,9,10}
    std::cout<<sum(a,9)<<"\n";
    system("pause");
    return 0;
}
ForEveR
В астрале
Эксперт С++
7971 / 4733 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
09.08.2010, 01:36  [ТС] #18
Определитель. Для 3 правильно считает. Дальше не проверял. 20 тужился тужился не посчитал. Или просто я не дождался.
Совсем сам сделать не смог. Пришлось посмотреть на другие программы, понять модель и сделать вот так.

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
#include <iostream>
#include <cmath>
#include <ctime>
 
double determ(int** Arr, int size);
 
int main()
{
    srand(time(NULL));
    int size=3;
    int**Arr;
    Arr=new int*[size];
    for(int i=0;i<size;++i)
        Arr[i]=new int[size];
    for(int i=0;i<size;++i)
        for(int j=0;j<size;++j)
            Arr[i][j]=0+rand()%5-1+1;
    for(int i=0;i<size;++i)
    {
        for(int j=0;j<size;++j)
            std::cout<<Arr[i][j]<<' ';
        std::cout<<std::endl;
    }
    std::cout<< determ(Arr, size) <<'\n';
    for(int i=0;i<size;++i)
        delete[] Arr[i];
    delete[] Arr;
    return 0;
}
 
double determ(int** Arr, int size)
{
    int i,j;
    double det=0;
    int** matr;
    if(size==1)
    {
        det=Arr[0][0];
    }
    else if(size==2)
    {
        det=Arr[0][0]*Arr[1][1]-Arr[0][1]*Arr[1][0];
    }
    else
    {
        matr=new int*[size-1];
        for(i=0;i<size;++i)
        {
            for(j=0;j<size-1;++j)
            {
                if(j<i) 
                    matr[j]=Arr[j];
                else
                    matr[j]=Arr[j+1];
            }
            det+=pow((double)-1, (i+j))*determ(matr, size-1)*Arr[i][size-1];
        }
        delete[] matr;
    }
    return det;
}
fasked
Эксперт С++
4935 / 2515 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
09.08.2010, 01:38 #19
Цитата Сообщение от Lavroff Посмотреть сообщение
Определитель. Для 3 правильно считает. Дальше не проверял. 20 тужился тужился не посчитал. Или просто я не дождался.
Совсем сам сделать не смог. Пришлось посмотреть на другие программы, понять модель и сделать вот так.
Проверять не буду, но на первый взгляд правильная. Точки останова вижу в 1 и в 2. Новая матрица создается. Зачтено
ForEveR
В астрале
Эксперт С++
7971 / 4733 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
09.08.2010, 01:42  [ТС] #20
fasked, Продолжение будет?) Только желательно без вышки) Скоро итак учеба уже)
fasked
Эксперт С++
4935 / 2515 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
09.08.2010, 01:43 #21
Цитата Сообщение от Lavroff Посмотреть сообщение
Продолжение будет?) Только желательно без матана/алгебры) Скоро итак учеба уже)
вот и готовься

Имеются числа 1, 2, 3, 4, 5. Сколькими способами, суммируя эти числа, можно получить 6, если каждое слагаемое можно использовать не более одного раза? Порядок суммирования не играет роли.
ForEveR
В астрале
Эксперт С++
7971 / 4733 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
09.08.2010, 01:46  [ТС] #22
fasked, 1+2+3, 1+5, 4+2. Или это программу такую написать?)
fasked
Эксперт С++
4935 / 2515 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
09.08.2010, 01:51 #23
Цитата Сообщение от Lavroff Посмотреть сообщение
fasked, 1+2+3, 1+5, 4+2. Или это программу такую написать?)
ахах а ты как думал, еще и рекурсивно!
ForEveR
В астрале
Эксперт С++
7971 / 4733 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
09.08.2010, 02:18  [ТС] #24
fasked, Я вот думаю, какое условие выхода из функции тогда поставить оО

Ради шутки) Рекурсивно) И по данной задаче

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>
 
int count(int size);
 
int main()
{
    int size=3;
    std::cout<< count(size) << '\n';
    return 0;
}
 
int count(int size)
{
    static int cnt=0;
    if(size==0)
        return cnt;
    else
    {
        cnt++;
        count(size-1);
    }
}
Добавлено через 24 минуты
Нет. Что-то ничего придумать не могу... Только если тупо перебором...
fasked
Эксперт С++
4935 / 2515 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
09.08.2010, 02:57 #25
Цитата Сообщение от Lavroff Посмотреть сообщение
Только если тупо перебором...
первое, что может прийти в голову, это конечно простой перебор.
для решения таким путем необходимо из данного множества составить все возможные множества.
то есть, например, есть множество { 1,2,3 }. для него всеми возможными множествами будут { 1 }, { 2 }, { 3 }, { 1, 2 }, { 1, 3 }, { 2, 3 }. далее необходимо просто найти сумму элементов каждого подмножества.
в контексте данной задачи можно исключить все подмножества из одного элемента.
ForEveR
В астрале
Эксперт С++
7971 / 4733 / 321
Регистрация: 24.06.2010
Сообщений: 10,541
Завершенные тесты: 3
09.08.2010, 03:00  [ТС] #26
fasked, О май год. Множества. М... Оригинально. Попробую быть может)
Т.е. все возможные k-элементные подмножества? В данном случае {1,2,3,4,5}, {1,2,3,4}, {2,3,4,5}, {1,3,4,5}, {1,2,4,5}, {1,2,3}, {2,3,4} {3,4,5}, {1,2,4}, {1,2,5}, {2,3,5}, {1,2}, {1,3}, {1,4}, {1,5}, {2,3}, {2,4}, {2,5}, {3,4}, {3,5}, {4, 5}.
fasked
Эксперт С++
4935 / 2515 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
09.08.2010, 03:06 #27
Цитата Сообщение от Lavroff Посмотреть сообщение
Множества
Еще подсказка для перебора. Все возможные подмножества можно сгенерировать примерно так:
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
#include <iostream>
#include <cmath>
 
using namespace std;
 
void main()
{
   int p[] = {1, 2, 3, 4, 5};
   int n = sizeof(p)/sizeof(int);
   int m = (int)pow((double)2, n);
 
   for (int i=0; i<m; ++i)
   {
      bool sep=false;
      cout << "{";
      for (int d=0; d<n; ++d)
      {
         if ((1<<d)&i)
         {
            cout << (sep ? ", " : "") << p[d];
            sep = true;
         }
      }
      cout << "}\n";
   }
 
   system("PAUSE");
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.08.2010, 03:06
Привет! Вот еще темы с ответами:

Сортировка выбором - C++
Выбираeтся минимaльный элeмeнт в мaссивe и пeрeнoсится в нoвый массив. 3aтем нa его местo записывается последний элемент исходного массива.

Сортировка выбором - C++
Помогите тут сделать сортировку выбором for (i = 0; i&lt;n; i++) { for (j = 0; j&lt;n; j++) { if (arr&gt;arr) { ...

Сортировка выбором на с++ - C++
Сортировка выбором. Выбрать минимальный элемент в массиве, перенести в выходной массив на очередную позицию. Во входном массиве все...

Сортировка выбором - C++
#include &quot;stdafx.h&quot; #include&quot;iostream&quot; #include&quot;time.h&quot; using namespace std; int main() {srand(time(0)); int a, n, k, q,j; ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
09.08.2010, 03:06
Ответ Создать тему
Опции темы

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