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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 37, средняя оценка - 4.70
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
08.08.2010, 02:47     Сортировка выбором. Рекурсия #1
Дичайше туплю... Нужна сортировка выборкой одномерного массива. Рекурсией. Итерацией могу сделать. Рекурсией - никак... Застопорило что-то. Буду благодарен за подсказку и помощь.

Добавлено через 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++ /сортировка выбором C++
сортировка выбором C++
C++ Сортировка выбором
C++ сортировка выбором
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
09.08.2010, 01:43     Сортировка выбором. Рекурсия #21
Цитата Сообщение от Lavroff Посмотреть сообщение
Продолжение будет?) Только желательно без матана/алгебры) Скоро итак учеба уже)
вот и готовься

Имеются числа 1, 2, 3, 4, 5. Сколькими способами, суммируя эти числа, можно получить 6, если каждое слагаемое можно использовать не более одного раза? Порядок суммирования не играет роли.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 3
09.08.2010, 01:46  [ТС]     Сортировка выбором. Рекурсия #22
fasked, 1+2+3, 1+5, 4+2. Или это программу такую написать?)
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
09.08.2010, 01:51     Сортировка выбором. Рекурсия #23
Цитата Сообщение от Lavroff Посмотреть сообщение
fasked, 1+2+3, 1+5, 4+2. Или это программу такую написать?)
ахах а ты как думал, еще и рекурсивно!
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
09.08.2010, 02:57     Сортировка выбором. Рекурсия #25
Цитата Сообщение от Lavroff Посмотреть сообщение
Только если тупо перебором...
первое, что может прийти в голову, это конечно простой перебор.
для решения таким путем необходимо из данного множества составить все возможные множества.
то есть, например, есть множество { 1,2,3 }. для него всеми возможными множествами будут { 1 }, { 2 }, { 3 }, { 1, 2 }, { 1, 3 }, { 2, 3 }. далее необходимо просто найти сумму элементов каждого подмножества.
в контексте данной задачи можно исключить все подмножества из одного элемента.
ForEveR
Модератор
Эксперт C++
 Аватар для ForEveR
7927 / 4709 / 318
Регистрация: 24.06.2010
Сообщений: 10,524
Завершенные тесты: 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}.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
09.08.2010, 03:06     Сортировка выбором. Рекурсия
Еще ссылки по теме:

C++ Сортировка выбором
C++ Сортировка выбором
C++ Сортировка выбором

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

Или воспользуйтесь поиском по форуму:
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 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");
}
Yandex
Объявления
09.08.2010, 03:06     Сортировка выбором. Рекурсия
Ответ Создать тему
Опции темы

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