Помогите с написанием программ!

[vet9690]

От модератора: для оформления кода программы используйте тэг 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 (это кнопка с изображением решётки: #)

[FPaul]

3) В графе найти максимальное расстояние между всеми парами его вершин.

Проблема в том, у нас есть длины , по которым и нужно искать, а не по количестве вершин.

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

[vet9690]

Сообщение от 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");
}

Код нужно оформлять правильно

[FPaul]

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

[vet9690]

Сообщение от 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;
}

[Poma][a]

Кроме того, проверь работоспособность твоей реализации алгоритма Флойда-Уоршелла

Тут два варианта. Ищем именно диаметр (тогда решение есть при любом графе) (и Уоршелл нам не нужен). Или ищем максимальное расстояние между двумя вершинами, понимая под ним, не max(v[i][j]), где i - вершина, для которой ищется расстояние, j - все возможные вершины. (и уже используем его)

[FPaul]

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

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

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

[vet9690]

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

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

Отдохнуть не даю, потому что нету у меня этой базы знаний, я не представляю себе это на С++, я не всегда понимаю где и какой цикл нужен( куда его вставить) что уж там говорить про другие задания.Но очень хочу все это знать. Как раз читаю об алгоритме, мне все очень интересно так как это все новое для меня.

[Poma][a]

Согласно определению расстояния - это количество рёбер на кратчайшем пути между вершинами

Для начала о каком графе речь?
Взвешенный или нет?

Про расстояние :
тыц. Читаем последний абзац

[vet9690]

Сообщение от Poma][a

Для начала о каком графе речь?
Взвешенный или нет?

Про расстояние :
тыц. Читаем последний абзац

Взвешенный!