Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > C/C++ программирование > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 12.05.2009, 18:22   #1
Petruha-nsk
Пользователь
 
Аватар для Petruha-nsk
 
Регистрация: 10.04.2009
Сообщений: 69
По умолчанию

Я написал программу,точнее жалкую на нее породию, но что-то лучшее моего ума не хватило мне нужна программа для нахождения длины кратчайшего цикла в графе.

Код:
#include<stdio.h>
#include<conio.h>
#define n 10

struct s_do{int top; int data[n];};
struct s_ddp{int dop; int dline[1];};


int vstek_s_ddp(s_ddp *a,int t)
{
   if (a->dop < 1)
  {
	a->dop++;
	a->data[a->dop]= t;

	if(a->data[a->top] < a->data[a->top--])
	{
		a->data[a->top--] = a->data[a->top];
	}

	a->dop--;
    return 1;
  }
 else return 0;
}

int vsteck_s_do(s_do &a, int t)
{
   if (s->top < n)
  {
   a->top++;
   a->data[a->top]=t;
   return 1;
  }
 else return 0;
}

void poisk_cycle(int last[], int t, s_ddp *b)
{
	int i,g,dline;

	g=last[t];
	for(i=t-2;t>-1&&g==last[i];i--)
		last[i];

	if(last[i]==g)
	{
		dline = (t-i)+1;
		vstek_s_ddp(b,dline);
	}
}

int proverit_na-nalichie_v_last(int t, int last[])
{
	for(int i=size; i>-1 && t==last[i]; i--)
		last[i];

	if(i != -1) return 1;
		else return 0;
}

void obhod_grapha(int graph[][], int size)
{
 s_do A;
 s_ddp B;
 int i,j,t,last[size];

 	A.dop=-1;
	B.top=-1;

 j=0;
 while(j < size)
 {
	 t=0; last[t]=graph[0][j];
	 while(t < size)
	 {
		if (t>1)poisk_cycle(last,t);

		k=1;
		while(k < size-1)
		{
			if(graph[k][j])
			{
				if(proverit_na-nalichie_v_last(graph[k][j], last)==0)
				{
					k++;
				}
					else vsteck_s_do(&A, graph[k+1][j]);
			}
				else
				{
					if(j < size)j++;
						else 
						{
							if() izsteck(&A);
								else vyvod();
						}
				}
		}
		t++;
	 }
 }
}

void main()
{
 clrscr();
 int i,j,t,k,size,graph[128][128];

	FILE *in, *out;
	in = fopen ("d:\input.txt", "r");
	out = fopen ("d:\output", "w");
	
	if(in==NULL)
	{							
		printf("\n Error! File ne byl nayden!");
		fprintf(out," Error! File ne byl nayden!");
	}	
	
	fscanf(in, "%d", &size);
	for(i=0;i<size;i++)
		for(j=0;j<size;j++)
			graph[i][j]=0;

	 
	while(!feof(in))
	{
		j=0;
		while (j < size)
		{
			i=0;
			fscanf(in, "%d", &graph[i][j]);
			fscanf(in, "%d", &t);

			i=1;
			while ((i < t+1)&&(i < size))
			{
				fscanf(in, "%d", &graph[i][j]);
				i++;
			}
			j++;
		}
	}

	obhod_grapha(graph, size);


 getch();
}
кому не сложно, помогите довести программу до законченного работающе продукта. заранее спасибо!

по большому счёту это наброски программы...

Последний раз редактировалось MaTBeu; 12.05.2009 в 20:18.
Petruha-nsk вне форума Ответить с цитированием
Старый 13.05.2009, 02:08   #2
Nomlpppp
Пользователь
 
Регистрация: 26.02.2009
Сообщений: 51
По умолчанию

Что значит "кратчайшего цикла в графе"? Может кратчайшего пути в графе?
Можно решить используя алгоритм Дейкстры, "нахождение наименьшего расстояяния от заданной точки до всех остальных".

Т.о кратчайшее расстояние от вершины а до а наверно и будет кратчайшим циклом..

Последний раз редактировалось Nomlpppp; 13.05.2009 в 02:54.
Nomlpppp вне форума Ответить с цитированием
Старый 13.05.2009, 10:55   #3
vvviperrr
Тупой студент
Форумчанин
 
Аватар для vvviperrr
 
Регистрация: 12.05.2007
Сообщений: 614
По умолчанию

2Nomlpppp кратчайший цикл это кратчайший цикл, т.е найти все циклы в графе и выбрать из них самый короткий, что непонятного?

2Petruha-nsk извини, код твой не смотрел, но я как то делал похожую задачу, циклы искал обходом графа в глубину. вечером посмотрю, остались ли сырцы
vvviperrr вне форума Ответить с цитированием
Старый 13.05.2009, 12:17   #4
sneakerfile332
Заблокирован
 
Регистрация: 23.04.2009
Сообщений: 7
Подмигивание Wholesale Brand Sunglass

We offer you Brand Sunglass related with products,the Wholesale Brand Sunglass picture-related products,poor prices and other information,wholesale or retail,and the Brand Sunglass related products introduced, related products, please contact with sneaker-file@hotmail.com
sneakerfile332 вне форума Ответить с цитированием
Старый 13.05.2009, 17:08   #5
Petruha-nsk
Пользователь
 
Аватар для Petruha-nsk
 
Регистрация: 10.04.2009
Сообщений: 69
По умолчанию

Мне бы и они помогли! если не затруднит можно небольшие комментарии в вашей работе...
Petruha-nsk вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Поиск Эйлерова цикла в графе Danion Помощь студентам 3 22.05.2010 18:47
Поиск кратчайшего пути в графе методом полного перебора в глубину. Метод ветвей и границ Олинька Помощь студентам 1 24.12.2008 16:22
1) Поиск кратчайшего пути в графе методом полного перебора в ширину(очередь) Serega123 Помощь студентам 3 30.10.2008 22:26
применить Алгоритм Дейкстры для поиска кратчайшего пути в графе Эдгар Microsoft Office Excel 13 24.10.2008 21:01