VPF::Найти самое длинное слово (си) - Форум программистов

Bony

Дата 16.12.2005, 13:58 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 16.12.2005
Где: Новосибирск

Репутация: нет
Всего: нет

Задача:

Найти самое длинное общее слово двух заданных предложений.

Язык Си, просто Си.

En_t_end

Дата 16.12.2005, 15:35 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2074
Регистрация: 4.12.2004

Репутация: 2
Всего: 20

Код


char *readword(const char *Str, unsigned &lastbyte, char *buffer)
{
if(lastbyte >= strlen(Str)) return NULL;
unsigned i = 0;
while((buffer[i++] = Str[lastbyte++]) != ' ');
buffer[i-2] = '\0';
return buffer;
}
void main()
{
char *Str1;
char *Str2;
unsigned i =  0;
unsigned lb1 = 0;
char LastLongWord[MAX_WORD];
char word1[MAX_WORD], word2[MAX_WORD];
while(readword(Str1, lb1, word1) != NULL)
{
unsigned lb2 = 0;
while(readword(Str2, lb2, word2) != NULL)
{
if(strcmpi(word1, word2) == 0 && strlen(word1) > i)
{
strcpy(LastLongWord, word1);
i = strlen(word1);
}
}
}
}

Что типа этого, писал быстро поэтому 1. Коряво сделал добывание слова из предложения в функции readword - возможен выход за границы массива. 2. Не сделал пару проверок.
Но алгоритм вроде верный. ЗЫ + не проверял.
Добавлено @ 15:40
Короче скорее всего код выше бред, но алгоритм таков. Выбирай одно слово из первого предложения, далее перебирай все выбранные слова из второго предложения, пока не найдешь такое же или не подойдешь к концу второго предложения, если найдешь похожее слово, то получай его длину, сравнивай с имеющимся рекордом и если оно выше рекорда записывай слово в буффер, который затем в конце работы будешь показывать. Далее выбирай следующее слово из первого предложения, опять прокатывайся по второму и так далее пока не достигнешь конца первого.

Это сообщение отредактировал(а) En_t_end - 16.12.2005, 16:00

Bony

Дата 16.12.2005, 16:04 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 16.12.2005
Где: Новосибирск

Репутация: нет
Всего: нет

Спасибо. С алгорится я все понял!
Если не затруднит можно код, ну если нет так нет

Еще раз спасибо

En_t_end

Дата 16.12.2005, 17:18 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2074
Регистрация: 4.12.2004

Репутация: 2
Всего: 20

Bony
В моем коде нужно только исправить функцию readword, я точно не помню, но по-моему есть такая стандартная функция - умеет выдирать совокупность символов от и до определенного символа в нашем случае - это 32 символ, также нужно срезать запятые и точки + знаки восклицания и всевозможные символы, для этого достаточно просто воспользоваться функцией(станд.) для узнавания является ли данный символ буквой.

Bony

Дата 17.12.2005, 18:45 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 16.12.2005
Где: Новосибирск

Репутация: нет
Всего: нет

А для простого Си этот код потянет!!!

Bony

Дата 18.12.2005, 11:06 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 16.12.2005
Где: Новосибирск

Репутация: нет
Всего: нет

Есть несколько вопросов:
1. что делает и эта библиотечная функция strlen(Str))
2. buffer[i++] - это как?

En_t_end

Дата 18.12.2005, 19:12 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2074
Регистрация: 4.12.2004

Репутация: 2
Всего: 20

buffer[i++] - возвращает элемент с индексом i и после этого увеличивает i на единицу.
strlen возвращает длину строки оканчивающуюся нуль-терминатором, причем не включая его в возвращаемое значение.

Bony

Дата 20.12.2005, 15:45 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 16.12.2005
Где: Новосибирск

Репутация: нет
Всего: нет

En_t_end чет не пашет, ошибок много!!!

Dov

Дата 21.12.2005, 01:24 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Для простоты считаем, что:

Код

#include <stdio.h> 
#include <string.h>
   
int main()
{
    char  str1[]           = "qwer, qwe qwerty qwert";
    char  str2[]           = "asadf qwe asdf,  qwert asdfgh";
    char* word1;                                     // будем запоминать слова первой строки
    char* word2;                                     // и второй
    char* wordArr1[20];                              // сюда будем заносим слова первой строки
    char* wordArr2[20];                              // а сюда - второй
    int   ind1             = 0;                      // количество слов в первом массиве
    int   ind2             = 0;                      // и во втором
    int   maxLen           = 0;                      // здесь храним максимальную длину найденного слова
    int   out              = 0;                      // индекс слова с максимальной длиной
    int   i,
          j,
          len;                                       // длина найденного общего слова

    printf("str1: %s\n", str1);
    printf("str2: %s"  , str2);
    
    word1                  = strtok(str1, " ,");     // выделяем слово в первой строке
    wordArr1[ind1++]       = word1;                  // и заносим его в первый массив слов
    while(word1)                                     // пока в строке есть слова
    {
        word1              = strtok(NULL, " ,");     // выделяем слово ...
        wordArr1[ind1++]   = word1;                  // заносим ...
    }

    word2                  = strtok(str2, " ,");     // то же самое со второй строкой ...
    wordArr2[ind2++]       = word2;                  // ...  
    while(word2)                                     // ...
    {
        word2              = strtok(NULL, " ,");     // ...
        wordArr2[ind2++]   = word2;                  // ...
    }

    for(i = 0; i < ind1 - 1; i++)                    // в цикле идём по первой строке
    {
        for(j = 0; j < ind2 - 1; j++)                // и по второй 
        {
            if(!strcmp(wordArr2[j], wordArr1[i]))    // ищем одинаковые слова и если находим, то 
            {
                len        = strlen(wordArr1[i]);    // определяем длину найденного    слова
                if(len > maxLen)                     // и если она больше, чем максимальная, то
                {
                    maxLen = len;                    // запоминаем максимальную длину
                    out    = i;                      // и индекс найденного слова
                }
            }
        }
    } 

    printf("\n\nword: ");                            // вывод на экран
    if(out)
        puts(wordArr1[out]);                         // нашли слово
    else
        puts("not found");                           // или не нашли ничего

    return 0;
}

--------------------

Тут вечности запах томительный,
И свежие фрукты дешевые,
А климат у нас – изумительный,
И только соседи – #уевые.
Игорь Губерман.

Bony

Дата 21.12.2005, 18:22 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 16.12.2005
Где: Новосибирск

Репутация: нет
Всего: нет

Dov Спасибо огромное!!! Как мне благодорить тебя???

Может конечно я покажесь наглым, но не могу сделать чтоб самому предложения вводить, ошибки появляются (наверно потому что не сам код писал)!

И можно ли как нибудь на подпрограммы разбить???

Но как бы там ни было еще раз спасибо, спас мою шкуры!!! smile

Это сообщение отредактировал(а) Bony - 21.12.2005, 18:24

noBony

Дата 21.12.2005, 22:31 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Цитата

Есть несколько вопросов:
1. что делает и эта библиотечная функция strlen(Str))
2. buffer[i++] - это как?

Встречный вопрос :
1. Что такое ЯЗЫК ПРОГРАММИРОВАИЯ ???
2. А С/С++ ???

После ответа на эти вопросы (только честно)
оба твоих отпадают сразу .

Dov

Дата 21.12.2005, 22:35 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Цитата(Bony @ 21.12.2005, 18:22)

...не могу сделать чтоб самому предложения вводить...

Вот исправленная версия:

Код

#include <stdio.h> 
#include <string.h>
   
int main()
{
    char  str1[255];
    char  str2[255];
    char* word1;                                      // будем запоминать слова первой строки
    char* word2;                                      // и второй
    char* wordArr1[20];                               // сюда будем заносим слова первой строки
    char* wordArr2[20];                               // а сюда - второй
    int   ind1             =  0;                      // количество слов в первом массиве
    int   ind2             =  0;                      // и во втором
    int   maxLen           =  0;                      // здесь храним максимальную длину найденного слова
    int   out              = -1;                      // индекс слова с максимальной длиной
    int   i,
          j,
          len;                                        // длина найденного общего слова

    printf("Enter a string1: ");
    gets(str1);

    printf("Enter a string2: "); 
    gets(str2);
    
    word1                  = strtok(str1, " ,");     // выделяем слово в первой строке
    wordArr1[ind1++]       = word1;                  // и заносим его в первый массив слов
    while(word1)                                     // пока в строке есть слова
    {
        word1              = strtok(NULL, " ,");     // выделяем слово ...
        wordArr1[ind1++]   = word1;                  // заносим ...
    }

    word2                  = strtok(str2, " ,");     // то же самое со второй строкой ...
    wordArr2[ind2++]       = word2;                  // ...  
    while(word2)                                     // ...
    {
        word2              = strtok(NULL, " ,");     // ...
        wordArr2[ind2++]   = word2;                  // ...
    }

    for(i = 0; i < ind1 - 1; i++)                    // в цикле идём по первой строке
    {
        for(j = 0; j < ind2 - 1; j++)                // и по второй 
        {
            if(!strcmp(wordArr2[j], wordArr1[i]))    // ищем одинаковые слова и если находим, то 
            {
                len        = strlen(wordArr1[i]);    // определяем длину найденного    слова
                if(len > maxLen)                     // и если она больше, чем максимальная, то
                {
                    maxLen = len;                    // запоминаем максимальную длину
                    out    = i;                      // и индекс найденного слова
                }
            }
        }
    } 

    printf("\nword           : ");                   // вывод на экран
    if(out >= 0)
        puts(wordArr1[out]);                         // нашли слово
    else
        puts("not found");                           // или не нашли ничего

    return 0;
}

Цитата(Bony @ 21.12.2005, 18:22)

наверно потому что не сам код писал

Нет, потому, что плохо учишся. smile

Цитата(Bony @ 21.12.2005, 18:22)

И можно ли как нибудь на подпрограммы разбить???

Какие?
Что, конкретно, тебя интересует?

--------------------

noBony

Дата 21.12.2005, 22:44 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

for Dov

Цитата

wordArr1[ind1++] = word1;

а почему инкремент ( вначале проги ? ) к чему
лишние напряги (читай - лишние такты).
Почему не указать индекс явно ???

Dov

Дата 21.12.2005, 23:04 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Цитата(noBony @ 21.12.2005, 22:44)

for Dov

Цитата

wordArr1[ind1++] = word1;

а почему инкремент ( вначале проги ? ) к чему
лишние напряги (читай - лишние такты).
Почему не указать индекс явно ???

noBony, если есть что-нибудь умное сказать - скажи, а оффтопить мы и сами умеем. Вот человеку подпрограммы нужны, например. Помоги.

--------------------

noBony

Дата 21.12.2005, 23:35 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Я не понял суть задачи :

Цитата

Найти самое длинное общее слово

если слово общее - значит это одно и тоже слово.
Как они могут иметь разную длинну ???

Dov

Дата 21.12.2005, 23:50 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Цитата(noBony @ 21.12.2005, 23:35)

если слово общее - значит это одно и тоже слово.Как они могут иметь разную длинну ???

Общих слов может быть несколько. Нужно найти самое длинное из них.

--------------------

noBony

Дата 22.12.2005, 00:10 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

Общее слово - ХАЛЯВА.
strlen("Халява") == strlen("Халява") == 6;
В чём прикол ???

Dov

Дата 22.12.2005, 00:18 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Общих слов два (пейте, пиво).
самое длинное - пейте.

--------------------

noBony

Дата 22.12.2005, 00:22 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

насёт пива - в точку (на злобу дня).
А насчёт слов - общие по смыслу чтоли ???

Dov

Дата 22.12.2005, 00:27 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

noBony, вот ты гусь лапчатый. smile

Зараз як скажу хранцюзьке слово на иврите, одразу кобылою станэш.

--------------------

noBony

Дата 22.12.2005, 00:32 (ссылка)

(голосов: 0)

Загрузка ...

Unregistered

осёл!!!
Родину продал!!!
По-русски писать не можешь !!!
Давай мыло - сразимся на С\С++.

Dov

Дата 22.12.2005, 00:35 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

А шампуня тебе не дать

--------------------

Bony

Дата 22.12.2005, 13:13 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 16.12.2005
Где: Новосибирск

Репутация: нет
Всего: нет

Цитата

А насчёт слов - общие по смыслу чтоли ???

Ну ты чувак даешь????? Я чуть со смеху не опписался!!!

Dov

Цитата

Нет, потому, что плохо учишся.

Просто помимо программирования нужно еще и по трем математикам упевать чето понимать!
Но ни че потехоньку да по-маленьку, как нибудь на 2-ой семестр переберусь!!!

Цитата

Цитата (Bony @ 21.12.2005, 18:22)
И можно ли как нибудь на подпрограммы разбить???

Какие?
Что, конкретно, тебя интересует?

Прихоть нашего препода, использовать подпрограммы, в данном случае подпрограммы ввода, сравнения и т.д. Я понимаю глупо делать подпр. ввода, но можно сделать попр. сравнения!!

Dov

Дата 23.12.2005, 00:30 (ссылка)

(нет голосов)

Загрузка ...

аСинизатор

Профиль
Группа: Завсегдатай
Сообщений: 1721
Регистрация: 10.5.2003
Где: Эрец-Исраэль

Репутация: 50
Всего: 88

Bony, вот с подпрограммами, которые в С / С++ называются функциями. smile

Код

#include <stdio.h> 
#include <string.h>

void InputString  (char*  str);
int  FillArray    (char*  str, char** ar);
int  CompareWord  (char** ar1, char** ar2, int  size1, int size2);
void OutputWord   (char** ar , int    out);
   
int main()
{
    char  str1[255];
    char  str2[255];
    char* wordArr1[20];                               
    char* wordArr2[20];                               
    int   count1;
    int   count2;
    int   word;

    InputString(str1);
    InputString(str2);

    count1 = FillArray(str1, wordArr1);
    count2 = FillArray(str2, wordArr2);

    word   = CompareWord(wordArr1, wordArr2, count1, count2);

    OutputWord(wordArr1, word);

    return 0; 
}

void InputString(char* str)
{
    static int n = 0;

    printf("Enter a string%d: ", ++n);
    gets(str);    
}

int FillArray(char* str, char** ar)
{
    int   ind         = 0;
    char* seps        = " ,";                   // разделители
    char* word        = strtok(str, seps);

    ar[ind++]         = word;    
    while(word)                                     
    {
        word          = strtok(NULL, seps);     
        ar[ind++]     = word;                  
    } 

    return ind;
}

int CompareWord(char** ar1, char** ar2, int size1, int size2)
{
    int i,
        j,
        len,
        maxLen = 0,
        result = -1;

    for(i = 0; i < size1 - 1; i++)                    
        for(j = 0; j < size2 - 1; j++)                
            if(!strcmp(ar2[j], ar1[i]))    
            {
                len = strlen(ar1[i]);    
                if(len > maxLen)                     
                {
                    maxLen = len;                   
                    result = i; 
                    break;
                }
            }
    
    return result;
}

void OutputWord(char** ar, int out)
{
    printf("\nWord           : %s\n", out >= 0 ? ar[out] : "not found");                   
}

Это сообщение отредактировал(а) Dov - 23.12.2005, 02:08

--------------------

Bony

Дата 23.12.2005, 15:38 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 16.12.2005
Где: Новосибирск

Репутация: нет
Всего: нет

Благодорность моя не знает границ

И для ясности:

функции:

1. InputString - ввод предложений
2. FillArray - ввыдерка слова.
3. CompareWord - сравнение слов
4. OutputWord - ввывод слова

И последний наверно вопрос: вот *, тобишь указатель на чето там, на Х, а что значит **?

Это сообщение отредактировал(а) Bony - 23.12.2005, 15:44

Bony

Дата 25.12.2005, 11:52 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 16.12.2005
Где: Новосибирск

Репутация: нет
Всего: нет

Чем в данном коде являются:

char **ar
char **ar1
char **ar2

Это сообщение отредактировал(а) Bony - 25.12.2005, 12:02

En_t_end

Дата 25.12.2005, 12:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2074
Регистрация: 4.12.2004

Репутация: 2
Всего: 20

Bony
Массивы указателей.

Bony

Дата 25.12.2005, 18:47 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 16.12.2005
Где: Новосибирск

Репутация: нет
Всего: нет

О как!! Массивы указателей! А цель их какая?

En_t_end

Дата 25.12.2005, 18:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2074
Регистрация: 4.12.2004

Репутация: 2
Всего: 20

Bony
В данном случае они хранят слова.
Если тебе известно char - символ, а char[] - несколько символов, поэтому чтобы хранить слова нужно иметь несколько char[].
Чтобы иметь несколько char[] можно сделать так: char[][].

Bony

Дата 25.12.2005, 18:57 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 21
Регистрация: 16.12.2005
Где: Новосибирск

Репутация: нет
Всего: нет

Цитата(En_t_end @ 25.12.2005, 18:51)

Чтобы иметь несколько char[] можно сделать так: char[][].

А можно ** так что ли?

En_t_end

Дата 27.12.2005, 07:19 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Участник Клуба
Сообщений: 2074
Регистрация: 4.12.2004

Репутация: 2
Всего: 20

Bony
char** some; - это всего лишь указатель на двумерный массив. Выделение памяти идет в стеке или в куче. В функциях же этот указатель используется для получения адресса на нужный нам массив, чтобы работать с ним, не копируя его содержимое в другую область памяти.
char someS[20][13] - обьявление двумерного массива, с практически мгновенным выделением памяти в стеке.
char** some; - обьявление указателя на двумерный массив, без выделения памяти. Может применятся для хранения адресса двумерного массива, того же someS. Или же ты можешь сам выделить память, используя менеджер кучи:
some = new char*[20];
for(unsigned i = 0; i<20;i++) some[i] = new char[13];

Отчистка области кучи, занятой под some:
for(unsigned i = 0; i<20;i++) delete[] some[i];
delete[] some;

Обращаясь к двумерному массиву, мы работаем по тому же принципу, что и с обычным массивом символов.То есть используя оператор [] - разыменования для доступа к членам массива по определенному индексу. Не забывая, что массив имеет ещё одну вложенность.

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »