0

Задание: в строку подается начальное слово(word), затем подается цепочка слов(words, столбиком, в строку заполняется до первого пробела), по главному слову построить самаую длинную цепочку из words. Слова подбираются так: по последний букве предыдущего слова, слова не должны повторяться. Я понимаю что тут алгоритм с полным перебором с возратом + метод ветвей и границ. Я написала функцию поиска в слова в строке, "удаление" слова в строке если есть оно(путем перезаписи), создала матрицу где хранитсяс( первая буква, последняя, само слово(words)) Но как реализовать алгорим не пойму....

#include <stdio.h>
#include <string.h >
#pragma warning(disable : 4996)
#define N 100000
unsigned char matr_words[N][3][81];
char word[N], words[N], ABC_words[N];
char words_v2[N];

int find(char* word, char* words) //сам код по поиску слово word в строке words
{
    char* istr;
    istr = strstr(words, word);
    int t = istr - words;
    if (istr == NULL) return -1;
    else return t;
}
int popkf(int alllenn) { //тут по сути должен был алгоритм по нахождении цепи но вообще не понимаю как релизовывать его 
    
}

int main() {
    int wd = 0, ws = 0, kol_enter = 0, kol_strok = 0;
    scanf("%[^' ']s", word); while (getchar() != ' ');  //здесь будеть вводиться значения до пробела 
    scanf("%[^' ']s", words); while (getchar() != ' ');
    wd = strlen(words);
    ws = strlen(word);


    int slova = 0, alllenn = 0;
    for (int i = 0; i < wd; i++) {                   //здесь считается сколько слов||строк в строке words 
        if (words[i] == '\n') kol_enter++;
        kol_strok = kol_enter + 1;
        if (words[i] != '\n') slova++;
    }
    alllenn = slova + kol_enter - 1;                 //alllenn - общее число бкув + ентеров

    int sym_word = 0;                                
    for (int i = 0; i < ws; i++) {           // подсчет символов в  word 
        if (word[i] != '\n') sym_word++;
    }
    
    int n = 0;
    char* w;
    int y = find(word, words); // y - начало делитного слова
    int wdw = sym_word + 1;  //WDW(weight delite word) -
    int new_len_words = alllenn - wdw;    //new_len_words-длина без вычеркнутового слова
    if (y != -1) {   // сама функция перезаписи если функция find вернет число не равное -1 (-1 ознаяет что повторения слова в words нет) то будет перезапись в другой массив
        for (int i = 0; i < y; i++) {
            words_v2[i] = words[i];
        }
        for (int i = y; i < (alllenn - wdw + 1); i++) words_v2[i] = words[i + wdw];
        for (int i = 0; i < new_len_words + 1; i++) {
            printf("%c", words_v2[i]);
        }
        w = strtok(words_v2, "\n");   // для записи матрицы matr_words 
    }
    else {
        w = strtok(words, "\n");
    }

    unsigned char matr_word[1][80];
    char b = 0;
    for (int i = 0; i < sym_word; i++) { //последняя буква word
        b = word[i];
    }
    for (int i = 0; i <= sym_word; i++) { //заносим в матрицу последнее букву ключегового слова
        matr_word[0][0] = b;
        matr_word[0][i + 1] = word[i];
    }
    printf("\n");



    while (w != NULL) //сама запись wprds в матрицу 
    {
        matr_words[n][0][0] = w[0];
        matr_words[n][0][1] = 0;//конец строки
        matr_words[n][1][0] = w[strlen(w) - 1];
        matr_words[n][1][1] = 0; //конец строки
        strcpy(matr_words[n][2], w);
        n++;

        w = strtok(NULL, "\n");
    }
    
    



    return 0;

}
3
  • Вы можете объяснить по-другому, какому правилу должна удовлетворять цепочка слов? То, что у вас написано не очень-то и осмысленно. Или просто приведите пример входных-выходных данных
    – EzikBro
    19 янв 2022 в 14:08
  • @EzikBro Как игра в города: каждое следующее слово начинается с последней буквы предыдущего 19 янв 2022 в 14:11
  • @EzikBro Необходимо построить цепочку из слов максимальной длины по следующему принципу. П последней о букве с начального лова выбирается следующее слово, которое на неё начинается и так далее. Запрещено повторять слова, которые уже попали в цепочку.
    – nineirl
    19 янв 2022 в 14:17

1 ответ 1

0

К сожалению, C я по сути не знаю, поэтому я написал примерный код на плюсах. Под кодом объяснение самого алгоритма.

void get_longest_path(vector<string>& words, vector<int>& current, vector<bool>& used, vector<int>& longest) 
{
    for (int i = 0; i < words.size(); i++)
    {
        if (!used[i] && words[i].front() == words[current.back()].back())
        {
            used[i] = true;
            current.push_back(i);

            get_longest_path(words, current, used, longest);

            current.pop_back();
            used[i] = false;
        }
    }

    if (current.size() > longest.size())
        longest = current;
}

int main()
{
    vector<string> words; 
    string temp;
    while (cin >> temp)
        words.push_back(temp); // words[0] содержит стартовое слово

    vector<int> longest;
    vector<bool> used(words.size());
    vector<int> current;
    used[0] = true; current.push_back(0);

    get_longest_path(words, current, used, longest);
    for (auto i : longest)
        cout << words[i] << '\n';

    return 0;
}

Окей, пусть у нас есть массив слов words (у меня стартовое слово - первое слово из этого массива, но это не важно). Давайте заведем пустые массивы current и longest, обозначающие соответственно текущий и длиннейший путь. Также будем использовать булев массив used, который для каждого слово хранит, содержится ли это слово в текущем пути.

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

Стоит отметить важную оптимизацию, которую вы заметили и сами: слова стоит сгруппировать по начальной букве. Тогда вместо того, чтобы перебирать все слова каждый раз, мы в среднем случае будем перебирать только 1/26 их часть (но конечно же можно подобрать тест, в котором это совершенно не поможет).

Существует еще несколько оптимизаций, основанных на запоминании частичных результатов и использовании их в будущем. Я не уверен, что это даст большой выигрыш, но на достаточно больших блоках слов может оказаться полезным.

1
  • спасибо большое! сейчас начну разбираться
    – nineirl
    19 янв 2022 в 15:32

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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