Вектор А=(А1,А2,…,Аn) считается лексикографически большим вектора В=(В1,В2,…,Вn), если существует k>=0 такое что Аi=Вi(i<=k),Ak+1>Bk+1. Составить программу лексикографической сортировки числовых векторов. При составлении программы сортировки использовать минимальную необходимую память и эффективные структуры данных.

Давал пост в разделе задачи Лексикографическая сортировка числовых векторов., мне помогли с заданием но реализация была на паскале... вот попробовал перевести в сишку... возникли вопросы.... в сишке ни разу не пробовал процедуры... правильно ли я написал? и нет под рукой книги или хелпа, хотелось бы узнать что дает в паскале команда 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, означающий, что программа нормально завершила работу
}

Очень внимательно изучи это код на предмет оформления и вызова процедур, да и общей структуры программы.

Теперь, что касается перевода.

1. Перенеси объявление массивов vv и sorted наверх, иначе из тела функции их не будет видно

2. Строку main() убери, и объяви функцию main отдельно, как я показал в примере выше.

3. Во всех проверках "=" записывается в си как "==". Здесь:

if (sort_by=len+1) exit;  

и здесь:

vv[sorted[j+1]][sort_by]=vv[sorted[j]][sort_by]

4. exit, означающий преждевременный выход из процедуры, в си записывается как return;

5. Вот такой цикл

for i := 1 to up_bound - low_bound + 1 do

Записывается так

for (i=1;i<=up_bound-low_bound+1;i++)

У тебя все правильно, но стоит "=" вместо "<=".

6. То же самое:

for j := low_bound to up_bound - 1 do

Записывается так:

for (j=low_bound;j<=up_bound-1;j++)

Тоже было "=", надо "<=".

7. Вот здесь:

while (j < up_bound) and (vv[sorted[j + 1], sort_by] = vv[sorted[j], sort_by]) do

Ты заменил случайно j на i. Верни И не забудь про "==" вместо "="

8. Inc(j); - это просто j++.

9. Вот здесь:

i := j + 1;

Ты тоже случайно заменил j на i. Верни.


Давай, заменяй и приходи обратно. Какой у тебя си? Может си++? И ты уверен, что ты должен осилить именно "минимальную необходимую память и эффективные структуры данных"? Намучаешься немеряно, обещаю ;)

Может давай для начала напишем такую простую сортировку пузырьком? Вот тебе шаблон, попробуй дописать:

#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;
}

Не заметил в названии темы ВС++. Тогда вообще хорошо, можно std::sort юзать. Там ведь есть stl (последний раз, когда я видел BC++, я не знал, что такое stl )? Впрочем, это уже другая история. Давай пока пузырьком.

#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
}

Что произойдет, если vv[x][0] = vv[y][0]? Безо всяких сомнений функция вернет тебе 0, т.к. else относится только к результату сравнения if (vv[x][i]<vv[y][i])... Элементы равны, следовательно условие НЕ выполнилось, возвращен 0... Всё. Результат неверный... До второй итерации дело вообще не дойдет, хотя по идее если
vv[x][0] = vv[y][0], но vv[x][1] < vv[y][1] функция должна вернуть 1...

Тебе, кстати, компилятор должен давать Warning... Ты почему его игнорируешь?

Перечитал задание... i - это порядковый номер элемента, k - это элемент?
т.е. например
A) 1 2 3
B) 4 2 1

у А2 k=2, оно больше 0... и такое что A2=B2 и порядковый номер =2 (i<=k), а А3>B3... следовательно Вектор А считается лексиграфически большим вектора B.... так?

Т.е. цель задачи в том чтобы отсортировать вектор, так, чтобы он подходил к вышесказанному условию?

Представь себе, что векторы - это слова, а элементы в векторах - буквы в словах. Твоя задача - отсортировать слова по алфавиту.

все врубился...
сортировка идет по первым элементам вектора, если они равны, то по второму элементу...

Только остается вопрос:


Каким макаром добиться этого условия?

Честно говоря, я тебе уже ответил на этот вопрос в самом начале. Но давай ты все-таки сделаешь, чтоб работало, а потом уж возмешься за оптимизацию. Доделай мой шаблон, убедись, что всё "сходится", и вектора действительно сортируются, выложи результат сюда, и потом попробуй разобраться в том, что я тебе ответил в той теме. Там - и память минимальная, и время.

#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;
}

Например
9 5
1 1
2 3
9 1
6 5

результат:
1 1
2 3
6 5
9 1
9 5

Молодец.



Жду вопросов ;)

На всякий случай, на пальцах тот алгоритм. Переходим к аналогии сортировки слов. Что я делаю. Сначала сортирую слова по первой букве. Потом *отдельно* сортирую все слова, начинающиеся на А. Потом - на Б, на В и т.д. Как я *отдельно* сортирую все слова, начинающиеса на А? Я их сортирую по второй букве. Потом *отдельно* сортирую все слова, начинающиеся на АА, АБ, АВ и т.д. рекурсивно.

#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();
}

Проблема.... бесконечная процедура получается, потому что ретурн не срабатывает if (sort_by==len+1) return...когда выполняется это условие... он не может выйти с процедуры...

Может ретурн с каким-то параметром должен быть указан?

В паскале нумерация была с нуля, поэтому я написал "if sort_by = len + 1 then". В си нумерация с 0, поэтому замени на "if (sort_by==len)".

Кроме этого, посмотри на процедуру PrintResult. В ней ты выводишь вектора в том порядке, в котором они записаны в vv. А мы их в vv то не меняли местами, мы индексы перемещали в sorted[]. Поэтому теперь надо переделать PrintResult так, чтобы она выводила не сверху вниз, а по порядку, записанному в sorted. Давай.

Вроде будет работать нормально. Не забудь еще, что у нас внутри пузырек, который надо заменить быстрой сортировкой, так что возвращайся ;)

Все заработало как надо, Принтрезульт исправил. Чем заменить пузырек? Вставкой?

Лучше std::sort'ом просто. Надо объявить компаратор, и передать его третьим параметром. Сможешь?

неа ))) Первый раз слышу про компаратор )) ... да и помоему лучше не использовать STL... В задаче ничего не сказано... да и препод ничего такого не давал на лекциях...

А помоему лучше использовать stl - это стандартная (уже) библиотека, не понимаю, зачем самому писать сортировку.

Показать как?

Конечно, если не использую, так хоть буду знать как использовать 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;  
};

Это класс-компаратор. Его единственный оператор () возвращает true, когда сортируемые объекты находятся в правильном порядке (т.е. когда i меньше j в нашем понимании). В нашей ситуации сортируемые объекты - это значения массива sorted, а условие, по которому мы определяем, в правильном ли порядке расположены два таких значения, получается точно таким же, как было в пузырьке: сравнение vv[i] и vv[j] по элементу 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));

sorted - массив, и одновременно sorted - это указатель на первый элемент массива. Поэтому sorted + low_bound - указатель на начало нашего отрезка, а sorted + up_bound + 1 - на следующий за концом (правый конец в stl обычно "не включительно", поэтому добавляем единицу). Если третьим параметром ничего не передать, sort отсортирует указанный кусок массива просто по возрастанию (используя обычный оператор <). А когда мы указываем ему компаратор, он выполняет сравнения не оператором <, а оператором () этого компаратора, т.е. делает то, что нам нужно.

Проверил, вроде работает.

А если лексикографически больше или меньше?