3

На вход программе даются две точки: точка старта и точка финиша. Необходимо из точки старта попасть в точку финиша. Шагать из любой точки можно несколькими способами.

int start; //точка старта 
2*start; //из любой точки
(3*start)+1; //тоже из любой точки
start/2; //только из точек с четным номером
(start-1)/3; //из точек номер которых при делении на 3 дает остаток от деления 1

Как сделать перебор всех вариантов и вывести самый короткий путь? Интересует сам алгоритм.

Пример программы.

На вход 1 6.

На выход

7

1 4 8 16 5 10 3 6.

8
  • 2
    Что-то странно. Какие значения в массиве? Как вы в примере из 1 получаете 4? Чему равно a[1]? На входе 1 и 6 - а значения массива? Словом, у меня есть подозрения, что вы хотите, но пока не будет четкого ТЗ, браться не хочется...
    – Harry
    2 мая 2017 в 8:50
  • @Harry неверно записала условие. 3*a[i]+1
    – Alone_Fox
    2 мая 2017 в 8:52
  • Ну какая разница... Я спрашиваю - что дальше? Почему из 1 следует 4? А если a[i] все нули? И что такое - новые значения? Индексы? Значения массива?
    – Harry
    2 мая 2017 в 8:53
  • @Harry исправила условие
    – Alone_Fox
    2 мая 2017 в 8:56
  • Вот это уже другое дело :) Я бы делал поиском в ширину.
    – Harry
    2 мая 2017 в 8:57

1 ответ 1

5

Вобщем, строим граф на лету, индексы - номера вершин. Поиск в ширину. Классика, так сказать...

На коленке писанный код тут и ниже. Оптимизации, ввод-вывод и т.п. - напишите сами, я этим не заморачивался, жестко прошил 1 и 6....

#include <vector>
#include <iostream>
#include <iomanip>
#include <queue>
#include <stack>
#include <set>

using namespace std;

struct Node
{
    Node(int i, int p = -1):idx(i),prev(p){}
    int idx;   // Индекс
    int prev;  // Предыдущий узел - для восстановления пути
    bool operator <(const Node& n) const { return idx < n.idx; }
};

int main()
{
    int start = 1, stop = 6;

    queue<Node> Q;   // Очередь BFS
    set<Node> S;     // Множество уже обработанных узлов

    Q.push(Node(start));
    while(!Q.empty())
    {
        S.insert(Q.front());        // Внесли в обработанные
        int index = Q.front().idx;  // Индекс
        if (index == stop) break;   // Найден!
        Q.pop();                    // Убираем из очереди
        vector<int> next;           // Возможные варианты
        next.push_back(2*index);
        next.push_back(3*index+1);
        if (index%2 == 0) next.push_back(index/2);
        if (index%3 == 1) next.push_back((index-1)/3);
        for(int i: next)            // Обработка возможных вариантов
        {
            Node n(i,index);
            if (S.find(n) != S.end()) continue;  // Уже отработан
            Q.push(n);              // Внесение в очередь еще не рассмотренных
        }
    }

    // Вывод цепочки - так как в обратном порядке, используем стек
    stack<int> path;
    for(int index = Q.front().idx; index != -1; )
    {
        path.push(index);
        auto i = S.find(Node(index));    // Поиск предыдущего
        if (i == S.end()) break;         // Береженого Бог бережет :)
        index = i->prev;                 // Предыдущий в цепочке
    }
    // Вывод из стека
    while(!path.empty())
    {
        cout << path.top() << "  ";
        path.pop();
    }
    cout << endl;
}
1
  • Забавно. Хотелось бы понять логику минусующего (через полтора года после ответа :))
    – Harry
    6 окт 2018 в 18:19

Ваш ответ

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

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.