Найти максимальную строку матрицы 4х4


Я написал рекурсивную функцию, которая я думаю, будет возвращать 'максимум' строки матрицы 4х4 его кормят. На 'максимум' я имею в виду, что максимальный строк матрицы.

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

строке 4 (на счет первого столбца значений); максимальное строке матрицы

1 2 3 4
2 3 4 1
4 4 1 2
4 1 2 3

это строки 3 (на счет значений первого и второго столбцов'); максимальная строке матрицы

1 2 3 4
2 3 4 1
4 4 1 2
4 4 2 3

это строки 4 (на счет первого, второго и третьего столбцов значений); максимальное строке матрицы

1 2 3 4
2 3 4 1
4 4 1 2
4 4 1 3

это строки 4 (на счет значений в каждом столбце); и максимальная строке матрицы

1 2 3 4
2 3 4 1
4 4 1 3
4 4 1 3

это строки 3 (на счет значений в каждом столбце - выберите самую верхнюю строку).

Эта функция гораздо больше, чем я ожидал, когда я сел писать это. Скажите, пожалуйста, есть более простой способ, чтобы выразить этот алгоритм в C!

(Функция работает в программе, написанной Pascalite; прошу простить тот факт, что массивы игнорировать свои члены 0-го!)

Вот эта функция (совместно со своим помощником метода indexOf(), который никогда не кормил массив, в котором вал не появляются!) Извиняюсь за переменная отступ - кошмар просто получать его до такого состояния!

int indexOf(int a[], int val) 
{ /* returns index at which val occurs in a[] */
    int i=1;

    while(a[i] != val)
        i++;

    return i;
}

int maxRow (int a[5][5], int index) 
{
  int store [5] = {-1, a[1][index], a[2][index], a[3][index], a[4][index] };
  int store2[5] = {-1, a[1][index], a[2][index], a[3][index], a[4][index] };

  int i, j, k, max, i1=0, i2=0, i3=0, i4=0;
  int arr[5]={-1,-1,store2[2],store2[3],store2[4]};

  if (index==5)
  {
    if(a[1][4]>=0)
        return 1;
    else if(a[2][4]>=0)
        return 2;
    else if(a[3][4]>=0)
        return 3;
    else if(a[4][4]>=0)
        return 4;               
  }

  /* order store[] from max -> min: */ 

  for(i=1; i<=3; i++)
  {  
    max=store[i]; 
    j=i;
    for(k=i+1; k<=4; k++)
        if(store[k]>max)
        {
            max=store[k];
            j=k;
        }
    store[j]=store[i]; 
    store[i]=max;
  } 

  i1 = indexOf(store2, store[1]);

  /* now we must indicate which (if any ) rows to recurse on... */

  if (store[1]==store[2])
  {         
    if(i1==1)           
        i2 = indexOf(arr,store[1]);     
    else if (i1==2)
    {
        arr[2] = -1;
        i2 = indexOf(arr, store[1]);        
    }
    else if (i1==3)
        i2 = 4;

    /* note: if i2==4 then can't have store[1] equal to any other members of store[] */

    if(store[1]==store[3])
    {
        /* i2 = 2 or 3 */

        if(store2[4] <= store2[3])          
            i3 = 3;         
        else i3=4;      

        if (store[1]==store[4])
        {
            i4=4;
        }
    }  
  }      

    if (i2==0) 
        return i1;

    else if(i3==0)
    {
          i = indexOf(store2,store[4]);

          for(j=0;j<5;j++)
            a[i][j]=-1; 

          i = indexOf(store2,store[3]);

          for(j=0;j<5;j++)
            a[i][j]=-1;         

          return maxRow(a, index+1);              
    }   
    else if (i4==0)
    {
      i = indexOf(store2,store[4]);

      for(j=0;j<5;j++)
            a[i][j]=-1; 
      return maxRow(a, index+1);
    }
    else /* all i are non-zero */
      return maxRow(a, index+1);
}


1669
5
задан 21 мая 2011 в 06:05 Источник Поделиться
Комментарии
5 ответов

Первое, что я сделаю, если я рефакторинг этого кода избавиться от рекурсии.

Вы должны быть в состоянии сделать это с переменным отслеживать "лучший номер строки до сих пор", а просто "для каждой строки" петли. Внутри цикла будет код, который сравнивает текущую строку с лучшими строки до сих пор (а не "лучшие строки до сих пор = текущая строка", если в текущей строке, тем лучше).

Пример:

int maxRow(int a[4][4]) {
int i,j;
int bestRow = 0;

for(i = 1; i < 4; i++) {
for(j = 0; j < 4; j++) {
if(a[i][j] != a[bestRow][j]) {
if(a[i][j] > a[bestRow][j]) {
bestRow = i;
}
break;
}
}
}
return bestRow;
}

6
ответ дан 21 мая 2011 в 07:05 Источник Поделиться

Один из способов сделать это, чтобы просто сравнить две строки в то время, и найти, какие строки величайших видели до сих пор:

итеративная версия:

int maxrow(int *matrix, int width, int height) {       
int maxrowindex = 0; // first, assume the first row is the maxrow
int r, c;
for (r = 0; r < height; r++) {
for (c = 0; c < width; c++) {
if (matrix[maxrowindex*width+c] != matrix[r*width+c]) {
if (matrix[maxrowindex*width+c] < matrix[r*width+c]) {
maxrowindex = r;
}
break;
}
}
}
return maxrowindex;
}

рекурсивный вариант:

int lexicographic_compare(int a[], int b[], int width) {
if (width == 1) return a[0] <= b[0];
if (a[0] == b[0]) return lexicographic_compare(a+1, b+1, width-1);
return a[0] <= b[0];
}
int maxrow(int *matrix, int width, int height) {
if (height == 1) return 0;
int a = 0;
int b = maxrow(matrix + width, width, height-1) + 1;
if (lexicographic_compare(matrix+a*width, matrix+b*width, width)) {
return b;
} else {
return a;
}
}

этот код должен работать для матрицы произвольного размера.

3
ответ дан 21 мая 2011 в 07:05 Источник Поделиться

Можно воспользуйтесь strcmp(char*, то тип char*) для сравнения двух строк. При преобразовании строки матрицы эквивалентных символов, то чего strcmp() будет делать тяжелую работу за вас.

int isFirstGreater = strcmp("1234", "1232");

Это вернет 1 сказать, что первая строка больше. В вашем контексте:

for(int i=0; i < MatrixSize; i++)
{
charArray[i] = (char*) matrixRow[i];
}
charArray[MatrixSize] = 0; // You need to add a zero to make it a string.
strcmp(charArray, anotherCharArray);

Однако, это кажется немного сырой взломать.

Может быть, это лучше:

int number = 0;
for(int i=0; i< matrixSize; i++)
{
number += matrixRow[i] * pow(10, (matrixSize-i)-1);
}

Это просто преобразует строку матрицы на число, вы можете просто использовать >, < чтобы увидеть, какой из них больше, что эквивалентно своей первоначальной цели.

1
ответ дан 21 мая 2011 в 07:05 Источник Поделиться

Нерекурсивное решение может выглядеть так (к сожалению, нет кода C, но алгоритм, а не описание):


  • Держать типа bool массив row_ruled_out[4] с одной позиции в строке. Этот массив будет использоваться, чтобы отслеживать, какие строки уже "исключили". Изначально, все строки будут по-прежнему считать "в".

  • Для каждого столбца матрицы, выполните следующие действия:


    1. Найти максимальное число М , для которого в столбце. Например, в следующий столбец матрицы:

        . a . .
      . b . .
      . c . .
      . d . .

      м = Макс(а, б, с, д).


    2. Для каждой строки, которая еще не исключена (согласно row_ruled_out), если ее значение в этой колонке меньше, чем м, она не может быть самой широкой строке. Поэтому пометить эту строку как "исключать" в row_ruled_out массива. Это не будет рассматриваться дальше.


  • После того как вы сделали выше для каждого столбца, посмотри на row_ruled_out. Все строки, которые остались, т. е.. не исключено, должна быть наибольшей строк. Это может быть ноль, один или несколько рядов, в зависимости от вашего вклада.

0
ответ дан 21 мая 2011 в 07:05 Источник Поделиться

с тесты.... просто сравнивая каждую строку....

#include "seatest.h"

int m1[4][4] = {
{1,2,3,4},
{2,3,4,1},
{3,4,1,2},
{4,1,2,3}};

int m2[4][4] = {
{1,2,3,4},
{2,3,4,1},
{4,4,1,2},
{4,1,2,3}};

int m3[4][4] = {
{1,2,3,4},
{2,3,4,1},
{4,4,1,2},
{4,4,2,3}};

int m4[4][4] = {
{1,2,3,4},
{2,3,4,1},
{4,4,1,2},
{4,1,1,3}};

int m5[4][4] = {
{1,2,3,4},
{2,3,4,1},
{4,4,1,3},
{4,1,1,3}};

int compare(int* d1, int* d2, int l)
{
int i;
for(i=0; i<l; i++)
{
if(d1[i] > d2[i]) return 1;
if(d1[i] < d2[i]) return -1;
}
return 0;
}

int matrix_max_row_r(int* m, int w, int h)
{
int i;
int max = 0;
for(i=1; i<h; i++) max = compare(m+(w*i), m+(w*(i-1)), w) > 0 ? i : max;
return max;
}

int matrix_max_row(int* m)
{
return matrix_max_row_r(m, 4,4);
}

void test_max_matrix_row()
{
assert_int_equal(3, matrix_max_row((int*)m1));
assert_int_equal(2, matrix_max_row((int*)m2));
assert_int_equal(3, matrix_max_row((int*)m3));
assert_int_equal(2, matrix_max_row((int*)m4));
assert_int_equal(2, matrix_max_row((int*)m5));
}

void test_fixture_matrix( void )
{
test_fixture_start();
run_test(test_max_matrix_row);
test_fixture_end();
}

void all_tests( void )
{
test_fixture_matrix();
}

int main( int argc, char** argv )
{
run_tests(all_tests);
return 0;
}

0
ответ дан 23 мая 2011 в 05:05 Источник Поделиться