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

[patriarch]

функция как-то так будет выглядеть??...

int prov(int *M, int n, int i, int j, int temp, int ok, int sum)
{
	ok=1;
	i=0;
	do {
		temp=0;
		for(j=0; j<n; j++)
			temp+=a[i][j];
		if (temp!=sum) ok=o;
				i++;
	}
		j=0
			do{
				temp=0;
				for(i=0; i<n; i++)
					sum+=a[i][j]
				if (temp!=sum) ok=o;
				j++
			}

}

[Sazary]

функция как-то так будет выглядеть??...

О ужас! Нет!

Вот. Добавил я эту функцию. Но скажу вот что: здесь нужен абсолютно другой подход. Так делать нельзя.
Искать нужную матрицу он будет слишком долго. И скомпилировав приведенный ниже код, вы тоже врядли увидите хоть одну матрицу (я также поставил защиту от зависания).

Сумму нужно проверять не после генерирования матрицы, а на стадии ее составления.

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

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 checkSumm(int *M, int n)
{
 int i,j,SS=0,S;
 for(i=0;i<n;i++)
  {
   S = 0;
   for(j=0;j<n;j++)
    S += M[i*n+j];
  if(i==0) SS = S;
  else if(S != SS) return 0;
  }
 //--
 for(j=0;j<n;j++)
  {
   S = 0;
   for(i=0;i<n;i++)
    S += M[i*n+j];
   if(S != SS) return 0;
  }

 return 1;
}
//==================


int main()
{
const int N = 5;
const long cnt2MAX = 1000000;
int i,j,k,l,matr[N][N],mas[N],nm=0;
int b=0,cnt=0;
long cnt2=0;
srand(time(NULL));

printf("Zhdite...\n");
//------------------
do
{
//=========================
for(i=0;i<N;i++)
 {
  nm = 0;
  cnt = 0;
  for(j=0;j<N;j++)
   {
    b=0;
    while(b==0)
     {
      k = rand()%10;
      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
//---------------------------
cnt2++;
if(cnt2>=cnt2MAX) break;
} while(checkSumm(&matr[0][0],N)==0);


if(cnt2>=cnt2MAX)
 printf("Ne udalos sozdat matricu :(\n");
else
 for(i=0;i<N;i++)
 {
  for(j=0;j<N;j++)
    printf("%4d",matr[i][j]);
  printf("\n");
 }

getch();
return 0;
}

Если убрать защиту, то, возможно, через пару дней (а может и раньше! ) вы получите нужную матрицу.
Повторюсь: здесь нужен другой подход.

[Sazary]

Вот один из вариантов второй задачи: куст.
Генерируются точки, затем ищется "корень куста" и минимальная сумма.

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

// объявим структуру "точка"
struct Scoord
{
 double x;
 double y;
};
//------------------

int main()
{
const int N = 10;   // количество точек
const double LMAX=-10, RMAX=10;  // левая и правая границы для генерации координат
const double TMAX=-10, BMAX=10;  // верхняя и нижняя

Scoord mas[N];  // массив точек
int i,j,K;
double S,Smin;
srand(time(NULL));

for(i=0;i<N;i++)
 {
  //  разбрасываем точки
  mas[i].x = rand()*(RMAX-LMAX)/(double)RAND_MAX+LMAX;
  mas[i].y = rand()*(BMAX-TMAX)/(double)RAND_MAX+TMAX;
  printf("To4ka %d: %5.3lf  %5.3lf\n",i,mas[i].x,mas[i].y);
 }
printf("\n"); 
//==================

K = 0; // считаем, что вершина K - то, что нам нужно
Smin = -1;
for(i=0;i<N;i++)   // перебираем все возможные "корни куста"
 {
  S = 0; // изначально сумма равна 0
  for(j=0;j<N;j++)  // перебираем вершины куста
   {
    if(j==i) continue;  // если текущая вершина - корень, пропускаем
    S += pow( pow(mas[j].x-mas[i].x,2) + pow(mas[j].y-mas[i].y,2),0.5);    
   }
  if(Smin==-1)  // если мы еще пока ничего не запомнили...
   {
    Smin = S;  // то запоминаем эту сумму
    K = i;    // и номер вершины-корня
   }
  else
   {
    if(S<Smin)  // иначе, если текущая сумма меньше
     {
      Smin = S;  // запоминаем ее
      K = i;
     }
   } 
 }
//=======
printf("Vershina kusta: %5.3lf %5.3lf\n", mas[K].x,mas[K].y);
printf("Summa reber = %5.3lf\n", Smin);
//---------
getch();
return 0;
}

[patriarch]

честно говоря не очень понял что делает эта программа...и почему один из вариантов?

[Sazary]

честно говоря не очень понял что делает эта программа...и почему один из вариантов?

Вы еще на первой странице с Sasha_Smirnov уточняли по поводу этой задачи. Сошлись, что нужно подсчитать сумму ветвей куста, чтобы эта сумма была минимальной.

Один из вариантов как раз потому, что до конца все-таки не понятно (по крайней мере мне), что это такое (куст, дерево, или еще что-то).
Мне понравился вариант с кустом.

[patriarch]

ну просто я думал что под построить дерево имелась ввиду матрица смежности а не координаты точек.И задача для n а не для 10,наверное имееться ввиду что число n с клавиатуры вводиться

а у srand(time(NULL)); какие могут быть значения? и что означает NULL?

[Sazary]

И задача для n а не для 10,наверное имееться ввиду что число n с клавиатуры вводиться

А вы что, не можете изменить так, чтобы N вводилось с клавиатуры?

а у srand(time(NULL)); какие могут быть значения?

Это инициализация генератора.

и что означает NULL?

Это константа. Фактически, она равна 0.

ну просто я думал что под построить дерево имелась ввиду матрица смежности

А к чему тут матрица смежности? Да, можно ее сделать. Только вот не нужна она в этой задаче.
И, как это уже обсуждалось, здесь не полноценное дерево (куст).

[patriarch]

А вы что, не можете изменить так, чтобы N вводилось с клавиатуры?

Могу,конечно

Это константа. Фактически, она равна 0.

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

А к чему тут матрица смежности? Да, можно ее сделать. Только вот не нужна она в этой задаче.

Просто подумал что для большого количества точек будет не очень удобно смотреть на кучу координат.Да и одна из тех 3 задач которые я сделал была на графы и матрицу смежности.Вот я и решил что эта тоже.

[Sazary]

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

А как вы ее измените? )
Она определена в файле windef.h:

#define NULL 0

Просто подумал что для большого количества точек будет не очень удобно смотреть на кучу координат.Да и одна из тех 3 задач которые я сделал была на графы и матрицу смежности.Вот я и решил что эта тоже.

Здесь все точки в одностороннем порядке связаны с одной главной (с корнем куста). Поэтому считаю матрицу смежности избыточной. Кроме того. Здесь вершины графа (точки) имеют две координаты. А матрица смежности подошла бы, если бы они просто были пронумерованы.

[patriarch]

И мы структуры ещё не проходили...без них никак не получиться?
а что понимаеться под корнем куста?
И границы(левая,правая,верхняя и нижняя) взяты от -10 до 10 просто так?их можно изменять как захочеться?