Форум программистов [Powered by Invision Power Board]

Код


//Собственно алгоритм работы.
//
//Получаем наши слова. Затем заполним вспомогательный массив русскими буквами,
//каждой букве будет соответствовать некоторое количество слов, в которых она
//есть, номера этих слов, количество совпадений по каждому слову и сами позиции,
//в которых есть совпадение.
//
//Далее. Пробегаемся по всем словам в поисках слова, где больше всего пересечений.
//Это делает функция findMaxCrossedWord(). Его ставим как основное по горизонтали.
//Затем ищем одну из двух удобных позиций (с разным шагом), в какой из них больше
//несмежных пересечений, ту берем за основу, пристраиваем к ней по вертикали все
//наши слова.
//
//Что значит пристраиваем? То есть берем слово, по вертикали его рисуем
//в нужном месте, потом пробегаемся по всем буквам и в том месте, где это слово
//имело пересечения, убираем его оттуда (просто зануляем строку), попутно уменьшая
//количество совпадений. В позицию ПИШЕМ -1, чтобы потом ее не трогать при пересчете.
//Также при этом проходе убираем и основное слово, к которому идет пристыковка. После
//всех этих манипуляций снова ищем максимальные пересечения со словами, но уже
//с учетом удаленных элементов.

Код


#include <stdio.h>
#include <string.h>
#include <conio.h>
#include <alloc.h>
#include <mem.h>
//#include <graph.h>

//Собственно алгоритм работы.
//
//Получаем наши слова. Затем заполним вспомогательный массив русскими буквами,
//каждой букве будет соответствовать некоторое количество слов, в которых она
//есть, номера этих слов, количество совпадений по каждому слову и сами позиции,
//в которых есть совпадение.
//
//Далее. Пробегаемся по всем словам в поисках слова, где больше всего пересечений.
//Это делает функция findMaxCrossedWord(). Его ставим как основное по горизонтали.
//Затем ищем одну из двух удобных позиций (с разным шагом), в какой из них больше
//несмежных пересечений, ту берем за основу, пристраиваем к ней по вертикали все
//наши слова.
//
//Что значит пристраиваем? То есть берем слово, по вертикали его рисуем
//в нужном месте, потом пробегаемся по всем буквам и в том месте, где это слово
//имело пересечения, убираем его оттуда (просто зануляем строку), попутно уменьшая
//количество совпадений. В позицию ПИШЕМ -1, чтобы потом ее не трогать при пересчете.
//Также при этом проходе убираем и основное слово, к которому идет пристыковка. После
//всех этих манипуляций снова ищем максимальные пересечения со словами, но уже
//с учетом удаленных элементов.

typedef struct {
    char Letter;
    int wCount;
    int pCount;
    int *words;
    int *positions;
} TLetter;

typedef struct {
    char *word;
    int *allow;
    int index;
} TWord;

const LMAX = 33;

//-----------------------------------------------------------------------------
//ищет букву в массиве букв
TLetter findLetter(TLetter *Letters, char letter);
//считает пересечения по слову
int countCrossesOfWord(TLetter *Letters, int index, TWord *words);
//ищет максимально пересеченное слово, вернет его индекс
int findMaxCrossedWord(TLetter *Letters, TWord *words, int n);
//void delWord(char *mainWord, char *word, int pos,

//GRAPHIC MODE
const sq_x = 4;
const sq_y = 4;
void drawSquare(int x, int y);
void drawWordGrid(char *word, int horizontal);
//-----------------------------------------------------------------------------

TLetter findLetter(TLetter *Letters, char letter)
{
    int i;
    for (i=0; i<LMAX; i++)
      if (Letters[i].Letter == letter)
        return Letters[i];

    return Letters[0];
}

int findMaxCrossedWord(TLetter *Letters, TWord *words, int n)
{
    int i;
    int memCount;
    int count;
    int memIndex;

    for (i=0, memCount=0, memIndex=-1; i<n; i++)
    {
        count = countCrossesOfWord(Letters, i, words);
        if (count > memCount)
        {
            memCount = count;
            memIndex = i;
        }
    }

    return memIndex;
}

int countCrossesOfWord(TLetter *Letters, int index, TWord *words)
{
    //надо посчитать количество пересечений других слов с данным.
    //как сделать? Проходим по слову, берем каждую его букву, ищем
    //ее в нашем массиве буковок через findLetter(). Поиск производим
    //с некоторым шагом, изначально равным 0, если нашли совпадение с буквой
    // - ставим шаг в 1, и сбросим его на следующем шаге. Это обеспечит
    //отбрасывание случаев, когда совпадение букв может быть одно за другим
    //(смежные совпадения не приветствуются).
    int i, j;
    int step;
    int memory;
    TLetter Letter;
    int result = 0;

    for (i=0, step=0; i<strlen(words[index].word); i++) //идем по слову
    {
        if (step)
        {
            step--;
            continue;
        }

        //пройдемся по всем словам в этой букве в поисках нашего
        Letter = findLetter(Letters, words[index].word[i]);
        for (j=0; j<Letter.wCount; j++)
        {
            if (stricmp(words[Letter.words[j]].word, words[index].word) == 0)
            {
                result++; //нашли наше слово - увеличим количество совпадений
                step++;
            }
        }
    }
    memory = result;
    //повторим то же самое второй раз, но с другим начальным шагом
    result = 0;
    for (i=0, step=1; i<strlen(words[index].word); i++) //идем по слову
    {
        if ((i > 0) && (step))
        {
            step--;
            continue;
        }

        //пройдемся по всем словам в этой букве в поисках нашего
        Letter = findLetter(Letters, words[index].word[i]);
        for (j=0; j<Letter.wCount; j++)
        {
            if (stricmp(words[Letter.words[j]].word, words[index].word) == 0)
            {
                result++; //нашли наше слово - увеличим количество совпадений
                step++;
            }
        }
    }

    if (result > memory)
    {
        return result;
    }
    else
    {
        return memory;
    }
}

void drawSquare(int x, int y)
{

}

void main()
{
    int wCount; //количество слов
    int i, j; //счетчики
    TWord *Words; //главный массив со словами
    TLetter Letters[33]; //массив с русскими буквами (160-175, 224-239)
    int rCode; //код русской буквы (нужен при заполнении Letters)
    int wMaxLen; //макс. длина слова
    int maxCrossedIdx; //индекс максимально пересеченного слова

    printf("Enter count of words: ");
    scanf("%d", &wCount);
    Words = (TWord *)malloc(sizeof(TWord)*wCount);
    for (i=0; i<wCount; i++)
    {
      Words[i].index = i;
      Words[i].word = (char *)malloc(sizeof(char)*51); //max 50 symbols
    }

    //заполняем массив букв
    rCode = 160;
    for (i=0; i<LMAX; i++)
    {
        Letters[i].Letter = rCode;
        if (rCode == 175)
            rCode = 223;

        Letters[i].wCount = 0;
        Letters[i].pCount = 0;
        Letters[i].words = (int *)malloc(sizeof(int) * wCount);
        rCode++;
    }

    //получаем слова
    wMaxLen = 0; //попутно считаем максимальную длину слова
    for (i=0; i<wCount; i++)
    {
        printf("Word %d: ", i+1);
        scanf("%s", Words[i].word);
        //пока что все позиции в слове доступны для анализа, покажем это
        Words[i].allow = (int *)malloc(sizeof(int) * strlen(Words[i].word));
        for (j=0; j<strlen(Words[i].word); j++)
          Words[i].allow[j] = 1;

        //и еще пропишем такого же размера массив в буквах
        Letters[i].positions = (int *)malloc(sizeof(int)*strlen(Words[i].word));
    }

    /* sample of memory dump
       -----------------------
       words:
           [0]: "безымянный"
           [1]: "игра"
                             2 words|1w: 10 letters|2w: 4 letters
       letters:               vvvvv    vvvvvvvvvv    vvvv
           [0]: 'а', 0, 0, { (0, 0), ("0000000000", "0000") }
           [1]: 'б', 0, 0, { (0, 0), ("0000000000", "0000") }
    */

//    maxCrossedIdx = findMaxCrossedWord(letters, words, wCount);
}