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

quickSelect - C++

Восстановить пароль Регистрация
Другие темы раздела
SFML Visual studio 2010 и SFML 2.1, ошибка LNK1112 http://www.cyberforum.ru/cpp-beginners/thread1063484.html
Всем привет. Ситуация такова. Решил значит ознакомится с VS и SFML. Скачал (как-бы грешно это не звучало) Visual studio 2010 и SFML 2.1 (Visual C++ 10 (2010) - 64 bits, т.к. у меня 64 разрядная система). После свершил некоторые деяния над VS по инструкции http://www.sfml-dev.org/tutorials/2.0/start-vc.php. Однако после запуска введенного кода (дабы лицезреть "зеленый кружек"), мне высвечивается...
C++ CodeBlocks-13.12mingw + SDL выдает ошибку Привет, начал освоения SDL библиотеки. Уроки читаю здесь. По урокам версия КодеБлокс и СДЛ отличается (они там более старые). Я скачал библиотеку на офф сайте, SDL2-devel-2.0.1-mingw.tar.gz. Установил, пустой проект запускает без ошибок. Сейчас по уроку нужно в файл CApp_OnInit.cpp записать такой код: bool CApp::OnInit() { if(SDL_Init(SDL_INIT_EVERYTHING) < 0) { ... http://www.cyberforum.ru/cpp-beginners/thread1063483.html
C++ Дано последовательность чисел b1,.bn . Получить квадратную матрицу порядка n
Дано последовательность чисел b1,...bn . Получить квадратную матрицу порядка n, элементами которой являются числа b1,...,bn^n. , расположены по схеме:
C++ Задание с массивом
Передать массив I(10) в массив J(10) в обратной последовательности. Буду сильно благодарен за помощь.
C++ Нарисовать фигуру и закрасить ее сканирующей строкой http://www.cyberforum.ru/cpp-beginners/thread1063450.html
В компиляторе Borland с++ требуется нарисовать фигуру и закрасить ее сканирующей строкой. Помогите пожалуйста... вот фигура
C++ Увеличить указатель на размер адресуемой им структуры Увеличить указатель на размер адресуемой им структуры. Буду очень признателен за помощь. подробнее

Показать сообщение отдельно
Aliru
0 / 0 / 0
Регистрация: 07.05.2013
Сообщений: 83
05.01.2014, 15:48     quickSelect
Есть несколько вопросов.
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
// QuickSelect.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include "conio.h"
 
using namespace std;
 
template<class T>
void printArray(T *A, long N)
{
    for (long i = 0; i < N; i++) 
    {
        cout << A[i];
        if (i < N - 1)
            cout << ' ';
    }
    cout << endl;
}
 
template<class T>
long partition(T* a, T &p, long N) 
{
// На входе - массив a[], a[N] - его последний элемент.
 
  long i = 0, j = N - 1;        // поставить указатели на исходные места
  T temp;
 
  printArray(a,N);
  p = a[(i + j)/2];        // центральный элемент
 
  // процедура разделения
  do 
  {
    while ( a[i] < p ) i++;
    while ( a[j] > p ) j--;
    if (i <= j) 
    {
      temp = a[i]; a[i] = a[j]; a[j] = temp;
      i++; j--;
    }
  } 
  while ( i<=j );
  printArray(a,N);
  return ++j;
}
 
 
template<class T>
T quickSelect(T* input, T &p, long N, long k)
{
           long j = partition(input,p, N);
    long pivot = j + 1;
    if ( j == k - 1) 
        return p;
    else 
        if ( k < pivot ) 
            return quickSelect(input, p, j, k);
        else  
            return quickSelect(input + j, p, N - j, k - j);
}
 
int _tmain(int argc, _TCHAR* argv[])
{
    int A[] = {-900,1,0,777,-34,4,-87,6};
    int pivot = A[0];
    cout << quickSelect(A, pivot, sizeof(A)/sizeof(int), 2);
    _getch();
    return 0;
}
1. Как partition() знает что делать и как с помощью printArray() - я думал, это возможно в случае когда printArray() передается как параметр partition() и quickSelect() cоответственно.
2. В рекурсивном варианте
C++
1
quickSelect(input + j, p, N - j, k - j);
ошибка когда доходит до массива из 2 элементов и выбирается не искомый элемент - начинается зацикливание

Добавлено через 1 час 15 минут
Немного переделал
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if (2 < N)
    {
        if ( j == k - 1) 
            return p;
        else 
            if ( k < pivot ) 
                return quickSelect(input, p, j, k);
            else  
                return quickSelect(input + j, p, N - j, k - j);
    }
    else 
    {
        if ( j == k - 1) 
            return p;
        else
            return input[1];
    }
Теперь вроде бы работает.
Есть еще какие-то варианты?
Ну кроме -
C++
1
std::nth_element
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 04:17. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru