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

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

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

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

18.03.2009, 19:59. Просмотров 4091. Ответов 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++ . Задана некоторая фраза. Определить, является ли она анаграммой палиндрома.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Анаграмма палиндрома - 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
2788 / 1602 / 145
Регистрация: 03.12.2007
Сообщений: 4,193
Завершенные тесты: 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