Форум программистов, компьютерный форум, киберфорум
Наши страницы
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/4: Рейтинг темы: голосов - 4, средняя оценка - 5.00
Zivaka
0 / 0 / 0
Регистрация: 02.11.2014
Сообщений: 21
1

Интересная задача на графы

28.03.2015, 20:52. Просмотров 707. Ответов 13
Метки нет (Все метки)

Помогите решить. Никак не могу придумать способ. Мне говорят, что на графы, а связать это с графами не могу. Может хоть способ решения и объясните как решать.
Дан набор слов. Требуется определить количество вершин в луче, построенном над ними.

Входные данные:
В первой строчке находится число N - количество слов, N не превышает 10000
В каждой следующий строчке записано очередное слово, состоящее из заглавных английских букв.
Длина слова не превышает 20 символов.

Выходные данные:
Одно число - количество вершин в луче

Пример входных данных:
4
CAT
CLEAR
CAR
MORE

Пример выходных данных:
13

Пояснение примера. На рисунке (смотри вложение) изображен луч, построенный над набором слов 'CAT', 'CLEAR', 'CAR', 'MORE'.
0
Изображения
 
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.03.2015, 20:52
Ответы с готовыми решениями:

Интересная задача на вывод процентов
Задан текст, слова которого разделены %. Выяснить и вывести на экран, какой...

Интересная задача на числа Фибоначчи
Требуется решить данную задачу: Караси и пираньи В озеро «Карасевое» ради...

Судоку. Задача довольно-таки интересная
Написать программу через рекурсию, делающую судоку.... Добавлено через 2...

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

Интересная задача. (вывод своего кода на экран)
Вот, сидели с другом на паре и возник вопрос: Можно ли в с\с++ написать...

13
1XPLoade1
30 / 30 / 38
Регистрация: 23.01.2015
Сообщений: 174
28.03.2015, 21:01 2
Мне кажется, что "лучем на набором слов" является путь в графе, состоящий из числа вершин, которое больше или равно количества букв самого длинного слова. По моему так.
0
Миниатюры
Интересная задача на графы  
Kastaneda
Jesus loves me
Эксперт С++
4938 / 3014 / 346
Регистрация: 12.12.2009
Сообщений: 7,610
Записей в блоге: 2
Завершенные тесты: 1
28.03.2015, 21:38 3
Судя по ответу из примера нужно подсчитать кол-во вершин. Мне кажется тут будет удобней использовать список смежности.
Какое именно место не понятно?
0
Zivaka
0 / 0 / 0
Регистрация: 02.11.2014
Сообщений: 21
28.03.2015, 23:40  [ТС] 4
Непонятно какой из алгоритмов на графах использовать и как его строить.
0
_Ivana
29.03.2015, 00:55
  #5

Не по теме:

Имхо, как-то так. Навскидку, без оптимизации, не знаю как поведет себя на больших данных типа 10000 слов по 20 символов

Haskell
1
2
3
4
5
6
7
res = (+1) . go where
    go [] = 0
    go l  = length g + sum (map go g) where
        p = filter (not.null) l
        g = map (\c -> map tail . filter ((==c).head) $ p) $ nub . map head $ p
 
main = print $ res ["CAT","CLEAR","CAR","MORE"]

0
igorrr37
1867 / 1483 / 751
Регистрация: 21.12.2010
Сообщений: 2,473
Записей в блоге: 11
29.03.2015, 10:39 6
Лучший ответ Сообщение было отмечено Zivaka как решение

Решение

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
#include <vector>
#include <string>
#include <utility>
 
class Graph
{
public:
    Graph()
    {
        vert.emplace_back(0, std::vector<int>());
    }
    void push(std::string const& rhs)
    {
        for(int i = 0, k = 0; i < rhs.size(); ++i)
        {
            int j;
            for(j = 0; j < vert[k].second.size(); ++j)
            {
                if(vert[vert[k].second[j]].first == rhs[i]) break;
            }
            if(j == vert[k].second.size())
            {
                vert.emplace_back(rhs[i], std::vector<int>());
                vert[k].second.push_back(vert.size() - 1);
                k = vert.size() - 1;
            }
            else k = vert[k].second[j];
        }
    }
    std::vector<std::pair<char, std::vector<int> > > vert;
};
 
int main()
{
    Graph g;
    g.push("cat");
    g.push("more");
    g.push("car");
    g.push("clear");
    std::cout << g.vert.size() << " ";
    return 0;
}
1
Zivaka
0 / 0 / 0
Регистрация: 02.11.2014
Сообщений: 21
29.03.2015, 19:37  [ТС] 7
Цитата Сообщение от igorrr37 Посмотреть сообщение
Код C++
А в какой среде разработан этот код?

У меня выдает ошибку в этой строчке:
C++
1
vert.emplace_back(0, std::vector<int>());
Добавлено через 11 минут
Ошибка:
C++
1
[bcc32 Error] File1.cpp(24): E2316 'emplace_back' is not a member of 'std::vector<std::pair<char,std::vector<int,std::allocator<int> > >,std::allocator<std::pair<char,std::vector<int,std::allocator<int> > > > >'
0
igorrr37
1867 / 1483 / 751
Регистрация: 21.12.2010
Сообщений: 2,473
Записей в блоге: 11
29.03.2015, 20:55 8
Лучший ответ Сообщение было отмечено Zivaka как решение

Решение

C++
1
2
vert.push_back(std::make_pair(0, std::vector<int>()));
vert.push_back(std::make_pair(rhs[i], std::vector<int>()));
1
Zivaka
0 / 0 / 0
Регистрация: 02.11.2014
Сообщений: 21
29.03.2015, 22:40  [ТС] 9
Спасибо большее) Пошел разбирать код.

Добавлено через 1 час 33 минуты
Цитата Сообщение от igorrr37 Посмотреть сообщение
Код C++
Возникла проблема, на одном из тестов возникает ошибка выполнения, а в чем причина не могу понять..
0
igorrr37
1867 / 1483 / 751
Регистрация: 21.12.2010
Сообщений: 2,473
Записей в блоге: 11
30.03.2015, 06:17 10
Что за ошибка
0
Zivaka
0 / 0 / 0
Регистрация: 02.11.2014
Сообщений: 21
30.03.2015, 16:54  [ТС] 11
Цитата Сообщение от igorrr37 Посмотреть сообщение
Что за ошибка
"Ошибка выполнения"
Я точно не знаю в чем проблема, возможно из-за несовместимости типов. Сами тесты не известны.
0
dmitrydm
0 / 0 / 0
Регистрация: 30.03.2015
Сообщений: 8
30.03.2015, 23:34 12
присоединяюсь к теме. очень интересная задача, хотелось бы получить результат
0
dmitrydm
0 / 0 / 0
Регистрация: 30.03.2015
Сообщений: 8
06.04.2015, 01:07 13
тоже делал эту задачу, но на 4-ом тесте мне выкинуло ошибку предела памяти (больше 3000кб)
прошу, подскажите как оптимизировать алгоритм, или укажите какой нужно использовать, что бы устранить эту ошибку! мой код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <string>
#include <iostream>
 
using namespace std;
 
struct node {                   // объявление структуры для дерева
    node *children[25];
};
 
int _tmain(int argc, _TCHAR* argv[]) {
    node *tree = new struct node;  // выделение памяти для дерева
    for (int i = 0; i < 25; ++i)             // обнуления веток
        tree->children[i] = NULL;
 
    node *current = tree;// присвоение текущей вершини - первой
 
    int N, cnt = 1;
    cin >> N; // считываем количество слов
    for (int i = 0; i < N; ++i) {
        string word;
        cin >> word; // считывание слова
        current = tree;
        for (int j = 0; j < word.length(); ++j) { // цикл по количеству символов в слове
            if (current->children[word[j] - 65] == NULL) {         //если элемент  под номером (код символа - 65) = NULL тогда
                current->children[word[j] - 65] = new struct node;// создаем новую ветку, выделяем память.
                current = current->children[word[j] - 65];  //переносим указатель текущей ветки на только, что "созданной ветке"
                cnt++;// увеличиваем счетчик вершин
                for (int m = 0; m < 25; ++m) {  //обнуления подветок только что созданной ветки
                    current->children[m] = NULL;
                }
            }
            else {        //если элемент под номером (код символа - 65)  не NULL тогда
                current = current->children[word[j] - 65];// переходим к следующей подветке
            }
        }
    }
    cout << cnt << endl;// вывод результата
    return 0;
}
Добавлено через 2 часа 8 минут
люди!! помогите как можно быстрее/срочнее/скорее... мне нужно все наладить до 7-8 апреля
0
igorrr37
1867 / 1483 / 751
Регистрация: 21.12.2010
Сообщений: 2,473
Записей в блоге: 11
07.04.2015, 15:39 14
через деревья
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <vector>
#include <string>
 
class Graph
{
public:
    Graph() : root(new Node(0)) {}
    void push(std::string const& rhs)
    {
        root->push(rhs);
    }
    int count() const
    {
        return root->count();
    }
    ~Graph()
    {
        delete root; root = 0;
    }
private:
    struct Node
    {
        Node(char const rhs) : c(rhs){}
        void push(std::string const& rhs)
        {
            int j;
            for(j = 0; j < vec.size(); ++j)
            {
                if(vec[j]->c == rhs[0]) break;
            }
            if(j == vec.size())
            {
                vec.push_back(new Node(rhs[0]));
                if(rhs.size() > 1) vec.back()->push(rhs.substr(1));
            }
            else if(rhs.size() > 1) vec[j]->push(rhs.substr(1));
        }
        int count() const
        {
            int res = 1;
            for(int i = 0; i < vec.size(); ++i)
            {
                res += vec[i]->count();
            }
            return res;
        }
        ~Node()
        {
            for(int i = 0; i < vec.size(); ++i)
            {
                delete vec[i]; vec[i] = 0;
            }
        }
 
        char c;
        std::vector<Node*> vec;
    };
 
    Node* root;
 
    Graph(Graph const&);
    Graph& operator=(Graph);
};
 
int main()
{
    Graph g;
 
    g.push("cat");
    g.push("more");
    g.push("car");
    g.push("clear");
 
    std::cout << g.count() << "\n\n";
    return 0;
}
0
07.04.2015, 15:39
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.04.2015, 15:39

Задача на графы
Помогите, пожалуйста, дана задача Произвести обход графа, начиная от данной...

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

Задача про графы
помогите если не сложно Тексты нужно переписывать в тело сообщения!


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru