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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 5.00
lesya21
0 / 0 / 0
Регистрация: 26.11.2011
Сообщений: 18
#1

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

02.12.2011, 19:04. Просмотров 1957. Ответов 12
Метки нет (Все метки)

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

Программа, проверяющая, можно ли введенное с клавиатуры слово составить из букв исходного слова - C++
вводятся с клавиатуры предложение, затем слово, которое надо составить из букв первого предложения. проверить можно ли составить. программа...

Программа, которая проверяет, можно ли введенное с клавиатуры слово (stroka_2) составить из букв исходного слова - C++
#include<stdio.h> #include<string.h> #include<locale.h> int Check(char *s, char *t) { int i, count = {0}; while(*s) ...

Проверить можно ли из букв составить слово - C++
Вводится число n. Далее вводится словарь из n букв. Буквы могут повторяться.Далее вводится слово.Нужно проверить можно ли из букв из...

Можно ли из букв, входящих в одно слово, составить другое - C++
Даны два слова. Составить программу проверки, можно ли из букв, входящих в одно слово, составить другое (каждая буква используется только...

Проверить, можно ли из данных букв составить заданное слово S - C++
Люди, помогите решить задачу: Двумерный массив М N содержит некоторые буквы русского алфавита, расположенные в произвольном порядке....

Проверить, можно ли из данных символов (букв) составить заданное слово (предложение) - C++
Здравствуйте! Помогите пожалуйста с идеей решение, не знаю с чего начать: Проверить, можно ли из данных символов (букв) составить...

12
Deviaphan
02.12.2011, 19:06
  #2

Не по теме:

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

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

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

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

Ну, а дальше сверяем словарь Y со словарем Х.
0
AncinetHero
49 / 49 / 3
Регистрация: 22.05.2011
Сообщений: 326
02.12.2011, 19:16 #6
Мой уровень в программировании еще низок, я согласен =(
0
Deviaphan
Делаю внезапно и красиво
Эксперт С++
1305 / 1220 / 50
Регистрация: 22.03.2011
Сообщений: 3,744
02.12.2011, 19:17 #7
Цитата Сообщение от Thinker Посмотреть сообщение
Можно за m+n шагов все сделать)
Я только за m+n+255 придумал. Если строки короткие, то 255 отбрасывать не буду из сложности.)
Но это для ASCI строк, разумеется.
0
go
Эксперт С++
3586 / 1366 / 128
Регистрация: 16.04.2009
Сообщений: 4,528
02.12.2011, 19:22 #8
Цитата Сообщение от Thinker Посмотреть сообщение
Можно за O(m+n) шагов все сделать)
Без сортировок?
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.12.2011, 19:28 #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 Посмотреть сообщение
Мой уровень в программировании еще низок, я согласен =(
Это не в обиду было сказано, а для того, чтобы дать понять, что можно улучшить алгоритм)
6
easybudda
Модератор
Эксперт CЭксперт С++
9683 / 5633 / 956
Регистрация: 25.07.2009
Сообщений: 10,819
02.12.2011, 20:21 #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;
}
1
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.12.2011, 22:47 #11
Цитата Сообщение от easybudda Посмотреть сообщение
Thinker, красиво

Не по теме:

спасибо



Не по теме:

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

0
easybudda
Модератор
Эксперт CЭксперт С++
9683 / 5633 / 956
Регистрация: 25.07.2009
Сообщений: 10,819
02.12.2011, 23:10 #12
Цитата Сообщение от Thinker Посмотреть сообщение
подозрение, что быстрее уже нельзя. имеется ввиду, что памятью дополнительной можно пользоваться
Ну есть ещё момент. Мой мутный алгоритм, если первая же буква из второго слова не найдётся в первом, дальше и проверять ничего не будет...
0
Thinker
Эксперт С++
4228 / 2202 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.12.2011, 23:17 #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)
0
02.12.2011, 23:17
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
02.12.2011, 23:17
Привет! Вот еще темы с ответами:

Определить, можно ли из букв одного слова составить другое - C++
Даны два слова, состоящие из одинакового количества букв(количество букв известно заранее). Определить, можно ли из букв одного слова,...

Определить сколько слов можно составить из букв прочитанного слова - C++
Прошу помощи, задание : Считываю слово с файла, например, abb,нужно посчитать, сколько других слов можно из него составить и вывести. Т.е....

Комбинаторика. Вывести все слова, которые можно составить из данных букв - C++
Всем привет. Вобщем. Есть такая игра, в которой дают 4 картинки, которые можно описать одним словом, длину этого слова и набор букв из...

Ввести строку и слово. Вывести те слова, которые не содержат букв, входящих в слово. - C++
Ребят помогите плииизз... только мне сказали через стандартную библиотеку Добавлено через 1 минуту Ах да и если не сложно, пояснения...


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

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

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