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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 30, средняя оценка - 4.87
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
#1

Анаграмма - C++

18.03.2009, 19:59. Просмотров 3950. Ответов 7
Метки нет (Все метки)

ПОМОГИТЕ РЕШИТЬ ПЛИИИЗ!!!!!

Пусть задано некоторое слово, состоящее из букв английского алфавита длинной не более 80 символов (например, “WORD”). Рассмотрим набор возможных перестановок, состоящих из букв данного слова (например, “RDOW”, “WODR” и т.д.). Требуется выбрать из этого множества слово, следующее по алфавиту за исходным.
Входные данные

В единственной строке входного файла INPUT.TXT записано слово, не последнее по алфавиту среди возможных его перестановок.
Выходные данные

В единственную строку выходного файла OUTPUT.TXT нужно вывести следующее слово по алфавиту.
Примеры№ INPUT.TXT OUTPUT.TXT
1 abdc acbd
2 word wrdo

Добавлено через 1 час 19 минут 23 секунды
Ну неужели никто не может помочь???
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.03.2009, 19:59     Анаграмма
Посмотрите здесь:

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

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

анаграмма - Pascal
1)как написать программу для шифрования обратной кодировкой(анаграммой) Весь текст кодируется, начиная с последнего символа до первого, в...

Анаграмма - Pascal ABC
Являются ли два данных трех значных числа анаграммами?( то есть состоят из одинаковых цифр, записанных,возможно,в другом порядке)

анаграмма панаграмма [Си] - C (СИ)
Помогите пожалуйста с двумя задачками. Собственно первая должна проверять являются ли пара слов/предложений анаграммой и вторая...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Devin
0 / 0 / 0
Регистрация: 19.03.2009
Сообщений: 6
19.03.2009, 17:58     Анаграмма #2
Не столь тупая программа как мне казалось. Вот решение. Как считать и записать в файл думаю разберешься.

За "рек" буду благодарен.
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
36
37
38
39
40
41
42
43
#include <iostream>
 
using namespace std;
 
int main()
{
    string input_str = "word";
    string output_str = input_str;
    bool solution_exists = false;
 
    int j = input_str.length()-1;
    while( (j>0) && (!solution_exists) )
    {
        int i = j;
        output_str = input_str;
        solution_exists = true;
        while(output_str<=input_str)
        {
            char ch = output_str[i];
            output_str[i] = output_str[i-1];
            output_str[i-1] = ch;
 
            i--;
            if(i<=0)
            {
                solution_exists = false;
                break;
            }
        }
        j--;
    }
 
    if(!solution_exists)
    {
        cout << "no solution\n";
    }
    else
    {
        cout << output_str.c_str() << "\n";
    }
 
    return 0;
}
Humanitis
172 / 164 / 6
Регистрация: 12.01.2009
Сообщений: 430
19.03.2009, 20:04     Анаграмма #3
с этой строкой протесть "DABCB"
Devin
0 / 0 / 0
Регистрация: 19.03.2009
Сообщений: 6
20.03.2009, 17:50     Анаграмма #4
согласен.. тогда думаю перебором влоб, напишу как виберу время.
Новенький
44 / 9 / 2
Регистрация: 03.03.2009
Сообщений: 254
21.03.2009, 18:27  [ТС]     Анаграмма #5
Ну кто нибудь может мне помочь, этот алгоритм даже примеры с условия не проходит...
Agent007
2 / 2 / 0
Регистрация: 23.03.2009
Сообщений: 7
23.03.2009, 14:37     Анаграмма #6
Алгоритм решения твоей задачи такой:
1) в слове к которому ищем анаграмму сортируем по возрастанию буквы т.е. слово преобразовываем в ключ (Пример: toxication -> aciinoottx);
2) берём словарь с нужными словами, в нём в каждом слове таким образом сортируем буквы (т.е. каждое слово преобразуем в ключ) и делаем новый словарь в котором данные будут храниться ввиде <слово>:<ключ>
3) смотрим позицию нашего слова от начала нового словаря
4) теперь берём <ключ> от нашего <слова> и банально ищем дальше <слово>, которое имеет такой же <ключ> как и наше <слово> - это и будет анаграмма.
P.S: я только начал изучать программирование, так что просьба если что не верно - ткнуть носом.
Devin
0 / 0 / 0
Регистрация: 19.03.2009
Сообщений: 6
23.03.2009, 17:40     Анаграмма #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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
 
using namespace std;
 
string sort_s(string in_str, bool asc)
{
    string ret = "";
 
    for(int i=0; i<in_str.length(); i++)
        for(int j=i+1;j<in_str.length(); j++)
            if(asc?in_str[i]<in_str[j]:in_str[in_str.length()-1-i]<in_str[in_str.length()-1-j])
            {
                string s = in_str;
                char c = s[i];
                s[i] = s[j];
                s[j] = c;
 
                if(ret=="")
                {
                    ret=s;
                }
                if( (asc?(ret>s):(ret<s)) && (in_str!=s) )
                {
                    ret = s;
                }
            }
    return ret;
}
 
int main()
{
    //string input_str = "41232"; // --> 41322
    string input_str = "abdc"; // --> acbd
    //string input_str = "1243"; // -->1324
    //string input_str = "word"; // --> wrdo
 
    string output_str = "";
 
    string ms;
 
    for(int i=1; i<input_str.length(); i++)
    {
        ms = input_str.substr(input_str.length()-i-1,i+1);
        ms = sort_s(ms,1);
 
        if(ms!="")
        {
            output_str = input_str.substr(0, input_str.length()-i-1);
 
            string pms = ms;
            while(ms!="")
            {
                output_str +=  ms.substr(0,1);
                ms = ms.substr(1);
                pms = ms;
                ms = sort_s(ms,0);
            }
            output_str += pms;
            break;
        }
    }
 
    cout << input_str.c_str() << "-->" << output_str.c_str() << "\n";
 
    return 0;
}
Somebody
2786 / 1600 / 145
Регистрация: 03.12.2007
Сообщений: 4,189
Завершенные тесты: 1
24.03.2009, 23:08     Анаграмма #8
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool next(string& s)
{
  int n = s.length() - 1;
  int i = n;
  do
  {
    i--;
  } while (i >= 0 && s[i] >= s[i + 1]);
  if (i < 0)
    return false;
  int j = n;
  while (s[j] <= s[i])
    j--;
  swap<char>(s[i], s[j]);
  i++;
  for (int j = 0; j <= (n - i + 1) / 2 - 1; j++)
    swap<char>(s[i + j], s[n - j]);
  return true;
}
[code]

Код
bool next(string& s)
{
  int n = s.length() - 1;
  int i = n;
  do
  {
    i--;
  } while (i >= 0 && s[i] >= s[i + 1]);
  if (i < 0)
    return false;
  int j = n;
  while (s[j] <= s[i])
    j--;
  swap<char>(s[i], s[j]);
  i++;
  for (int j = 0; j <= (n - i + 1) / 2 - 1; j++)
    swap<char>(s[i + j], s[n - j]);
  return true;
}
Yandex
Объявления
24.03.2009, 23:08     Анаграмма
Ответ Создать тему
Опции темы

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