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

[Sazary]

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

а что за запись mas[i].x и что такое pow?

mas - массив структур
mas[i] - элемент массива (то есть, в данном случае, одна точка)
mas[i].x - обращение к элементу структуры

Вместо структуры сделайте два массива: x и y.
Вместо mas[i].x пишите x[i], а вместо mas[i].y - y[i].

с массивами это будет выглядеть так?

Вы изменили в коде 2 строчки. Естественно, это будет выглядеть не так!
Все, что нужно, написал выше.

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

и что такое pow?

А это могли бы посмотреть в интернете. Это функция возведения в степень.
--------------------------

[patriarch]

ура вроде бы переписал!спасибо!
и можно ещё вопросы почему именно такие формулы? mas[i].y = rand()*(BMAX-TMAX)/(double)RAND_MAX+TMAX; и S += pow( pow(mas[j].x-mas[i].x,2) + pow(mas[j].y-mas[i].y,2),0.5);
А с замененной задачей не поможете?

[Sazary]

mas[i].y = rand()*(BMAX-TMAX)/(double)RAND_MAX+TMAX;

BMAX - нижний максимум
TMAX - верхний
rand() выдает целые числа. Чтобы получить рандомное вещественное число, нужно делить на RAND_MAX. Это будет случайное число от 0 до 1.
--------------

S += pow( pow(mas[j].x-mas[i].x,2) + pow(mas[j].y-mas[i].y,2),0.5);

Здесь правая часть - длина отрезка. Формула из школьного курса математики.
----------------------------------

А с замененной задачей не поможете?

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

[patriarch]

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

[Sazary]

Пока еще плохо видно, но, возможно, программа сможет уйти в бесконечный цикл (при определенных правилах).

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

Это интересный вопрос. И, вроде как, важный для данной задачи.

Это похоже просто перебор..

Естественно перебор. А как иначе?

Подумаю, как сделать через рекурсию. Но без компьютера врядли много надумаю. Посмотрим.

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

for(i=0;i<n;i++)
 scanf("%s->%s\n",&mas[i][0],&mas[i][1]);

как-то так

[patriarch]

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

P.S. Переписанная с массивами программа же такая будет?

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



int main()
{
const int N = 10; // количество точек

const double LMAX=-10, RMAX=10; // левая и правая границы для генерации координат
const double TMAX=-10, BMAX=10; // верхняя и нижняя


double masX[N];
double masY[N];

int i,j,K;
double S,Smin;
srand(time(NULL));

for(i=0;i<N;i++)
{
// разбрасываем точки
masX[i] = rand()*(RMAX-LMAX)/(double)RAND_MAX+LMAX;
masY[i] = rand()*(BMAX-TMAX)/(double)RAND_MAX+TMAX;
printf("To4ka %d: %5.3lf %5.3lf\n",i,masX[i],masY[i]);
}
printf("\n"); 
//==================

K = 0; // считаем, что вершина K - то, что нам нужно
Smin = -1;
for(i=0;i<N;i++) // перебираем все возможные "корни куста"
{
S = 0; // изначально сумма равна 0
for(j=0;j<N;j++) // перебираем вершины куста
{
if(j==i) continue; // если текущая вершина - корень, пропускаем
S += pow( pow(masX[j]-masX[i],2) + pow(masY[j]-masY[i],2),0.5); 
}
if(Smin==-1) // если мы еще пока ничего не запомнили...
{
Smin = S; // то запоминаем эту сумму
K = i; // и номер вершины-корня
}
else
{
if(S<Smin) // иначе, если текущая сумма меньше
{
Smin = S; // запоминаем ее
K = i;
}
} 
}
//=======
printf("Vershina kusta: %5.3lf %5.3lf\n", masX[K],masY[K]);
printf("Summa reber = %5.3lf\n", Smin);
//---------
getch();
return 0;
}

[Sazary]

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

P.S. Переписанная с массивами программа же такая будет?

Ну так запустите и увидите. Все так.

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

Ну тогда придумывайте. Это просто отговорка.
Если нет идей сейчас, то, может, появятся позже. Естественно, не с потолка свалятся. Нужно сидеть и думать.
Я вернусь, скорее всего, только в пятницу. Может, и придумаю что-нибудь к этому времени.

Ну вот первые идеи.

Будут две функции: стартовая и рекуррентная.
Пусть длина правила (точнее, одной его части. (длина правила ab->ba = 2)) будет lp.
В стартовой функции идем по исходному слову (in) от 0 до in.length()-lp.
Пусть будет булева переменная flag. На каждой итерации присваиваем ему true.
Флаг будет говорить о том, применялись ли какие-нибудь правила за данный проход.
Входим в цикл while. Условие - in[i]!=out[i] && flag, то есть пока текущий символ исходного слова не равен символу из конечного и установлен флаг (то есть были перестановки).
В цикле while ставим флаг в false и вызываем рекуррентную функцию fun.
Ее заголовок будет выглядеть примерно так:

string fun(string s, int pos, bool *flag, string t)

вызываем ее с такими параметрами:

fun(in,i,*flag,"");

после этого проверяем, были ли перестановки:

if(!flag) return false;

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

---------------------
В функции fun будет цикл от 0 до N-1 (где N - количество правил).
Там выделяем в sub подстроку:

string sub = s.substr(pos,lp);

Проверяем, есть ли такая подстрока в правилах. Если есть, то меняем в строке s эту подстроку на правило (и пишем, например, в tmp), ставим флаг в true и вызываем себя:

fun(tmp,pos+1,*flag,t);

Еще должно быть условие выхода, что-то вроде:

if(pos==in.length()-lp) return t;

---------------------
Ну вот. Естественно, это наброски, которые я писал на бумаге. Использовать их в таком виде нельзя.

[patriarch]

я пытался сдать преподу задачу с деревьями.Он сказал что это простейший случай и нужно писать задачу рекурсией.Нужны случаи когда у вершины ещё могут быть сыновья.

[Sasha_Smirnov]

Я балдею! То минимальное (по сумме рёбер) дерево — то сыновья!

Тогда надо поменять (ограничить) условие задачи. Странно, что это идёт вдогонку... сразу не сказать?

То, что Sazary уже сделал (по поиску минимального дерева) — это и есть решение. А у вас так:

— 2·2?
— 4.
— Это все знают. Найдите более сложное решение.

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

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

А более сложные случаи дерева — как правило*! — дают бульшую сумму рёбер. Именно поэтому мы и взяли «простейший случай дерева»: по одному сыну у каждой вершины, кроме последней. Это никоим образом (внешний вид в расчёт не берём) не противоречит определению дерева.

____________________________
* Так что препод в общем-то прав! Но он же заменил задачу про матрицу — как очень для вас сложную! А эта — ещё сложнее: надо делать полный перебор по простым, бинарным, тринарным, бинарно-тринарным, тринарно-бинарным и т. д. деревьям. К диплому дай бог успеть!

[Sazary]

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

Он сказал что это простейший случай и нужно писать задачу рекурсией.Нужны случаи когда у вершины ещё могут быть сыновья.

В таком случае реализуйте какой-нибудь известный алгоритм для деревьев.

Sasha_Smirnov +1 ))