матрицы и деревья(чистый С)

[Sazary]

Извините за наглость,а со второй никто не поможет?

Ну лично я с деревьями еще не работал и их не изучал.
Вопрос в тему: а вы сами-то что-нибудь делать будете?

[patriarch]

Сообщение от Sazary

Ну лично я с деревьями еще не работал и их не изучал.
Вопрос в тему: а вы сами-то что-нибудь делать будете?

да буду,нам задали 5 лаб.3 я вроде написал...сейчас пытаюсь разобраться с вашим кодом на 1 задачу(если не очень сложно то можно какие-нибудь комментарии к коду или алгоритм расписать?).Насчет деревьев мы их сами ещё не прошли,преподователь сказал что будут недели через 2.

[Sazary]

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

// функция проверяет, не встречается ли число (аргумент value)
// ранее в своей строке или столбце
// если нет, возвращает 1, иначе - 0
int check(int *M, int n, int numi, int numj, int value)
{
int i;
for(i=numi-1;i>=0;i--)  // идем по строке
 if(M[i*n + numj]==value)
  return 0;
for(i=numj-1;i>=0;i--)  // идем по столбцу
 if(M[numi*n + i]==value)
  return 0;
return 1;
}
//------------


int main()
{
const int N = 5;  // размерность матрицы
int i,j,k,l,matr[N][N],mas[N],nm=0;
int b=0,cnt=0;
srand(time(NULL));

//=========================
for(i=0;i<N;i++)   // идем по строкам
 {
  nm = 0;  
  cnt = 0;   // этот счетчик нужен для защиты от зависания
  for(j=0;j<N;j++)    // идем по столбцу
   {
    b=0;    // считаем, что число не подходит
    while(b==0)  // пока не нашли подходящее число
     {
      k = rand()%N+1;  // генерируем число
      b = 1;            // считаем, что оно нам подходит
      for(l=0;l<nm;l++)  // проходим по массиву чисел, которые уже проверили
       if(k==mas[l])   // если текущее число там есть
        b = 0;   // значит оно нам не подходит

     } // while
   
    if(check(&matr[0][0],N,i,j,k)==1)  // проверяем, подходит ли число
     {
      matr[i][j] = k;   // если да, то пишем его в матрицу
      mas[nm++] = k;   // и заносим в массив просмотренных чисел
     }
    else j--;    // иначе ищем число заново для данной ячейки
    cnt++;    
    if(cnt>=100)  // если зависли...
     {
      i--;   // то переделаем предыдущую строку
      break;
     }
   } // for j


 } //for i
//---------------------------

for(i=0;i<N;i++)
 {
  for(j=0;j<N;j++)
    printf("%4d",matr[i][j]);
  printf("\n");
 }

getch();
return 0;
}

Насчет деревьев мы их сами ещё не прошли,преподователь сказал что будут недели через 2.

Так а зачем тогда задачу выкладывать, если вы их еще даже не проходили?

[patriarch]

а что за защита от зависаний?? и зачем переменные nm и mas[N]?
Задачу дал чтобы вдруг если бы не понял то обьяснили бы...просто надо 5 лаб сдать на зачет.

[Sazary]

а что за защита от зависаний??

Ну я несколько раз позапускал, и там изредка программа вешалась. Это происходило из-за того, что она попадала в тупик и не могла найти подходящей комбинации чисел для строки.
Вот и добавил защиту - если программа виснет, то переделываем предыдущую строку.

и зачем переменные nm и mas[N]?

У нас берутся числа от 1 до 5. К примеру, для какой-то ячейки мы сгенерировали число. Но оно не подошло (не прошло check). Тогда нужно брать другое число. Но числа у нас берутся не по порядку, поэтому нужно держать массив чисел, которые не прошли проверку.
Вот mas и есть этот массив. А nm - его размер.

[patriarch]

а почему от 1 до 5? насколько я знаю цифры это от нуля до 9.
а программа зависает когда cnt принимает очень большие значения(больше или равные 100)?

[Sazary]

а почему от 1 до 5? насколько я знаю цифры это от нуля до 9.

от 1 до 5 потому что размер матрицы - 5.
Если сделать размер 6, то будут от 1 до 6.
В условии же сказано, чтобы суммы по столбцам и строкам были одинаковы. А самый удобный способ это реализовать - использовать один набор чисел для каждой строки и столбца.

а программа зависает когда cnt принимает очень большие значения(больше или равные 100)?

Изначально cnt вообще не было. Почему зависала я объяснил в предыдущем посте.
Ввел cnt. После каждого заполнения (скажем, попытки заполнения) конкретной строки, он увеличивается. Если он дошел до 100, то можно с уверенностью сказать, что программа висит, т.е. не может подобрать нужную комбинацию.

[Sasha_Smirnov]

Извините, если не в тему, но «работа с деревьями» — это тот же самый перебор координат (его узлов).

Поэтому задача 2 сводится к ПОДСЧЁТУ сумм расстояний (по теореме Пифагора), а не к рисованию ломаных линий и «кустов».

[Sazary]

Sasha_Smirnov, ну да. Собственно, как вы и говорили раньше, это больше напоминает граф. Только вот с графами я тоже пока не очень лажу )
Если бы тут точки могли бы соединяться только последовательно, то было бы легче.. Но из одной точки ведь может быть проведено несколько линий..
Вроде, есть какие-то стандартные алгоритмы для подобных задач.

[patriarch]

Сообщение от Sazary

от 1 до 5 потому что размер матрицы - 5.
Если сделать размер 6, то будут от 1 до 6.
В условии же сказано, чтобы суммы по столбцам и строкам были одинаковы. А самый удобный способ это реализовать - использовать один набор чисел для каждой строки и столбца.

То есть я правильно понимаю что для каждой строки и столбца используеться набор от 1 до 5?Просто сколько не запускал программу не видел в ней цифр больше 5.А разве с 6,7,8,9 подобную матрицу построить нельзя?