Вопрос Помогите решить задачу огэ

[Yesgoter]

добрый вечер, кто знает как решить эту задачку? Любой яп, но желательно c++ или питон.

 

[lemak]

так тут без кода можно сделать...

 

[ampersand]

Это же вроде руками делается, на бумаге

 

[PasterAlmir]

А не проще самому посчитать?
10 путей

 

[soondieyoung]

> p2c провайдер
> не слышал про обход графа

зодумойтес...

p.s.: Arkting ты бы хоть помог подопечному

 

[Yesgoter]

А не проще самому посчитать?
10 путей

проще, ну тут надо именно на пк

 

[jesu1901]

Во-первых, нам нужно определить количество путей из города A в город Ж. Для этого мы можем использовать простой рекурсивный подход. Мы можем рассматривать каждую дорогу как путь и рекурсивно найти количество путей из города A в город Ж, сложив количество путей из города A в каждый из соседних городов, а затем количество путей из этих городов в город Ж, и так далее.

Получив количество путей из города A в город Ж, мы можем использовать тот же рекурсивный подход, чтобы найти количество путей из города Ж в город K.

Чтобы найти общее количество путей из города A в город K, проходящих через город Ж, нам просто нужно умножить количество путей из города A в город Ж на количество путей из города Ж в город K.

Вот пример кода, демонстрирующий этот подход на CPP.

#include <iostream>

using namespace std;

// Рекурсивная функция для нахождения количества путей из города А в город Б
int findPaths(char A, char B) {
  // Базовый случай: если A и B — один и тот же город, существует только 1 путь.
  if (A == B) return 1;

  // Инициализировать счет до 0
  int count = 0;

  // Проверить каждую дорогу, чтобы увидеть, ведет ли она в город Б.
  if (A == 'A' && B == 'G') count += 1;
  if (A == 'A' && B == 'B') count += findPaths('B', 'G');
  if (A == 'B' && B == 'G') count += findPaths('A', 'G') + findPaths('C', 'G');
  if (A == 'C' && B == 'G') count += findPaths('B', 'G') + findPaths('D', 'G');
  if (A == 'D' && B == 'G') count += findPaths('C', 'G') + findPaths('E', 'G');
  if (A == 'E' && B == 'G') count += findPaths('D', 'G');
  if (A == 'G' && B == 'K') count += 1;

  // Возвращает общее количество путей
  return count;
}

int main() {
  // Найдите количество путей из города А в город К, проходящих через город Ж.
  int paths = findPaths('A', 'G') * findPaths('G', 'K');

  cout << "Number of paths from A to K passing through G: " << paths << endl;

  return 0;
}

 

[katzen]

так тут без кода можно сделать...

тут и надо делать без кода)