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

[patriarch]

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

[Sazary]

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

Нужно построить именно дерево,а то что я пытался сдать это простейший случай дерева.

Ну в таком случае слова Sasha_Smirnov нисколько не противоречивы.

Вы же еще 7-го числа писали:

поговорил с преподователем.Он сказал что правильно,но сделать не структурой а массивами.

[patriarch]

Да я знаю наверное мы не так друг друга поняли.Ваша программа из одной вершины проводит в оставшиеся отрезки и ищет минимальный.а насколько я понял нужна та которая берет одну вершину из нее отрезок в другую(потом проверяет то же и для вершины в которую толmrj что провели отрезок)Нужна метка которая будет отмечать уже пройденные и проверенные вершины.

[Sazary]

Вот обрывки из кода программы Lomanaya, которую я в этой теме выкладывал.
Начало работы:

for(i=0; i<N; i++)
 {
  tekPath[0] = i;
  ProgressBar1->Position++;
  getMinPath(tekPath, 1, 0);
 }

----------
Функция:

void TForm1::getMinPath(int *tekPath, int tek, double tekS)
{

if(tek==N)
 {
  if(tekS<Smin || Smin==0)
   {
    Smin = tekS;
    for(int j=0; j<N; j++)
     minPath[j] = tekPath[j];
   }
  return;
 }

 bool b;
 for(int i=0; i<N; i++)
 {
  b = false;
  for(int j=0; j<tek; j++)
   if(tekPath[j]==i) b=true;
  if(b) continue;
 //ProgressBar1->Position++;

 tekPath[tek] = i;

 getMinPath(tekPath, tek+1, tekS+matr[tekPath[tek-1]][i]);

 }

}

Массивы объявлены как

int N;

double Smin;
int *minPath;

И выделяются динамически.

Писал на Билдере. Разброс точек можно использовать из "Куста".
Собственно, если захотите, то разберетесь.
Если нужно, могу выложить весь проект, но там много ненужного, неиспользуемого. Можете запутаться, что надо, а что нет.

Минимальная сумма пишется в Smin, а путь - в minPath.
Разбирайтесь.

[patriarch]

я не очень понимаю,а в чем принципиальное отличие от того что было?тут она тоже вроде бы не реккурсивная.
и что за ProgressBar1->Position++;?

[Sazary]

и что за ProgressBar1->Position++;?

Это вам не нужно. Это для Билдера.

я не очень понимаю,а в чем принципиальное отличие от того что было?

Тогда я вам ничем помочь не смогу.

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

Вроде бы? Вообще-то, и этот и предыдущий вариант оба рекурсивные.

А самый лучший способ понять - решить самостоятельно.

[patriarch]

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

Это вам не нужно. Это для Билдера.
А самый лучший способ понять - решить самостоятельно.

А можете описать алгоритм искомого решения и того что вы выложили сейчас.

[Sazary]

Описываю функцию:

// функция принимает указатель на массив-текущий-путь 
//(формируется при рекуррентном вызове функции), номер текущей вершины и текущую сумму.
void TForm1::getMinPath(int *tekPath, int tek, double tekS)
{

if(tek==N)  // если перебрали все вершины, то...
 {
  if(tekS<Smin || Smin==0)  // если текущая сумма меньше минимальной (которую запомнили)
// или если еще ничего не успели запомнить...
   {
    Smin = tekS;  // запоминаем сумму
    for(int j=0; j<N; j++)  // и копируем в минимальный путь текущий
     minPath[j] = tekPath[j];
   }
  return;  // и выходим
 }
 
 bool b;
 for(int i=0; i<N; i++)  // перебираем имеющиеся вершины
 {
  b = false;  // флаг
  for(int j=0; j<tek; j++)  // перебираем вершины, которые уже участвуют в формировании текущего пути
   if(tekPath[j]==i) b=true; // если такая вершина уже использовалась, то ставим флаг в false
  // после цикла...
  if(b) continue; // если флаг установлен, значит пропускаем эту вершину
 //ProgressBar1->Position++;  -  а это просто удалите

 tekPath[tek] = i;  // после проверки вершины добавляем ее к текущему пути
 // и вызываем себя. Передаем текущий путь, номер (порядковый) следующей вершины
 // и сумму (добавив сумму текущего ребра)
 getMinPath(tekPath, tek+1, tekS+matr[tekPath[tek-1]][i]);

 }

}

Да, там еще будет матрица смежности, заполненная длинами ребер.
Объявление:

double **matr;

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

void fillMatr(double **matr)
{
 int i,j;
 double dlina;
 for(i=0;i<N;i++)
  for(j=0;j<N;j++)
   if(j==i) continue;
   else
    {
     dlina = sqrt(pow(mas[i].x-mas[j].x,2)+pow(mas[i].y-mas[j].y,2));
     if(dlina<matr[i][j] || matr[i][j]==0)
      matr[i][j] = dlina;
    }

}

[Sazary]

Вот вам про дерево на Си под консоль.
Решали бы сами, тогда б и не горело ничего. Да и с пониманием проблем бы не было.

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

// структура "точка"
struct Scoord
{
 double x;
 double y;
};

const int LMAX=0, RMAX=30, TMAX=24, BMAX=0;

int N;


double Smin;  // сюда запишем минимальную сумму
int *minPath;  // здесь будет минимальный путь
double **matr;  // матрица, где будем хранить длины ребер
Scoord *mas;  // массив точек

// рекурсивная функция для поиска пути.
// принимает указатель на текущий путь (который формируется с каждым вызовом)
// порядковый номер текущей вершины и текущую сумму ребер
void getMinPath(int *tekPath, int tek, double tekS)
{

if(tek==N)  // если перебрали все вершины
 {
  if(tekS<Smin || Smin==0)  // и если текущая сумма меньше той, которую запомнили
   {
    Smin = tekS;  // запоминаем
    for(int j=0; j<N; j++)
     minPath[j] = tekPath[j];  // и запоминаем путь
   }
  return;
 }
 // иначе...
 bool b;
 for(int i=0; i<N; i++)  // перебираем все вершины
 {
  b = false;  
  for(int j=0; j<tek; j++)  // смотрим, нет ли текущей вершины в уже сформировавшемся пути
   if(tekPath[j]==i) b=true;  // если есть, ставим флаг
  if(b) continue;  // если флаг установлен, пропускаем вершину и берем следующую

 tekPath[tek] = i;  // добавляем вершину к пути

 getMinPath(tekPath, tek+1, tekS+matr[tekPath[tek-1]][i]);  // и ищем следующую вершину

 }

}
//-----------

// функция для заполнения матрицы
// принимает указатель на матрицу
void fillMatr(double **matr)
{
 int i,j;
 double dlina;
 for(i=0;i<N;i++)
  for(j=0;j<N;j++)
   if(j==i) continue; 
   else
    {  // для двух разных вершин считаем длину ребра
     dlina = sqrt(pow(mas[i].x-mas[j].x,2)+pow(mas[i].y-mas[j].y,2));
     if(dlina<matr[i][j] || matr[i][j]==0)
      matr[i][j] = dlina;
    }
}
//----------------------


int main()
{
int i,j;
int *tekPath;

srand(time(NULL));
printf("Vvedite kolichestvo vershyn: ");
scanf("%d",&N);

// выделяем память под массив вершин
mas = new Scoord[N];
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");
//==================
// выделяем память под матрицу
matr = new double*[N];
for(i=0;i<N;i++)
 matr[i] = new double[N];


// память под минимальный и текущий пути
tekPath = new int[N];
minPath = new int[N];

Smin = 0;
for(i=0; i<N;i++)
 for(j=0;j<N;j++)
  matr[i][j] = 0;
fillMatr(matr);  // заполняем матрицу

// ищем минимальный путь
for(i=0; i<N; i++)  // в цикле перебираем стартовые вершины
 {
  tekPath[0] = i;
  getMinPath(tekPath, 1, 0);
 }

printf("\n Minimalnaya summa = %5.3lf\n\n",Smin);

printf("derevo:\n");
printf("%d",minPath[0]);
for(i=1;i<N;i++)
 printf(" -> %d",minPath[i]);
printf("\n");


for(i=0;i<N;i++)
 delete[] matr[i];
delete[] matr;
delete mas;

delete[] minPath;
delete[] tekPath;

getch();
return 0;
}

[patriarch]

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

Struct T{
int val;
struct T*left;
struct T*right;
}
int schet(strcut T*p, int k){
if(k==0) return 0;
}

2)Дана литерная матрица 40 на 56 нужно посчитать количество столбцов которые содержат не более двух фисмовлов цифр и все маленькие буквы упорядочены по возрастанияю своих кодов в ASCII таблице

char A[40][56]
int stol(){
for (int j=0;j!=56;J++) { int K=0 for(int i=0;i!=56;i++)
if(A[i][j]>="0" && A[i][j]<="9" ) k++;{
f(A[i][j]>="a" && A[i][j]<="z" )