LINUX.ORG.RU
Форум — Talks  

Поиск всех путей на графе (Небольшой тест. Часть 2)

 


1

2

Только тем, у кого есть время. Есть однонапрвленный упорядоченный граф (надо найти все пути из a в z, но, видимо, программно):

a → b, c, d, z
b → d, e, f, z
c → d, e, f, z
d → e, f, z
e → f, z
f → g, h, j, z
g → h, i, j, z
h → i, j, k, z
i → j, k, l, z
j → k, m, z
k → l, n, o, z
l → m, z
m → n, o, z
n → o, z
o → p, z
p → q, z
q → r, z
r → s, z
s → t, u, z
t → u, v, z
u → v, w, z
v → w, z
w → x, y, z
x → y, z
y → z
z → (нет исходящих)

Свой результат пишу сразу ( даже не уверен, что 100% правильный, но все ж…): Все пути:

22061

Все пути в массивах. Вывод кода: https://filebin.net/ysidtdizjge50kjh

Код для проверки: https://gitflic.ru/project/dcc0/mix-c-89-php/blob?file=allways_more_20k.php

★

Последнее исправление: AnonymUser (всего исправлений: 7)
← Что именно вас затянуло в Linux?
Проблема с банковской картой →
  1 2 3 →
Ответ на: комментарий от AnonymUser

Вот так же проще и понятнее записывать:

z = 1

y = 1 = 1
x = 1+1 = 2
w = 2+1+1 = 4
v = 4+1 = 5
u = 5+4+1 = 10
t = 10+5+1 = 16
s = 16+10+1 = 27
...
AlexVR ★★★★★
()
Последнее исправление: AlexVR (всего исправлений: 2)
Ответ на: комментарий от AnonymUser

Посмотрев на реакцию от firkax, я сократил ещё (т.е. теперь код C практически идентичен коду PHP и - это C89!):

#include <stdio.h>
#include <string.h>
//Объявим граф глобально
char a[] = "bcdz";
char b[] = "defz";
char c[] = "defz";
char d[] = "efz";
char e[] = "fz";
char f[] = "ghjz";
char g[] = "hijz";
char h[] = "ijkz";
char i[] = "jklz";
char j[] = "kmz";
char k[] = "lnoz";
char l[] = "mz";
char m[] = "noz";
char n[] = "oz";
char o[] = "pz";
char p[] = "qz";
char q[] = "rz";
char r[] = "sz";
char s[] = "tuz";
char t[] = "uvz";
char u[] = "vwz";
char v[] = "wz";
char w[] = "xyz";
char x[] = "yz";
char y[] = "z";
char z[] = "";
/*Массивы соответствий*/
char *array_corresp[]={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z};
char array_corresp2[]=  "abcdefghijklmnopqrstuvwxyz";

//Вернёт элемент, который потом допишем в массив x
char element_search_to_push ( char *x) {
char z;
int i;
	for (i=0; i  < strlen(array_corresp2); i++) {
		if (x[strlen(x)-1] == array_corresp2[i])
	z=array_corresp[i][0];
	}

	return z;
}
//Возвращает указатель на первый путь x
char *element_search ( char *x,  int j ) {
char *arr;
int i;
	for (i=0; i  < strlen(array_corresp2); i++) {
		if (x[j-1] == array_corresp2[i])
	arr=array_corresp[i];
	}

	return arr;
}


static int array_search (const char *ar, char el) {
    int i = 0;
    while (ar[i] != '\0') {
        if (ar[i] == el) return i;
        i++;
    }
    return -1;
}

int main() {
int all_ways_count =1;
int key;
//Первый путь
char x[] = "abdefghijklmnopqrstuvwxyz";
//Для добавления в массив
char z;
//Длина j.
int j = strlen(x)-1;
char last_point = 'z';
int i = 0;
char *ar;
int x_len = 0;
//Печать 1-го
for (i=0; x[i] != '\0'; i++)
printf("%c", x[i]);
printf("\n\r");

while (j != 0 )
 {
//Определяем и ищем элемент и его ключ
  ar=element_search (x,  j );
  key =  array_search(ar, x[j]);
       if ((key != -1) && (ar[key + 1] != '\0')) {
			//Ставим длину массива равной j
		 x_len = j;
		 //Заменим substr
		  x[j+1]='\0';
		  //Пишем в массив x
		   x[x_len++]= ar[key+1];
//Найдем z для записи
z=element_search_to_push(x);
while(1) {
		//Если дошли до последней точки выходим
		if ((x[strlen(x)-1] == last_point)) {
			//Пишем в x
			 x[x_len++] = z;
			 break;
		 }
			//Пишем в x
		x[x_len++] = z;
//Ещё найдем z для записи
z=element_search_to_push(x);
				}
				//Переменную ставим равной массиву
				j=strlen(x);
				//Выводим
				printf("%s", x);
				printf("\n\r");
				all_ways_count++;
			}
j--;
		}
printf("%d", all_ways_count);
 }

C89 жив! С89 победил! Осталось только вменяемые имена некоторым переменным дать.

AnonymUser ★
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 2)
Ответ на: комментарий от ratvier

На моей планете нету столько оперативы. Придётся подождать открытия галактических торговых путей.

ugoday ★★★★★
()
Ответ на: комментарий от AnonymUser

Какой питонщик? Ты там пьяный что-ли? Это раст, а на питон тебе надо посмотреть, может хоть какое-то представление появится о структризации/декомпозиции и вообще читаемости кода.

zurg ★★
()
Ответ на: комментарий от zurg

Кто-то написал про пайтон, а я и внимания не обратил.

P.S. Вот не лень это было прогрммировать на расте?! Выглядит, как ООП на JavaScript. В лучших традициях башскриптинга или даже php, когда много конкатенаций и т.д., а ещё меня ругали… Не даже так: в лучших традициях perl и аwk…

fn graph_parser(txt: &str) -> Graph {
   txt.lines().filter(|s| !s.is_empty()).map(|s| {
           let ss: Vec<&str> = s.split('→').collect();
           let nodes: Vec<_> = ss[1].split(',')
               .map(|s| s.trim().chars().next().unwrap()).collect();
           (ss[0].trim().chars().next().unwrap(), nodes)
       }).collect()
}
AnonymUser ★
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 1)
Ответ на: комментарий от AnonymUser

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

fn graph_parser(txt: &str) -> Graph {

Объявляется функция, которая принимает строку (указатель, ссылку?) и возвращает Graph.

txt.lines().….collect()

Большая строка разбирается на отдельные строчки, там с ними потом что-то сделают, а результат соберут методом collect.

filter(|s| !s.is_empty())

Понятное дело, пустые строчки игнорируем. На данном этапе мы имеем что-то вида "n→n1, n2, n3, … nn".

let ss: Vec<&str> = s.split('→').collect();

ss (не путать с SS!) бьёт строку на исходную и конечные узлы ["n", "n1, n2, n3, … nn'].

let nodes: Vec<_> = ss[1].split(',')

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

.map(|s| s.trim().chars().next().unwrap()).collect();

убирает пробелы и собирает в вектор.

(ss[0].trim().chars().next().unwrap(), nodes)

И вот эта штука (откуда, [куда]) и является возвращаемым значением. А вектор из таких — Graph, который является результом работы.

Весьма осмысленный и логичный код.

ugoday ★★★★★
()
Ответ на: комментарий от ugoday

На лиспе, естественно, всё красивее и элегантнее.

(defun graph-parser (txt))
(->> txt
     (ppcre:split "\\n")
     (mapcar #'(lambda (s)
		 (ppcre:all-matches-as-strings "\\w" s)))
     (mapcar #'(lambda (ss)
		 (list (car ss) (cdr ss)))))
ugoday ★★★★★
()
Последнее исправление: ugoday (всего исправлений: 1)
Ответ на: комментарий от ugoday

Лишь бы человека устраивало. Сказано без иронии.

AnonymUser ★
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 1)
Ответ на: комментарий от ugoday

Не знаю, на самом деле. Кода я видел немного. Самым структурированным кажется ASM (но мне малопонятен).


#include <stdio.h>
#include <string.h>

// Объявим граф глобально
char a[] = "bcd";
char b[] = "def";
char c[] = "def";
char d[] = "ef";
char e[] = "f";
char f[] = "";

/* Массивы соответствий */
char *array_corresp[] = {a, b, c, d, e, f};
char array_corresp2[] = "abcdef";
//Рёбра
char *ribs[] = {
    "ab", "ac", "ad", "bd", "be", "bf",
    "cd", "ce", "cf", "de", "df", "ef"
};
//Длины рёбeр
int ribs_count[] = {12, 13, 14, 24, 25, 26, 34, 35, 36, 45, 46, 56};
//Длина массива с длинами рёбер
int ribs_all_count = sizeof(ribs_count) / sizeof(ribs_count[0]);

/////////////////Функции//////////////////////////////////////////////////////
// Вернёт элемент, который потом допишем в массив x
char element_search_to_push(char *x) {
    char z;
    int i;
    for (i = 0; i < strlen(array_corresp2); i++) {
        if (x[strlen(x) - 1] == array_corresp2[i]) {
            z = array_corresp[i][0];
        }
    }
    return z;
}

// Возвращает указатель на первый путь x
char *element_search(char *x, int j) {
    char *arr;
    int i;
    for (i = 0; i < strlen(array_corresp2); i++) {
        if (x[j - 1] == array_corresp2[i]) {
            arr = array_corresp[i];
        }
    }
    return arr;
}

static int array_search(const char *ar, char el) {
    int i = 0;
    while (ar[i] != '\0') {
        if (ar[i] == el) return i;
        i++;
    }
    return -1;
}

//Найдем длину каждого пути
int count_way_lenght(int rib_length , char *x) {
 rib_length  = 0;
	int i, y;
	      for (y = 0; y < strlen(x) - 1; y++) {
                for (i = 0; i < ribs_all_count; i++) {
                    if (x[y] == ribs[i][0] && x[y + 1] == ribs[i][1]) {
                        rib_length += ribs_count[i];
                    }
                }
            }
	return rib_length;
}

/////////////////////////////////////////////////////////////////////////////////////////

int main() {
    char short_way_point[100];
    int y = 0;
    int rib_length = 0;
    int short_way = 1000;
    int key;
	//Первый путь задан
    char x[] = "abdef";
    char z;
    // Длина j
    int j = strlen(x) - 1;
    char last_point = 'f';
    int i = 0;
    char *ar;
    int x_len = 0;

    // Печать 1-го
//////////////////////////////////////////////////
    for (i = 0; x[i] != '\0'; i++)
        printf("%c", x[i]);

    // Найдем длину первого пути
    rib_length = 0;
    for (y = 0; y < strlen(x) - 1; y++) {
        for (i = 0; i < 12; i++) {
            if (x[y] == ribs[i][0] && x[y + 1] == ribs[i][1]) {
                rib_length += ribs_count[i];
            }
        }
    }
    printf(" %d ", rib_length);
    printf("\n\r");
///////////////////////////////////////////////////

    // Основной цикл поиска путей
    while (j != 0) {
        // Определяем и ищем элемент и его ключ
        ar = element_search(x, j);
        key = array_search(ar, x[j]);

        if ((key != -1) && (ar[key + 1] != '\0')) {
            // Задаем длину массива равной j
            x_len = j;
            // Заменяем substr
            x[j + 1] = '\0';
            // Пишем в массив x
            x[x_len++] = ar[key + 1];

            // Найдем z для записи
            z = element_search_to_push(x);
            while (1) {
                // Если дошли до 'f', выходим
                if (x[strlen(x) - 1] == last_point ) {
                    x[x_len++] = z;
                    break;
                }
                // Пишем в x
                x[x_len++] = z;
                // Ещё найдем z для записи
                z = element_search_to_push(x);
            }
            // Обновляем j
            j = strlen(x);
            // Выводим текущий путь
            printf("%s", x);
            // Пересчитываем длину пути

			rib_length=count_way_lenght(rib_length,  x);
            // Печать длины пути
            printf(" %d ", rib_length);
            printf("\n\r");

            // Обновляем кратчайший путь
            if (rib_length < short_way) {
				//Сохраним кратчайший путь
				strcpy(short_way_point, x);
                short_way = rib_length;
            }
        }
        j--;
    }

    printf("Самый короткий путь: %d \n\r", short_way);
    printf("Лежит через эти точки: %s \n\r", short_way_point);

    return 0;
}
AnonymUser ★
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 2)
Ответ на: комментарий от ugoday

Лично мне попадались и какие-то довольно понятные фрагменты (чужого) кода на C, которые казались вполне читаемыми. PHP действительно часто бывает запутан. Баш тем паче. Но даже на PHP видел хорошие примеры кода.

Но на PHP все-таки делались какие-то рабочие вещи, делались на лету. А когда надо, чтобы работало, то бывает не до изысков.

AnonymUser ★
() автор топика
Ответ на: комментарий от AnonymUser

код C практически идентичен коду PHP

Не уверен хуже ли это говорит о С или PHP. Если высокоуровневый код выглядит как низкоуровневый, то это плохо, как бы должна быть выгода от поднятия уровня за которую мы готовы платить производительностью. С другой стороны, «выглядит как код на PHP» тоже очень так себе комплимент.

ugoday ★★★★★
()
Ответ на: комментарий от ugoday

Я тоже не знаю. Но в этом C-подобность PHP. А у C-подобность псевдокоду. И в этом вижу его силу. А вкупе с инлайн синаксисом для вставки АСМ его ценность удваивается. Т.е. C окызвается почти незаменимым. Да и зачем его менять?!

Подпилил ещё с учетом критических рекомендаций:

#include <stdio.h>
#include <string.h>
//Количество всех вершин
#define ALL_POINTS 26
// Объявим граф глобально
char a[] = "bcdz";
char b[] = "defz";
char c[] = "defz";
char d[] = "efz";
char e[] = "fz";
char f[] = "ghjz";
char g[] = "hijz";
char h[] = "ijkz";
char i[] = "jklz";
char j[] = "kmz";
char k[] = "lnoz";
char l[] = "mz";
char m[] = "noz";
char n[] = "oz";
char o[] = "pz";
char p[] = "qz";
char q[] = "rz";
char r[] = "sz";
char s[] = "tuz";
char t[] = "uvz";
char u[] = "vwz";
char v[] = "wz";
char w[] = "xyz";
char x[] = "yz";
char y[] = "z";
char z[] = "";
/* Массивы соответствий */
char *array_corresp[] = {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x,y,z};
char array_corresp2[] = "abcdefghijklmnopqrstuvwxyz";

//Рёбра
char *ribs[] = {
"ab", "ac", "ad", "az",
    "bd", "be", "bf", "bz",
    "cd", "ce", "cf", "cz",
    "de", "df", "dz",
    "ef", "ez",
    "fg", "fh", "fj", "fz",
    "gh", "gi", "gj", "gz",
    "hi", "hj", "hk", "hz",
    "ij", "ik", "il", "iz",
    "jk", "jm", "jz",
    "kl", "kn", "ko", "kz",
    "lm", "lz",
    "mn", "mo", "mz",
    "no", "nz",
    "op", "oz",
    "pq", "pz",
    "qr", "qz",
    "rs", "rz",
    "st", "su", "sz",
    "tu", "tv", "tz",
    "uv", "uw", "uz",
    "vw", "vz",
    "wx", "wy", "wz",
    "xy", "xz",
    "yz"
};
//Длины рёбeр
int ribs_count[] = { 12, 13, 14, 24, 25, 26, 34, 35, 36, 45, 46, 56,
    7,  8,  9, 10, 11, 15, 16, 17, 18, 19, 20, 21, 22,
    23, 27, 28, 29, 30, 31, 32, 33, 37, 38, 39, 40, 41,
    42, 43, 44, 47, 48, 49, 50, 51, 52, 53, 54, 55, 57,
    58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70,
    71, 72, 73, 74, 75, 17, 99, 67};
//Длина массива с длинами рёбер
int ribs_all_count = sizeof(ribs_count) / sizeof(ribs_count[0]);

/////////////////Функции//////////////////////////////////////////////////////
// Вернёт элемент, который потом допишем в массив x
char element_search_to_push(char *x) {
    char z;
    int i;
    int j = strlen(x) - 1;
    for (i = 0; i <  ALL_POINTS; i++) {
        if (x[j] == array_corresp2[i]) {
            z = array_corresp[i][0];
        }
    }
    return z;
}

// Возвращает указатель на первый путь x
char *element_search(char *x, int j) {
    char *arr;
    int i;
    for (i = 0; i <  ALL_POINTS; i++) {
        if (x[j - 1] == array_corresp2[i]) {
            arr = array_corresp[i];
        }
    }
    return arr;
}

static int array_search(const char *ar, char el) {
    int i = 0;
    while (ar[i] != '\0') {
        if (ar[i] == el) return i;
        i++;
    }
    return -1;
}

//Найдем длину каждого пути
int count_way_lenght(int rib_length , char *x) {
	int j =strlen(x) - 1;
 rib_length  = 0;
	int i, y;
	      for (y = 0; y < j; y++) {
                for (i = 0; i < ribs_all_count; i++) {
                    if (x[y] == ribs[i][0] && x[y + 1] == ribs[i][1]) {
                        rib_length += ribs_count[i];
                    }
                }
            }
	return rib_length;
}

/////////////////////////////////////////////////////////////////////////////////////////

int main() {

    char short_way_point[100];
    int y = 0;
    int rib_length = 0;
    int short_way = 1000;
    int key;
	//Первый путь задан
    char x[100] = "abdefghijklmnopqrstuvwxyz";
    char z;
    // Длина j
    int j = strlen(x) - 1;
    char last_point = 'z';
    int i = 0;
    char *ar;
    int x_len = 0;
    //Все пути. 1 потому что выводим 1-ый вне циклов
	int all = 1;


    // Печать 1-го
//////////////////////////////////////////////////
    for (i = 0; x[i] != '\0'; i++)
        printf("%c", x[i]);

    // Найдем длину первого пути
    rib_length = 0;
    for (y = 0; y < j; y++) {
        for (i = 0; i < ribs_all_count; i++) {
            if (x[y] == ribs[i][0] && x[y + 1] == ribs[i][1]) {
                rib_length += ribs_count[i];
            }
        }
    }
    printf(" %d ", rib_length);
    printf("\n\r");
///////////////////////////////////////////////////

    // Основной цикл поиска путей
    while (j != 0) {
        // Определяем и ищем элемент и его ключ
        ar = element_search(x, j);
        key = array_search(ar, x[j]);

        if ((key != -1) && (ar[key + 1] != '\0')) {
            // Задаем длину массива равной j
            x_len = j;
            // Заменяем substr
            x[j + 1] = '\0';
            // Пишем в массив x
            x[x_len++] = ar[key + 1];

            // Найдем z для записи
            z = element_search_to_push(x);
            while (1) {
                // Если дошли до 'f', выходим
                if (x[strlen(x) - 1] == last_point ) {
                    x[x_len++] = z;
                    break;
                }
                // Пишем в x
                x[x_len++] = z;
                // Ещё найдем z для записи
                z = element_search_to_push(x);
            }
            // Обновляем j
            j = strlen(x);
            // Выводим текущий путь
            printf("%s", x);
             all++;
            // Пересчитываем длину пути

			rib_length=count_way_lenght(rib_length,  x);
            // Печать длины пути
            printf(" %d ", rib_length);
            printf("\n\r");

            // Обновляем кратчайший путь
            if (rib_length < short_way) {
				//Сохраним кратчайший путь
				strcpy(short_way_point, x);
                short_way = rib_length;
            }
        }
        j--;
    }

    printf("Самый короткий путь: %d \n\r", short_way);
    printf("Лежит через эти точки: %s \n\r", short_way_point);
    printf("Все пути: %d \n\r", all);

    return 0;
}
AnonymUser ★
() автор топика
Ответ на: комментарий от AnonymUser

Результат в выводом:

real	0m0,856s
user	0m0,610s
sys	0m0,245s
AnonymUser ★
() автор топика
Ответ на: комментарий от AnonymUser

Ну вы бы хоть на функции разбили и имена понятные дали. Основной цикл поиска путей внушает ужос.

ugoday ★★★★★
()
Ответ на: комментарий от ugoday

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

AnonymUser ★
() автор топика
Последнее исправление: AnonymUser (всего исправлений: 1)
Ответ на: комментарий от AnonymUser

Вроде отформатировал. Переменные изменил, а то они ещё с графом совпадали =) В цикле только печать в функцию убрал. Там особенно нечего в функции заворачивать.

#include <stdio.h>
#include <string.h>

// Количество всех вершин
#define ALL_POINTS 26

// Объявим граф глобально
char a[] = "bcdz";
char b[] = "defz";
char c[] = "defz";
char d[] = "efz";
char e[] = "fz";
char f[] = "ghjz";
char g[] = "hijz";
char h[] = "ijkz";
char i[] = "jklz";
char j[] = "kmz";
char k[] = "lnoz";
char l[] = "mz";
char m[] = "noz";
char n[] = "oz";
char o[] = "pz";
char p[] = "qz";
char q[] = "rz";
char r[] = "sz";
char s[] = "tuz";
char t[] = "uvz";
char u[] = "vwz";
char v[] = "wz";
char w[] = "xyz";
char x[] = "yz";
char y[] = "z";
char z[] = "";

/* Массивы соответствий */
char *array_corresp[] = {
    a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z
};
char array_corresp2[] = "abcdefghijklmnopqrstuvwxyz";

/* Рёбра */
char *ribs[] = {
    "ab", "ac", "ad", "az",
    "bd", "be", "bf", "bz",
    "cd", "ce", "cf", "cz",
    "de", "df", "dz",
    "ef", "ez",
    "fg", "fh", "fj", "fz",
    "gh", "gi", "gj", "gz",
    "hi", "hj", "hk", "hz",
    "ij", "ik", "il", "iz",
    "jk", "jm", "jz",
    "kl", "kn", "ko", "kz",
    "lm", "lz",
    "mn", "mo", "mz",
    "no", "nz",
    "op", "oz",
    "pq", "pz",
    "qr", "qz",
    "rs", "rz",
    "st", "su", "sz",
    "tu", "tv", "tz",
    "uv", "uw", "uz",
    "vw", "vz",
    "wx", "wy", "wz",
    "xy", "xz",
    "yz"
};

/* Длины рёбер */
int ribs_count[] = {
    12, 13, 14, 24, 25, 26, 34, 35, 36, 45, 46, 56,
    7, 8, 9, 10, 11, 15, 16, 17, 18, 19, 20, 21, 22,
    23, 27, 28, 29, 30, 31, 32, 33, 37, 38, 39, 40, 41,
    42, 43, 44, 47, 48, 49, 50, 51, 52, 53, 54, 55, 57,
    58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70,
    71, 72, 73, 74, 75, 17, 99, 67
};

// Длина массива с длинами рёбер
int ribs_all_count = sizeof(ribs_count) / sizeof(ribs_count[0]);

/////////////////Функции//////////////////////////////////////////////////////

int print_way(char *first_x_way, int rib_length) {
    // Выводим текущий путь
    printf("%s", first_x_way);
    // Печать длины пути
    printf(" %d ", rib_length);
    printf("\n\r");
    return 0;
}

// Вернёт элемент, который потом допишем в массив first_x_way
char search_element_to_push(char *first_x_way) {
    char z;
    int i;
    int j = strlen(first_x_way) - 1;
    for (i = 0; i < ALL_POINTS; i++) {
        if (first_x_way[j] == array_corresp2[i]) {
            z = array_corresp[i][0];
        }
    }
    return z;
}

// Возвращает указатель на первый путь first_x_way
char *element_search(char *first_x_way, int j) {
    char *arr;
    int i;
    for (i = 0; i < ALL_POINTS; i++) {
        if (first_x_way[j - 1] == array_corresp2[i]) {
            arr = array_corresp[i];
        }
    }
    return arr;
}

// Поиск ключа элемента
static int array_search(const char *ar_for_element_search, char el) {
    int i = 0;
    while (ar_for_element_search[i] != '\0') {
        if (ar_for_element_search[i] == el) return i;
        i++;
    }
    return -1;
}

// Найдем длину каждого пути
int count_way_length(int rib_length, char *first_x_way) {
    int j = strlen(first_x_way) - 1;
    rib_length = 0;
    int i, y;
    for (y = 0; y < j; y++) {
        for (i = 0; i < ribs_all_count; i++) {
            if (first_x_way[y] == ribs[i][0] && first_x_way[y + 1] == ribs[i][1]) {
                rib_length += ribs_count[i];
            }
        }
    }
    return rib_length;
}

/////////////////////////////////////////////////////////////////////////////////////////

int main() {
    char first_x_way[100] = "abdefghijklmnopqrstuvwxyz";
    char element_to_push;
    char short_way_point[100];
    char last_point = 'z';
    char *ar_for_element_search;
    int i, y, key;
    int rib_length = 0;
    int all = 1;
    // Вспомогательная переменная для определения самого короткого пути
    int short_way = 5000;
    // Первый путь задан
    // Длина j
    int j = strlen(first_x_way) - 1;
    int first_x_way_len = 0;

    // Все пути. 1 потому что выводим 1-ый вне циклов
    // Печать первого пути
    for (i = 0; first_x_way[i] != '\0'; i++)
        printf("%c", first_x_way[i]);

    // Найдем длину первого пути
    rib_length = 0;
    for (y = 0; y < j; y++) {
        for (i = 0; i < ribs_all_count; i++) {
            if (first_x_way[y] == ribs[i][0] && first_x_way[y + 1] == ribs[i][1]) {
                rib_length += ribs_count[i];
            }
        }
    }
    printf(" %d ", rib_length);
    printf("\n\r");

    // Основной цикл поиска путей
    while (j > 0) {
        /* Определяем и ищем элемент и его ключ */
        ar_for_element_search = element_search(first_x_way, j);
        key = array_search(ar_for_element_search, first_x_way[j]);

        if ((key != -1) && (ar_for_element_search[key + 1] != '\0')) {
            /* Задаем длину массива равной j */
            first_x_way_len = j;
            /* Режем первый путь */
            first_x_way[j + 1] = '\0';
            /* Пишем в массив first_x_way */
            first_x_way[first_x_way_len++] = ar_for_element_search[key + 1];
            /* Найдем element_to_push для записи */
            element_to_push = search_element_to_push(first_x_way);

            while (1) {
                /* Если дошли до последнего символа, выходим */
                if (first_x_way[strlen(first_x_way) - 1] == last_point) {
                    first_x_way[first_x_way_len++] = element_to_push;
                    break;
                }
                /* Пишем в first_x_way */
                first_x_way[first_x_way_len++] = element_to_push;
                /* Ещё найдем element_to_push для записи */
                element_to_push = search_element_to_push(first_x_way);
            }
            /* Обновляем j */
            j = strlen(first_x_way);
            all++;
            /* Пересчитываем длину пути */
            rib_length = count_way_length(rib_length, first_x_way);
            /* Печать */
            print_way(first_x_way, rib_length);
            /* Обновляем кратчайший путь */
            if (rib_length < short_way) {
                /* Сохраним кратчайший путь */
                strcpy(short_way_point, first_x_way);
                short_way = rib_length;
            }
        }
        j--;
    }

    /* Тут результаты */
    printf("Самый короткий путь: %d \n\r", short_way);
    printf("Лежит через эти точки: %s \n\r", short_way_point);
    printf("Все пути: %d \n\r", all);

    return 0;
}
AnonymUser ★
() автор топика
Закрыто добавление комментариев для недавно зарегистрированных пользователей (со score < 50)
  1 2 3 →
← Что именно вас затянуло в Linux?
Talks
Проблема с банковской картой →