Форум программистов, компьютерный форум CyberForum.ru

Можно ли из букв слова X составить слово Y? - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 5.00
lesya21
0 / 0 / 0
Регистрация: 26.11.2011
Сообщений: 18
02.12.2011, 19:04     Можно ли из букв слова X составить слово Y? #1
проверьте , можно ли из букв слова Х составить слово У.Пожалуйста помогите , вобще не понимаю как это делать(
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.12.2011, 19:04     Можно ли из букв слова X составить слово Y?
Посмотрите здесь:

Ввести строку и слово. Вывести те слова, которые не содержат букв, входящих в слово (через <stdio.h>) C++
C++ Ввести строку и слово. Вывести те слова, которые не содержат букв, входящих в слово.
C++ Составить слово из букв A, B, C
Проверить, можно ли из данных букв составить заданное слово S C++
C++ Программа, которая проверяет, можно ли введенное с клавиатуры слово (stroka_2) составить из букв исходного слова
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Deviaphan
02.12.2011, 19:06
  #2

Не по теме:

ХУ знает. Наверное можно.

AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
02.12.2011, 19:11     Можно ли из букв слова X составить слово Y? #3
Алгоритм:
Считываете две строки, пробегаетесь по элементам первой строки:
Если элемент первой строки найдет во второй строке удалить элемент во второй строке.

В конце, если 2 строка пуста, делаете выводы.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.12.2011, 19:13     Можно ли из букв слова X составить слово Y? #4
AncinetHero, ваш алгоритм рабочий, но его сложность O(mn), где m и n - длины соответствующих строк. Можно за O(m+n) шагов все сделать)
dyosick
 Аватар для dyosick
61 / 61 / 6
Регистрация: 25.08.2008
Сообщений: 178
02.12.2011, 19:16     Можно ли из букв слова X составить слово Y? #5
Выношу на обсуждение следующий вариант:

К примеру, есть слово "маракама" - это Х, составляем частотный словарь ():
а - 4 (число повторений буквы в слове)
к - 1
м - 2
р - 1
Надо получить слово "мама" - это Y, поступаем аналогично:
а - 2
м - 2

Ну, а дальше сверяем словарь Y со словарем Х.
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
02.12.2011, 19:16     Можно ли из букв слова X составить слово Y? #6
Мой уровень в программировании еще низок, я согласен =(
Deviaphan
Делаю внезапно и красиво
Эксперт C++
 Аватар для Deviaphan
1283 / 1217 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.12.2011, 19:17     Можно ли из букв слова X составить слово Y? #7
Цитата Сообщение от Thinker Посмотреть сообщение
Можно за m+n шагов все сделать)
Я только за m+n+255 придумал. Если строки короткие, то 255 отбрасывать не буду из сложности.)
Но это для ASCI строк, разумеется.
go
Эксперт C++
3582 / 1362 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
02.12.2011, 19:22     Можно ли из букв слова X составить слово Y? #8
Цитата Сообщение от Thinker Посмотреть сообщение
Можно за O(m+n) шагов все сделать)
Без сортировок?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.12.2011, 19:28     Можно ли из букв слова X составить слово Y? #9
Сообщение было отмечено автором темы, экспертом или модератором как ответ
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<stdio.h>
#include<string.h>
int Check(char *s, char *t)
{
   int i, count[256] = {0};
   while(*s)
      ++count[*s++];
   while(*t && --count[*t++] >= 0)
      ;
   return *t == '\0';
}
 
int main()
{
    char x[1024], y[1024];
    fgets(x, 1024, stdin);
    fgets(y, 1024, stdin);
    printf("%s\n", Check(x, y) ? "yes" : "no");
    return 0;
}
Добавлено через 46 секунд
Цитата Сообщение от go Посмотреть сообщение
Без сортировок?
конечно)

Добавлено через 31 секунду
Цитата Сообщение от Deviaphan Посмотреть сообщение
Я только за m+n+255 придумал. Если строки короткие, то 255 отбрасывать не буду из сложности.)
Но это для ASCI строк, разумеется.
Именно не более m+n шагов)

Добавлено через 2 минуты
Цитата Сообщение от AncinetHero Посмотреть сообщение
Мой уровень в программировании еще низок, я согласен =(
Это не в обиду было сказано, а для того, чтобы дать понять, что можно улучшить алгоритм)
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
02.12.2011, 20:21     Можно ли из букв слова X составить слово Y? #10
Thinker, красиво

Без понятия, что там со сложностью, и очевидно медленнее, за то туманно и запутанно:
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <string.h>
    
int main(void){
    char wrd1[BUFSIZ], wrd2[BUFSIZ];
    
    while ( printf("First: ") && scanf("%s", wrd1) == 1 && printf("Second: ") && scanf("%s", wrd2) == 1 ){
        char * p, * p1, * p2;
        for ( p = wrd2; *p; ++p ){
            if ( ( p2 = strchr(wrd2, *p) ) == p ){
                if ( p1 = strchr(wrd1, *p) )
                    while ( ( p2 = strchr(p2+1, *p) ) && ( p1 = strchr(p1+1, *p) ) )
                        ;
                if ( ! p1 )
                    break;
            }
        }
        printf("%s\n", ( *p ) ? "No way!" : "Oh Yeah!");
    }
    
    return 0;
}
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.12.2011, 22:47     Можно ли из букв слова X составить слово Y? #11
Цитата Сообщение от easybudda Посмотреть сообщение
Thinker, красиво

Не по теме:

спасибо



Не по теме:

подозрение, что быстрее уже нельзя. имеется ввиду, что памятью дополнительной можно пользоваться

easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9373 / 5423 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
02.12.2011, 23:10     Можно ли из букв слова X составить слово Y? #12
Цитата Сообщение от Thinker Посмотреть сообщение
подозрение, что быстрее уже нельзя. имеется ввиду, что памятью дополнительной можно пользоваться
Ну есть ещё момент. Мой мутный алгоритм, если первая же буква из второго слова не найдётся в первом, дальше и проверять ничего не будет...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2011, 23:17     Можно ли из букв слова X составить слово Y?
Еще ссылки по теме:

C++ Определить, можно ли из букв одного слова составить другое
C++ Получить из слова А, вычеркиванием некоторого количества букв, слово Б
Комбинаторика. Вывести все слова, которые можно составить из данных букв C++

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

Или воспользуйтесь поиском по форуму:
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.12.2011, 23:17     Можно ли из букв слова X составить слово Y? #13
Цитата Сообщение от easybudda Посмотреть сообщение
Ну есть ещё момент. Мой мутный алгоритм, если первая же буква из второго слова не найдётся в первом, дальше и проверять ничего не будет...
Имеется в виду средний случай
кстати, у меня так же. Если в строке y первая буква не содержится в строке x, то алгоритм тут же останавливается, поэтому число шагов оценивается двойным неравенством:
http://www.cyberforum.ru/cgi-bin/latex.cgi?m+1 \leq W(m,n) \leq m + n, где m = strlen(x), n=strlen(y)
Yandex
Объявления
02.12.2011, 23:17     Можно ли из букв слова X составить слово Y?
Ответ Создать тему
Опции темы

Текущее время: 18:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru