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

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

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

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

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

Ответ
 
Опции темы Поиск в этой теме
Старый 17.04.2015, 17:30   #11
vet9690
Пользователь
 
Регистрация: 15.04.2015
Сообщений: 12
По умолчанию

От модератора: для оформления кода программы используйте тэг code (это кнопка с изображением решётки: #)

ВОт еще наработки по второй задачи, только здесь нельзя копировать строки( strcpy ), а нужно перетаскивать по символам, кто знает исправьте.

Код:
#include "StdAfx.h"

#include "iostream"

using namespace std;

char *text;
char *time;
char *print;
char word[80];
char last[80];
int words, chars1, charsintxt;
bool skip = 0;

void main()
{
	words = 0;
	chars1 = 0;
	charsintxt = 0;
	text = time = print = NULL;
	do
	{
		for(int i = 0; i<80; i++)
		{
			word[i] = 0;
		}
		do
		{
			cin.get(word[chars1]);
			chars1++;
			if(word[chars1-1] == ' ')
			{
				if(chars1 == 1)
				{
					skip = 1;
				}
				break;
			}
			if(word[chars1-1] == '.')
			{
				if(chars1 != 1)
					for(int i = 0; i<=chars1-2; i++)
					{
						last[i] = word[i];
					}
				break;
			}

		}while(1);

		if(!skip)
		{
			words++;
			if(text != NULL)
			{
				time = (char*)calloc(charsintxt, sizeof(char));
				strcpy(time, text);
				text = NULL;
			}
			charsintxt += chars1;
			text = (char*)calloc(charsintxt, sizeof(char));
			if(time != NULL)
			{
				strcpy(text, time);
				time = NULL;
			}
			strcpy(text+(charsintxt-chars1), word);
			
			if(word[chars1-1] == '.')
					break;
		}

		skip = 0;
		chars1 = 0;

	}while(1);

	skip = 0;
	chars1 = 0;
	charsintxt = 0;
	int count = words;

	do
	{
		for(int k = 0; k<80; k++)
		{
			word[k] = 0;
		}
		do
		{
			word[chars1] = text[chars1+charsintxt];

			chars1++;

			if(text[chars1+charsintxt] == ' ')
				break;

			if(text[chars1+charsintxt] == '.')
				break;

		}while(1);


		if(strcmp(word, last) == 0)
			continue;

		for(int j = 0; j < chars1; j++)
		{
			if(word[j] != word[chars1-j])
			{
				skip = 1;
				break;
			}
		}
		charsintxt += chars1+1;
		if(!skip)
		{
			if(print != NULL)
			{
				print = (char*)calloc(charsintxt, sizeof(char));
				strcpy(time, print);
				print = NULL;
			}
			print = (char*)calloc(charsintxt, sizeof(char));
			if(time != NULL)
			{
				strcpy(print, time);
				time = NULL;
			}
			strcpy(print+(charsintxt-chars1), word);
		}

		skip = 0;
		chars1 = 0;
		count--;
	}while(1);

	cout << print << endl;
	system("Pause");
}
От модератора: для оформления кода программы используйте тэг code (это кнопка с изображением решётки: #)

Последний раз редактировалось Вадим Мошев; 17.04.2015 в 17:32.
vet9690 вне форума Ответить с цитированием
Старый 17.04.2015, 17:36   #12
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 472
По умолчанию

Цитата:
3) В графе найти максимальное расстояние между всеми парами его вершин.
Цитата:
Проблема в том, у нас есть длины , по которым и нужно искать, а не по количестве вершин.
Я не слепой. Просмотрел твой код и не увидел там матрицы весов, только матрицу смежности (0 - ребра нет, 1 - ребро есть). Значит расстояния (веса) игнорируются. Кроме того, читаем определение расстояния в Wikipedia.
Подытоживая, Флойд-Уоршелл, матрица расстояний, диаметр, ответ.
FPaul вне форума Ответить с цитированием
Старый 17.04.2015, 18:05   #13
vet9690
Пользователь
 
Регистрация: 15.04.2015
Сообщений: 12
По умолчанию

Цитата:
Сообщение от FPaul Посмотреть сообщение
Я не слепой. Просмотрел твой код и не увидел там матрицы весов, только матрицу смежности (0 - ребра нет, 1 - ребро есть). Значит расстояния (веса) игнорируются. Кроме того, читаем определение расстояния в Wikipedia.
Подытоживая, Флойд-Уоршелл, матрица расстояний, диаметр, ответ.
Нашел вот что, а как максимальную длину то?

Код:
#include "stdafx.h"
#include <iostream>
using namespace std;
const int maxV=1000;
int i, j, n;
int GR[maxV][maxV];
//алгоритм Флойда-Уоршелла
void FU(int D[][maxV], int V)
{
int k;
for (i=0; i<V; i++) D[i][i]=0;

for (k=0; k<V; k++)
for (i=0; i<V; i++)
for (j=0; j<V; j++)
if (D[i][k] && D[k][j] && i!=j)
if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)
D[i][j]=D[i][k]+D[k][j];

for (i=0; i<V; i++)
{
for (j=0; j<V; j++) cout<<D[i][j]<<"\t";
cout<<endl;
}
}
//главная функция
void main()
{
setlocale(LC_ALL, "Rus");
cout<<"Количество вершин в графе > "; cin>>n;
cout<<"Введите матрицу весов ребер:\n";
for (i=0; i<n; i++)
for (j=0; j<n; j++)
{
cout<<"GR["<<i+1<<"]["<<j+1<<"] > ";
cin>>GR[i][j];
}
cout<<"Матрица кратчайших путей:"<<endl;
FU(GR, n);
system("pause>>void");
}
Код нужно оформлять правильно

Последний раз редактировалось Аватар; 17.04.2015 в 18:07.
vet9690 вне форума Ответить с цитированием
Старый 17.04.2015, 18:13   #14
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 472
По умолчанию

А я в первом посте давал ссылки на теорию. Кроме того, в твоём последнем посте приведена реализация алгоритма - ты же знаешь, что он делает и какой результат на выходе.
Соотнеси эти знания с определением диаметра.
--------------------------
Кроме того, проверь работоспособность твоей реализации алгоритма Флойда-Уоршелла. Я в январе-феврале 2015 помогал с этим алгоритмом на форуме и сделал вывод для себя, что если между вершинами пути нет, то нужно записывать специальное число INFINITY, а не 0, как в матрице смежности.

Последний раз редактировалось FPaul; 17.04.2015 в 18:31.
FPaul вне форума Ответить с цитированием
Старый 17.04.2015, 18:33   #15
vet9690
Пользователь
 
Регистрация: 15.04.2015
Сообщений: 12
По умолчанию

Цитата:
Сообщение от FPaul Посмотреть сообщение
А я в первом посте давал ссылки на теорию. Кроме того, в твоём последнем посте приведена реализация алгоритма - ты же знаешь, что он делает и какой результат на выходе.
Соотнеси эти знания с определением диаметра.
Так должно быть?

Код:
#include "stdafx.h"
#include <iostream>
using namespace std;
const int maxV=1000;
int i, j, n;
int GR[maxV][maxV];
//алгоритм Флойда-Уоршелла
void FU(int D[][maxV], int V)
{
int k;
for (i=0; i<V; i++) D[i][i]=0;

for (k=0; k<V; k++)
for (i=0; i<V; i++)
for (j=0; j<V; j++)
if (D[i][k] && D[k][j] && i!=j)
if (D[i][k]+D[k][j]<D[i][j] || D[i][j]==0)
D[i][j]=D[i][k]+D[k][j];

for (i=0; i<V; i++)
{
for (j=0; j<V; j++) cout<<D[i][j]<<"\t";
cout<<endl;
}
}
int Diam()
{
    int **edge = new int *[n];
    for (int i = 0; i < n; i++)
        edge[i] = new int [n];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++) {
            edge[i][j] = a[i][j];
            if (!edge[i][j]) 
                edge[i][j] = 10000;
        }
    }
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (i != j)
                    edge[i][j] = MIN(edge[i][j], edge[i][k]+edge[k][j]);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (edge[i][j] == 10000) 
                edge[i][j] = 0;
        }
    }
    int max = edge[0][1];
    for(int i = 0; i < n; i++)
    {
        for (int j = i+1; j < n; j++) {
            if(edge[i][j] > max)
                max = edge[i][j];
        }
    }
    return max;
    delete [] edge;
}
vet9690 вне форума Ответить с цитированием
Старый 17.04.2015, 18:37   #16
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
Кроме того, проверь работоспособность твоей реализации алгоритма Флойда-Уоршелла
Тут два варианта. Ищем именно диаметр (тогда решение есть при любом графе) (и Уоршелл нам не нужен). Или ищем максимальное расстояние между двумя вершинами, понимая под ним, не max(v[i][j]), где i - вершина, для которой ищется расстояние, j - все возможные вершины. (и уже используем его)
Poma][a вне форума Ответить с цитированием
Старый 17.04.2015, 18:47   #17
FPaul
Форумчанин
 
Регистрация: 25.01.2015
Сообщений: 472
По умолчанию

vet9690
Я так понимаю, что ты не даёшь яндексу отдохнуть.
Жаль, что ты так и не узнал об алгоритме Флойда, ну да ладно.
Язык С (С++) для меня неродной - говорю на нём с акцентом. Но даже так вижу, что int Diam() - и есть то, что я описывал (Флойд-Уоршелл, матрица расстояний, диаметр).
Раз ты не хочешь думать, то мне уже не интересно. Но задача №3 уже решена.

Poma][a
Нет. Согласно определению расстояния - это количество рёбер на кратчайшем пути между вершинами. Значит для определения диаметра, нужны все расстояния между всеми вершинами. А это Флойд.

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

Последний раз редактировалось FPaul; 17.04.2015 в 18:57.
FPaul вне форума Ответить с цитированием
Старый 17.04.2015, 18:52   #18
vet9690
Пользователь
 
Регистрация: 15.04.2015
Сообщений: 12
По умолчанию

Цитата:
Сообщение от FPaul Посмотреть сообщение
vet9690
Я так понимаю, что ты не даёшь яндексу отдохнуть.
Жаль, что ты так и не узнал об алгоритме Флойда, ну да ладно.
Язык С (С++) для меня неродной - говорю на нём с акцентом. Но даже так вижу, что int Diam() - и есть то, что я описывал (Флойд-Уоршелл, матрица расстояний, диаметр).
Раз ты не хочешь думать, то мне уже не интересно. Но задача №3 уже решена.
Отдохнуть не даю, потому что нету у меня этой базы знаний, я не представляю себе это на С++, я не всегда понимаю где и какой цикл нужен( куда его вставить) что уж там говорить про другие задания.Но очень хочу все это знать. Как раз читаю об алгоритме, мне все очень интересно так как это все новое для меня.
vet9690 вне форума Ответить с цитированием
Старый 17.04.2015, 18:53   #19
Poma][a
Новичок
Джуниор
 
Регистрация: 11.10.2011
Сообщений: 3,882
По умолчанию

Цитата:
Согласно определению расстояния - это количество рёбер на кратчайшем пути между вершинами
Для начала о каком графе речь?
Взвешенный или нет?

Про расстояние :
тыц. Читаем последний абзац
Poma][a вне форума Ответить с цитированием
Старый 17.04.2015, 18:55   #20
vet9690
Пользователь
 
Регистрация: 15.04.2015
Сообщений: 12
По умолчанию

Цитата:
Сообщение от Poma][a Посмотреть сообщение
Для начала о каком графе речь?
Взвешенный или нет?

Про расстояние :
тыц. Читаем последний абзац
Взвешенный!
vet9690 вне форума Ответить с цитированием
Ответ


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

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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Помогите с написанием программ на С (не ++) bazik Помощь студентам 4 05.03.2015 20:15
Помогите, с написанием. Chesterfield20 C# (си шарп) 2 10.05.2014 10:17
Помогите с написанием программ для Pascal zhenia19 Помощь студентам 1 06.11.2013 20:32
Помогите с написанием двух простых программ на с++ Alex1991 Помощь студентам 0 20.04.2009 17:33