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

[Sasha_Smirnov]

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

[Sazary]

Sasha_Smirnov, да, интересно ) А по какому принципу вы искали путь?
Хотя бы в общих чертах (понимаю, что раз диплом, то там не все так просто)..

[Sasha_Smirnov]

Ну там строится матрица расстояний (типа графика дежурств), и берутся для начала минимальные. Если маршрут замкнулся (что далеко не обязательно происходит) — кратчайший маршрут найден. Иначе идёт частичный перебор. Хороший (линейный) алгоритм, до 1996 года по крайней мере, известен не был. Но достаточно было найти просто "неплохой" путь, без доказательства того, что меньшего не существует.

А между прочим, ваш KUST.rar решает т. наз. задачу о столице! Или о головном предприятии "куста" заводов. На тот случай, конечно, когда дороги прямые и "равнопроходимые".

[Sazary]

Познавательно )

[patriarch]

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

И в конце-то концов, patriarch, есть ли смысл осознавать своё задание тремя головами?

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

[Sasha_Smirnov]

Ну четырьмя!

Уточнить — хорошо, а можно, с умным видом, показать два решения.

[patriarch]

поговорил с преподователем.Он сказал что правильно,но сделать не структурой а массивами.
Насчет задачи про матрицу,он сказал что надо использовать все цифры и делать проверку,а так как такую проверку я все равно не напишу он дал мне вместо нее другую задачу...

2) Грамматики, языки и автоматы.
Задано множество правил подстановки вида v(i)->w(i), где все v(i) и w(i) - слова
одной и той же длины. Определить, можно ли перевести одно заданное слово в
другое последовательным применением заданных правил подстановки. Например, если
имеются правила подстановки ba->ab, cb->bc, ca->ac, то слово cbba переводится в
слово abbc следующим образом: cbba->cbab->cabb->acbb->abcb->abbc.
Правила подстановки,начальное и конечное слово вводяться пользователем с клавиатуры.

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

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

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

// объявим структуру "точка"
struct Scoord
{
 double x;
 double y;
};
//------------------

int main()
{
const int N = 10;   // количество точек
const double LMAX=-10, RMAX=10;  // левая и правая границы для генерации координат
const double TMAX=-10, BMAX=10;  // верхняя и нижняя

Scoord mas[N];  // массив точек
int i,j,K;
double S,Smin;
srand(time(NULL));

for(i=0;i<N;i++)
 {
  //  разбрасываем точки
  pixels[i][0] = rand()*(RMAX-LMAX)/(double)RAND_MAX+LMAX; // тут x
  pixels[i][1] = rand()*(BMAX-TMAX)/(double)RAND_MAX+TMAX; // тут у
  printf("To4ka %d: %5.3lf  %5.3lf\n",i,pixels[i][0].pixels[i][1]);
 }
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(mas[j].x-mas[i].x,2) + pow(mas[j].y-mas[i].y,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", mas[K].x,mas[K].y);
printf("Summa reber = %5.3lf\n", Smin);
//---------
getch();
return 0;
}

[Sasha_Smirnov]

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

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

«...А так как другую задачу я всё равно не пойму...» и так далее?!
Проверка проще некуда, сумма пяти цифр! Зачем же так себя принижать...

А главное, все цифры использовать (их у нас 10, а их сумма 45) возможно лишь в матрице 10 на 10:

0 1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9 0
2 3 4 5 6 7 8 9 0 1
3 4 5 6 7 8 9 0 1 2
4 5 6 7 8 9 0 1 2 3
5 6 7 8 9 0 1 2 3 4
6 7 8 9 0 1 2 3 4 5
7 8 9 0 1 2 3 4 5 6
8 9 0 1 2 3 4 5 6 7
9 0 1 2 3 4 5 6 7 8

(можно даже сделать так, чтобы и по диагоналям суммы были равны 45).

А вот размерность 5 на 5 позволяет использовать лишь какие-то 5 цифр, а не все.
Вам это не напоминает изначальный вариант, с простыми числами? Типа «сделай то не знаю что».

[patriarch]

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

«...А так как другую задачу я всё равно не пойму...» и так далее?!
Проверка проще некуда, сумма пяти цифр! Зачем же так себя принижать...

Это слова препода...он всем нам заменил задачу с матрицей,решив что она слишком сложна...

[Sasha_Smirnov]

Ясно. Но по идее это ваша ПРОГРАММА должна была сообщить, что такая матрица невозможна.

Или опять-таки можно было (чтобы решение стало возможным) чуть-чуть ослабить условие: использовать не все цифры — а любые разные цифры. Уж кому-кому, а программисту разница ясна!