Странная задача С. I курс.

[EniOk]

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

...
Матрица создана. Теперь ищем первый элемент, равный нулю. Это ячейка (i1,j1). Теперь для j1 ищем такой столбец k, для которого (j1,k)=0.
Ну вот так и доходим до конца, в поисках самой длинной цепочки.
Думаю, идея должна быть ясна.

Вот попробовал создать псевдокодовский вариант этого алгоритма:

Функция(Матрица, i, Массив, s, число)
   Начало
     для j от 1 до число шаг 1
         для k от 0 до число шаг 1
             если (не матрица[j][k]) то
                 начало
                     массив[s++] = k;
                     Функция (Матрица, k, Массив, s, число);
                  конец
    конец

где Матрица - собственно матрица связей, i - элемент для которого мы ищем не связанный, Массив - массив элементов, чтобы на выходе иметь готовю цепочку элементов, s - количество таких элементов и Число - число окружностей всего.
Верно?

[Sazary]

Не совсем. Там, вроде, один цикл только нужен.

Функция(Матрица, i, Массив, s, Число, Длина)
 Начало
 для j от 0 до Число
   начало 
   флаг = истина
   для l от 0 до s
     если j == Массив[l] то флаг = ложь
   если (не флаг) или (Матрица[i][j]==0) то continue
   Массив[s++] = j
   Функция(Матрица, j, Массив, s, Число, Длина + 1
   конец 
 Конец

i - номер предыдущего круга, Длина - длина текущей цепочки.
Тут, может, еще что-нибудь надо будет добавить.. Это так, навскидку.

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

[EniOk]

Итак... Я чесно отпрогал все и... ноль...

проблема: где то идет не верное обращение к массиву или что то в этом духе.

int MatrixCreator(int **s, int n, CIRCLE *circle)
{
int i2,j2;
for (i2=0;i2 for (j2=0; j2 if (test (circle[i2],circle[j2])) s[i2][j2]=1 ;
int k2;
for (i2=0;i2 for (j2=0;j2 for (k2=0;k2 if(s[k2][i2] && s [j2][k2]) s[i2][j2]=1;
return 0;
}
int Vibor(int **s, int i, int *mas, int*w, int n)
{
for (j1=0;j1 ///for(k1=0;k1 /// if(!s[j1][k1])
/// {
/// mas[*w++]=k1;
/// Vibor(s,k1,mas,w,n);
/// }
k1=1;
for(l=0;l<*w;l++)
if (j1==mas[l]) k1=0;
if ((!k1)||(s[i][j1]==0))
{ *w++;
mas[*w]=j1;
Vibor(s,j1,mas,w,n);

}
}

может кто видит проблему?

[Sazary]

for (i2=0;i2 for (j2=0; j2 if (test (circle[i2],circle[j2])) s[i2][j2]=1 ;
int k2;
for (i2=0;i2 for (j2=0;j2 for (k2=0;k2 if(s[k2][i2] && s [j2][k2]) s[i2][j2]=1;

Это что за конструкция такая? о_О

[EniOk]

Извеняюся) капирую все не думая))

int MatrixCreator(int **s, int n, CIRCLE *circle)
{
	int i2,j2;
	for (i2=0;i2<n;i2++)
		for (j2=0; j2<n; j2++)
			if (test (circle[i2],circle[j2])) s[i2][j2]=1    ;
	int k2;
	for (i2=0;i2<n;i2++)
		for (j2=0;j2<n;j2++)
			for (k2=0;k2<n;k2++)
				if(s[k2][i2] && s [j2][k2]) s[i2][j2]=1;
return 0;
}
 int Vibor(int **s, int i, int *mas, int*w, int n)
 {
	for (j1=0;j1<n;j1++)
		///for(k1=0;k1<n;k1++)
		///	if(!s[j1][k1])
		///		{
		///			mas[*w++]=k1;
		///			Vibor(s,k1,mas,w,n);
		///		}
		k1=1;
		for(l=0;l<*w;l++)
		if (j1==mas[l]) k1=0;
		if ((!k1)||(s[i][j1]==0))
		{       *w++;
			mas[*w]=j1;
			Vibor(s,j1,mas,w,n);

		}
 }

вот что должно быть)

[Sazary]

У вас в функции Vibor тело цикла цикла по j1 не заключено в скобки. Поэтому выполняться будет только

k1 = 1;

И тут еще условие выхода нужно добавить в начало функции.
И когда вызываете функцию рекурсивно, нужно (n+1) посылать.

[EniOk]

Спасибо) Да, вещь глупая, но тока проблема - кончается динамическая память при работе функции выбора. И скорее всего есть ошибка при создании матрицы связанностей... А вот как улучшить алгоритм - неясно(
Помогите плз. Очень надо...

[Sazary]

кончается динамическая память при работе функции выбора.

Тогда, наверное, нужно избавиться от рекурсии и использовать обычный цикл с отходом назад.

А в функции создания, возможно, имеет смысл заполнять не только ячейку s[i2][j2], но и s[j2][i2] (то есть обе полуматрицы).

[EniOk]

Итак. Написал не рабочую прогу.
Исходник вот:
Файл Main.cpp

/************************Preprocessor's operations***********************/
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <conio.h>
#include "d:\ddz\proc.cpp"
/*****************************Global variables***************************/
FILE *in,*out;                   //Servise variables
char inname[80], outname[80];    //Names of input & output files
int count;                       //Count of circles
int i,j,w;				 //
/******************************Main function*****************************/
int main()
{

	clrscr();
	//Ask the user about name of the input file
	printf("Enter the name of input file, please: ");
	scanf("%s", &inname);
	///////////////////////////////////////////

	//Opening input file
	if ((in = FOpen(inname,"r"))==NULL) return 1;
	////////////////////

	//Reading nomber of circles
	fscanf(in, "%d", &count);
	if (count <1)
	{
		printf("Incorrect format of input file\n");
		fclose(in);
		return 1;
	}
	///////////////////////////
	//Declaring array of CIRCLE
	CIRCLE *circle = new  CIRCLE[count];
	////////////////////////

	//Reading circles information
	printf("Information from input file:\n Count of circles: %i\n",count);
	printf("ЙННННННННННННННННННННННННННННННН»\n");
	printf("є #і    X    і    Y    і   R    є\n");
	for (i=0;i<count;i++)
	{
		fscanf(in,"%f %f %f", &circle[i].x, &circle[i].y, &circle[i].r);
		printf("є%2iі  %5.4fі  %5.4fі  %5.4fє\n",i, circle[i].x,circle[i].y,circle[i].r);
		circle[i].crossflag=0;
	}
	printf("ИНННННННННННННННННННННННННННННННј");
	/////////////////////////////
	//Now test)
	int **s = new int*[count];
	for (i=0;i<count;i++) for (j=0;j<count;j++) s[i][j]=0;
	MatrixCreator(s, count, circle);
	printf("\n");
	for (i=0;i<count;i++) {for (j=0;j<count;j++) if (i!=j)printf(" %i",s[i][j]); else printf(" °"); printf("\n");};
	///////////
	getch();
//	int *mas=new int[count];

  //	Vibor(s,0,mas,&w, count);
	printf("\n");
	getch();
    //	for (i=0;i<w;i++) printf("%i ", mas[i]);
      //	getch();
	///////////
	return 0;
}

файл Proc.cpp

//Declaring new data type
struct CIRCLE {
    float x, y, r;
    char crossflag;
};
int j1, k1,l;
/////////////////////////
//Folloving we'll have dinamic array of one
/*******************************Opening file****************************/
FILE *FOpen(char *path, char *reg)
{
	FILE *name;
	if ((name = fopen(path,reg))!=NULL) return name;
	printf("Unable to open file '%s'",path);
	return NULL;
}
/*Tests crossing of 2 circles*/
int test(CIRCLE c1,CIRCLE c2)
{
	//printf("%i %i %i %i %i %i", c1.x, c1.y, c1.r, c2.x, c2.y, c2.r);
	if ( sqrt( (fabs(c1.x-c2.x)*fabs(c1.x-c2.x))+(fabs(c1.y-c2.y)*fabs(c1.y-c2.y)))  <(c1.r+c2.r)) return 1;
	return 0;
}
/////
int test2(CIRCLE c1, CIRCLE c2)
{
	if (((sqrt( ((c1.x-c2.x)*(c1.x-c2.x))+((c1.y-c2.y)*(c1.y-c2.y)))+c1.r)<c2.r)||( (sqrt( ((c1.x-c2.x)*(c1.x-c2.x))+((c1.y-c2.y)*(c1.y-c2.y)))+c2.r)<c1.r))
	return 0;
	return 1;
}
int MatrixCreator(int **s, int n, CIRCLE *circle)
{
	int i2,j2,k2;
	for (i2=0;i2<n;i2++)
		for (j2=0; j2<n; j2++)
			if(i2!=j2)
			 if (test (circle[i2],circle[j2]))
			  if (test2(circle[i2],circle[j2])) s[i2][j2]=5    ;

	for (i2=0;i2<n;i2++)
		for (j2=0;j2<n;j2++)
			for (k2=0;k2<n;k2++)
				if (i2!=j2)
				 if(s[k2][i2] && s [j2][k2])
				  s[j2][i2]=4;
//        for (i2=1;i2<n;i2++) for (j2=1; j2<n; j2++) s[n-j2][i2]= s[i2][n-j2];
return 0;
}
 int Vibor(int **s, int i, int *mas, int*w, int n)
 {
	for (j1=0;j1<n;j1++)
		///for(k1=0;k1<n;k1++)
		///	if(!s[j1][k1])
		///		{
		///			mas[*w++]=k1;
		///			Vibor(s,k1,mas,w,n);
		///		}
		k1=1;
		for(l=0;l<*w;l++)
		if (j1==mas[l]) k1=0;
		if ((!k1)||(s[i][j1]==0))
		{       *w++;
			mas[*w]=j1;
			Vibor(s,j1,mas,w,n);

		}
 }

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

Вопрос: как бы это сделать чтобы не шло неверное обращение к этой матрице)

[Sazary]

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

Ошибка доступа возникает тут:

int **s = new int*[count];
for (i=0;i<count;i++) for (j=0;j<count;j++) s[i][j]=0;

потому что нужно выделить память под каждую строку:

int **s = new int*[count];
for(i=0; i<count; i++)
 s[i] = new int[count];
for (i=0;i<count;i++) for (j=0;j<count;j++) s[i][j]=0;

И также не забывайте освобождать память!

Добавьте где-нибудь в конце

for(i=0; i<count; i++)
 delete[] s[i];
delete[] s;