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

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

Войти
Регистрация
Восстановить пароль
 
Zyfchik
0 / 0 / 0
Регистрация: 14.09.2012
Сообщений: 10
#1

Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? - C++

18.02.2013, 14:25. Просмотров 746. Ответов 9
Метки нет (Все метки)

F. Заданы две строки А и В. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми?
Выведите "Yes", если можно переставить буквы в одном из слов, чтобы слова стали одинаковыми или "No" иначе.
F.in
bca
cba
F.out Yes
F.in
ada
dada
F.out No
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.02.2013, 14:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Заданы две строки. Можно ли переставить буквы в одном из слов так, чтобы слова стали одинаковыми? (C++):

Заданы две символьные строки. Все ли буквы первого слова встречаются во втором - C++
проблема вот с этим "Все ли буквы первого слова встречаются во втором." не могу организовать цикл мозгов не хватает)) однокурсник пытался...

Файловый ввод/вывод. Во всех словах строки переставить все входящие буквы «а» в начало слова, а буквы «я» – в конец - C++
Здравствуйте! Помогите, пожалуйста, составить программу, которая считывает из текстового файла input.txt строку символов S.Во всех словах...

Переставить буквы в строке так, чтобы первой буквой была гласная - C++
Есть строка "acomabugopabt" Сколько есть различных способов переставить буквы в этой строке так, чтобы первой буквой была...

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

Проверить, можно ли переставить элементы массива так, чтобы получилась арифметическая прогрессия - C++
Реализовать выполнение заданных действий над одномерным массивом. Число элементов массива задаётся пользователем. Элементы могут...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
18.02.2013, 16:39 #2
Например, упорядочить подсчетом, раз уж только "буквы", и сравнить получившиеся строки. В качестве оптимизации, если строки не равны по длине, вывести No.
akk
44 / 44 / 7
Регистрация: 28.01.2012
Сообщений: 341
18.02.2013, 16:43 #3
Можно сделать лексикографический анализ, т. е. одно первое слово распарсить в бинарное дерево, а потом с обходом его сравнить символы со вторым словом. Но программировать это для меня еще через чур сложно
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
18.02.2013, 16:53 #4
Цитата Сообщение от akk Посмотреть сообщение
Можно сделать лексикографический анализ, т. е. одно первое слово распарсить в бинарное дерево, а потом с обходом его сравнить символы со вторым словом. Но программировать это для меня еще через чур сложно
Сложное решение, будет затруднительно разобраться с повторяющимися элементами.
Вот если обе строки распарсить... Но тогда от сортировки это будет отличаться только более сложным алгоритмом.
akk
44 / 44 / 7
Регистрация: 28.01.2012
Сообщений: 341
18.02.2013, 17:03 #5
Цитата Сообщение от lemegeton Посмотреть сообщение
будет затруднительно разобраться с повторяющимися элементами
а по-моему это тут не важно, главное чтобы
Цитата Сообщение от Zyfchik Посмотреть сообщение
можно переставить буквы в одном из слов, чтобы слова стали одинаковыми
если надо, и подойдет такой вариант, то могу кинуть код обходов бинарных деревьев. только он на Си, а не на Си++
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
18.02.2013, 17:07 #6
Цитата Сообщение от akk Посмотреть сообщение
а по-моему это тут не важно, главное чтобы
Прикиньте, как будут разбираться строки aaaab и bbbba. Обход должен учитывать повторения, причем как в разобранной строке, так и в не разобранной.
akk
44 / 44 / 7
Регистрация: 28.01.2012
Сообщений: 341
18.02.2013, 17:18 #7
Цитата Сообщение от lemegeton Посмотреть сообщение
Прикиньте, как будут разбираться строки aaaab и bbbba.
Так вроде в структуре дерева есть еще переменная count (счетчик)
C++
1
2
3
4
5
6
struct tnode {
    char * word;
    int count;
    struct tnode *left;
    struct tnode *right;
};
в 1 случаи
а count = 4
b count = 1
во 2
а count = 1
b count = 4
lemegeton
2923 / 1352 / 135
Регистрация: 29.11.2010
Сообщений: 2,725
23.02.2013, 09:13 #8
Хм. Неплохая идея. Тогда можно упростить и не городить дерево, воспользоваться массивом и посчитать количество символов в строках.

Добавлено через 20 часов 7 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cstring>
 
bool isAnagram(const char *a, const char *b) {
  const int numberOfCharacters = 256;
  if (strlen(a) != strlen(b)) {
    return false;
  }
 
  int count[numberOfCharacters];
  for (int i = 0; i < numberOfCharacters; ++i) {
    count[i] = 0;
  }
 
  while (*a != '\0' || *b != '\0') {
    ++count[*a++];
    --count[*b++];
  }
 
  for (int i = 0; i < numberOfCharacters; ++i) {
    if (count[i] != 0) {
      return false;
    }
  }
 
  return true;
}
 
int main(int argc, char **argv) {
  std::cout << ((isAnagram("aabbb", "bcabb")) ? "yes" : "no") << std::endl;
  std::cout << ((isAnagram("acbbb", "bcabb")) ? "yes" : "no") << std::endl;
 
  std::cin.get();
  return 0;
}
Nick Alte
Эксперт С++
1636 / 1008 / 119
Регистрация: 27.09.2009
Сообщений: 1,945
Завершенные тесты: 1
23.02.2013, 10:25 #9
C++
1
2
3
4
5
6
7
8
9
 using std::string;
bool isAnagram(const string& word1, const string& word2)
{
    string w1(word1);
    std::sort(w1.begin(), w1.end());
    string w2(word2);
    std::sort(w2.begin(), w2.end());
    return w1 == w2;
}
DiffEreD
1430 / 767 / 95
Регистрация: 21.06.2011
Сообщений: 1,740
Записей в блоге: 2
23.02.2013, 12:23 #10
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <iostream>
#include <string>
#include <algorithm>
 
bool compare(const std::string& s1, const std::string& s2)
{
    if (s1.size() != s2.size()) return false;
    std::string comp(s1);
    std::sort(comp.begin(), comp.end());
    do
    {
        if (comp == s2)
            return true;
    }while (std::next_permutation(comp.begin(), comp.end()));
    return false;
}
 
int main() 
{
    std::string first = "discovery";
    std::string second = "diveryocs";
    std::string third = "discovero";
    
    std::cout << std::boolalpha;
    std::cout<<first<<" and "<<second<<" : "<<compare(first, second)<<"\n";
    std::cout<<first<<" and "<<third<<" : "<<compare(first, third)<<"\n";
    return 0;
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.02.2013, 12:23
Привет! Вот еще темы с ответами:

Переставить строки матрицы так, чтобы наименьший элемент находился на главной диагонали - C++
задать двумерный массив размером 4 на 4. массив заполняется целыми числами случайным образом. в массиве переставить строки так, чтобы...

В матрице переставить строки так, чтобы наименьший элемент находился на главной диагонали - C++
задать двумерный массив размером 4 на 4. массив заполняется целыми числами случайным образом. в массиве переставить строки так, чтобы...

Переставить строки матрицы так, чтобы элементы последнего столбца были отсортированы по возрастанию - C++
Срочно понадобилась помощь! Дано такое условие: Переставить строки матрицы так, чтобы элементы последнего столбца были отсортированы...

вывести из строки те слова ,которые содержат две буквы z. - C++
вывести из строки те слова ,которые содержат две буквы z. ПОМОГИТЕ ПОЖАЛУСТА


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
23.02.2013, 12:23
Ответ Создать тему
Опции темы

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