Форум программистов «Весельчак У»
  *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

  • Рекомендуем проверить настройки временной зоны в вашем профиле (страница "Внешний вид форума", пункт "Часовой пояс:").
  • У нас больше нет рассылок. Если вам приходят письма от наших бывших рассылок mail.ru и subscribe.ru, то знайте, что это не мы рассылаем.
   Начало  
Наши сайты
Помощь Поиск Календарь Почта Войти Регистрация  
 
Страниц: [1]   Вниз
  Печать  
Автор Тема: Нужна помощь!  (Прочитано 8139 раз)
0 Пользователей и 1 Гость смотрят эту тему.
maximys
Гость
« : 07-10-2007 05:31 » 

Имеется псевдокод Рекурсивного алгоритма поразрядной MSD-сортировки
Код:
MSD_Sort (A, l, r, d, C)
1. А – массив
2. С – вспомогательный массив для карманов
3. l, r – левая и правая границы части массива A
4. R – основание системы счисления для поразрядной сортировки
5. k – максимальное количество цифр в значениях
6. d – номер текущей цифры
7. M – пороговый размер кармана для окончания рекурсии
8. k← bitsword / bitsdigit  bitsword – число битов в ячейке мас-сива А
9.         bitsdigit – число битов в цифре
10. if d > k
11.      then return
12. if r – l   M
13.      then  Insertion_Sort(A + l, r – l)
14.                return
15.   вычисление размеров карманов
16. for j ← 1 to R + 1
17.      do count[j] ← 0
18. for i ← l to r
19.      do j ← digit(A[i], d, R) digit(…) – извлечение d-й цифры
20.           count[j + 1] ← count[j + 1] + 1
21. for j ← 2 to R
22.      do count[j] ← count[j] + count[j – 1]
23. распределение значений по карманам
24. for j ← l to r
25.      do j ← digit(A[i], d, R)
26.           C[l + count[j]] ← A[i]
27.           count[j] ← count[j] + 1
28.   перенос значений из карманов в массив A
29. for i ← l to r
30.      do A[i] ← C[i]
31. MSD_Sort (A, l, l + count[1], d + 1, C)
32. for i ← 2 to R
33.      do MSD_Sort (A, l + count[i], l + count[i + 1] – 1, d + 1, C)

Нужно перевести этот псевдокод в код на С++.Помогите кто может.
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #1 : 07-10-2007 09:39 » 

какой размер массива А и его тип ?

какие типы переменных
Код:
l, r, d, C
?

как понять выражение
Код:
l, r – левая и правая границы части массива A
?

непонятно начальное значение переменной i в выражениях твоего кода типа
Код:
for i < l to r

Записан

maximys
Гость
« Ответ #2 : 08-10-2007 14:12 » 

Цитата
какой размер массива А и его тип ?
Тип массива произвольный(класс), а размер можно обозначить переменной maxN(размерность увеличивается, будет прописано в другом методе)Н-р:
Код:
Vector С[maxN];

Цитата
какие типы переменных
int
Цитата
как понять выражение:  l, r – левая и правая границы части массива A?
так и понимать..?

Цитата
непонятно начальное значение переменной i в выражениях твоего кода типа:for i < l to r
for i ← l to r // символ "←" это символ присваивания, а "l"- это буква

И ещё в 12ой строчке
Код:
12. if r – l  < M //минимальный размер корзины
Записан
Алексей++
глобальный и пушистый
Глобальный модератор

ru
Offline Offline
Сообщений: 13


« Ответ #3 : 08-10-2007 15:49 » 

уфф, в общем я запутался в твоих переменных и необъявленных массивах ))) , но что то вроде этого должно получиться

Код:
typedef DWORD vector;

void MSD_Sort(vector* A, int l, int r, int d, vector* C)
{

// А[l...r] - массив
// С[l...r] - вспомогательный массив для карманов
// l, r - левая и правая границы части массива A

int R=2;// - основание системы счисления для поразрядной сортировки

//максимальное количество цифр в значениях
int k=10;

//номер текущей цифры
int D=0;

//пороговый размер кармана для окончания рекурсии
int M=100;//?

//
int bitsword=8;// - число битов в ячейке мас-сива А
int bitsdigit=8;// - число битов в цифре

k= bitsword / bitsdigit;// 

if(d > k)return;

if (r - l >   M) // знак сравнения какой ?
{
Insertion_Sort(A + l, r - l);
return;
}

//вычисление размеров карманов
for(j=1; j<=R+1; j++)
{
count[j] = 0;
}

for(i=l;i<=r;i++)
{
j = digit(A[i], d, R);//digit(...) - извлечение d-й цифры
count[j + 1] = count[j + 1] + 1;
}

for(j=2;j<=R;j++)
{
count[j] < count[j] + count[j - 1];
}

//распределение значений по карманам
for(j=l;j<=r;j++)
{
j = digit(A[i], d, R);
C[l + count[j]] < A[i];
count[j] < count[j] + 1;
}

//перенос значений из карманов в массив A
for(i=l;i<=r;i++)
{
A[i] = C[i];
}

MSD_Sort (A, l, l + count[1], d + 1, C);
for(i=2;i<=R;i++)
{
MSD_Sort (A, l + count[i], l + count[i + 1] - 1, d + 1, C);
}
}

//пример вызова
void F()
{
#define maxN 10

vector A[maxN];
vector C[maxN];

MSD_Sort(A, 0, maxN-1, 2, C);
}
Записан

maximys
Гость
« Ответ #4 : 19-10-2007 16:19 » 

Довел до ума сортировку, вот что получилось
Код:
template <class T> void Vector <T>::Sort ()
{

        MSD_Sort (mass,0, size0,0,C);
}

template <class T> void Vector <T>::MSD_Sort (T* mass,int l, int r, int d, T *C)
{

int R=16;// - основание системы счисления для поразрядной сортировки
int count[100];
int bitsword,bitsdigit,k;
int i,j;
   bitsword = sizeof(int) * 8; // - число битов в ячейке мас-сива А
   bitsdigit = ceil(log(R)/log(2));// - число битов в цифре
//максимальное количество цифр в значениях
k=ceil(1.0* bitsword/bitsdigit);

//пороговый размер кармана для окончания рекурсии
int M=100;//?

if(d > k)return;

if (r - l <=   M)
{
Insertion_Sort(mass + l, r - l);
return;
}

//вычисление размеров карманов
for(j=1; j<=R+1; j++)
{
count[j] = 0;
}

for(i=l;i<=r;i++)
{
j = (mass[i]>>bitsdigit*(bitsword-d-1)&(R-1));

count[j + 1] = count[j + 1] + 1;
}

for(j=2;j<=R;j++)
{
count[j] < count[j] + count[j - 1];
}

//распределение значений по карманам
for(j=l;j<=r;j++)
{
j = (mass[i]>>bitsdigit*(bitsword-d-1)&(R-1));
C[l + count[j]] < mass[i];
count[j] < count[j] + 1;
}

//перенос значений из карманов в массив A
for(i=l;i<=r;i++)
{
mass[i] = C[i];
}

MSD_Sort (mass, l, l + count[1], d + 1, C);
for(i=1;i<=R;i++)
{
MSD_Sort (mass, l + count[i], l + count[i + 1] - 1, d + 1, C);
}
}

void  Insertion_Sort(T* mass,int n){
  int k,i,j;
  for(  i=1; i<n; i++){
  int v=mass[i];
  for( k=0; k<i; k++)
  if(mass[k]>v) break;
  for( j=i-1;j>=k;j--)
  mass[j+1]=mass[j];
  mass[k]=v;
  }}
Записан
Страниц: [1]   Вверх
  Печать  
 

Powered by SMF 1.1.21 | SMF © 2015, Simple Machines