Вектор А=(А1,А2,…,Аn) считается лексикографически большим вектора В=(В1,В2,…,Вn), если существует k>=0 такое что Аi=Вi(i<=k),Ak+1>Bk+1. Составить программу лексикографической сортировки числовых векторов. При составлении программы сортировки использовать минимальную необходимую память и эффективные структуры данных.
Давал пост в разделе задачи http://forum.pascal.net.ru/index.php?showtopic=13498&hl=kerk, мне помогли с заданием но реализация была на паскале... вот попробовал перевести в сишку... возникли вопросы.... в сишке ни разу не пробовал процедуры... правильно ли я написал? и нет под рукой книги или хелпа, хотелось бы узнать что дает в паскале команда inc, и как она должна выглядеть в С. Потом не совсем понял какая структура должна быть у программы на С. НАпример на паскале
...
...
procedure
main();
end;
Begin
End.
а как на си?
И посмотрите пожалуйста мой код.... где какие ошибки? и как продолжить главный модуль программы?
#include <conio.h>
#include <iostream.h>
#include <math.h>
void SortAt(int low_bound,int up_bound,int sort_by)
main()
{
int i,j,t;
if (sort_by=len+1) exit;
for (i=1;i=up_bound-low_bound+1;i++)
for (j=low_bound;j=up_bound-1;j++)
if (vv[sorted[j]][sort_by]>vv[sorted[j+1]][sort_by])
{
t=sorted[j];
sorted[j]=sorted[j+1];
sorted[j+1]=t;
}
i=low_bound;
while (i<=up_bound)
{
j=i;
while (i<up_bound)&&(vv[sorted[j+1]][sort_by]=vv[sorted[j]][sort_by])
inc(j); //???????????????????
SortAt(i,j,sort_by+1);
i=i+1;
}
}
int vv[3][3];
int sorted[3];
Если тебе на сях надо было, ты б так и говорил, я б на сях и пример приводил.
Ну че, давай по порядку. main() - это стандартное для си название главной функции программы. Такая функция всегда есть, и всегда одна. Например:
На паскале
program a_plus_b;
var a, b: integer;
z: array [1..5, 1..10] of integer; //просто для примера
function CalculateSum(a, b: integer): integer;
var s: integer;
begin
s := a + b;
CalculateSum := s;
end;
procedure PrintResult(a, b, s: integer);
begin
Writeln(a, ' + ', b, ' = ', s);
end;
begin
Readln(a, b);
PrintResult(a, b, CalculateSum(a, b));
end.
#include "stdio.h"
int a, b;
int z[5][10]; //просто для примера
int CalculateSum(int a, int b) //тип возвращаемого значения указываем *перед* именем функции
{
int s;
s = a + b;
return s; //вместо CalculateSum := s просто делаем return s
}
void PrintResult(int a, int b, int s) //процедуры объявляются с ключевым словом void вместо типа
{
printf("%d + %d = %d\n", a, b, s);
}
int main() //вместо главной пары begin-end объявляем функцию main
{
scanf("%d %d", &a, &b);
PrintResult(a, b, CalculateSum(a, b));
return 0;//возвращаем 0, означающий, что программа нормально завершила работу
}
if (sort_by=len+1) exit;
vv[sorted[j+1]][sort_by]=vv[sorted[j]][sort_by]
for i := 1 to up_bound - low_bound + 1 do
for (i=1;i<=up_bound-low_bound+1;i++)
for j := low_bound to up_bound - 1 do
for (j=low_bound;j<=up_bound-1;j++)
while (j < up_bound) and (vv[sorted[j + 1], sort_by] = vv[sorted[j], sort_by]) do
i := j + 1;
#include <stdio.h>
const int MAX_N = 100;
const int MAX_LEN = 100;
int vv[MAX_N][MAX_LEN];
int n;
int len;
int LexSmaller(int x, int y)
//вернуть 1, если vv[x] лексикографичекси меньше, чем vv[y], и 0 в противном случае
{
for (int i = 0; i < len; ++i)
if (...)
return 1; //лексикографически меньше
else if (...)
return 0; //лексикографически больше
//отличий не нашли, значит вектора равны; возвращаем 0
return 0;
}
void Swap(int x, int y)
//поменять местами векторы vv[x] и vv[y]
{
//проходим по векторам и меняем попарно все элементы
for (int i = 0; i < len; ++i)
{
//меняем местами vv[x][i] и vv[y][i]
...
...
...
}
}
void ReadVectors()
{
printf("Введите количество векторов: ");
scanf("%d", &n);
printf("Введите размерность (длину) векторов: ");
scanf("%d", &len);
for (int i = 0; i < n; ++i)
for (int j = 0; j < len; ++j)
{
printf("vv[%d][%d] = ", i, j);
scanf("%d", &vv[i][j]);
}
}
void BubbleSort()
//сортировка пузырьком
{
for (int i = 0; i < n; ++i)
for (int j = 0; j < n - 1; ++j)
if (LexSmaller(j + 1, j) == 1) //следующий вектор лекс. меньше текущего
//меняем их местами
Swap(j, j + 1);
}
void PrintResult()
{
printf("Результат сортировки:");
...
...
...
}
int main()
{
ReadVectors();
BubbleSort();
PrintResult();
return 0;
}
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <math.h>
const int MAX_N = 100;
const int MAX_LEN = 100;
int vv[MAX_N][MAX_LEN];
int n;
int len;
int temp;
int LexSmaller(int x, int y)
//вернуть 1, если vv[x] лексикографичекси меньше, чем vv[y], и 0 в противном случае
{
for (int i = 0; i < len; ++i)
if (vv[x][i]<vv[y][i])
return 1; //лексикографически меньше
else return 0; //если отличий не нашли, значит вектора равны или ; возвращаем 0
}
void Swap(int x, int y)
//поменять местами векторы vv[x] и vv[y]
{
//проходим по векторам и меняем попарно все элементы
for (int i = 0; i < len; ++i)
{
//меняем местами vv[x][i] и vv[y][i]
temp=vv[x][i];
vv[x][i]=vv[y][i];
vv[y][i]=temp;
}
}
void ReadVectors()
{
printf("Введите количество векторов: ");
scanf("%d", &n);
printf("Введите размерность (длину) векторов: ");
scanf("%d", &len);
for (int i = 0; i < n; ++i)
for (int j = 0; j < len; ++j)
{
printf("vv[%d][%d] = ", i, j);
scanf("%d", &vv[i][j]);
}
}
void BubbleSort()
//сортировка пузырьком
{
for (int i = 0; i < n; ++i)
for (int j = 0; j < n - 1; ++j)
if (LexSmaller(j + 1, j) == 1) //следующий вектор лекс. меньше текущего
//меняем их местами
Swap(j, j + 1);
}
void PrintResult()
{
printf("Результат сортировки:");
for (int i = 0; i < n; ++i)
for (int j = 0; j < len; ++j)
{
printf("vv[%d][%d] = ", i,j);
cout<<vv[i][j]<<"\n";
}
}
int main()
{
ReadVectors();
BubbleSort();
PrintResult();
return 0;
}
int LexSmaller(int x, int y)
//вернуть 1, если vv[x] лексикографичекси меньше, чем vv[y], и 0 в противном случае
{
for (int i = 0; i < len; ++i)
if (vv[x][i]<vv[y][i])
return 1; //лексикографически меньше
else return 0; //если отличий не нашли, значит вектора равны или ; возвращаем 0
}
int LexSmaller(int x, int y)
//вернуть 1, если vv[x] лексикографичекси меньше, чем vv[y], и 0 в противном случае
{
for (int i = 0; i < len; ++i)
if (...)
return 1; //лексикографически меньше
else if (...)
return 0; //лексикографически больше
//отличий не нашли, значит вектора равны; возвращаем 0
return 0;
}
int LexSmaller(int x, int y)
//вернуть 1, если vv[x] лексикографичекси меньше, чем vv[y], и 0 в противном случае
{
for (int i = 0; i < len; ++i)
if (vv[x][i]<vv[y][i])
return 1; //лексикографически меньше
else return 0; //если отличий не нашли, значит вектора равны или ; возвращаем 0
}
Представь себе, что векторы - это слова, а элементы в векторах - буквы в словах. Твоя задача - отсортировать слова по алфавиту.
#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <math.h>
const int MAX_N = 100;
const int MAX_LEN = 100;
int vv[MAX_N][MAX_LEN];
int n;
int len;
int temp;
int LexSmaller(int x, int y)
//вернуть 1, если vv[x] лексикографичекси меньше, чем vv[y], и 0 в противном случае
{
for (int i = 0; i < len; ++i)
{
if (vv[x][i]<vv[y][i])
return 1; //лексикографически меньше
else if (vv[x][i]>vv[y][i])
return 0; //если отличий не нашли, значит вектора равны или ; возвращаем 0
cout<<i;
}
return 0;
}
void Swap(int x, int y)
//поменять местами векторы vv[x] и vv[y]
{
//проходим по векторам и меняем попарно все элементы
for (int i = 0; i < len; ++i)
{
//меняем местами vv[x][i] и vv[y][i]
temp=vv[x][i];
vv[x][i]=vv[y][i];
vv[y][i]=temp;
}
}
void ReadVectors()
{
printf("Введите количество векторов: ");
scanf("%d", &n);
printf("Введите размерность (длину) векторов: ");
scanf("%d", &len);
for (int i = 0; i < n; ++i)
for (int j = 0; j < len; ++j)
{
printf("vv[%d][%d] = ", i, j);
scanf("%d", &vv[i][j]);
}
}
void BubbleSort()
//сортировка пузырьком
{
for (int i = 0; i < n; ++i)
for (int j = 0; j < n - 1; ++j)
if (LexSmaller(j + 1, j) == 1) //следующий вектор лекс. меньше текущего
//меняем их местами
Swap(j, j + 1);
}
void PrintResult()
{
printf("Результат сортировки:");
for (int i = 0; i < n; ++i)
for (int j = 0; j < len; ++j)
{
printf("vv[%d][%d] = ", i,j);
cout<<vv[i][j]<<"\n";
}
}
int main()
{
ReadVectors();
BubbleSort();
PrintResult();
return 0;
}
Молодец.
#include <conio.h>
#include <iostream.h>
#include <math.h>
#include <stdio.h>
const int MAX_N = 100;
const int MAX_LEN = 100;
int n,len;
int vv[MAX_N][MAX_LEN];
int sorted[MAX_N]; //сортируемый массив номеров векторов
//отсортировать группу от sorted[low_bound] до sorted[up_bound] по элементу sort_by
void SortAt(int low_bound,int up_bound,int sort_by)
{
int i,j,t;
if (sort_by==len+1) return; //сортировка по (len+1)му элементу -> процесс окончен
//сортируем пузырьком
for (i=0;i<=up_bound-low_bound+1;i++)
for (j=low_bound;j<=up_bound-1;j++)
if (vv[sorted[j]][sort_by]>vv[sorted[j+1]][sort_by])
{
//меняем вектора местами
t=sorted[j];
sorted[j]=sorted[j+1];
sorted[j+1]=t;
}
//теперь выделяем группы и рекурсивно их сортируем
i=low_bound;
while (i<=up_bound)
{
j=i;
while ((j<up_bound)&&(vv[sorted[j+1]][sort_by]==vv[sorted[j]][sort_by]))
j=j+1;
//у векторов от sorted[i] до sorted[j] совпадает элемент sort_by
SortAt(i,j,sort_by+1);
i = j + 1;
}
}
void ReadVectors()
{
printf("Введите количество векторов: ");
scanf("%d", &n);
printf("Введите размерность (длину) векторов: ");
scanf("%d", &len);
for (int i = 0; i < n; ++i)
for (int j = 0; j < len; ++j)
{
printf("vv[%d][%d] = ", i, j);
scanf("%d", &vv[i][j]);
}
}
void PrintResult()
{
printf("Результат сортировки:");
for (int i = 0; i < n; ++i)
for (int j = 0; j < len; ++j)
{
printf("vv[%d][%d] = ", i,j);
cout<<vv[i][j]<<"\n";
}
}
void main()
{
ReadVectors();
//изначальный порядок
for (int i = 0; i < n; ++i)
sorted[i] = i;
SortAt(0, n, 0);
PrintResult();
}
А помоему лучше использовать stl - это стандартная (уже) библиотека, не понимаю, зачем самому писать сортировку.
Показать как?
Сверху (перед функцией) объявляешь такой класс
struct CVectorComparator
{
CVectorComparator(int i_sort_by)
: sort_by(i_sort_by)
{
}
bool operator () (int i, int j)
{
return vv[i][sort_by] < vv[j][sort_by];
}
private:
int sort_by;
};
for (i=0;i<=up_bound-low_bound+1;i++)
for (j=low_bound;j<=up_bound-1;j++)
if (vv[sorted[j]][sort_by]>vv[sorted[j+1]][sort_by])
{
//меняем вектора местами
t=sorted[j];
sorted[j]=sorted[j+1];
sorted[j+1]=t;
}
std::sort(sorted + low_bound, sorted + up_bound + 1, CVectorComparator(sort_by));